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

Программирование для смартфонов

17:32 07-07-2009

DimonVideo

Статья не моя, нашел на хабре, показалась занятной. Источник, коменты там тоже занятные.
Зашел тут у нас в офисе разговор как наиболее «красиво» и быстро склеить список списков в Питоне. Действительно как?
Даже такую казалось бы тривиальную задачу можно решить несколькими способами, существенно отличающимися по скорости и выразительности.
ВАРИАНТ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)]  \n gc.enable()'
def  test (variants, initstr,n= 100 ):
print "Test repeats n =" ,n, " times \n INITSTR:" ,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 ]

Чат в Telegram