exercise: partition a list by equivalence

[John Machin]

Reinhold Birkenfeld wrote:
> Reinhold Birkenfeld wrote:
>
> > My solution (which may not be the fastest or most effective, but
till
> > now is the shortest <wink> and it works):

[snip RB]
>
> A recursive solution (around twice as fast as the above, though very
> slow still...)
>
[snip RB2]
>
> Another one:
>

[snip RB3]

Dunno what data you are using for timing, but my tests suggest that RB
is fast enough, RB3 is slightly faster, but RB2 is a real dog and
appears to be quadratic [hint: it has that same for-for-for-update
signature found in phase 2 of Xah's effort]. Not only that, but it
seems to be somewhat irregular. Below are some results on trivial test
data:

prototype input: python -m timeit -s "import
merge;n=3000;inp=((x,x+1)for x in xrange(0,n,2))"
"merge.merge_RB3(inp)"
100000 loops, best of 3: 3.98 usec per loop

n=3000;RB2  64.9 msec per loop
n=3000;RB3  3.98 usec per loop
n=3000;RB  3.06 usec per loop
n=3000;JM3  2.73 usec per loop

n=1000;RB2  4.92 usec per loop
n=1250;RB2  5.34 usec per loop
n=1500;RB2  20.4 usec per loop
n=1750;RB2  22.1 msec per loop
n=2000;RB2  28.8 msec per loop
n=2500;RB2  44.9 msec per loop
n=3000;RB2  64.9 msec per loop

[background: Python 2.4, Win2000, 1.4GHz Athlon chip, 768Mb memory]

Here's a function to generate some serious timing data:
!def mktimedata(n,lev):
!    res = []
!    d = 1
!    for k in range(lev):
!        res.extend(zip(xrange(0, n, 2*d), xrange(d, n, 2*d)))
!        d *= 2
!    return res

Try that with n=3000 and lev=5 ...

Cheers,
John