Teaching Kids Programming: Videos on Data Structures and Algorithms
The accumulate function is provided in itertools and allows us to return a generator containing the sum of previous items. For example:
from itertools import accumulate
a = [1, 2, 3, 4, 5]
print(accumulate(a))
<itertools.accumulate object at 0xa770d0>
list(accumulate(a))
[1, 3, 6, 10, 15]
We can define an accumulate function that returns a list:
def accumulate(a):
for i in range(1, len(a)):
a[i] += a[i - 1]
return a
We can also make it return a generator:
def accumulate(a):
for i in range(1, len(a)):
a[i] += a[i - 1]
yield from a
If we want to not modify the original list:
def accumulate(a):
b = [a[0]]
for i in range(1, len(a)):
b.append(a[i] + b[-1])
yield from b
Time complexity is O(N) where N is the number of elements in the list.
See also: Teaching Kids Programming – Matrix Prefix Sum Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
297 wordsLast Post: Simple Exponential Backoff Retry Class in C++
Next Post: Alarming on High Disk Usage using BASH + AWK + Crontab Job
