Welcome, guest | Sign In | My Account | Store | Cart

Implements a data structure for sets of natural numbers, represented by a single integer. The interface is similar to the built-in structure 'set'.

Python, 116 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class CompactSet:

    def __init__(self, numbers = None, bits = None):
        self.bits = bits or 0       
        if numbers:
            for n in numbers:
                self.add(n)

    def add(self, n):
        self.bits |= 1 << n

    def remove(self, n):
        self.bits &= ~(1 << n)

    def clear(self):
        self.bits = 0

    def union(self, other):
        return CompactSet(bits = self.bits | other.bits)

    __or__ = union

    def intersection(self, other):
        return CompactSet(bits = self.bits & other.bits)

    __and__ = intersection

    def difference(self, other):
        return CompactSet(bits = self.bits & ~other.bits)

    __sub__ = difference
    
    def union_update(self, other):
        self.bits |= other.bits

    def intersection_update(self, other):
        self.bits &= other.bits

    def difference_update(self, other):
        self.bits &= ~other.bits

    def numbers(self):
        return list(self)

    def isdisjoint(self, other):
        return not (self.bits & other.bits)
    
    def __eq__(self, other):
        return (self.bits == other.bits)

    def __ne__(self, other):
        return not (self == other)

    def issubset(self, other):
        return (self.bits | other.bits == other.bits)

    __le__ = issubset

    def issuperset(self, other):
        return (other <= self)

    __ge__ = issuperset
    
    def __lt__(self, other):
        return (self <= other and self != other)

    def __gt__(self, other):
        return (other < self)

    def __len__(self):
        bits = self.bits
        count = 0
        while bits:
            bits &= bits - 1
            count += 1
        return count
        
    def __contains__(self, n):
        return self.bits & (1 << n)

    def __iter__(self):
        if self.bits == 0:
            raise StopIteration
        mask = 1
        for n in range(self.bits.bit_length()):
            if self.bits & mask:
                yield n
            mask <<= 1
        
    def __repr__(self):
        return ''.join(["CompactSet(", str(self.numbers()), ")"])


if __name__ == '__main__':

    s = CompactSet([3, 7, 10])
    t = CompactSet([5, 2, 3])

    assert 7 in s
    assert s & t
    assert s | t == CompactSet([2, 3, 5, 7, 10])

    s.remove(3)
    assert not s & t

    assert CompactSet([2, 3]) < t

    print 'OK'
    

    import sys
    
    s = set(xrange(10000))
    cs = CompactSet(xrange(10000))
    print 'Size of set(xrange(10000)) is ', sys.getsizeof(s) # this is actually underestimated
    print 'Size of CompactSet(xrange(10000)) is ', sys.getsizeof(cs.bits)

This is just an example showing off some basics of bitwise operators and Python's data model. Efficient in terms of space and set operations, quite inefficient when it comes to converting to and from uncompressed, human-readable containers. Insertion, removal and the usual set operations are implemented via bitwise operations (I'm quite sure that some of them can be made a lot faster).

Created by jimmy2times on Sun, 17 Apr 2011 (MIT)
Python recipes (4591)
jimmy2times's recipes (4)

Required Modules

Other Information and Tasks