LISTS: Extract every other element

[Christian Tismer]

Randall Hopper wrote:
> 
>    eric jones:
>    Mike Fletcher:
>       |>>> from Numeric import *
>       |>>> a = array(range(10))
>       |>>> a[::2]
> 
> Pretty fast.
> 
>    Christian Tismer:
>       |def slice100(d):
> 
> Most impressive.  Not as readable, but amazing performance without having
> to resort to a C extension.

Your results are most interesting. Mike did the Numeric tests
without re-converting to a true list. You do it, and then
I beat Numeric. This was what I expected, btw.

I also assume that you do one test after the other, many times?
If not, I loose! :-))
This is since I use an unusual stack size which causes
reallocs of stack frames, which in turn causes reallocs
of result variables which no longer fit the hole.

I'm working on a malloc scheme for Python which does not
suffer from this. Mallocs will be cahced with the code
location.

> APPROACH #8  |   33.29%  (0.696691 sec)    |      34.40%  (0.686397 sec) *
> APPROACH #9  |   31.34%  (0.656048 sec)    |      34.14%  (0.681241 sec)

> APPROACH #8  - Christian's 100 element walker
> APPROACH #9  - lst2 = mxTools.extract( lst, mxTools.trange( 0, len(lst), 2 ) )

This is unbelievable. Marc has the extra overhead of creating the
trange object, I have the overhead of the three interpreted
machine instructions.
But we are both stopped by the C API, which always goes through
the general object protocol. Let's see how fast we can get:

try:
	from slice2 import everyother
except:
	everyother = None

if everyother:
	data = range(1000000)
	print timing(chrisInline, data, 10)[0]
	print timing(everyother, data, 10)[0]

25.54
3.02	

This tells us that we can be 8 times faster. :-)

Here your module:


-------- slice2.c --------
/* very quick hack for randall Hopper
	to show how fast slicing can be,
	and to give him a fast module
	with thanks for the nice race

  Chris Tismer, 991220
*/

/* start: 6:40 pm */

#include "python.h"

PyObject *
everyother(self, args)
	PyObject *self, *args;
{
	PyObject *inlist, *outlist, *thing;
	int p, p2;
	int insize, outsize;
	if (PyTuple_GET_SIZE(args) != 1
		|| !(PyList_Check(PyTuple_GET_ITEM(args, 0))) ) {
		PyErr_SetString(PyExc_TypeError, 
			"everyother needs exactly one list argument");
		return NULL;
	}
	inlist = PyTuple_GET_ITEM(args, 0);
	insize = PyList_GET_SIZE(inlist);
	outsize = insize / 2;
	outlist = PyList_New(outsize);
	if (!outlist)
		/* must be mem error */
		return NULL;
	for ( p=1, p2=0 ; p2 < outsize ; p+=2, p2++) {
		thing = PyList_GET_ITEM(inlist, p);
		Py_INCREF(thing);
		PyList_SET_ITEM(outlist, p2, thing);
	}
	return outlist;
}

static PyMethodDef slice2_methods[] = {
  {"everyother",	(PyCFunction)everyother, 1},
  {NULL,		NULL}		/* sentinel */
};

#ifdef _MSC_VER
_declspec(dllexport)
#endif
void
initslice2()
{
	PyObject *m;

	m = Py_InitModule("slice2", slice2_methods);
}

/* finished 7:00 pm */

/* finished testing & debugging: 7:20 pm */

------ end of slice2.c -------

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101   :    *Starship* http://starship.python.net
10553 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home