CODEWITHSUNDEEP
pythonlistreduce
daveeloo
daveeloo

Reputation: 953

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?

Upvotes: 8

Views: 867

Answers (2)

jchl
jchl

Reputation: 6532

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.

Upvotes: 14

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798746

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))

Upvotes: 2

Related Questions