These results will vary per machine, and they may vary per Python release. But at least
for this specific test case, the dictionary-based set implementation (fastest) is roughly
three times faster than the simple list-based set (set). In fact, this threefold speedup is
probably sufficient. Python dictionaries are already optimized hashtables that you
might be hard-pressed to improve on. Unless there is evidence that dictionary-based
sets are still too slow, our work here is probably done.
By comparison, results for Python 2.4 in the prior edition of this book showed
fastest to be six times faster than set in all cases. Either iteration operations sped up,
or dictionary operations slowed down in 3.X. In the even older Python 1.5.2 and second
edition, the relative results were the same as they are today in Python 3.1. In any event,
this well underscores the fact that you must test performance on your machine and
your Python—today’s Python performance observation may easily be tomorrow’s his-
toric anecdote.
Adding Relational Algebra to Sets (External)
If you are interested in studying additional set-like operations coded in Python, see the
following files in this book’s examples distribution:
PP4E\Dstruct\Basic\rset.py
RSet implementation
PP4E\Dstruct\Basic\reltest.py
Test script for RSet; its expected output is in reltest.results.txt
The RSet subclass defined in rset.py adds basic relational algebra operations for sets of
dictionaries. It assumes the items in sets are mappings (rows), with one entry per col-
umn (field). RSet inherits all the original Set operations (iteration, intersection, union,
& and | operators, uniqueness filtering, and so on), and adds new operations as
methods:
Select
Return a set of nodes that have a field equal to a given value.
Bagof
Collect set nodes that satisfy an expression string.
Find
Select tuples according to a comparison, field, and value.
Match
Find nodes in two sets with the same values for common fields.
Product
Compute a Cartesian product: concatenate tuples from two sets.
Join
Combine tuples from two sets that have the same value for a field.
1382 | Chapter 18: Data Structures