patternpythonMinor
Find an array slice equaling sum
Viewed 0 times
equalingfindarraysumslice
Problem
I would like to be reviewed on efficiency, style, and obviously if there is a bug I would like to know.
def findsum(a, n):
''' Find whether a consecutive array slice sums up to n '''
for i in range(len(a)):
j = i + 1
while j <= len(a):
if sum(a[i:j]) == n:
return True
j += 1
return FalseSolution
-
There's a bug:
but the result should be
-
The docstring could be clearer. "a consecutive array slice" — of which array? Presumably the parameter
-
The function has runtime \$Θ(n^3)\$. That's because
There's a bug:
>>> a = [1, 2, 3]
>>> findsum(a, 0)
Falsebut the result should be
True because the consecutive slice a[0:0] sums to zero.-
The docstring could be clearer. "a consecutive array slice" — of which array? Presumably the parameter
a is meant, but it is best to be explicit. Similarly, "Find whether" — and then what? The docstring should say what value is returned.-
The function has runtime \$Θ(n^3)\$. That's because
sum(a[i:j]) takes an unnecessary copy of the slice, and because it sums it starting at the beginning of the slice. But if you maintained a running sum, then the runtime would come down to \$Θ(n^2)\$. That's easy to implement using itertools.accumulate and itertools.islice:from itertools import accumulate, islice
def findsum(a, n):
"""Return True if any consecutive slice of the sequence a sums to n,
False if none do.
"""
return n == 0 or any(total == n
for i in range(len(a))
for total in accumulate(islice(a, i, None)))Code Snippets
>>> a = [1, 2, 3]
>>> findsum(a, 0)
Falsefrom itertools import accumulate, islice
def findsum(a, n):
"""Return True if any consecutive slice of the sequence a sums to n,
False if none do.
"""
return n == 0 or any(total == n
for i in range(len(a))
for total in accumulate(islice(a, i, None)))Context
StackExchange Code Review Q#109481, answer score: 6
Revisions (0)
No revisions yet.