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

Question

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

我正在使用列表计算斐波那契数字,从列表中添加元素-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

A list以连续的方式将其元素存储在内存中.

所以对象的append方法list需要不时地调整分配的内存块(不是每次append都调用,幸运的是)

有时,系统能够"就地"调整大小(在当前内存块之后分配更多内存),有时不会:它必须找到一个足够大的内存块来存储新列表.

当调整大小不是"就地"时,需要复制现有数据.(注意,当列表的大小减小时不会发生)

因此,如果复制时列表中的元素较少,则操作会更快.

请注意,list.append仍然非常快.在列表的末尾添加是最快的方式(相比之下insert每次移动元素以释放其"插槽")

Answer 2

当列表很长时,"查找"列表的最后一个元素会慢得多吗？

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

当您删除不需要的列表元素时,Python永远不必为列表分配更大的缓冲区.它还可以重用为int对象分配的内存,而不是从OS请求更多内存.考虑到你的整数有多大,重用他们的记忆是一件大事.(内存分配的细节取决于Python版本和底层标准库分配器.Python 2有ints 的空闲列表,但不是longs; Python 3没有ints的空闲列表.Python本身不会重复使用大型分配对象,但底层分配器可能正在做某事.)

另外,当你必须继续分配新的整数时,特别是那些像99999th斐波纳契数一样大的整数,你不会从CPU的缓存中获得很多好处.主内存访问比缓存慢得多.

最后,你的分配模式fib_stack1(大量的分配,而不是那么多的对象refcounts降到0)触发了Python的循环检测器系统,也就是垃圾收集器,它需要时间来运行并触及大量不需要触摸的内存,破坏缓存性能.暂时禁用收集器会fib_stack1在我自己的测试中产生显着的加速,特别是在Python 3上.