[Python-Dev] Efficient set complement and operation on large/infinite sets.

[Guido van Rossum]

Hm...  Without reading though all this, I expect that you'd be better
off implementing this for yourself without attempting to pull the
standard library sets into the picture (especially since sets.py is
obsolete as of 2.4; set and frozenset are now built-in types).  You're
really after rather specialized set representations. I've done this
myself and as long as you stick to solving *just* the problem at hand,
it's easy. If you want a general solution, it's hard...

--Guido

On 5/11/06, Terry Jones <terry at jon.es> wrote:
> I'm about to write some code to manage sets, and wanted to float a few
> thoughts here because I have various ideas about how to implement what I
> want to do, and I think one of them could be done by changing Python's set
> type in useful and backward compatible way.
>
> Apologies if this is discussed in the archives. I didn't see it.
>
> My original motivation is a need to work efficiently with very large sets,
> let's say 10M elements. In some cases, you can operate on a set without
> needing to explicitly represent all its elements. For example, if my set is
> the Universal (U) set, then X in U, should return True. If my set is U and
> I union it with any other set, it is unchanged, etc. By also maintaining a
> finite set of things that are _not_ in my large set, I can do other
> operations efficiently. E.g., calling U.remove(X) would _add_ X to the set
> of elements that were known not to be in the big set that you were trying
> to represent efficiently. In most cases, such a set class would simply do
> the opposite/inverse operation on its finite exclusion set.
>
> While it's convenient to warm up by talk about the infinite Universal set,
> we could just as easily be talking about arbitrarily large finite sets.
> There are some examples below.
>
> Another way to discuss the same thing is to talk about set complements. It
> would be nice to be able to complement (or invert) a set. Once you did so,
> you might have an infinite set on your hands, but as the last paragraph
> argues, you can still operate on an infinite set efficiently. Naturally,
> you can't fully enumerate it, or take its size.
>
> I think that giving Python sets the ability to handle complementarity would
> have some nice uses - and that these go well beyond the particular thing
> that I need right now.
>
> For example, suppose you want to represent the set of all floating point
> numbers. You just create an empty set and complement it. Then you can test
> it as usual, and begin to exclude things from it. Or if you have a system
> with 10M objects and you need to support operations on these objects via a
> query language that lets the user type "not X" where X is a set of objects,
> there is a natural and efficient way (constant time) to execute the query -
> you just mark the set as being inverted (complemented).
>
> If I were going to implement the above by changing Python's built in set
> type, here's what I think I'd do:
>
> Add four optional keyword arguments to the set constructor:
>
>   - invert=False
>   - universalSet=None
>   - universalSetSize=None
>   - universeExclusionFunc=None
>
> invert is just a flag, indicating the sense of the set.
>
> If inverse is False:
>
>   the set behaves exactly as a normal Python set and the other three
>   new arguments are ignored.
>
> If inverse is True:
>
>   universalSet represents the universal set. If it is None, then the
>   universal set is infinite. Otherwise, universalSet is an iterable. The
>   implementation should not call this iterable unless it's unavoidable, on
>   the presumption that if the programmer wanted to operate directly on the
>   contents of this iterable, they'd be doing it in a conventional fashion
>   (e.g., with a normal set). The universalSetSize, used for len()
>   calculations, is the number of elements in universalSet, if known &
>   if finite.
>
>   The universeExclusionFunc can be called with a single element argument to
>   see if the element should be considered excluded from the universalSet.
>   This may seem like a weird idea, but it's the key to flexibility and
>   efficiency. In an invert=True set, the code would use the normal set
>   content as a mutable set of objects that are not in the universe, as
>   described above, but would, in addition, use the universeExclusionFunc
>   (if defined) to identify elements not in the set (because they are not in
>   the universe), and thus avoid the use of the expensive (or infinite)
>   universalSet.
>
> Note that an inverted (or normal) set can be inverted by simply setting
> invert=False, so this requires a new invert() method (which could be
> triggered by the use of something like 'not' or '!' or '~'). In this case,
> an inverted set becomes a normal Python set. The elements represented by
> universeExclusionFunc remain invalid - they are simply not in the universe
> (and, if deemed sensible, this could be sanity checked in add()).
>
> If it's not clear, when a set is inverted, any iterable given to __init__,
> (i.e., the iterable argument in the normal case of constructing a Python
> set), is just treated as usual (but in this case will be taken to
> represent things not in the set initially).
>
>
> Here are some examples of usage:
>
> 1. Suppose you want to work with the set of integers [0, 100000000) and
>    that initially your set is all such integers. You could create this set
>    via:
>
>        S = set(invert=True,
>                universalSet=xrange(100000000),
>                universalSetSize=100000000,
>                universeExclusionFunc=(lambda x: x >= 100000000)
>
>    This has the intended effect, is efficient, and no-one need call the
>    iterator. You can (I think) do everything you could do with a normal set
>    (including inverting it). If the user happens to want to list all the
>    elements in the set, that's their business and they can do it, except in
>    the case where universalSet=None, in which case I would raise an
>    exception.
>
> 2. Suppose you wanted to represent the set of all floating point numbers
>    > 0.0 that were not integers. You'd do this via:
>
>        def excludeFunc(f):
>            try:
>                f = float(f)
>            except ValueError:
>                return True
>            if f <= 0.0:
>                return True
>            if f - math.floor(f) == 0.0:
>                return True
>            return False
>
>        S = set(invert=True, universeExclusionFunc=excludeFunc)
>
> 3. Let's say you wanted to work with the set of all IP addresses, as
>    represented by lists of 4 integers, but that you want to exclude
>    127.0.0.1, and all the reserved RFC1918 address blocks
>
>        def excludeFunc(ip):
>            # Insert code to check type and length.
>            if (ip == [127, 0, 0, 1]):
>                return True
>            if (ip[0] == 10 or
>                (172, 16, 0, 0) <= ip <= (172, 31, 255, 255) or
>                (191, 168, 0, 0) <= ip <= (192, 168, 255, 255)):
>                return True
>            # Insert code to check all bytes in [0..255], return True if not.
>            return False
>
>        S = set(invert=True, universeExclusionFunc=excludeFunc)
>
> It's pretty easy to think of other examples of wanting to efficiently use
> big sets, or to use small sets and then needing to complement them and
> operate efficiently on their large complements.
>
> One reaction to these examples might be that it's no big deal to write your
> own code to, say, manage sets of IP addresses. I think that's not so easy
> to do efficiently if the set is massive (and you'd end up keeping track of
> the complement or using offline storage). Doing it as suggested above makes
> it simple, and once you call the constructor, you just do normal Python set
> operations.
>
> This suggestion goes a little way towards giving "continuous" sets. One way
> to categorize set support is:
>
>   A. Only support finite sets.
>
>   B. Provide category A but also support infinite sets where at least
>      one of the set and its complement is finite.
>
>   C. Provide category B but also allow for the case where a set and its
>      complement may both be infinite.
>
> Thus I am proposing something that would take set support in Python from
> category A to category B.  Implementing B efficiently is provably possible
> since all operations are done on either a set or its complement, whichever
> is known to be finite, and Python already handles those operations (via its
> category A support).
>
>
> The downsides that I see at the moment are:
>
> 1. Two new exceptions that can arise. These only happen on sets that are in
>    the inverted state, and only when the universal set is infinite:
>
>      - You try to enumerate an infinite set.
>      - You call len() on an infinite set.
>
> 2. Operations on regular sets get slightly slower because virtually all set
>    operations would need to test the invert flag. So that's an extra
>    Boolean test on every set operation.
>
> I don't think the implementation is too hard - the Python sets.py code is
> very clean - though there may be gotchas.
>
> Anyway, I wanted to see what people think of this before I go ahead and
> solve my actual problem. If the above is considered potentially worthwhile
> to Python, I can work on adapting sets.py. If not, I'll do the faster and
> simpler thing and write my own class.
>
> Regards,
> Terry
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/guido%40python.org
>


-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)