代码之家 › 专栏 › 技术社区 › SingleNegationElimination

在列表中删除此不需要的副本。扩展

optimization python

SingleNegationElimination · 技术社区 · 14 年前

给定两个普通的python列表, newlist 和 oldlist ,带整数 index &中尉; len(oldlist) ,我要执行以下操作:

newlist.extend(oldlist[index:])

但是没有创建中间列表 oldlist[index:] ,或等效地,

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

没有发电机的开销。不用C就可以吗?

编辑:这个问题来源于一些查看某些列表操作的c实现的问题,特别是 list.extend() ,当解释器确定它可以猜出要添加到列表中的尾部的大小时,它将该完整大小分配给头列表,并在生成元素时复制它们;对于其他情况,它一次分配几个元素(如果内存可用,大约8个),一次复制几个元素。

当它执行完全分配时的特定情况似乎是针对python列表,以及其他一些具有 __len__ . 据我所知,没有内置类型的“列表视图”可以满足这些要求。

4 回复 | 直到 13 年前

nosklo 14 年前

别猜,量一下

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

Zack Bloom 14 年前

显而易见的解决办法是:

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

但是要小心过早的优化,我从来没有遇到过这种情况,在这个解决方案中失去可读性是值得的。当然,还要对所有选项进行基准测试,以确保认为实际上是更快。

John Machin Santi 14 年前

appendnew = newlist.append
try:
    while 1:
        appendnew(oldlist[index])
        index += 1
except IndexError:
    pass

或者,稍微不那么令人费解:

appendnew = newlist.append
for i in xrange(index, len(oldlist)):
    appendnew(oldlist[i])

John Machin Santi 14 年前

关于更好的基准测试的一些线索

测量开销并减去它。

将代码放在函数或方法中(模拟实际情况;有助于确保将变量作为全局变量不会产生恶劣影响)。

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)结果应该是进行调查的原因。

同时,将两对候选人的结果与合理的期望值进行比较——应调查野生变异;它们可能是由实验误差引起的。