为什么从 Python 中的列表中删除不需要的项目时计算时间会减少
Why does computational time decrease when removing unnecessary items from a list in Python
过去几天我一直在努力更好地理解计算复杂性以及如何改进 Python 代码。为此，我尝试了不同的函数来计算斐波那契数列，比较了如果我进行小的更改脚本运行的时间。
我正在使用列表计算斐波那契数，添加列表中元素 -2 和 -1 的总和。
我很困惑地发现，如果我在循环中添加 .pop() 并删除列表中不需要的元素，我的脚本运行速度会明显加快。我不明白为什么会这样。循环中的每一步，计算机都会多做一件事。所以我未经训练的直觉表明这应该会增加计算时间。当列表很长时，'looking up' 列表的最后一个元素会慢很多吗？
这是我的代码：
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
A list 以 连续 方式将其元素存储在内存中。
所以list对象的append方法需要时不时调整分配的内存块的大小（不是每次调用append，还好）
有时，系统能够调整大小"in-place"（在当前内存块之后分配更多内存），有时不能：它必须找到足够大的连续内存块来存储新列表.
当调整大小不是"in-place"时，需要复制现有数据。 （请注意，当列表的大小 减少 时不会发生这种情况）
因此，如果复制时列表中的元素较少，操作速度会更快。
请注意 list.append 仍然非常快。在列表末尾添加是最快的方法（与 insert 相比，后者每次都必须移动元素以释放其 "slot"）
不，查找列表中的任何元素都在相同的时间内完成（计算机科学中称为恒定时间行为）。添加对 pop 的调用确实会稍微增加每次循环迭代所需的工作，但列表永远不会超过 3 个元素。在您的第一个版本中，列表在每次迭代中都会增长，这样的操作可以是 完全免费 或 相当昂贵，具体取决于多少 额外 列表实际分配的内存，这是一个无法直接访问的信息。
基本上，当您实例化一个列表时，会预先分配一些额外的 space，为将来的 append 腾出空间，但要牺牲 "wasting" space。如果列表被填满，则需要扩大它以便进一步 append 发生，因此这些特定的追加比通常要昂贵得多。如果数组末尾的内存中已经存在一些其他数据，则必须将列表元素中的 all 数据（实际上只是指针）复制到新的内存位置整个新列表可以存储在一个连续的内存块中。
有关列表增长行为的更多信息（仅在 CPython 中，因为这是特定于实现的），例如参见here
维护列表的开销超过额外的操作。这可以通过 inspecting the size of the resulting list as the functions run:
来证明
# Func List Size (Sum of Elements Size)
fib_stack1: 120 (72)
fib_stack1: 90136 (4888568)
fib_stack1: 162720 (19034164)
fib_stack1: 260864 (42436332)
fib_stack1: 330256 (75095060)
fib_stack1: 418080 (117010332)
fib_stack1: 529224 (168182184)
fib_stack1: 595424 (228610568)
fib_stack1: 669896 (298295536)
fib_stack1: 753680 (377237048)
fib_stack2: 112 (48)
fib_stack2: 112 (1904)
fib_stack2: 112 (3752)
fib_stack2: 112 (5608)
fib_stack2: 112 (7456)
fib_stack2: 112 (9312)
fib_stack2: 112 (11160)
fib_stack2: 112 (13008)
fib_stack2: 112 (14864)
fib_stack2: 112 (16712)
fib_stack3: 48
fib_stack3: 1904
fib_stack3: 3752
fib_stack3: 5608
fib_stack3: 7456
fib_stack3: 9312
fib_stack3: 11160
fib_stack3: 13008
fib_stack3: 14864
fib_stack3: 16712
注意：
- 在第一种情况下，python 不知道您不需要旧值所以它必须索引并存储所有以前的值，包括，正如其他人提到的那样，复制该列表，因为它需要分配更多内存。
- 在第二种情况下，python 不必存储旧值，因此自从每次 add/pop 以来列表都不会增长 。它删除项目零，将所有较大的项目复制回一个 space，然后继续。
- 在第三种情况下（如下所述），我们删除中间列表并仅手动应用转换。这就是为什么
fib_stack2 的元素大小之和等于 fib_stack3. 中两个整数的组合
可以通过不列出开头来进一步改进：
def fib_stack3(n):
""" Modified function """
assert type(n) is int, 'Expected an integer as input.'
if n < 2:
return n
else:
second_anc, first_anc = 0, 1
for i in range(n-1):
second_anc, first_anc = first_anc, second_anc + first_anc
return first_anc
运行 repl.it 上的所有三个给出：
fib_stack1 1.3875333309173583
fib_stack2 0.41049718856811523
fib_stack3 0.33348443508148196
很明显，最后一种情况，即我们根本不用列表，胜出。
这是因为我们不再缩小我们的列表，我们只是重复使用相同的两个整数。这是有效的，因为 python evaluates the right side before the left 因此允许单行交换。
Is 'looking up' the last element of the list so much slower when the list is very long?
不，列表长度对查找速度没有影响。这些是数组列表，而不是链表。这更有可能与内存分配或缓存性能有关。垃圾收集器也参与其中。
当您删除不需要的列表元素时，Python 永远不必为列表分配更大的缓冲区。它还可以重用为 int 对象分配的内存，而不是从 OS 请求更多内存。考虑到你的整数有多大，重用它们的内存是一件大事。 （内存分配的细节取决于 Python 版本和底层标准库分配器。Python 2 有 ints 的空闲列表，但没有 longs; Python 3 没有 ints 的空闲列表。Python 本身没有努力为大对象重用分配，但底层分配器可能正在做一些事情。）
此外，当您必须不断分配新整数时，尤其是像第 99999 个斐波那契数这样大的整数，您不会从 CPU 的缓存中获得太多好处。主内存访问比缓存慢得多。
最后，您 fib_stack1 的分配模式（大量分配，没有那么多对象引用计数降为 0）触发 Python 的循环检测器系统，a.k.a。垃圾收集器，它需要时间 运行 并触及大量不需要触及的内存，从而损害缓存性能。在我自己的测试中，disabling the collector 暂时为 fib_stack1 带来了显着的加速，尤其是在 Python 3.
上
过去几天我一直在努力更好地理解计算复杂性以及如何改进 Python 代码。为此，我尝试了不同的函数来计算斐波那契数列，比较了如果我进行小的更改脚本运行的时间。
我正在使用列表计算斐波那契数，添加列表中元素 -2 和 -1 的总和。
我很困惑地发现，如果我在循环中添加 .pop() 并删除列表中不需要的元素，我的脚本运行速度会明显加快。我不明白为什么会这样。循环中的每一步，计算机都会多做一件事。所以我未经训练的直觉表明这应该会增加计算时间。当列表很长时，'looking up' 列表的最后一个元素会慢很多吗？
这是我的代码：
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
A list 以 连续 方式将其元素存储在内存中。
所以list对象的append方法需要时不时调整分配的内存块的大小（不是每次调用append，还好）
有时，系统能够调整大小"in-place"（在当前内存块之后分配更多内存），有时不能：它必须找到足够大的连续内存块来存储新列表.
当调整大小不是"in-place"时，需要复制现有数据。 （请注意，当列表的大小 减少 时不会发生这种情况）
因此，如果复制时列表中的元素较少，操作速度会更快。
请注意 list.append 仍然非常快。在列表末尾添加是最快的方法（与 insert 相比，后者每次都必须移动元素以释放其 "slot"）
不，查找列表中的任何元素都在相同的时间内完成（计算机科学中称为恒定时间行为）。添加对 pop 的调用确实会稍微增加每次循环迭代所需的工作，但列表永远不会超过 3 个元素。在您的第一个版本中，列表在每次迭代中都会增长，这样的操作可以是 完全免费 或 相当昂贵，具体取决于多少 额外 列表实际分配的内存，这是一个无法直接访问的信息。
基本上，当您实例化一个列表时，会预先分配一些额外的 space，为将来的 append 腾出空间，但要牺牲 "wasting" space。如果列表被填满，则需要扩大它以便进一步 append 发生，因此这些特定的追加比通常要昂贵得多。如果数组末尾的内存中已经存在一些其他数据，则必须将列表元素中的 all 数据（实际上只是指针）复制到新的内存位置整个新列表可以存储在一个连续的内存块中。
有关列表增长行为的更多信息（仅在 CPython 中，因为这是特定于实现的），例如参见here
维护列表的开销超过额外的操作。这可以通过 inspecting the size of the resulting list as the functions run:
来证明# Func List Size (Sum of Elements Size)
fib_stack1: 120 (72)
fib_stack1: 90136 (4888568)
fib_stack1: 162720 (19034164)
fib_stack1: 260864 (42436332)
fib_stack1: 330256 (75095060)
fib_stack1: 418080 (117010332)
fib_stack1: 529224 (168182184)
fib_stack1: 595424 (228610568)
fib_stack1: 669896 (298295536)
fib_stack1: 753680 (377237048)
fib_stack2: 112 (48)
fib_stack2: 112 (1904)
fib_stack2: 112 (3752)
fib_stack2: 112 (5608)
fib_stack2: 112 (7456)
fib_stack2: 112 (9312)
fib_stack2: 112 (11160)
fib_stack2: 112 (13008)
fib_stack2: 112 (14864)
fib_stack2: 112 (16712)
fib_stack3: 48
fib_stack3: 1904
fib_stack3: 3752
fib_stack3: 5608
fib_stack3: 7456
fib_stack3: 9312
fib_stack3: 11160
fib_stack3: 13008
fib_stack3: 14864
fib_stack3: 16712
注意：
- 在第一种情况下，python 不知道您不需要旧值所以它必须索引并存储所有以前的值，包括，正如其他人提到的那样，复制该列表，因为它需要分配更多内存。
- 在第二种情况下，python 不必存储旧值，因此自从每次 add/pop 以来列表都不会增长 。它删除项目零，将所有较大的项目复制回一个 space，然后继续。
- 在第三种情况下（如下所述），我们删除中间列表并仅手动应用转换。这就是为什么
fib_stack2的元素大小之和等于fib_stack3. 中两个整数的组合
可以通过不列出开头来进一步改进：
def fib_stack3(n):
""" Modified function """
assert type(n) is int, 'Expected an integer as input.'
if n < 2:
return n
else:
second_anc, first_anc = 0, 1
for i in range(n-1):
second_anc, first_anc = first_anc, second_anc + first_anc
return first_anc
运行 repl.it 上的所有三个给出：
fib_stack1 1.3875333309173583
fib_stack2 0.41049718856811523
fib_stack3 0.33348443508148196
很明显，最后一种情况，即我们根本不用列表，胜出。
这是因为我们不再缩小我们的列表，我们只是重复使用相同的两个整数。这是有效的，因为 python evaluates the right side before the left 因此允许单行交换。
Is 'looking up' the last element of the list so much slower when the list is very long?
不，列表长度对查找速度没有影响。这些是数组列表，而不是链表。这更有可能与内存分配或缓存性能有关。垃圾收集器也参与其中。
当您删除不需要的列表元素时，Python 永远不必为列表分配更大的缓冲区。它还可以重用为 int 对象分配的内存，而不是从 OS 请求更多内存。考虑到你的整数有多大，重用它们的内存是一件大事。 （内存分配的细节取决于 Python 版本和底层标准库分配器。Python 2 有 ints 的空闲列表，但没有 longs; Python 3 没有 ints 的空闲列表。Python 本身没有努力为大对象重用分配，但底层分配器可能正在做一些事情。）
此外，当您必须不断分配新整数时，尤其是像第 99999 个斐波那契数这样大的整数，您不会从 CPU 的缓存中获得太多好处。主内存访问比缓存慢得多。
最后，您 fib_stack1 的分配模式（大量分配，没有那么多对象引用计数降为 0）触发 Python 的循环检测器系统，a.k.a。垃圾收集器，它需要时间 运行 并触及大量不需要触及的内存，从而损害缓存性能。在我自己的测试中，disabling the collector 暂时为 fib_stack1 带来了显着的加速，尤其是在 Python 3.