3
\$\begingroup\$

I recently created a function calculating the sum of an arbitrary range object in \$O(1)\$:

def sum_of_range(range_obj):
    """Calculates the sum of a range object (Python 3) in O(1).

    This function always returns a python integer representing the sum 
    without loss of precision (as would happen if it uses intermediate
    floating point values).
    """
    start, stop, step = range_obj.start, range_obj.stop, range_obj.step
    len_ = len(range_obj)
    if step > 0:
        if start >= stop:
            return 0
        # Find the last "really" included number. Subtract one from stop
        # because the stop is not included in ranges.
        upper = (stop - 1 - start) // step * step + start
    else:
        if stop >= start:
            return 0
        # In case the step is negative we need to add one to the difference
        # instead of subtracting one.
        upper = (stop - start + 1) // step * step + start
    sum_first_and_last = upper + start
    return (sum_first_and_last * len_) // 2

I used "random" tests to verify that it works:

import random

for i in range(100000):  # make a lot of random tests
    up = random.randint(-10000, 10000)
    lo = random.randint(-10000, 10000)
    step = random.randint(-25, 25)
    if step == 0:  # steps of zero are not possible
        continue
    rg = range(lo, up, step)
    assert sum_of_range(rg) == sum(rg)

Is there any room for improvement? Especially (but not only):

  • Code readability
  • Code performance
  • Should I replace the random tests with explicit tests or can I neglect explicit tests? Or should I include both?
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Not clear why you hoisted the len_ computation. You only use it once, at the end of the routine. So no performance advantage for hoisting. In cases of early exit, actually a deficit. And distance between load into local variable and use raises clarity issues. \$\endgroup\$ Commented Jan 19, 2017 at 20:10
  • \$\begingroup\$ Now that you mention it... no idea why it's hoisted. :( \$\endgroup\$
    – MSeifert
    Commented Jan 19, 2017 at 20:22

2 Answers 2

7
\$\begingroup\$

Let's get a closer look at the sum you're trying to calculate:

$$start + (start+step) + (start+2 \times{}step) + \ldots + (start + (len-1)\times{} step)$$

Which can be reordered as:

$$start + \ldots + start + step + 2\times{}step + \ldots + (len-1)\times{}step$$

Which gives you a nice formula regardless of the sign of start or step or even the value of stop:

$$start \times{} len + step \times\frac{len(len-1)}{2}$$

All the complexity being hidden in the len(range_obj) call. So you can just write:

def sum_of_range(range_obj):
    """Calculates the sum of a range object (Python 3) in O(1).

    This function always returns a python integer representing the sum
    without loss of precision (as would happen if it uses intermediate
    floating point values).
    """

    length = len(range_obj)
    step_counts = length * (length - 1) // 2
    return range_obj.start * length + range_obj.step * step_counts
\$\endgroup\$
2
  • \$\begingroup\$ Ah, that's really clever, it took a moment to realize that one of len and len-1 is even so their product is even as well and one can safely use floor division. Thanks. \$\endgroup\$
    – MSeifert
    Commented Jan 19, 2017 at 21:45
  • \$\begingroup\$ @MSeifert Yes, thats basic sum from 0 to n: en.m.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF \$\endgroup\$ Commented Jan 19, 2017 at 21:48
-3
\$\begingroup\$

range_obj is not a container, and you cannot rely on len(range_obj) being \$O(1)\$. A simple experiment

$ python -mtimeit "len(range(10))"
10000000 loops, best of 3: 0.158 usec per loop

$ python -mtimeit "len(range(10000000))"
10 loops, best of 3: 188 msec per loop

shows that it is in fact linear.

The bright side is that you don't need len at all. You need a number of elements, and even though it is numerically equal to len, it can (and should) be computed as

    len_ = (obj.stop - obj.start) // obj.step
\$\endgroup\$
4
  • 3
    \$\begingroup\$ At least on my computer it's constant, what python and python version are you using? \$\endgroup\$
    – MSeifert
    Commented Jan 19, 2017 at 22:45
  • 4
    \$\begingroup\$ You're probably testing in Python 2, but either way, you can't reasonably pin the linear time on len as you're timing the creation of the range object too. Instead use the setup argument to remove this possibility, as then you can time only len. \$\endgroup\$
    – Peilonrayz
    Commented Jan 20, 2017 at 2:39
  • 1
    \$\begingroup\$ stackoverflow.com/questions/31839032/… \$\endgroup\$ Commented Jan 20, 2017 at 7:07
  • 1
    \$\begingroup\$ To expand on my last comment, I used: python -m timeit -s "r=range(10)" "len(r)", where I changed; Python versions, the size of the range, and used xrange and range in Python 2, and found no reasonable (0.1usec) change in time. \$\endgroup\$
    – Peilonrayz
    Commented Jan 20, 2017 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.