of a dictionary whose values are all None. Because lookup time is constant and short for
dictionaries, the in list scans of the original set can be replaced with direct dictionary
fetches in this scheme. In traditional terms, moving sets to dictionaries replaces slow
linear searches with fast hashtable fetches. A computer scientist would explain this by
saying that the repeated nested scanning of the list-based intersection is an exponen-
tial algorithm in terms of its complexity, but dictionaries can be linear.

The module in Example 18-11 implements this idea. Its class is a subclass of the original
set, and it redefines the methods that deal with the internal representation but inherits
others. The inherited & and | methods trigger the new intersect and union methods
here, and the inherited len method works on dictionaries as is. As long as Set clients
are not dependent on the order of items in a set, most can switch to this version directly
by just changing the name of the module from which Set is imported; the class name
is the same.

Example 18-11. PP4E\Dstruct\Basic\fastset.py

"optimize with linear-time scans using dictionaries"

import set

fastset.Set extends set.Set

class Set(set.Set):
def init(self, value = []):
self.data = {} # manages a local dictionary
self.concat(value) # hashing: linear search times

def intersect(self, other):
res = {}
for x in other: # other: a sequence or Set
if x in self.data: # use hash-table lookup; 3.X
res[x] = None
return Set(res.keys()) # a new dictionary-based Set

def union(self, other):
res = {} # other: a sequence or Set
for x in other: # scan each set just once
res[x] = None
for x in self.data.keys(): # '&' and '|' come back here
res[x] = None # so they make new fastset's
return Set(res.keys())

def concat(self, value):
for x in value: self.data[x] = None

inherit and, or, len

def getitem(self, ix):
return list(self.data.keys())[ix] # 3.X: list()

def repr(self):
return '<Set:%r>' % list(self.data.keys()) # ditto

Implementing Sets | 1379