在Python中尽可能高效地构建列表

Question

一般问题:假设你必须在一个循环内完成它,在效率方面是否有建立列表的优选风格？例如,这些选项之一是否优于构建整数列表:

mylist = []

for x, y in mystuff:
  # x, y are strings that need to be
  # added sequentially to list
  mylist.extend([int(x), int(y)])

与

for x, y in mystuff:
  mylist.append(int(x))
  mylist.append(int(y))

还是其他人？如果相关,可以使用scipy/numpy.谢谢.

Answer 1

如果你需要像这样进行微优化,那么了解最快速度的唯一方法就是测试.

简短的版本是:append速度快extend,而且Joran Beasley的建议itertools.chain.from_iterable比两者都要快 - 但只有当你用map列表理解取而代之时.

所以:

import itertools
import timeit

def makestuff(count):
    for i in range(count):
        yield (i, i)

def f_extend(mystuff):
    mylist = []
    for x, y in mystuff:
        mylist.extend([int(x), int(y)])
    return mylist

def f_append(mystuff):
    mylist = []
    for x, y in mystuff:
        mylist.append(int(x))
        mylist.append(int(y))
    return mylist

def f_chainmap(mystuff):
    return list(map(int, itertools.chain(*mystuff)))

def f_chaincomp(mystuff):
    return [int(x) for x in itertools.chain(*mystuff)]

def f_chainfrommap(mystuff):
    return list(map(int, itertools.chain.from_iterable(mystuff)))

def f_chainfromcomp(mystuff):
    return [int(x) for x in itertools.chain.from_iterable(mystuff)]

def f_reducecompcomp(mystuff):
    return [int(x) for x in reduce(operator.iadd, (list(y) for y in mystuff), [])]

def f_reducecompmap(mystuff):
    return [int(x) for x in reduce(operator.iadd, map(list, mystuff), [])]


try:
    import numpy
    def f_numpy(mystuff):
        return numpy.array(mystuff).flatten().tolist()
    def f_numpy2(mystuff):
        return numpy.array(list(mystuff)).flatten().tolist()
except:
    pass

if __name__ == '__main__':
  import sys
  main = sys.modules['__main__']
  count = int(sys.argv[1]) if len(sys.argv) > 1 else 10000
  for f in dir(main):
    if f.startswith('f_'):
      func = getattr(main, f)
      mystuff = makestuff(count)
      testfunc = lambda: func(mystuff)
      print('{}: {}'.format(f, timeit.timeit(testfunc, number=count)))

对于Python 2,我尝试了map没有额外的版本list,它稍微快一点,但仍然没有竞争力.对于Python 3,当然,这list是必要的.

这是我的时间:

$ python testlister.py 1000000
f_append: 1.34638285637
f_chaincomp: 2.12710499763
f_chainfromcomp: 1.20806899071
f_chainfrommap: 2.77231812477
f_chainmap: 3.67478609085
f_extend: 1.38338398933
f_numpy: 5.52979397774
f_numpy2: 7.5826470852
f_reducecompcomp: 2.17834687233
f_reducecompmap: 3.16517782211

$ python3 ./testlister.py 1000000
f_append: 0.9949617639649659
f_chaincomp: 2.0521950440015644
f_chainfromcomp: 0.9724521590862423
f_chainfrommap: 2.5558998831082135
f_chainmap: 3.5766013460233808
f_extend: 1.149905970087275
f_reducecompcomp: 2.2112889911513776
f_reducecompmap: 1.9317334480583668

我的python是Apple的股票Python 2.7.2,同时python3是64位的python.org 3.3.0,两者都是OS X 10.8.2,搭载的是2012年中期的MacBook Pro,配备2.2GHz i7和4GB.

如果你在POSIX平台上使用32位Python,我过去已经注意到在不太遥远的过去的某个地方,迭代器得到了一个优化,似乎加速了itertools64位构建中的许多东西,但在32位减速.所以,append在这种情况下你可能会发现胜利.(一如既往,在您真正关心优化的平台上进行测试.)

Ashwini Chaudhary链接到Flattening Python中的浅表列表,它进一步链接到有效查找python关联列表中的元素.我怀疑我的结果和他们的结果之间的区别是2.6.0和2.7.2/3.3.0之间的迭代器的改进,但我们明确使用2元素元素而不是更大元素的事实可能更重要.

此外,至少有一个答案声称reduce是最快的.reduce原帖中的实现都非常慢,但我能够提出更快的版本.他们仍然不具有竞争力append或chain.from_iterable,但他们在大致正确.

该f_numpy函数是heltonbiker的实现.既然mystuff是2D迭代器,这实际上只是生成一个包装迭代器的0D数组,所以所有numpy可以做的就是增加开销.我能够提出一个生成迭代器的一维数组的实现,但这甚至更慢,因为现在所有numpy可以做的是经常增加N次开销.我可以得到一个2D整数数组的唯一方法是list首先调用,因为f_numpy2它使事情变得更慢.(公平地说,将额外list的功能投入到其他功能中也会减慢它们的速度,但不会像使用它那样糟糕numpy.)

但是,我很可能在这里消隐,并且有一种合理的方式可以numpy在这里使用.当然,如果您可以确定顶层mystuff或每个元素mystuff是a list还是a tuple,您可以更好地编写一些内容 - 如果您可以重新设计应用程序,那么您首先要有一个2D numpy.array,而不是一般的序列序列那将是一个完全不同的故事.但是如果你只是对序列进行一般的2D迭代,那么对于这个用例似乎并不是很好.