On Oct 28, 10:50 pm, Paul Rubin <no.em...@nospam.invalid> wrote:
> John Nagle <na...@animats.com> writes:
> > d1 = set('monday','tuesday')
> > days_off = set('saturday','sunday')
> > if not d1.isdisjoint(days_off) :...
> > This is cheaper than intersection, since it doesn't have to
> > allocate and construct a set. It just tests whether any element in the
> > smaller of the two sets is in the larger one.
>
> I wonder what the complexity is, since the simplest implementation using
> the dict-like features of sets is quadratic.
I don't how isdisjoint is implemented, nor exactly what you mean by
dict-like features, but this implementation is linear on length of
smaller_set in the typical case:
def disjoint(smaller_set,larger_set):
for item in smaller_set:
if item in larger_set:
return False
return True
(Unless you meant worst case, which I don't consider important for
dictionary lookups.)
Carl Banks
--
http://mail.python.org/mailman/listinfo/python-list
