[Baypiggies] a python puzzle

Damon McCormick damonmc at gmail.com
Wed Apr 14 18:32:18 CEST 2010


Sorry about the cut-and-paste error.  Corrected below.  Also, I believe my
code is equivalent to Thomas'.

-Damon


On Wed, Apr 14, 2010 at 9:29 AM, Damon McCormick <damonmc at gmail.com> wrote:

> Keeping your original approach, you could define a function like this:
>
> def next_or_none_pair (itr):
>     def result_func ():
>         try:
>             return itr.next()
>         except StopIteration:
>             return (None, None)
>     return result_func
>
> and then replace your current definitions of xnext and ynext by the
> following:
>
>     xnext = next_or_none_pair(itertools.groupby(xs, grouper))
>     ynext = next_or_none_pair(itertools.groupby(ys, grouper))
>
> The condition of your while loop is already set up to exit when either x or
> y is None (a condition which, I believe, is currently never True, since the
> loop ends when StopIteration is thrown).
>
> So the only other modification you'd need is that your comparisions between
> x and y need to handle None:
>
>         elif y is None or x < y:
>             yield list(xgroup), None
>             x, xgroup = xnext()
>         elif x is None or x > y:
>             yield (None, list(ygroup))
>             y, ygroup = ynext()
>
> So the entire thing would look like this:
>
>

> import itertools
>
>
> def next_or_none_pair (itr):
>     def result_func ():
>     try:
>             return itr.next()
>     except StopIteration:
>             return (None, None)
>     return result_func
>
>
> def as_pairs (xs, ys, grouper=lambda _: _):
>
> """
>     >>> aordered = [1, 1, 2, 4, 6, 8,
> 9]
>     >>> bordered = [1, 3, 4, 5, 6, 7,
> 8]
>     >>> for a, b in as_pairs(aordered,
> bordered):
>     ... a,
> b
>     ([1, 1],
> [1])
>     ([2],
> None)
>     (None,
> [3])
>     ([4],
> [4])
>     (None,
> [5])
>     ([6],
> [6])
>     (None,
> [7])
>     ([8],
> [8])
>     ([9],
> None)
>     """
>     # assume xs and ys are
> sorted.
>     xnext = next_or_none_pair(itertools.groupby(xs, grouper))
>     ynext = next_or_none_pair(itertools.groupby(ys, grouper))
>     x, xgroup = xnext()
>     y, ygroup = ynext()
>
>     while x or y:
>         if x == y:
>             yield list(xgroup), list(ygroup)
>             x, xgroup = xnext()
>             y, ygroup = ynext()
>         elif y is None or x < y:
>             yield list(xgroup), None
>             x, xgroup = xnext()
>         elif x is None or x > y:
>             yield (None, list(ygroup))
>             y, ygroup = ynext()
>         else:
>             assert False
>
> if __name__ == "__main__":
>     import doctest
>     doctest.testmod()
>
>
>
>
>
> On Wed, Apr 14, 2010 at 9:04 AM, Brent Pedersen <bpederse at gmail.com>wrote:
>
>> On Wed, Apr 14, 2010 at 8:20 AM, Brent Pedersen <bpederse at gmail.com>
>> wrote:
>> > hi, in trying to write a func that does a kind of merging of 2 sorted
>> lists,
>> > i've come up with a fairly simple implementation that "almost works":
>> > http://gist.github.com/365485
>> >
>> > but it hits StopIteration before returning the last value ([9], None)
>> > i can wrap the whole thing in a bunch more if statements, i've tried
>> > heapq.merge, but cant find a nice solution.
>> >
>> > any ideas? i think it's an interesting problem.
>> > -brent
>> >
>>
>> i should add the for my real use-case, the iterables going in will not
>> be lists, they'll be lazily generated, and very large, so
>> i dont want to read them into memory to get the last element or slice
>> them.
>> ______________________________
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/baypiggies/attachments/20100414/bf0e94f1/attachment-0001.html>


More information about the Baypiggies mailing list