David Wilson <d...@botanicus.net> writes:
> Hi,
>
> During a fun coding session yesterday, I came across a problem that I
> thought was already solved by itertools, but on investigation it seems
> it isn't.
>
> The problem is simple: given one or more ordered sequences, return
> only the objects that appear in each sequence, without reading the
> whole set into memory. This is basically an SQL many-many join.
As it is a nice little problem I tried to find a solution today. FWIW,
here it is (tested extensively only on the example below :):
def intersect(iterables):
nexts = [iter(iterable).next for iterable in iterables]
v = [next() for next in nexts]
while True:
for i in xrange(1, len(v)):
while v[0] > v[i]:
v[i] = nexts[i]()
if v[0] < v[i]: break
else:
yield v[0]
v[0] = nexts[0]()
>>> list(intersect([[1, 100, 142, 322, 12312],
... [2, 100, 101, 322, 1221],
... [100, 142, 322, 956, 1222]]))
[100, 322]
--
http://mail.python.org/mailman/listinfo/python-list
