`in range` in python 2 --- is too slow

Question

I wanted to check if the given x in the interval [0,a-1] . As a lazy coder, I wrote

 x in range(a) 

and (since this part of the code was in 4.5 nested loops), performance problems quickly arise. I tested it and it really turns out that the runtime n in range(n) lies in O (n), give or take. I really thought my code would be optimized for x >= 0 and x < a , but it doesn't seem to be that way. Even if I correct range(a) in advance, the time does not become constant (although it improves significantly) - see Side notes.

So my question is:

Should I use x >= 0 and x < a and never again write x in range(a) ? Is there an even better way to write this?

---

Side notes:

• I tried to find SO for range, python-2.7, performance tags , didn't find anything (same with python-2.x ).

• If I try to do the following:

   i = range(a) ... x in i 

  so that the range is fixed, and I only measure the runtime x in i , I still get runtime in O (x) (assuming a is big enough).

• runtime n in xrange(n) also lies in O (n).
• I found this post that asks a similar question for python 3. I decided to test the same stuff on python 3 and it went through the tests as if nothing. I was sad for python 2.

Answer 1

The problem with range in Python 2 is that it creates list values, so x in range(a) will create a list and scan this list linearly. xrange should be a generator, but it is not much faster; probably still just linearly scans the values, just not creating the whole list in the first place.

 In [2]: %timeit 5*10**5 in range(10**6 + 1) # Python 2 10 loops, best of 3: 18.1 ms per loop In [3]: %timeit 5*10**5 in xrange(10**6 + 1) # Python 2 100 loops, best of 3: 6.21 ms per loop 

In Python 3, the range much smarter, not only not creating the entire list, but also providing a quick implementation of the contains check.

 In [1]: %timeit 5*10**5 in range(10**6 + 1) # Python 3 1000000 loops, best of 3: 324 ns per loop 

Even faster and IMHO more readable: using a comparison chain:

 In [2]: %timeit 0 <= 5*10**5 < 10**6 + 1 # Python 2 or 3 10000000 loops, best of 3: 46.6 ns per loop 

---

Should I use x >= 0 and x < a and never again write x in range (a)? Is there an even better way to write this?

No, it depends, and yes. You should not use x >= 0 and x < a , because 0 <= x < a is shorter and easier to parse (for weak people) and interpreted as (0 <= x) and (x < a) . And you shouldn't use in range in Python 2, but in Python 3 you can use it if you want.

However, I would prefer a comparison chain, since a <= x < b much more explicit about boundaries than x in range(a, b) (what if x == b ?), Which can prevent many errors One by one or t217 range.

Also note that 0 <= x < a not exactly the same as x in range(0, a) , since range will only contain integer values, i.e. 1.5 in range(0, 5) is False , while 0 <= 1.5 < 5 is True , which may not be what you want. Also, using range , you can use steps other than 1 , for example. 5 in range(4, 10, 2) is False , but the same can also be implemented using pure mathematics, for example. as (4 <= x < 10) and (x - 4 % 2 == 0) .

Answer 2

You can get the same performance as in python3 using your own range class and overriding the in operator. For trivial cases, this is not as simple as a simple comparison, but you will avoid using O(n) memory and the time you get with the built-in range() or xrange() .

Note that testing value in range(low, high) is different from low < value <= high , since the range will contain integers. So 7.2 in range(10) == False .

But more importantly, range() can take the optional argument of the third step, so if you need to test value in range(low, high, step) , you can use a custom class.

EDIT: @ mike239x found a future package that contains a range object similar to the one in my answer (in addition to other functions that will help you write python2 / 3 compatible code). This should be safe to use, as it is supposedly well tested and stable.

An object of this class wraps an xrange object and only overrides the very expensive in operation. For regular iteration, it works the same as xrange .

 class range(object): """Python 2 range class that emulates the constant time `in` operation from python 3""" def __init__(self, *args): self.start, self.end = (0, args[0]) if len(args) == 1 else args[:2] self.step = 1 if len(args) < 3 else args[2] self.xrange = xrange(*args) def __contains__(self, other): # implements the `in` operator as O(1) instead of xrange O(n) try: assert int(other) == other except Exception: return False # other is not an integer if self.step > 0: if not self.start <= other < self.end: return False # other is out of range else: if not self.start >= other > self.end: return False # other is out of range # other is in range. Check if it a valid step return (self.start - other) % self.step == 0 def __iter__(self): # returns an iterator used in for loops return iter(self.xrange) def __getattr__(self, attr): # delegate failed attribute lookups to the encapsulated xrange return getattr(self.xrange, attr) 

The built-in xrange object xrange implemented in C, so we cannot use class inheritance. Instead, we can use composition and delegate everything except __contains__ to an encapsulated xrange object.

