Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Do list comprehensions in Python reduce in a memory efficient manner?

I am a beginner at Python, and this is my first post, so don't be too harsh :). I've been playing around with Python lately and was wondering if something like

max([x for x in range(25)]) 

would result in Python first creating a list of all the elements and then finding the max, resulting in O(2n) time, or it would keep track of the max as it was iterating for Θ(n). Also, since range differs in Python3 (being a iterable), would that make it different than in Python2?

like image 802
daveeloo Avatar asked Mar 18 '11 08:03

daveeloo


People also ask

Is list comprehension more memory efficient?

As you can see, list comprehensions are a bit faster but allocate more memory.

Are list comprehensions memory efficient than generator comprehensions?

So what's the difference between Generator Expressions and List Comprehensions? The generator yields one item at a time and generates item only when in demand. Whereas, in a list comprehension, Python reserves memory for the whole list. Thus we can say that the generator expressions are memory efficient than the lists.

What are the advantages of using list comprehensions in Python?

One main benefit of using a list comprehension in Python is that it's a single tool that you can use in many different situations. In addition to standard list creation, list comprehensions can also be used for mapping and filtering. You don't have to use a different approach for each scenario.

Are list comprehensions slow Python?

List comprehensions are faster than for loops to create lists. But, this is because we are creating a list by appending new elements to it at each iteration. This is slow. Side note: It would even be worse if it was a Numpy Array and not a list.


2 Answers

Your example will result in Python first building the entire list. If you want to avoid that, you can use a generator expression instead:

max((x for x in range(25)))

or simply:

max(x for x in range(25))

Of course (in Python 2), range itself builds an entire list, so what you really want in this case is:

max(x for x in xrange(25))

However, regarding the time taken, all these expressions have the same complexity. The important difference is that the last one requires O(1) space, whereas the others require O(n) space.

like image 164
jchl Avatar answered Sep 28 '22 09:09

jchl


List comprehensions always generate a list (unless something throws an exception). Use of a genex instead is recommended in most cases.

max(x for x in xrange(25))
like image 37
Ignacio Vazquez-Abrams Avatar answered Sep 25 '22 09:09

Ignacio Vazquez-Abrams