Getting into Python loops

13 Jan 2006

Looping is such a commonly used construct that I thought I’d do an informal comparison of the flavors of loops provided. For comparison, I define a function for scaling a list using (1) list comprehension, (2) the map function, (3) the for loop, and finally, just for the fun of it, (4) a recursive function. Mathematically, scaling a lists involves multiplying each elements by a scale factor, e.g., applying a scale factor of 10 to [1, 2, 3] yields [10, 20, 30].

The following code benchmarks each method, running it 500 times in a row. Furthermore, to ensure that the results are independent of the length of the list, I test each function on lists of sizes 1000 to 30000, in 100 increments, looking for a clear growth patterns (but found none).

from time import time
def scale_using_recursion(s, l):
    if len(l) == 0:
        return []
    else:
        return [(l[0] * s)] + scale_using_recursion(s, l[1:])

def scale_using_loop(s, l):
    r = []
    for e in l:
        r.append(e * s)
    return r

def scale_using_map(s, l):
    return map(lambda e: e * s, l)

def scale_using_list_comprehension(s, l):
    return [e * s for e in l]

def run(func, iterations, list_size):
    l = [e for e in range(list_size)]
    t = time()
    [func(10, l) for i in range(iterations)]
    return (time() - t) / iterations

def time_stuff():
    iterations = 500

    for list_size in range(1000, 30000, 100):
        t1 = run(scale_using_list_comprehension, iterations, list_size)
        t2 = run(scale_using_map, iterations, list_size)
        t3 = run(scale_using_loop, iterations, list_size)
        print("%s %s %s %s") % (list_size, t1/t1, t2/t1, t3/t1)

if __name__ == "__main__":
    time_stuff()

The benchmark was performed under MS Windows, running Python 2.4.2. To make the results independent of the speed of the hardware, I compare each scaling method to the winner of the race, the list comprehension approach.

scale_using_list_comprehension:  1.0
scale_using_loop:                1.7
scale_using_map:                 2.1
(scale_using_recursion:         76.0)

Not surprisingly, the recursive approach is slow and infeasible for real use (and only tested on a list size of 500 to get an indication of relative performance). Generally, recursive functions are of limited use in Python because the interpreter doesn’t optimize for tail recursion; a technique commonly used in functional languages that causes a tail recursion to get transformed into an iteration, making a recursive and an interative approach equally fast.

Lacking this features, Python blows up with a “RuntimeError: maximum recursion depth exceeded”, when it reaches the default recursion depth of 500. We could increase the number for certain situations, of course, but we would never truly be in safe range of the RuntimeError, and performing the way it does, it doesn’t really matter.

I was surprised to learn that map and for loops are roughly 70% and 110% slower, respectively, than list comprehension. I can’t really put my finger on what makes them so slow.

Although this isn’t the most scientific of studies, it does indicate that list comprehension is the way to go, if possible. Luckily, in most cases, list comprehension is also the shortest, the most elegant, and the most readable of the approaches.