Python: How to calculate the length of a range without creating the range?

Question

I need to calculate the length of a range, but ideally without creating the range, (hopefully will be faster and use less memory. This is important, because this function will be called a lot). The length is used to set an extended slice.

Right now I have tried:

int_div = lambda n, d: (n + d // 2) // d

def range_len(start, stop, step):
    return int_div(stop - start, step)

But on some cases, such as range_len(9, 100, 3) it gives 30 when the correct answer is 31. I feel like this should be simple, what am I doing wrong?

Answer 1

You can use this formula: (end - start - 1) // step + 1

def calc_length(start, end, step):
    return (end - start - 1) // step + 1

for i in range(start, end):
    calculated = calc_length(start, i, step)
    empirical = len(range(start, i, step))

    assert calculated == empirical, "{} {}".format(calculated, empirical)

Answer 2

In Python 2, you can use xrange. In Python 3, you can use range. In both, they return xrange/range objects instead of generating the whole list.

Python 2

return len(xrange(start, stop, step))

Python 3

return len(range(start, stop, step))

From the xrange help (in the Python 2 interpreter type help(xrange)):

class xrange(object)  
|  xrange([start,] stop[, step]) -> xrange object  
|  
|  Like range(), but instead of returning a list, returns an object that   
| generates the numbers in the range on demand.  For looping, this is  
|  slightly faster than range() and more memory efficient.

Or the range help in Python 3:

class range(object)  
 |  range(stop) -> range object  
 |  range(start, stop[, step]) -> range object  
 |  
 |  Return an object that produces a sequence of integers from start (inclusive)  
 |  to stop (exclusive) by step.  range(i, j) produces i, i+1, i+2, ..., j-1.  
 |  start defaults to 0, and stop is omitted!  range(4) produces 0, 1, 2, 3.  
 |  These are exactly the valid indices for a list of 4 elements.  
 |  When step is given, it specifies the increment (or decrement).

Creating xrange/range objects is faster and more memory efficient than creating the length of the associated lists.

Calculating the range from 0 to 1000000 using this method took my PC about 0.000004291534423828125 seconds.