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?
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\$