4 ms·

when you know the number of elements you'll be putting in the list, you can save on resizing and copying. A comprehension doesn't always know how many elements

by chrsig 5y ago

when you know the number of elements you'll be putting in the list, you can save on resizing and copying. A comprehension doesn't always know how many elements it will require.

dec0dedab0de 5y ago
I think the article, and my test just showed that the comprehension is faster than preallocating. So if it's something that works well in a comprehension, you should do it that way. The preallocation is only an improvement when the code you're doing per loop is too complex to be done in a comprehension. My initial thought was that a function in a comprehension would be better than preallocation with code in the loop, but I was wrong. Unless you're suggesting that Python has a special optimization for the range generator in comprehensions, which is plausible, let me think of a way to test for that. EDIT: I changed it to iterate over the characters in my shadow file, and comprehensions were still faster. I'm not sure if that is enough to fake out possible optimizations, but it definitely rules out range. def pgen(): with open('/etc/passwd') as f: for char in f.read(): yield char def func(i): """simplest function""" return i length = len(list(pgen())) %%timeit #preallocating list without range pre = [None] * length for i, v in enumerate(pgen()): pre[i] = v 711 µs ± 14 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #preallocating list from custom generator, and zipping from range to avoid enumerate pre = [None] * length for i,v in zip(range(length), pgen()): pre[i] = v 687 µs ± 1.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #comprehension without range comp = [v for v in pgen()] 456 µs ± 6.48 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #comprehension without range, and using enumerate to judge the difference fairly comp = [v for i, v in enumerate(pgen())] 648 µs ± 14.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
- bobbylarrybobby 5y ago
  Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list. The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python.
  - dec0dedab0de 5y ago
    Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list. ok, that makes sense then. So when I made a generator it didn't get the preallocation advantage, but range did because the range object has len. The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python. I learned this a long time ago, and have tried to use comprehensions since, To the point where I had to draw a line for readability because it was annoying co-workers. Though I never really took the time to understand what "In C" actually meant beyond it being an optimization over using a for loop with append. Do you happen to know why list(map(func, iterable)) is faster than [func(_) for _ in iterable] ? I assume something about calling back to a python function from C, but my knowledge of the internals is obviously lacking at these levels.

by chrsig 5y ago

when you know the number of elements you'll be putting in the list, you can save on resizing and copying. A comprehension doesn't always know how many elements it will require.

dec0dedab0de 5y ago

I think the article, and my test just showed that the comprehension is faster than preallocating. So if it's something that works well in a comprehension, you should do it that way. The preallocation is only an improvement when the code you're doing per loop is too complex to be done in a comprehension. My initial thought was that a function in a comprehension would be better than preallocation with code in the loop, but I was wrong. Unless you're suggesting that Python has a special optimization for the range generator in comprehensions, which is plausible, let me think of a way to test for that. EDIT: I changed it to iterate over the characters in my shadow file, and comprehensions were still faster. I'm not sure if that is enough to fake out possible optimizations, but it definitely rules out range. def pgen(): with open('/etc/passwd') as f: for char in f.read(): yield char def func(i): """simplest function""" return i length = len(list(pgen())) %%timeit #preallocating list without range pre = [None] * length for i, v in enumerate(pgen()): pre[i] = v 711 µs ± 14 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #preallocating list from custom generator, and zipping from range to avoid enumerate pre = [None] * length for i,v in zip(range(length), pgen()): pre[i] = v 687 µs ± 1.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #comprehension without range comp = [v for v in pgen()] 456 µs ± 6.48 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) %%timeit #comprehension without range, and using enumerate to judge the difference fairly comp = [v for i, v in enumerate(pgen())] 648 µs ± 14.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

bobbylarrybobby 5y ago
Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list. The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python.
- dec0dedab0de 5y ago
  Python does have a special optimization: when the iterable in a comprehension has len() defined, then Python preallocates the list. ok, that makes sense then. So when I made a generator it didn't get the preallocation advantage, but range did because the range object has len. The comprehension is faster than manual preallocation+filling because the indexing happens in C instead of in Python. I learned this a long time ago, and have tried to use comprehensions since, To the point where I had to draw a line for readability because it was annoying co-workers. Though I never really took the time to understand what "In C" actually meant beyond it being an optimization over using a for loop with append. Do you happen to know why list(map(func, iterable)) is faster than [func(_) for _ in iterable] ? I assume something about calling back to a python function from C, but my knowledge of the internals is obviously lacking at these levels.