Python:一个不会被重新定位的列表

Question

我正在尝试优化 Python 中的算法纯粹是为了好玩/好奇。我有一个列表，我不断地从中添加项目和删除项目。我知道 Python 列表的实现方式，Python 会根据列表的大小为您在内存中重新定位列表。例如，如果您有一个包含 10 个成员的列表，这 10 个指针将连续存储在内存中，但可能没有空间容纳 100 个连续的指针，因为另一个程序可能占用了挡路的内存块。因此，当您向列表中添加更多成员时，有时 Python 会将整个列表重新定位到内存中的不同位置，以便为列表扩展提供更多空间。

我很想知道 Python 中是否有一个自定义数据结构，其行为类似于列表，但允许我避免执行重定位的性能成本。我期待这个数据类型会事先询问我，我预计它会有多少成员，然后它会在内存中分配一个大的连续空间，这样它就不需要重新定位列表，因为它会慢慢增长到我的成员数量指定。

(注意:我尝试使用 Numpy 数组，但我不得不保留一个单独的“针”变量来保持列表的大小，恐怕在 Python 中维护该针的开销比收获。)

Answer 1

出于好奇，我实现了简单的基准测试来测试这里提到的各种方法。正如人们预测的那样，差异非常小。也就是说，对于较大的数据集，预先分配列表并跟踪大小会更快，但这当然只是在最后添加/删除项目时的情况。

基准

import time
from collections import deque

def normal(size):
    res = []
    for x in xrange(size):
        res.append(x)

def prealloc(size):
    res = [0] * size
    len = 0 # Separate length tracking
    for x in xrange(size):
        res[len] = x
        len += 1

def deq(size):
    res = deque()
    for x in xrange(size):
        res.append(x)

FUNCS = [
    ['list', normal],
    ['pre-allocate', prealloc],
    ['deque', deq]
]

size = 10
while size <= 10000000:
    print 'size: {0}'.format(size)
    for n, f in FUNCS:
        start = time.clock()
        for i in xrange(30):
            f(size)
        t = time.clock() - start
        print '{}: {}'.format(n, (t / 30))
    size *= 100
    print ''

结果

size: 10
list: 2.13049681786e-06
pre-allocate: 2.03719038788e-06
deque: 2.00608824456e-06

size: 1000
list: 0.000104425446219
pre-allocate: 8.72415120307e-05
deque: 0.000106369330176

size: 100000
list: 0.00984092031242
pre-allocate: 0.00825001457913
deque: 0.0101434508606

size: 10000000
list: 1.23171166758
pre-allocate: 0.876017370547
deque: 1.05051393959

测试是在 Windows 8 上使用 Python 2.7.10 运行的。