import stack4 # in-place stacks: y.append(x)
import timer # general function timer utility

rept = 200
from sys import argv
pushes, pops, items = (int(arg) for arg in argv[1:])

def stackops(stackClass):
x = stackClass('spam') # make a stack object
for i in range(pushes): x.push(i) # exercise its methods
for i in range(items): t = x[i] # 3.X: range generator
for i in range(pops): x.pop()

or mod = import(n)

for mod in (stack2, stack3, stack4): # rept*(push+pop+ix)
print('%s:' % mod.name, end=' ')
print(timer.test(rept, stackops, getattr(mod, 'Stack')))

Results under Python 3.1

The following are some of the timings reported by the test driver script. The three
outputs represent the measured run times in seconds for the original, tuple, and in-
place stacks. For each stack type, the first test creates 200 stack objects and performs
roughly 120,000 stack operations (200 repetitions × (200 pushes + 200 indexes + 200
pops)) in the test duration times listed. These results were obtained on a fairly slow
Windows 7 netbook laptop under Python 3.1; as usual for benchmarks, your mileage
will probably vary.

C:\...\PP4E\Dstruct\Basic> python stacktime.py 200 200 200

stack2: 0.838853884098

stack3: 2.52424649244

stack4: 0.215801718938

C:\...\PP4E\Dstruct\Basic> python stacktime.py 200 50 200

stack2: 0.775219065818

stack3: 2.539294115

stack4: 0.156989574341

C:\...\PP4E\Dstruct\Basic> python stacktime.py 200 200 50

stack2: 0.743521212289

stack3: 0.286850521181

stack4: 0.156262000363

C:\...\PP4E\Dstruct\Basic> python stacktime.py 200 200 0

stack2: 0.721035029026

stack3: 0.116366779208

stack4: 0.141471921584

If you look closely enough, you’ll notice that the results show that the tuple-based stack
(stack3) performs better when we do more pushing and popping, but worse if we do
much indexing. Indexing lists is extremely fast for built-in lists (stack2 and stack4), but
very slow for tuple trees—the Python class must traverse the tree manually.

1372 | Chapter 18: Data Structures