LISTS: Extract every other element - SUMMARY

[Christian Tismer]

Hi Kids,

the following will outperform everything by far,
also Numeric. hee hee.

Randall Hopper wrote:
> 
> Adrian Eyre:
>  |> I coded each of these up, working with the same list of 100,000
>  |> integers.  Here are the results.
>  |>
>  |> [snip]
>  |
>  |Did you try them all with the -O option?
> 
> No, these were without -O.  -O betters the times around 4-5%.  Relative
> performance rankings stay the same though.
> 
>     > python odd_elements.py
>     APPROACH #1 :   100.00%  (2.07391 sec)
>     APPROACH #1b:    96.95%  (2.01062 sec)
>     APPROACH #2 :   697.01%  (14.4554 sec)
>     APPROACH #3 :   122.20%  (2.53422 sec)
>     APPROACH #4 :   315.16%  (6.53619 sec)
>     APPROACH #4b:   719.41%  (14.92 sec)
>     APPROACH #5 :   109.06%  (2.26185 sec)
>     APPROACH #6 :    68.83%  (1.42751 sec)

Please test approach 7, it should range at 40% or so.

def slice100(d):
	return [
	d[ 1],d[ 3],d[ 5],d[ 7],d[ 9],d[11],d[13],d[15],d[17],d[19],
	d[21],d[23],d[25],d[27],d[29],d[31],d[33],d[35],d[37],d[39],
	d[41],d[43],d[45],d[47],d[49],d[51],d[53],d[55],d[57],d[59],
	d[61],d[63],d[65],d[67],d[69],d[71],d[73],d[75],d[77],d[79],
	d[81],d[83],d[85],d[87],d[89],d[91],d[93],d[95],d[97],d[99],
	]

def algo7(data):
	l = len(data)
	res = (l+1)/2 * [None]
	for p in xrange(0, l-99, 100):
		q = p/2
		res[q:q+50] = slice100(data[p:p+100])
	for i in range(p+1, l, 2): res[i/2] = data[i]
	return res

The key observation is this:
Access to the indexed elements costs three fast opcodes
each: Here the end of its code.

        342 LOAD_FAST           0 (d)
        345 LOAD_CONST         49 (97)
        348 BINARY_SUBSCR  
        349 LOAD_FAST           0 (d)
        352 LOAD_CONST         50 (99)
        355 BINARY_SUBSCR  
        356 BUILD_LIST         50
        359 RETURN_VALUE   

I used this trick long before when I needed fast access to many
database columns in arbitrary order. My approach was to create
a function on the fly with explicit indexing. 
Hard to beat.

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