patternpythonMinor
Accurate sum of a range object in O(1)
Viewed 0 times
rangeobjectaccuratesum
Problem
I recently created a function calculating the sum of an arbitrary
I used "random" tests to verify that it works:
Is there any room for improvement? Especially (but not only):
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_) // 2I 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?
Solution
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 \times{} len + step \times\frac{len(len-1)}{2}$$
All the complexity being hidden in the
$$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_countsCode Snippets
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_countsContext
StackExchange Code Review Q#153068, answer score: 7
Revisions (0)
No revisions yet.