Aaron Watters wrote:
> ...is to forget they are sorted???
code snipped
Aaron I just flung your python merge code into pyrex and the results show that
the iteration overhead can be brought down without much effort. The real deal
would presumably be to start using pointers into the result list rather than
the
generic python type code which I have used. I haven't done much of that with
pyrex yet, but I believe others do that all the time with these predetermined
list lengths. The pyrex code doesn't look too different from python that it
puts
them off (I guess). I'm guessing a lot of the pyrex time is spent incrementing
and decrementing refcounts etc etc and that can clearly be made more efficient.
Also since None is being used as a place holder we could eliminate that by
using
null or undefined initial contents for the result lists thus saving time
decrementing None's refcount since each result list element is only accessed
once.
####start obvmerge.pyx
def PyxObviousMerge(L1, L2):
"obvious way"
cdef int len1, len2, resultlen, index1, index2
len1 = len(L1)
len2 = len(L2)
resultlen = len1+len2
result = [None] * resultlen
count = 0
index1 = 0
index2 = 0
while count<resultlen:
if index1<len1:
elt1 = L1[index1]
if index2<len2:
elt2 = L2[index2]
if elt1<elt2:
result[count] = elt1
index1 = index1+1
else:
result[count] = elt2
index2 = index2 + 1
else:
result[count] = elt1
index1 = index1+1
else:
result[count] = L2[index2]
index2=index2+1
count = count + 1
return result
def PyxAggregateTailMerge(L1, L2):
"obvious way, aggregating the tail"
cdef int len1, len2, resultlen, index1, index2
len1 = len(L1)
len2 = len(L2)
resultlen = len1+len2
result = [None] * resultlen
count = 0
index1 = 0
index2 = 0
while index1<len1 and index2<len2:
elt1 = L1[index1]
elt2 = L2[index2]
if elt1<elt2:
result[count] = elt1
index1= index1+1
else:
result[count] = elt2
index2 = index2+1
count=count+1
if index1<len1:
result[count:] = L1[index1:]
if index2<len2:
result[count:] = L2[index2:]
return result
####end obvmerge.pyx
==========test results
C:\code\users\robin>tmerge.py
constructing global test data
done with making global test data
running timings
now timing <function ResortEverythingMerge at 0x00C150F0>
for 10 elapsed 0.00000 for ResortEverythingMerge
for 100 elapsed 0.00000 for ResortEverythingMerge
for 1000 elapsed 0.00000 for ResortEverythingMerge
for 10000 elapsed 0.00000 for ResortEverythingMerge
for 100000 elapsed 0.06200 for ResortEverythingMerge
for 1000000 elapsed 0.78100 for ResortEverythingMerge
now timing <function ObviousMerge at 0x00C15070>
for 10 elapsed 0.00000 for ObviousMerge
for 100 elapsed 0.00000 for ObviousMerge
for 1000 elapsed 0.00000 for ObviousMerge
for 10000 elapsed 0.00000 for ObviousMerge
for 100000 elapsed 0.12500 for ObviousMerge
for 1000000 elapsed 1.32800 for ObviousMerge
now timing <built-in function PyxObviousMerge>
for 10 elapsed 0.00000 for PyxObviousMerge
for 100 elapsed 0.00000 for PyxObviousMerge
for 1000 elapsed 0.00000 for PyxObviousMerge
for 10000 elapsed 0.01600 for PyxObviousMerge
for 100000 elapsed 0.09300 for PyxObviousMerge
for 1000000 elapsed 1.09400 for PyxObviousMerge
now timing <function AggregateTailMerge at 0x00C150B0>
for 10 elapsed 0.00000 for AggregateTailMerge
for 100 elapsed 0.00000 for AggregateTailMerge
for 1000 elapsed 0.00000 for AggregateTailMerge
for 10000 elapsed 0.00000 for AggregateTailMerge
for 100000 elapsed 0.12500 for AggregateTailMerge
for 1000000 elapsed 1.20300 for AggregateTailMerge
now timing <built-in function PyxAggregateTailMerge>
for 10 elapsed 0.00000 for PyxAggregateTailMerge
for 100 elapsed 0.00000 for PyxAggregateTailMerge
for 1000 elapsed 0.00000 for PyxAggregateTailMerge
for 10000 elapsed 0.00000 for PyxAggregateTailMerge
for 100000 elapsed 0.09400 for PyxAggregateTailMerge
for 1000000 elapsed 1.03100 for PyxAggregateTailMerge
C:\code\users\robin>
--
Robin Becker
--
http://mail.python.org/mailman/listinfo/python-list
