python - 最大限度。求和数组部分的有效方法

Question

我正试图找到一种更有效的方法来执行下面的任务。

函数被提供一些列表。我需要:

1) 找到列表的总和并将结果存储在另一个专门为此准备的列表中。

2) 移除输入列表的第一个元素

3) 找到新列表的总和并追加到第 1 步的列表中。

4) 重复直到输入列表为空。

基本上，下面的代码已经完成了任务，但在速度方面效率低下(据我所知，append 方法并不是 Python 库中最精简的工具)。执行此操作的更有效方法是什么？

def parts_sums(ls):
    sums = []

    if len(ls) == 0:
            sums.append(0)

    while len(ls) > 0:
        sums.append(sum(ls))
        ls.pop(0)

        if len(ls) == 0:
            sums.append(0)

    return sums

提前谢谢你。

Answer 1

ls.pop(0) 的计算量很大，因为这意味着所有剩余的元素都向左移动一位。对于 n 个元素，这是一个 O(n) 操作。此外，您每次都计算子列表的总和，这又是一个O(n) 操作。

例如，我们可以先计算整个列表的总和，然后每次从中减去一个元素，例如:

def parts_sums(ls):
    total = sum(ls)
    yield total
    for item in ls:
        total -= item
        yield total

这给了我们:

>>> list(parts_sums([1,4,2,5]))
[12, 11, 7, 5, 0]

我们可以通过对列表进行简单的扫描来计算列表，例如:

def parts_sums(ls):
    a = 0
    result = [0]
    for e in reversed(ls):
        a += e
        result.append(a)
    result.reverse()
    return result

例如:

>>> parts_sums([1,4,2,5])
[12, 11, 7, 5, 0]

我们这里就是这样计算出反转列表的累积和数组，然后反转那个列表，这在功能上是一样的。

我们也可以为此使用 numpy:

import numpy as np

def parts_sums(iterable):
    return np.hstack((np.flip(np.cumsum(np.flip(iterable))), [0]))

例如:

>>> parts_sums([1,4,2,5])
array([12, 11,  7,  5,  0])

性能

我在 Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz 上运行了一些测试。如果 data 是一个包含 10'000 个元素的列表，我们将获得 1'000 次运行的以下结果:

>>> timeit(lambda: list(parts_sums1(data)), number=1000)
1.5667014829959953
>>> timeit(lambda: parts_sums2(data), number=1000)
1.095261047994427
>>> timeit(lambda: parts_sums3(data), number=1000)
0.5962606709945248

对于包含 100'000 个元素的列表 data，我们每次运行 100 次得到以下结果:

>>> timeit(lambda: list(parts_sums1(data)), number=100)
1.6292997589989682
>>> timeit(lambda: parts_sums2(data), number=100)
1.1703664560045581
>>> timeit(lambda: parts_sums3(data), number=100)
0.6373857369981124