efficient idiomatic queue?
James_Althoff at i2.com
James_Althoff at i2.com
Thu Jan 17 15:28:40 EST 2002
<Tim Peters>
Following is the spelling of mergesort I've had in mind ("a temp array and
a
handful of index variables"). It's eminently practical.
</Tim Peters>
Thanks for sharing this. I tried it on a list of 100,000 ints in reverse
order. It ran about 4.5x faster than the generator version (the
generator-with-list.append version was a little faster than the
all-generator version).
<Tim Peters>
I wrote Python's current list.sort(), and it
runs faster than the quickest mergesort I was able to code in C at the time
<snip>
I expect it remains very hard to beat (for Python's
specific ratio of slow comparison to cheap object movement (just pointer
copies)).
</Tim Peters>
On the list of 100,000 the builtin tim.list.sort was a mere 800x or so
faster than the generator version.
The bad news -- for us Jython users -- is that on the list of 100,000
Jython.list.sort was about 45x slower than cpython.list.sort. :-(
Jim
<Tim Peters>
def mergesort(A):
"Sort list, via stable mergesort."
n = len(A)
B = [None] * n
swapped = 0
s = 1
while s < n:
s2 = s+s
# Invariant: viewing A as a sequence of slices of length s (plus
# perhaps an oddball at the end), each slice is sorted. (This is
# trivially so when s=1; proceed by induction.) Now merge adjacent
# pairs of slices into sorted slices twice as large.
for i in range(0, n, s2):
ihi = j = i+s # start of adjacent slice
jhi = min(j+s, n) # final slice may have an oddball size
k = i # start of output slice
while i < ihi and j < jhi:
if A[i] <= A[j]:
B[k] = A[i]
i += 1
else:
B[k] = A[j]
j += 1
k += 1
# Copy tail. At most one of these isn't vaccuous.
B[k : k+ihi-i] = A[i : ihi]
B[k : k+jhi-j] = A[j : jhi]
# Swap input and output lists.
A, B = B, A
swapped = not swapped
s = s2
if swapped: # copy back into original input list
B[:] = A
</Tim Peters>
More information about the Python-list
mailing list