Ok, that one looks more sleak than what I came up with.
Couple of things I learn from your solution, please correct me if I
misunderstood something:
1. list containing other lists will sort itself based on first element
on lists inside ?
2. sort(), pop() is not costly operations
Other than that you seem to not use the cmp operator but that's easily
fixed.
This one looks much better than mine, here's what I came up with:
def merge_sorted(iterables, comparer=None):
"""
Generator that will take a list of iterables/generators that is
individually sorted, and then produce
values in a sorted order by taking the lowest value from each
source each call.
@param iterables: List of iterables/generators to retrieve values
from
@type iterables: List of iterables/generators
@param comparer: Optional fn(v1, v2) function that can compare two
values, should return <0 if v1<v2,
>0 if v1>v2 and ==0 if v1==v2.
@type comparer: function-object, example: lambda x, y: x-y
@note: The "list of iterables" can actually be anything that
produces a list of iterables, so you can
use a function that yields lists for instance.
"""
# First convert whatever we're given into a list of sources
iterables = [iterable for iterable in iterables]
# This series of if-statements will determine how many sources we
have and work out sub-problems
# that are manageable.
if len(iterables) != 2:
if len(iterables) == 0:
# List, but no sources
pass
elif len(iterables) == 1:
# Only 1 source, just return its contents
for value in iterables[0]:
yield value
elif len(iterables) == 3:
# 3 sources, sub-divide into 0 <--> (1, 2)
left_iterable = iterables[0]
right_iterable = merge_sorted([iterables[1], iterables[2]],
comparer)
for value in merge_sorted([left_iterable, right_iterable],
comparer):
yield value
elif len(iterables) == 4:
# 4 sources, sub-divide into (0, 1) <--> (2, 3)
left_iterable = merge_sorted([iterables[0], iterables[1]],
comparer)
right_iterable = merge_sorted([iterables[2], iterables[3]],
comparer)
for value in merge_sorted((left_iterable, right_iterable),
comparer):
yield value
elif len(iterables) > 4:
# >4 sources, sub-divide into (0, 1) <--> (2, ...)
left_iterable = merge_sorted([iterables[0], iterables[1]],
comparer)
right_iterable = merge_sorted(iterables[2:], comparer)
for value in merge_sorted((left_iterable, right_iterable),
comparer):
yield value
raise StopIteration
# The method will only get here if there is only two sources, which
is an easy case to handle
i1 = iter(iterables[0])
i2 = iter(iterables[1])
# Grab the first two values from the two sources, if possible
try:
v1 = i1.next()
has_v1 = True
except StopIteration:
has_v1 = False
try:
v2 = i2.next()
has_v2 = True
except StopIteration:
has_v2 = False
# As long as we got values from both generates/iterators/whatever,
compare and yield the lowest of the
# two, and then get the next value from the corresponding source
while has_v1 and has_v2:
# Work out which of v1 and v2 comes first
if comparer is not None:
comp = comparer(v1, v2)
if comp <= 0:
yield_v1 = True
else:
yield_v1 = False
else:
if v1 <= v2:
yield_v1 = True
else:
yield_v1 = False
# Yield the next value, then grab a new value from the
corresponding source
if yield_v1:
yield v1
try:
v1 = i1.next()
except StopIteration:
has_v1 = False
else:
yield v2
try:
v2 = i2.next()
except StopIteration:
has_v2 = False
# When we get here, we got 3 possibilities:
# 1. has_v1 == True, has_v2 == False --> yield rest of v1/i1 and
just exit on StopIteration exception
# 2. has_v1 == False, has_v1 == True --> yield rest of v2/i2 and
just exit on StopIteration exception
# 3. has_v1 == has_v2 == False --> while-loops will skip, function
falls off the end
while has_v1:
yield v1
v1 = i1.next()
while has_v2:
yield v2
v2 = i2.next()
--
http://mail.python.org/mailman/listinfo/python-list
