In which we defend the honor of enumerate()
Although I learned from and appreciated the write-up by Peilonrayz, I was not
convinced by all of the characterizations. Also, I had some specific questions
not covered in those benchmarks, so I explored on my own using the script
below. These notes cover a few things I learned and reframe the discussion
a bit.
enumerate() itself is not slow. Merely invoking the enumerate() callable
is an O(1) operation, because it does nothing with the underlying iterable of
values other than store an iterator created from the original iterable.
Is consuming an iterable via enumerate() slow? That depends on what the
alternative is. Compared to direct iteration (for x in xs), yes it's slower
and the magnitude of the slowdown is not trivial. But we use enumerate() for
a reason: we need the indexes too. In that context, there are three obvious
alternatives: manage the index yourself (i += 1), use range() for iteration
and then obtain the value by via get-item (x = xs[i]), or ask Python to
compute the index (i = xs.index(x)). Compared to those alternatives,
enumerate() is quite good: it's a little faster than managing the index
yourself or using range(), and it is substantially faster than using
list.index() every time. In that light, saying that "index() is just faster
than enumerate()" seems not quite right -- but perhaps I misunderstood or
there are errors in my findings.
Should you worry about tuple unpacking when using enumerate(). No, it adds
almost nothing. And especially don't avoid enumerate() on performance grounds
if it forces you to use get-item on the tuple (i = x[0]), because that is
slower than direct unpacking.
Some evidence. The numbers below are for a run of the script with
--count=1000 (how many numbers to be sorted) and --trials=100 (how many times
did we measure to get the statistics). The output here just adds up the total
of the times for all trials (--stat=total), but you can also run the code to
see mean, min, and max as well (those results tell similar stories). For each
function, the table shows both a scaled value (2nd column) and the raw value
(3rd column). The scaled values are easier to compare because they are
expressed as a ratio relative to the minimum value in that column. The comment
column has a schematic summary of function's behavior.
# Just calling enumerate().
# Nothing slow here: O(1).
enumerate_call_baseline : 1.0 : 0.000018 # it = None
enumerate_call : 2.0 : 0.000035 # it = enumerate()
# Direct Python iteration.
# If you need an index, don't use xs.index(x) as a general approach.
iterate_baseline : 38.4 : 0.000678 # for x in xs: pass
iterate_with_index : 190.0 : 0.003351 # for x in xs: i += 1
iterate_range_getitem : 198.6 : 0.458601 # for i in range(len(xs)): x = xs[i]
iterate_get_index : 24850.3 : 0.438433 # for x in xs: i = xs.index(x)
# Iteration with enumerate().
# Slow only when compared to a no-op for loop.
# If you need the indexes, use enumerate().
enumerate_consume : 155.6 : 0.002746 # for x in it: pass
enumerate_consume_unpack : 157.4 : 0.002778 # for i, x in it: pass
enumerate_consume_getitem : 263.8 : 0.005475 # for x in it: x[0]
Sometimes index() is faster. Here are the benchmarks for the sorting
functions we have discussed. As others have reported, the classic compare-swap
stategy is worse than those relying on the insert-index-pop family of methods.
sort_baseline : 1.0 : 0.007389 # xs.sort()
sort_classic_swap : 618.4 : 4.569107 # classic compare-swap
sort_insert_index_pop : 122.5 : 0.905445 # xs.insert(xs.index(x2), xs.pop(i))
sort_insert_pop : 150.7 : 1.113629 # xs.insert(j, xs.pop(i))
I find that counterintuitive at first glance. When reading through the code
of sort_insert_index_pop(), my first impression was puzzlement. In
particular, don't insert(), index(), and pop() each imply linear
scans/shifts of the data? That seems bad, right? Moreover, having done the
enumerate benchmarks, I am not entirely convinced by an explanation based
solely on the general point that language operations implemented in C (such as
list.index()) have a big speed advantage over the language operations
implemented directly in Python. Although that point is both true and important,
the enumerate benchmarks prove that in the general case, retrieving indexes via
xs.index(x) is very slow. Out of the two forces -- the speed of the C-based
list methods vs the inefficiency of those costly scans/shifts -- which one
has a larger magnitude within the context of the short-circuiting behavior of
insertion sort?
Summary of the tradeoffs. The table below tries to summarize the advantages
and disadvantages of the two approaches. The insert-index-pop approach uses the
fastest looping style in its inner loop, makes many fewer swaps, in a faster
language -- but the swap itself is algorithmically inefficient. We know from
the benchmarks how those tradeoffs weigh out in the end, but I cannot say with
confidence that a survey of experienced Python engineers would have necessarily
predicted this empirical outcome in advance -- and that is what we mean when we
describe something as counterintuitive.
| classic-swap | insert-index-pop
-------------------------------------------------------
| |
Looping machinery | |
| |
- for x in xs | . | inner
- enumerate()/range() | outer | outer
- while COND | inner | .
| |
Swaps | |
| |
- Number | N * N / 2 | N
- Cost per swap | 1 | N * 1.5
- Language | Python | C
The code:
import argparse
import sys
from collections import namedtuple
from random import randint, shuffle
from time import time
####
# Benchmarking machinery.
####
# Groups of functions that we will benchmark.
FUNC_NAMES = {
'enumerate': [
# Just calling enumerate().
'enumerate_call_baseline', # it = None
'enumerate_call', # it = enumerate()
# Direct Python iteration.
'iterate_baseline', # for x in xs: pass
'iterate_with_index', # for x in xs: i += 1
'iterate_range_getitem', # for i in range(len(xs)): x = xs[i]
'iterate_get_index', # for x in xs: i = xs.index(x)
# Iteration with enumerate().
'enumerate_consume', # for x in it: pass
'enumerate_consume_unpack', # for i, x in it: pass
'enumerate_consume_getitem', # for x in it: x[0]
],
'sort': [
'sort_baseline', # xs.sort()
'sort_classic_swap', # classic index-based compare-swap
'sort_insert_index_pop', # xs.insert(xs.index(x2), xs.pop(i))
'sort_insert_pop', # xs.insert(j, xs.pop(i))
],
'check_sorts': [],
}
# Constants and simple data types.
STAT_NAMES = ('count', 'total', 'mean', 'min', 'max')
VALUE_NAMES = ('randint', 'random', 'shuffle', 'direct')
Stats = namedtuple('Stats', STAT_NAMES)
Result = namedtuple('Result', 'func stats')
def main(args):
# Parse command-line arguments.
ap = argparse.ArgumentParser()
ap.add_argument('scenario', choices = list(FUNC_NAMES))
ap.add_argument('--stat', default = 'total', choices = STAT_NAMES)
ap.add_argument('--count', type = int, default = 1000)
ap.add_argument('--trials', type = int, default = 100)
ap.add_argument('--values', default = 'randint', choices = VALUE_NAMES)
ap.add_argument('--presort', action = 'store_true')
opts = ap.parse_args(args)
# Generate some values.
xs = generate_values(opts.count, opts.values, opts.presort)
# Either sanity check to ensure than our sorts actually sort.
if opts.scenario == 'check_sorts':
exp = sorted(xs)
for fname in FUNC_NAMES['sort']:
ys = xs.copy()
f = globals()[fname]
f(ys)
print(ys == exp, fname)
# Or benchmark some functions.
else:
funcs = [globals()[fname] for fname in FUNC_NAMES[opts.scenario]]
results = measure_funcs(funcs, xs, opts.trials)
report = list(summarize(opts, results))
print('\n'.join(report))
def generate_values(count, mode, presort = False):
# Various ways of generating numbers to be sorted or enumerated.
if mode == 'randint':
xs = [randint(1, 1000) for _ in range(count)]
elif mode == 'random':
xs = [random() for _ in range(count)]
elif mode == 'shuffle':
xs = list(range(count))
shuffle(xs)
elif mode == 'direct':
xs = [int(x) for x in mode.split(',')]
return sorted(xs) if presort else xs
def measure_funcs(funcs, xs, trials):
# Benchmark several functions.
results = []
for f in funcs:
stats = measure(trials, f, xs)
r = Result(f, stats)
results.append(r)
return results
def measure(trials, func, xs):
# Benchmark one function.
times = []
for t in range(trials):
ys = xs.copy()
t0 = time()
func(ys)
t1 = time()
times.append(t1 - t0)
count = len(xs)
total = sum(times)
mean = total / len(times)
return Stats(count, total, mean, min(times), max(times))
def summarize(opts, results):
# Generate tabular output.
# Scenario header.
fmt = '\n# {} : stat={}, count={}, trials={}'
header = fmt.format(opts.scenario, opts.stat, opts.count, opts.trials)
yield header
# For the statistic we are analyzing, get its minimum value.
min_tup = min(results, key = lambda tup: tup[1])
min_val = getattr(min_tup[1], opts.stat)
# Print table for that statistic.
fmt = '{:<30} : {:8.1f} : {:.6f}'
for f, stats in results:
val = getattr(stats, opts.stat)
scaled_val = val / min_val
row = fmt.format(f.__name__, scaled_val, val)
yield row
####
# Benchmarking targets: enumerate() vs alternatives.
####
def enumerate_call_baseline(xs):
it = None
def enumerate_call(xs):
it = enumerate(xs)
def iterate_baseline(xs):
for x in xs:
pass
def iterate_with_index(xs):
i = 0
for x in xs:
i += 1
def iterate_range_getitem(xs):
for i in range(len(xs)):
x = xs[i]
def enumerate_consume(xs):
it = enumerate(xs)
for x in it:
pass
def enumerate_consume_getitem(xs):
it = enumerate(xs)
for x in it:
x[1]
def enumerate_consume_unpack(xs):
it = enumerate(xs)
for i, x in it:
pass
def iterate_get_index(xs):
for x in xs:
i = xs.index(x)
####
# Benchmarking targets: in-place insertion sorts.
####
def sort_baseline(xs):
xs.sort()
def sort_classic_swap(xs):
for i in range(1, len(xs)):
x = xs[i]
while i > 0 and xs[i - 1] > x:
xs[i] = xs[i - 1]
i -= 1
xs[i] = x
def sort_insert_pop(xs):
for i, x1 in enumerate(xs):
for j, x2 in enumerate(xs):
if x2 >= x1:
xs.insert(j, xs.pop(i))
break
def sort_insert_index_pop(xs):
for i, x1 in enumerate(xs):
for x2 in xs:
if x2 >= x1:
xs.insert(xs.index(x2), xs.pop(i))
break
if __name__ == '__main__':
main(sys.argv[1:])
a.insert(a.index(y), a.pop(i))to be very slow indeed. \$\endgroup\$