Python:没有重定位的列表

Question

我正在尝试用Python优化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 运行。