python at rcn.com
Mon Jun 15 09:45:13 CEST 2009
> 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.
FWIW, this is equivalent to the Welfare Crook problem in David Gries
book, The Science of Programming, http://tinyurl.com/mzoqk4 .
> I thought it could be accomplished through recursively embedded
> generators, but that approach failed in the end.
Translated into Python, David Gries' solution looks like this:
def intersect(f, g, h):
i = j = k = 0
if f[i] < g[j]:
i += 1
elif g[j] < h[k]:
j += 1
elif h[k] < f[i]:
k += 1
i += 1
streams = [sorted(sample(range(50), 30)) for i in range(3)]
for s in streams:
More information about the Python-list