The implementation contains can be compared to range_contains_long in a cpython implementation of rangeobject . Here is the python 3.6 source code for this function.

Edit: for a more complete python implementation, future.builtins.range from the future library.

Answer 3

Call x in range( a ) slow? ^{(Note that py2 is hidden by RISK when using range() ...)}

  23[us] spent in [py2] to process ( x in range( 10E+0000 ) ) 4[us] spent in [py2] to process ( x in range( 10E+0001 ) ) 3[us] spent in [py2] to process ( x in range( 10E+0002 ) ) 37[us] spent in [py2] to process ( x in range( 10E+0003 ) ) 404[us] spent in [py2] to process ( x in range( 10E+0004 ) ) 4433[us] spent in [py2] to process ( x in range( 10E+0005 ) ) 45972[us] spent in [py2] to process ( x in range( 10E+0006 ) ) 490026[us] spent in [py2] to process ( x in range( 10E+0007 ) ) 2735056[us] spent in [py2] to process ( x in range( 10E+0008 ) ) MemoryError 

The syntax of the in range( a ) constructor is not only slow in the [TIME] , having - best of all - O (log N), if we make it smarter than a pure sequential search on the listed domain of value lists, but
in
py2, native range() always also has composite additional O( N ) costs for both [TIME] domain costs (assembly time) and [SPACE] (allocation of storage space + spend more time transferring all of these data through ...) from such memory range representation.

---

Let me test the safe, O( 1 ) scaled approach ^{(+ always do the test)}

 >>> from zmq import Stopwatch >>> aClk = Stopwatch() >>> a = 123456789; x = 123456; aClk.start(); _ = ( 0 <= x < a );aClk.stop() 4L >>> a = 123456789; x = 123456; aClk.start(); _ = ( 0 <= x < a );aClk.stop() 3L 

It takes 3 ~ 4 [us] to evaluate a condition-based formulation that has O (1) scaling that is invariant to x .

---

Then do the same tests using the x in range( a ) formula:

 >>> a = 123456789; x = 123456; aClk.start(); _ = ( x in range( a ) );aClk.stop() 

and your computer will almost slow down in memory-bandwidth associated with CPU-starvation (not to mention the unpleasant redistribution of swaps from cost ranges from several ~ 100 [ns] several orders of magnitude higher to some t217> costs of input / output data flows with disk sharing).

---

No no no. Never check x within a limited range.

The ideas of creating some other class-based appraiser that still approaches the problem using an enumeration (set) can never match the test 3 ~ 4 [us] _{(unless some extraterrestrial magic is used outside my understanding of the laws causally -investigations in classical and quantum physics)}

---

Python 3 changed the way range() -constructor works , but that was not the main merit of the original post

  3 [us] spent in [py3] to process ( x in range( 10E+0000 ) ) 2 [us] spent in [py3] to process ( x in range( 10E+0001 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0002 ) ) 2 [us] spent in [py3] to process ( x in range( 10E+0003 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0004 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0005 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0006 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0007 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0008 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0009 ) ) 2 [us] spent in [py3] to process ( x in range( 10E+0010 ) ) 1 [us] spent in [py3] to process ( x in range( 10E+0011 ) ) 

---

In Python 2, none of range() not xrange() comes out of the O( N ) scaling trap, where the xrange() generator seems to only work with 2x less slow

 >>> from zmq import Stopwatch >>> aClk = Stopwatch() >>> for expo in xrange( 8 ): ... a = int( 10**expo); x = a-2; aClk.start(); _ = ( x in range( a ) );aClk.stop() ... 3L 8L 5L 40L 337L 3787L 40466L 401572L >>> for expo in xrange( 8 ): ... a = int( 10**expo); x = a-2; aClk.start(); _ = ( x in xrange( a ) );aClk.stop() ... 3L 10L 7L 77L 271L 2772L 28338L 280464L 

---

The range boundary syntax has an O( 1 ) constant time ~ < 1 [us] , as shown above, so a criterion for comparing repetitions was set:

 >>> for expo in xrange( 8 ): ... a = int( 10**expo); x = a-2; aClk.start(); _ = ( 0 <= x < a );aClk.stop() ... 2L 0L 1L 0L 0L 1L 0L 1L 

Answer 4

So yes, basically, using range in Python 2 (as described) is a bad idea - python actually creates a list with all range + values, after which it scans the entire list in the most direct direction way.

One option is as follows: use range from Python 3, which handles the situation more efficiently for various reasons . "Well," you ask, "how do I use range from Python 3 to Python 2"? Answer: using future library . Install it, write down

 from future.builtins import range 

in the header of the code and wuolah! - your range now behaves like one of Python 3, and now you can use x in range(a) again, without any performance issues.