6 способов слияния списка списков

Python*

Зашел тут у нас в офисе разговор как наиболее «красиво» и быстро склеить список списков в Питоне. Действительно как?

Даже такую казалось бы тривиальную задачу можно решить несколькими способами, существенно отличающимися по скорости и выразительности.

ВАРИАНТ1
Все знают, что элементы списка можно перебирать в цикле и, то что можно добавлять элементы в конец. Это приводит нас к первому варианту решения:

def listmerge1(lstlst):
    all=[]
    for lst in lstlst:
        for el in lst:
            all.append(el)
    return all

Мало того, что функция растянулось аж на 6 строк, так вдобавок она еще и не эффективная.
Попробуем её улучшить в обоих смыслах: скорости и красоты («pythonic way»).

ВАРИАНТ2
Тут мы вспоминаем, что в Питоне есть оператор "+" для строк и получаем:

def listmerge2(lstlst):
    all=[]
    for lst in lstlst:
      all=all+lst
    return all

Это самая медленная реализация. Прокол в том что в таком виде оператор "+" в каждом шаге создает новый объект-список, который на следующем шаге выкидывается и т.д.

ВАРИАНТ3
Исправить легко, надо заменить "+" на форму которая не создает новый список, а добавляет к старому. Это оператор "+=", но я предпочитаю писать в явном виде метод «extend».

Так мы получили самый быстрый вариант, но не самый короткий.

def listmerge3(lstlst):
    all=[]
    for lst in lstlst:
      all.extend(lst)
    return all

Все последующие решения я буду писать через лямбда-выражения, тк они состоят из одного выражения. Имя аргумента сокращено до ll, тк в коде в одну строку это не уменьшает читабельности.

# через анонимную функцию
 listmerge=lambda ll : simple-statement
# эквивалентно
def listmerge(ll):
  return simple-statement

ВАРИАНТ4
Используя встроенные функции работы со списками, можно переписать вариант2 в стиле функционального программирования:

listmerge4a=lambda ll: reduce(lambda a,b: a+b, ll, [])
listmerge4b=lambda ll: sum(ll, [])

Он чуть чуть быстрее, но все еще тормозной по той же причине, что и его итеративный родственник. Здесь «lambda a,b: a+b» — анонимная функция двух аргументов, которая просто возвращает их сумму. Вариант B это просто шорткат, встроенный в Питон для удобста вычисления суммы элементов. Этот вариант самый короткий.

Лично меня не устраивает ни самый короткий (скорость), ни самый быстрый (красота). Попробуем найти компромисс.

ВАРИАНТ5
С помощью списковых выражений:

listmerge5=lambda ll: [el for lst in ll for el in lst]

Не сильно длиннее предыдущего, но радикально быстрее. Вариант несомненно красив, хотя вложенные списковые выражения не всегда понятны с первого взгляда.

ВАРИАНТ6
А что если попробовать переписать самый быстрый вариант в функцональном стиле? Легко:

listmerge6=lambda s: reduce(lambda d,el: d.extend(el) or d, s, [])

Заметьте "d.extend(el) or d" нам пришлось добавить оператор "or" тк метод extend возвращает None. По скорости он практически не уступает самому быстрому методу №3 (разница в скорости буквально единицы процентов и на мой взгляд не существенна).

По моему мнению "выбор редакции" стоит присудить варианту №6)

Для замеров скорости маленьких кусков кода в Питоне есть библиотека timeit. Вот пример кода, тестирующего варианты 3, 5 и 6 (самые быстрые и красивые).

import timeit
 
variants = {
 'Reduce' :
 'listmerge=lambda s: reduce(lambda d,el: d.extend(el) or d, s, [])',
 'Iterate' :
"""
def listmerge(lstlst):
  all=[]
  for lst in lstlst:
    all.extend(lst)
  return all
""",
  'Comprehension' :
  'listmerge=lambda ll: [x for lst in ll for x in lst]',
}
 
initstr='lstlst=[range(i) for i in range(1000)]\ngc.enable()'
 
def test(variants, initstr,n=100):
  print "Test repeats n =",n," times\nINITSTR:",initstr,"\n\n"
  for k,v in variants.iteritems():
    print k, " - ", timeit.Timer("listmerge(lstlst)", initstr+"\n"+v).timeit(n)
  print
 
test(variants,initstr,100)

Пример запуска теста времени. Видно что разница скорости между итеративным и функциональным вариантом исчезающе мала. Вариант на списковых выражениях заметно медленней (тут на погрешности не спишешь), но и размер наших списков огромен, для некритичных к скорости приложений он тоже имеет право на жизнь. 
Test repeats n = 100 times
INITSTR: lstlst=[range(i) for i in range(1000)]
gc.enable()

Iterate - 1.56133103371
Reduce - 1.57647109032
Comprehension - 7.5749669075


ДОМАШНЕЕ ЗАДАНИЕ
Предлагаю решить/обсудить более сложную задачу развертывание вложенных списков в линейный.
Пример: 

# Исходный список:
[7,[[[[2]]],[[[]],[4]],[4,5,[6,7]]],8]
# Результат:
[7, 2, 4, 4, 5, 6, 7, 8]