MyTetra Share
Делитесь знаниями!
6 способов слияния списка списков
Время создания: 31.08.2017 21:01
Текстовые метки: code
Раздел: Python - Types data - Списки
Запись: xintrea/mytetra_db_mcold/master/base/1504202479ykj5aeyw7f/text.html на raw.githubusercontent.com

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]
# Результат:
[
72445678]


Так же в этом разделе:
 
MyTetra Share v.0.58
Яндекс индекс цитирования