[Python-Dev] A "new" kind of leak

[James Althoff]

Hey Tim,

Remember the exchange below from a while back on python-list (you submitted
a nice sorting algorithm in response)?

Isn't this the kind of thing that could create lots of generators?  I'm not
saying one should write this kind of code -- mine was just a "for fun"
rewrite of David's original example (he seemed to want to be able to use
generators for quicksort) -- and it was relatively slow, in any case.  And
of course there are lots of other, better ways to get the end result.

Just curious.

Jim

====================

David Eppstein wrote:
>Ok, but your merge routine gets rid of a key advantage of using generators:
>it returns a list, rather than yielding the items one at a time, so the
>total time is always Theta(n log n), while for the version I posted (and
>the cleaner ADT-ized version someone else posted later) the merges all
>happen in parallel as items are requested, and the time to pull off the
>first k items from a sorted list of n items is O(n + k log n).

Ok. Here is essentially the same thing but we return an interator instead
of a list (same idea as your version).

BTW, I also like Alex's ADT approach.  Mine was just a suggestion if class
defs were to be avoided.

Jim

==========================

from __future__ import generators

def gen(alist):
    result = {'isempty':1,'value':None}
    for value in alist:
        result['isempty'] = 0
        result['value'] = value
        yield result
    result['isempty'] = 1
    while 1:
        yield result

def merge(list1,list2):
    gen1, gen2 = gen(list1), gen(list2)
    next1, next2 = gen1.next(), gen2.next()
    while 1:
        if next1['isempty'] and next2['isempty']:
            break
        if (next2['isempty'] or
            (not next1['isempty'] and next1['value'] <= next2['value'])):
            yield next1['value']
            next1 = gen1.next()
        else:
            yield next2['value']
            next2 = gen2.next()

def mergesort(alist):
    if len(alist) <= 1:
        return iter(alist)
    return merge(mergesort(alist[:len(alist)//2]),
        mergesort(alist[len(alist)//2:]))