By Rick supports Monica

2015-05-06 15:32:43 8 Comments

It is my understanding that the range() function, which is actually an object type in Python 3, generates its contents on the fly, similar to a generator.

This being the case, I would have expected the following line to take an inordinate amount of time, because in order to determine whether 1 quadrillion is in the range, a quadrillion values would have to be generated:

1000000000000000 in range(1000000000000001)

Furthermore: it seems that no matter how many zeroes I add on, the calculation more or less takes the same amount of time (basically instantaneous).

I have also tried things like this, but the calculation is still almost instant:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

If I try to implement my own range function, the result is not so nice!!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1

What is the range() object doing under the hood that makes it so fast?

Martijn Pieters' answer was chosen for its completeness, but also see abarnert's first answer for a good discussion of what it means for range to be a full-fledged sequence in Python 3, and some information/warning regarding potential inconsistency for __contains__ function optimization across Python implementations. abarnert's other answer goes into some more detail and provides links for those interested in the history behind the optimization in Python 3 (and lack of optimization of xrange in Python 2). Answers by poke and by wim provide the relevant C source code and explanations for those who are interested.

Related Questions

Sponsored Content

26 Answered Questions

[SOLVED] Does Python have a ternary conditional operator?

38 Answered Questions

[SOLVED] How to get the current time in Python

  • 2009-01-06 04:54:23
  • user46646
  • 3290820 View
  • 2877 Score
  • 38 Answer
  • Tags:   python datetime time

62 Answered Questions

[SOLVED] Calling an external command from Python

10 Answered Questions

[SOLVED] Does Python have a string 'contains' substring method?

30 Answered Questions

[SOLVED] Finding the index of an item in a list

  • 2008-10-07 01:39:38
  • Eugene M
  • 3865480 View
  • 3161 Score
  • 30 Answer
  • Tags:   python list indexing

20 Answered Questions

[SOLVED] What are metaclasses in Python?

26 Answered Questions

3 Answered Questions

[SOLVED] Why is printing "B" dramatically slower than printing "#"?

Sponsored Content