Home Original page

fastest way to find the intersection of n lists of sets

Prateek surekap at gmail.com
Sun Apr 29 19:41:42 EDT 2007 
On Apr 30, 3:48 am, James Stroud <jstr... at mbi.ucla.edu> wrote:
> Prateek wrote:
> > I have 3 variable length lists of sets. I need to find the common
> > elements in each list (across sets) really really quickly.
>
> > Here is some sample code:
>
> > # Doesn't make sense to union the sets - we're going to do
> > intersections later anyway
> > l1 = reduce(operator.add, list(x) for x in l1)
> > l2 = reduce(operator.add, list(x) for x in l2)
> > l3 = reduce(operator.add, list(x) for x in l3)
>
> > # Should I do this in two steps? Maybe by intersecting the two
> > shortest lists first?
> > s = frozenset(l1) & frozenset(l2) & frozenset(l3)
>
> > I'm assuming frozensets are (somehow) quicker than sets because
> > they're immutable.
>
> > Any code suggestions? Maybe using something in the new fancy-schmancy
> > itertools module?
>
> > Thanks,
> > Prateek
>
> I don't understand why you cast to list. I would propose:
>

The reason why I'm casting to a list first is because I found that
creating a long list which I convert to a set in a single operation is
faster (although probably less memory efficient - which I can deal
with) than doing all the unions.

Prateek
More information about the Python-list mailing list