Best way to merge/sort two sorted lists?...

[Robin Becker]

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