On 2007-12-06, Aaron Watters <[EMAIL PROTECTED]> wrote: > ...is to forget they are sorted??? > > While trying to optimize some NUCULAR libraries I discovered > that the best way to merge 2 sorted lists together > into a new sorted list is to just append > them and re-sort. The following test case demonstrates this. > It can be criticized in many ways: it only tests lists of the same > size, > it only uses "hashed" data, etcetera... > Still, my testing shows "resort everything" is consistently > two times faster than an explicit python merge even for fairly large > data. > > I'm beginning to think > a "sorted list merger" might make a nice tiny extension module > (at least for my purposes). > > See timing demonstration code below. Let me know if there > is a better way or if the test is fatally flawed, please. > > --- Aaron Watters >==== > http://www.xfeedme.com/nucular/pydistro.py/go?FREETEXT=greedy+bastard > >==========snip: test code below > "test different ways to merge two sorted lists" > > def ObviousMerge(L1, L2): <SNIP> > def AggregateTailMerge(L1, L2): <SNIP>
Your merge functions are pretty complex; here's a simpler, obvious solution: def merge_sorted(a, b): """Merge two sorted lists into a new sorted list. >>> merge_sorted(range(10), range(5)) [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9] >>> merge_sorted(range(5), range(10)) [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9] >>> merge_sorted(range(3), []) [0, 1, 2] >>> merge_sorted([], range(3)) [0, 1, 2] >>> merge_sorted([], []) [] """ rval = [] aix, bix = 0, 0 astop, bstop = len(a), len(b) while aix < astop and bix < bstop: if a[aix] < b[bix]: rval.append(a[aix]) aix += 1 else: rval.append(b[bix]) bix += 1 while aix < astop: rval.append(a[aix]) aix += 1 while bix < bstop: rval.append(b[bix]) bix += 1 return rval It should beat ResortEverything consistently once the lists become larger than a certain size. Do you get better results at all with the above function? -- Neil Cerutti The audience is asked to remain seated until the end of the recession. --Church Bulletin Blooper -- http://mail.python.org/mailman/listinfo/python-list