The in-place change stacks (stack4) are almost always fastest, unless no indexing is
done at all—tuples (stack3) win by a hair in the last test case. When there is no indexing,
as in the last test, the tuple and in-place change stacks are roughly six and five times
quicker than the simple list-based stack, respectively. Since pushes and pops are most
of what clients would normally do to a stack, tuples are a contender here, despite their
poor indexing performance.
Of course, we’re talking about fractions of a second after many tens of thousands of
operations; in many applications, your users probably won’t care either way. If you
access a stack millions of times in your program, though, this difference may accumu-
late to a significant amount of time.
More on performance analysis
Two last notes on performance here. Although absolute times have changed over the
years with new Pythons and test machines, these results have remained relatively the
same. That is, tuple-based stacks win when no indexing is performed. All performance
measurements in a dynamic language like Python are prone to change over time,
though, so run such tests on your own for more accurate results.
Second, there’s often more to performance measurement than timing alternatives this
way. For a more complete picture, read about Python’s standard library profile module
(and its optimized workalike, cProfile). The profilers run Python code, collect per-
formance data along the way, and provide it in a report on code exit. It’s the most
complete way to isolate your code’s bottleneck, before you start working on optimizing
with better coding, algorithms, and data structures or moving portions to the
C language.
For simple performance analysis, though, our timing module provides the data we need.
In fact, we’ll reuse it to measure a more dramatic improvement in relative speed for set
implementation alternatives—the topic of the next section.
Implementing Sets
Another commonly used data structure is the set, a collection of objects that support
operations such as:
Intersection
Make a new set with all items in common.
Union
Make a new set with all items in either operand.
Membership
Test whether an item exists in a set.
Other operations, such as difference and subset tests, can be useful as well, depending
on the intended use. Sets come in handy for dealing with abstract group combinations.
Implementing Sets | 1373