python - 为什么在 Python 中从列表中删除不需要的项目时计算时间会减少

Question

过去几天，我一直在努力更好地理解计算复杂性以及如何改进 Python 代码。为此，我尝试了不同的函数来计算斐波那契数列，比较了如果我进行小的更改脚本运行的时间。

我正在使用列表计算斐波那契数，将列表中的元素 -2 和 -1 相加。

我很困惑地发现，如果我在循环中添加一个 .pop() 并删除列表中不需要的元素，我的脚本运行速度会明显加快。我不明白为什么会这样。循环中的每一步，计算机都会多做一件事。所以我未经训练的直觉表明这应该会增加计算时间。当列表很长时，“查找”列表的最后一个元素会慢很多吗？

这是我的代码:

import time
import numpy as np

def fib_stack1(n):
    """ Original function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
        return stack[-1]

def fib_stack2(n):
    """ Modified function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
            ### CHANGE ###
            stack.pop(-3)
            ##############
        return stack[-1] 


rec1 = []
rec2 = []
for _ in range(10):
    t1 = time.time()
    fib_stack1(99999)  
    t2 = time.time()
    rec1.append(t2-t1)
    t1 = time.time()
    fib_stack2(99999)  
    t2 = time.time()
    rec2.append(t2-t1)
print(np.array(rec1).mean())
print(np.array(rec2).mean())

输出如下:

# Original 
0.26878631115
# Modified
0.145034956932

Answer 1

Is 'looking up' the last element of the list so much slower when the list is very long?

不，列表长度对查找速度没有影响。这些是数组列表，而不是链表。这更有可能与内存分配或缓存性能有关。垃圾收集器也参与其中。

当您删除不需要的列表元素时，Python 永远不必为列表分配更大的缓冲区。它还可以重用为 int 对象分配的内存，而不是从操作系统请求更多内存。考虑到你的整数有多大，重用它们的内存是一件大事。 (内存分配的细节取决于 Python 版本和底层标准库分配器。Python 2 有一个用于 int 的空闲列表，但没有 long；Python 3 有没有 int 的空闲列表。Python 本身不会努力为大对象重用分配，但底层分配器可能正在做一些事情。)

此外，当您必须不断分配新整数时，尤其是像第 99999 个斐波那契数这样大的整数，您不会从 CPU 的缓存中获得太多好处。主内存访问比缓存慢得多。

最后，fib_stack1 的分配模式(大量分配，没有那么多对象引用计数降为 0)触发 Python 的循环检测器系统，也就是垃圾收集器，它需要时间来运行和接触了很多不需要接触的内存，损害了缓存性能。临时disabling the collector在我自己的测试中，特别是在 Python 3 上，fib_stack1 产生了显着的加速。