Re: Fast union/intersection of two sequences?

Aaron Watters (aaron@funcity.njit.edu)
Wed, 25 Jan 1995 12:29:59 GMT

In article <199501240837.AAA06111@infoseek.com> Jim Roskind <jar@infoseek.com> writes:
>> Date: Tue, 24 Jan 1995 02:47:38 -0500
>> From: Skip Montanaro <skip@automatrix.com>
>> Is there any faster way to compute the union/intersection of two sequences
>Yup, there is an easy and efficient way in python :-)
>...The cool trick in python is to use a dictionary, which employs what is
>called hashing....

... and it's even faster if the ops are implemented in C, for instance
using the kjSet datatype from my kjbuckets C extension module, EG:

>>> from kjbuckets import *
>>> x = kjSet([1,2,4,8,16])
>>> y = kjSet([0,2,4,6,8,10])
>>> x + y
kjSet([1, 4, 16, 0, 10, 6, 2, 8])
>>> x & y
kjSet([4, 2, 8])
>>> x - y
kjSet([1, 16])
The implementation uses hashing too. It's available at the
python ftp site and the mirrors, if you're interested.

Unfortunately, neither of these will work for collections
containing "unhashable types" (eg, containing lists).
a.
==
-You seem unusually intelligent, for an American.
-Actually, I'm not. - from the movie _Barcelona_