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 -- http://mail.python.org/mailman/listinfo/python-list
