Python Patterns: An Optimization Anecdote

http://www.python.org/doc/essays/list2str.html

by llambda • 15 years ago

80 11 15 years ago

python.org

casenelson• 15 years ago

Just a note that there was good discussion about this before [1].

Remember that this essay is quite old (2002) and Python has changed significantly. [2]

[1] http://news.ycombinator.com/item?id=1859417

[2] http://keithdevens.com/weblog/archive/2002/Apr/10/AnOptimiza...

machrider• 15 years ago

Thanks for the links. The most interesting thing in the previous HN thread was learning that this article is a) really old (probably outdated), and b) written by Guido!

njharman• 15 years ago

It's troubling to read something about Python optimization/performance without mention that this is atrocious in a loop

string = string + s

That is such a code smell I cringed every time I saw it.

Should append to list and join at the end (once). Which, I bet (I, or you, don't know anything until we actually profile), dumping the += is significant reason why last two examples where much faster.

chubot• 15 years ago

I still follow that rule, perhaps somewhat anachronistically. This has been long optimized in CPython so it's not quadratic:

$ python -V

Python 2.5.2

$ python -m timeit -s 'v=["a"]' 'v.append("a")'

1000000 loops, best of 3: 0.199 usec per loop

$ python -m timeit -s 's="a"' 's+="a"'

10000000 loops, best of 3: 0.127 usec per loop

The string append is actually FASTER now. Tried with strings of length 5 and it is still faster.

beaumartinez• 15 years ago

This[1] was my bible when I first wondered how best to build strings in Python.

[1] http://www.skymind.com/~ocrow/python_string/

epidemian• 15 years ago

I'm a total newbie at Python, but wouldn't

  ''.join(map(chr, list))

avoid the quadratic time of doing "string += something" (and also be a prettier solution IMO)?

(In Python 2.x doing ''.join(chr(n) for n in list) might be a better solution to avoid the intermediate list created by map)

sgk284• 15 years ago

The article is from 2002, so it's entire line of reasoning is quite outdated.

Xion• 15 years ago

Bear in mind this is extremely outdated article and some of the advice should be taken with very big grain of salt, as things have changed since 2002. The most significant improvement of Python (in this context) is the introduction of generators, which seem like an almost obvious choice for a problem such as this. The solutions that immediately came to my mind, for example, were this:

    import itertools
    def f2_1(list):
        return str(itertools.imap(chr, list))

and this:

    def f2_2(list):
        return str(chr(c) for c in list)

They are both about twice as fast (in 2.7.2 CPython) as the suggested array solution (f2_1 performs slightly better for smaller lists), and their readability is rather significantly better.

todddeluca2• 15 years ago

To avoid confusing newbies, str() does not concatenate a list (or generator, etc.) of strings into a single string. You probably meant to call ''.join() instead.

  >>> import itertools
  >>> def f2_1(list):
  ...         return str(itertools.imap(chr, list))
  ... 
  >>> f2_1(range(10))
  '<itertools.imap object at 0x10048e850>'
  >>> def f2_2(list):
  ...         return str(chr(c) for c in list)
  ... 
  >>> f2_2(range(10))
  '<generator object <genexpr> at 0x10046b780>'

kitanata• 15 years ago

", ".join([0,1,2,3,4,5,6,7,8,9]) works well. Why not that?

todddeluca2• 15 years ago

Here are performance numbers for a variety of approaches using a list of length 256. You can see that having a local reference to the global chr function (as discussed in the article) can give a slight speed boost. Using join() in conjunction with map() performs fairly well.

  python -m timeit -s 'l = range(256);' '"".join([chr(i) for i in l])'
  # 10000 loops, best of 3: 80.5 usec per loop
  python -m timeit -s 'l = range(256); lchr = chr' '"".join([lchr(i) for i in l])'
  # 10000 loops, best of 3: 75 usec per loop
  python -m timeit -s 'import itertools; l = range(256); lchr = chr' '"".join(itertools.imap(chr, l))'
  # 10000 loops, best of 3: 52.8 usec per loop
  python -m timeit -s 'l = range(256); lchr = chr' '"".join(map(chr, l))'
  # 10000 loops, best of 3: 48.9 usec per loop
  python -m timeit -s 'l = range(256); lchr = chr' '"".join(lchr(i) for i in l)'
  # 10000 loops, best of 3: 87.2 usec per loop
  python -m timeit -s 'l = range(256); lchr = chr' '
  s = ""
  for i in l:
    s += lchr(i)
  '
  # 10000 loops, best of 3: 64.2 usec per loop

Python Patterns: An Optimization Anecdote

Related Stories