python - 在 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，我尝试了没有额外 list 的 map 版本，速度稍快，但仍然没有竞争力。当然，对于 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 是 python.org 3.3.0，都是 64 位的，都在 OS X 10.8.2 上，配备 2.2GHz i7 和 4GB 的 2012 年中期 MacBook Pro。

如果您在 POSIX 平台上使用 32 位 Python，我注意到在不久前的某个地方，迭代器得到了优化，似乎在 itertools 在 64 位构建中，但在 32 位构建中减慢了它们的速度。因此，您可能会发现 append 在这种情况下获胜。 (一如既往，在您真正关心优化的平台上进行测试。)

Ashwini Chaudhary 链接到 Flattening a shallow list in Python ，进一步链接到finding elements in python association lists efficiently .我怀疑我的结果和他们的结果之间的部分差异是 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 倍的开销。获得二维整数数组的唯一方法是首先调用 list，如 f_numpy2 中那样，这会使事情变得更慢。 (公平地说，将额外的 list 放入其他函数中也会减慢它们的速度，但远不如 numpy 糟糕。)

不过，很有可能我在这里留空了，这里有一个合理的方法来使用numpy。当然，如果您可以确定顶级 mystuff 或 mystuff 中的每个元素都是 list 或 tuple，你可以写出更好的东西——如果你可以重新设计你的应用程序，那么你首先有一个 2D numpy.array，而不是一般的序列序列，那将是一个完全不同的故事。但是，如果您只有序列的一般 2D 迭代，它似乎不太适合此用例。