Pythonic way of saying 'at least one of a, b, or c is in some_list'

Carl Banks pavlovevidence at gmail.com
Fri Oct 29 09:40:50 CEST 2010


On Oct 28, 10:50 pm, Paul Rubin <no.em... at nospam.invalid> wrote:
> John Nagle <na... at 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



More information about the Python-list mailing list