bisect intersection

[Gabriel Genellina]

En Mon, 28 Apr 2008 13:50:13 -0300, Robert Bossy <Robert.Bossy at jouy.inra.fr> escribió:

> I stumbled into a sorted list intersection algorithm by Baeza-Yates
> which I found quite elegant. For the lucky enough to have a springerlink
> access, here's the citation:
> http://dblp.uni-trier.de/rec/bibtex/conf/cpm/Baeza-Yates04
>
> I implemented this algorithm in python and I thought I could share it.
> I've done some tests and, of course, it can't compete against dict/set
> intersection, but it will perform pretty well. Computing union and
> differences are left as an exercise...

Nice. As it only uses comparisons, it can be used even if the elements aren't hashable, that's good.
But if they are hashable, using a set and sorting again at the end is much faster, as you discovered.

-- 
Gabriel Genellina