消除list.extend中的不必要副本

Question

假设你有两个普通的 Python 列表，分别叫做 newlist 和 oldlist，还有一个整数 index，这个整数小于 oldlist 的长度。我想要进行以下操作：

newlist.extend(oldlist[index:])

但是我不想创建一个中间列表 oldlist[index:]，或者说，

newlist.extend(oldlist[i] for i in xrange(index, len(oldlist)))

也不想使用生成器带来的额外开销。这样做有可能吗，不用 C 语言？

补充说明：这个问题源于我查看了一些列表操作的 C 语言实现，特别是 list.extend() 这个方法。当解释器判断可以猜测要添加到列表尾部的大小时，它会为头部列表分配足够的空间，并在生成元素时直接复制这些元素；而在其他情况下，它会一次分配几个元素（如果没记错，大约是八个），然后逐个复制元素。

它进行完全分配的特定情况似乎是针对 Python 列表，以及一些其他有 __len__ 方法的类型。根据我的了解，似乎没有内置的“列表视图”类型可以满足这些要求。

Answer 1

显而易见的解决方案是：

while index < len(oldlist):
    newlist.append(oldlist[index])
    index += 1

但是要注意，过早优化可能会带来问题。我从来没有遇到过这种情况，觉得这种解决方案的可读性下降是值得的。当然，最好对所有选项进行性能测试，以确保你认为更快的解决方案，实际上真的更快。

Answer 2

一些关于更好基准测试的提示

先测量一下额外的开销，然后把它减去。

把代码放在一个函数或方法里（这样更接近真实情况；还能避免因为使用全局变量而产生的意外问题）。

from itertools import islice
def f0(newlist, oldlist, index):
    pass
def f1(newlist, oldlist, index):
    newlist.extend(oldlist[index:])
def f2(newlist, oldlist, index):
    newlist.extend(oldlist[i] for i in xrange(index, len(oldlist)))
def f3(newlist, oldlist, index):
    newlist.extend(islice(oldlist, index, None))
def f4(newlist, oldlist, index):
    while index < len(oldlist):
        newlist.append(oldlist[index])
        index += 1


>python -mtimeit -s"old=range(1000);new=range(5000,10000);ix=500;import xtnd"; "xtnd.f4(new,old,ix)"

如果你要测试的代码里有一个变量 N（在这个例子中 N = len(oldlist) - index），那么最好用多个不同的 N 值来进行基准测试。如果你预期它的表现是 O(N)，但结果却是 O(1)，那就需要好好调查一下原因。

另外，比较不同候选方案的结果时，要有合理的预期——如果结果差异很大，就要查查原因；这可能是实验错误造成的。

Answer 3

别猜，量一下

create = """
oldlist = range(5000)
newlist = range(5000, 10000)
index = 500
"""
tests = [
    "newlist.extend(oldlist[index:])",
    "newlist.extend(oldlist[i] for i in xrange(index, len(oldlist)))",
    "newlist.extend(islice(oldlist, index, None))",
    """\
while index < len(oldlist):
   newlist.append(oldlist[index])
   index+=1""",
]

import timeit
for test in tests:
    t = timeit.Timer(create + test, setup='from itertools import islice')
    print test, min(t.repeat(number=100000))

---

newlist.extend(oldlist[index:]) 17.2596559525
newlist.extend(oldlist[i] for i in xrange(index, len(oldlist))) 53.5918159485
newlist.extend(islice(oldlist, index, None)) 19.6523411274
while index < len(oldlist):
   newlist.append(oldlist[index])
   index+=1 123.556715012