Python - Какова относительная производительность различных методов для добавления элементов из многих списков?

Question

Существует несколько вопросов о stackoverflow о способах добавления всех элементов из многих списков. То, что я не вижу, является окончательным ответом об относительной производительности этих разных методов. Кроме того, иногда небольшое увеличение производительности происходит за счет некоторой удобочитаемости, поэтому было бы полезно знать несколько разных подходов.

Задача: Учитывая список, содержащий произвольное количество списков, каждое из которых содержит произвольное количество элементов, образуют единый список со всеми элементами. Сначала все элементы из первого списка, затем все элементы второго списка и т. Д. Это неглубокое добавление: если в списке есть элемент, который является списком, НЕ извлекайте эти отдельные элементы. Например.

append_all([ [11, 12, 13], [21, 22], [31, [320, 329], 33, 34] ]) 

=>

[11, 12, 13, 21, 22, 31, [320, 329], 33, 34] 

Answer 1

Вот тайминги для нескольких способов, чтобы добавить вместе несколько списков.

Показаны с самых быстрых и медленных.

Python 2.7 (CPython - работает внутри Autodesk Maya 2014), Windows 7 64-бит, Intel Core i7-37770K @ 3,5 ГГц.

import timeit 
def p_timeit_min(msg, expr_str, number, setup): 
    times = timeit.repeat(expr_str, number=number, setup=setup, repeat=3) 
    print('{0:18} => {1:6.3f}'.format(msg, min(times))) 

n = 1000 
timeit.repeat('1+1', number=10000) # "dummy" -- I'm in an environment where the first timeit call is erratic in performance. 
setup_0 = '; import operator; L1 = list(range(n)); LL = [[10 * x + v for v in L1] for x in range(n)]' 
print 
p_timeit_min('map+extend 100', 'all = []; map(all.extend, LL)', number=n, setup='n = 100'+setup_0) 
p_timeit_min('for+extend 100', """ 
all = [] 
for L in LL: 
    all.extend(L) 
""", number=n, setup='n = 100'+setup_0) 
p_timeit_min('extend 100', 'all = []; [all.extend(L) for L in LL]', number=n, setup='n = 100'+setup_0) 
# reduce with [] initializer, to avoid need to wrap each L in list(). 
p_timeit_min('reduce+iadd 100 []', 'all = reduce(operator.iadd, LL, [])', number=n, setup='n = 100'+setup_0) 
p_timeit_min('filter extend 100', 'all = []; filter(lambda x: False, iter(all.extend(L) for L in LL))', number=n, setup='n = 100'+setup_0) 
# WARNING: If remove "list()" wrapper around "list_", since this version isn't supplying a [] to accumulate the results, iadd will MODIFY the first element of LL, which may not be desired. 
p_timeit_min('reduce+iadd 100 list()', 'all = reduce(operator.iadd, (list(list_) for list_ in LL))', number=n, setup='n = 100'+setup_0) 
p_timeit_min('chain 100', 'all = list(itertools.chain(*LL))', number=n, setup='n = 100'+setup_0) 
p_timeit_min('comprehension 100', 'all = [x for list_ in LL for x in list_]', number=n, setup='n = 100'+setup_0) 
p_timeit_min('nested for append 100', 
""" 
all = [] 
for L in LL: 
    for x in L: 
     all.append(L) 
""", number=n, setup='n = 100'+setup_0) 
p_timeit_min('sum 100', 'all = sum(LL, [])', number=n, setup='n = 100'+setup_0) 
print 
p_timeit_min('map+extend 200', 'all = []; map(all.extend, LL)', number=n, setup='n = 200'+setup_0) 
p_timeit_min('for+extend 200', """ 
all = [] 
for L in LL: 
    all.extend(L) 
""", number=n, setup='n = 200'+setup_0) 
p_timeit_min('extend 200', 'all = []; [all.extend(L) for L in LL]', number=n, setup='n = 200'+setup_0) 
p_timeit_min('reduce+iadd 200 []', 'all = reduce(operator.iadd, LL, [])', number=n, setup='n = 200'+setup_0) 
p_timeit_min('filter extend 200', 'all = []; filter(lambda x: False, iter(all.extend(L) for L in LL))', number=n, setup='n = 200'+setup_0) 
p_timeit_min('reduce+iadd 200 list()', 'all = reduce(operator.iadd, (list(list_) for list_ in LL))', number=n, setup='n = 200'+setup_0) 
p_timeit_min('chain 200', 'all = list(itertools.chain(*LL))', number=n, setup='n = 200'+setup_0) 
p_timeit_min('comprehension 200', 'all = [x for list_ in LL for x in list_]', number=n, setup='n = 200'+setup_0) 
p_timeit_min('nested for append 200', """ 
all = [] 
for L in LL: 
    for x in L: 
     all.append(L) 
""", number=n, setup='n = 200'+setup_0) 
p_timeit_min('sum 200', 'all = sum(LL, [])', number=n, setup='n = 200'+setup_0) 
print 

Выход:

map+extend 100  => 0.062 
for+extend 100  => 0.064 ** within margin of error of first place, but slower on average 
extend 100   => 0.066 
reduce+iadd 100 [] => 0.063 ** see "200" case for reason this isn't placed higher in list. 
filter extend 100 => 0.078 
reduce+iadd 100 list=> 0.105 ** ignore this - use the better "reduce" above. 
chain 100   => 0.127 
comprehension 100 => 0.250 
nested for append 100=>0.672 
sum 100   => 1.424 

Эти времена ~ 4x больше, для O (N) алгоритмы порядка -

"200" случай 200 х 200, так что 4x, как многие общие элементы, как Случай «100».

НАБЛЮДЕНИЕ: 5 лучших вариантов делают значительно лучше, чем O (n) - примерно в 3 раза больше для 4-х элементов. Это потому, что каждый список длиннее; количество подсписков увеличилось в 2 раза:

map+extend 200  => 0.187 
for+extend 200  => 0.190 
extend 200   => 0.194 
reduce+iadd 200 [] => 0.204 
filter extend 200 => 0.217 
reduce+iadd 200 list=> 0.311 ** ignore this - use the better "reduce" above. 
chain 200   => 0.426 
comprehension 200 => 0.931 
nested for append 200=>2.676 
sum 200   => 13.432 

АНАЛИЗ: Верхние четыре решения не являются существенно различными, если каждый список имеет много элементов.

Вложенное понимание списка занимает 4 раза больше (как лучшее решение). С другой стороны, это все равно O (n) для всех # элементов. Для многих ситуаций это 4 раза малое значение времени, которое не имеет значения.

ЗАКЛЮЧЕНИЕ: если это критический фактор для вашей ситуации, используйте list.extend с любыми способами зацикливания или reduce(operator.iadd, LL, []). Варианты выбора: itertools.chain по цене 2x, или [ .. for .. for .. ] (вложенные списки) при стоимости 4 раза.

CAVEAT: Это один тест на одной машине на одной реализации Python 2.7.

Предполагается, что у вас есть списки &, вам нужен результат в виде списка; если у вас есть/нужны последовательности/генераторы/итераторы, которые могут изменить баланс (возможно, в пользу itertools.chain)?

TODO: Тест со многими краткими списками.