6

In the following trivial examples there are two functions that sort a list of random numbers. The first method passes sorted a generator expression, the second method creates a list first:

import random
l = [int(1000*random.random()) for i in xrange(10*6)]

def sort_with_generator():
    return sorted(a for a in l)

def sort_with_list():
    return sorted([a for a in l])

Benchmarking with line profiler indicates that the second option (sort_with_list) is about twice as fast as the generator expression.

Can anyone explain what's happening, and why the first method is so much slower than the second?

Hamish
  • 22,860
  • 8
  • 53
  • 67
  • 3
    are you adding 1 to each element in the list example? – elyase Sep 06 '13 at 02:03
  • I'm at a loss. Can you isolate the two and benchmark them separately? Maybe the interpreter is doing some intelligent caching of the list or something weird like that. – Brian Sep 06 '13 at 02:10
  • List comprehension creates the ENTIRE list in memory at once whereas generator expressions feed each element of the resulting sequence through the tuple that gets passed to your sorted function. Thus, list comprehension is faster but it consumes more memory. The generator expression is slower, but memory is only conserved for one element of the list at any given time. For more information, check out this question: http://stackoverflow.com/questions/47789/generator-expressions-vs-list-comprehension – Shashank Sep 06 '13 at 02:12
  • @elyase apologies, that snuck in during paste - no, they should be the same aside from the expression. – Hamish Sep 06 '13 at 02:12
  • I assume there's a mistake. Both are adding 1. http://codepad.org/Hek5SPZm I think @Brian might be right about caching. If you flip arond the latter is faster. When a list if involve, it does an append so in general it shouldn't be faster. – CppLearner Sep 06 '13 at 02:12
  • "Early timings showed that generators had a significant performance advantage over list comprehensions. However, the latter were highly optimized for Py2.4 and now the performance is roughly comparable for small to mid-sized data sets. As the data volumes grow larger, generator expressions tend to perform better because they do not exhaust cache memory and they allow Python to re-use objects between iterations." http://www.python.org/dev/peps/pep-0289/ – iMom0 Sep 06 '13 at 02:12
  • @ShashankGupta thanks - I understand what is happening, but I don't understand why the list comprehension is quicker, nor does that question have an answer to my question. – Hamish Sep 06 '13 at 02:15
  • @iMom0 thanks - although even with 10^5 items the comprehension seems to be quicker :/ – Hamish Sep 06 '13 at 02:18
  • 2
    The question can be reduced to `list(a for a in l)` vs. `[a for a in l]`. This is where the difference comes from. The latter is faster by the same difference as it is when you use sorted. – flornquake Sep 06 '13 at 03:04
  • Related: [List comprehension vs generator expression's weird timeit results?](http://stackoverflow.com/questions/11964130/list-comprehension-vs-generator-expressions-weird-timeit-results) – Ashwini Chaudhary Sep 06 '13 at 21:36

3 Answers3

6

Your first example is a generator expression that iterates over a list. Your second example is a list expression that iterates over a list. Indeed, the second example is slightly faster.

>>> import timeit
>>> timeit("sorted(a for a in l)", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.963912010192871
>>> timeit("sorted([a for a in l])", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.021576881408691

The reason for this is undoubtedly that making a list is done in one go, while iterating over a generator requires function calls.

Generators are not to speed up small lists like this (you have 60 elements in the list, that's very small). It's to save memory when creating long lists, primarily.

Lennart Regebro
  • 167,292
  • 41
  • 224
  • 251
  • Flip the two around and tell me if you see generator is faster. I also assumed it does a ``a+1`` – CppLearner Sep 06 '13 at 02:17
  • In the case the two are isolated because each has separate initialization of `l`. I doubt we'll observe the same phenomenon. – Brian Sep 06 '13 at 02:19
  • Actually, my code should have initialized `10**6` items =D. It seems that they become break-even somewhere between `10**5` and `10**5`. I'm still not sure I understand why. – Hamish Sep 06 '13 at 02:21
  • @Brian: Huh? If you two are trying to say that if I move the generation of random numbers directly into the `sorted()` call it would change the outcome: I tried, just to make sure, before I posted the answer. As I suspected, it didn't. – Lennart Regebro Sep 06 '13 at 02:21
  • No not that. We were suggesting that two successive iterations over a single list might introduce a performance difference due to some sort of caching or the like. The more I think about it the less likely I find it – Brian Sep 06 '13 at 02:25
  • @Brian: Right, there are no such effects. – Lennart Regebro Sep 06 '13 at 02:26
  • @Hamish: I'm, not sure, but I'm guessing the memory allocation of the list starts eating up more time when it get's larger. – Lennart Regebro Sep 06 '13 at 02:32
  • Upvoted, although it would be great if someone could say definitively. – Hamish Sep 06 '13 at 02:41
3

If you look at the source for sorted, any sequence you pass in gets copied into a new list first.

newlist = PySequence_List(seq);

generator --> list appears to be slower than list --> list.

>>> timeit.timeit('x = list(l)', setup = 'l = xrange(1000)')
16.656711101531982
>>> timeit.timeit('x = list(l)', setup = 'l = range(1000)')
4.525658845901489

As to why a copy must be made, think about how sorting works. Sorts aren't linear algorithms. We move through the data multiple times, sometimes traversing data in both directions. A generator is intended for producing a sequence through which we iterate once and only once, from start to somewhere after it. A list allows for random access.

On the other hand, creating a list from a generator will mean only one list in memory, while making a copy of a list will mean two lists in memory. Good 'ol fashioned space-time tradeoff.

Python uses Timsort, a hybrid of merge sort and insertion sort.

Brian
  • 3,091
  • 16
  • 29
  • No, generator --> list is not slower than list --> list. However, it's possibly slower than first generating the list and then copying it into a list. So +1 anyway. – Lennart Regebro Sep 06 '13 at 03:08
0

List expressions, firstly, loads data into a memory. Then doing any operations with resulting list. Let the allocation time is T2 (for second case). Generator expressions not allocating time at once, but it change iterator value for time t1[i]. Sum of all t1[i] will be T1. T1 ≈ T2.

But when you call sorted(), in the first case time T1 added with time of allocation memory of every pairs compared to sort (tx1[i]). In result, T1 added with sum of all tx1[i].

Therefore, T2 < T1 + sum(tx1[i])

Vladimir Chub
  • 461
  • 6
  • 19
  • `sorted` does not allocate "memory of every pairs compared", so this makes little sense. For huge lists that would require an enormous amount of memory. It is possible that the sorting is less efficient with generators, but this reason is not it. – Lennart Regebro Sep 06 '13 at 02:38
  • So, and how do you then explain that the generator expressions are not stored in the memory of all previous values ​​when iterating? HOW do they sort it then? – Vladimir Chub Sep 06 '13 at 03:10
  • It obviously stores the values it sorts, yes. pairs, no. Since there is no key or cmp function in this case, what it stores is the list that it sorts. – Lennart Regebro Sep 06 '13 at 06:08