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

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

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

    ВАРИАНТ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]


    UPD: Ответ habrahabr.ru/blogs/python/63539/#comment_1764419

    UPD2:
    ВАРИАНТ 6Б (от анонимного комментатора в ЖЖ)
    import operator
    listmerge6b=lambda s: reduce(operator.iadd, s, [])
    Метки:
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 74
    • +11
      Вариант 3 не только самый быстрый, но и самый понятный и простой.

      Лямбда-выражения это, конечно, типа круто, но смысл использования в данном конкретном случае под вопросом. Экономия строк?
      • –1
        Разминка для мозгов.

        К тому же я предлагаю вам решить задачку в конце, способом аналогичным Варинту 3. И мы сравним с моим, аналогичным Варианту 6.
        • +3
          Разминка для мозгов людям, которым понадобится разбираться в вашем коде?
          • –1
            Да, вы же тоже разобрались ..)
        • +2
          Судя по всему попытка ностальгия за перл-прошлым у автора :)
          • +1
            Скорее это ностальгия за Хаскель-будущим автора)
            • +2
              как люди ограничены…
              • +1
                Писать на perl можно на любом языке программирования
                • 0
                  Можно, но тут это не в тему. Чистые функции повышают читабельность и понятность кода. Но у них естественно есть некий порог вхождения, до которого ничего не понятно.

                  Если вас смущает, что в программировании есть вещи сложнее мануала к PHP, то кто виноват?
                  • +1
                    меня не смущают лямбды, просто при отладке чудого кода, допустим при поиске какойнибудь трудноуловимой ошибки мне было бы приятнее встретить 3тий вариант, а не 5тый.
            • 0
              Для вложенных списков, самый очевидный вариант с рекурсией:
              def listmerge(lst):
                  res = []
                  for el in lst:
                      res += listmerge(el) if isinstance(el, list) else [el]
                  return res
              • +2
                Вариант 7:
                import itertools
                listmerge = lambda lst: list(itertools.chain(*(el for el in lst))) 
                • +2
                  Как-то у вас сложно всё вышло.

                  import itertools
                  listmerge = lambda lst: list(itertools.chain(*lst))
                  • 0
                    Да, действительно, что-то я перемудрил :)
                    • 0
                      А если добавить волшебную звёздочку — можно будет передавать сколько угодно параметров.

                      from itertools import chain
                      listmerge = lambda *lst: list(chain(*lst))

                      Я вот только не знаю хорошо это или плохо.
                      • 0
                        Это никак. Функция перестаёт делать то, что требуется в задаче.
                        • 0
                          >>> l1 = [1,2,3]
                          >>> l2 = [4,5,6]
                          >>> l3 = [7,8,9]
                          >>> listmerge(l1, l2, l3)
                          [1, 2, 3, 4, 5, 6, 7, 8, 9]

                          Ничего функция не перестаёт. Прикол в том, что можно передавать сколько угодно списков, а на выходе получить один. Список списков можно передать так: listmerge(*lstlst)

                          Но вот, судя по этому ответу, код перестаёт быть понятным всем.
                          • 0
                            Я прекрасно понимаю как работает звёздочка.

                            Функция не выполняет то, что задано в задаче. В задаче сказано: склеить список списков. Ваша функция этого не делает.
                            • 0
                              >>> listmerge(*[[1,2], [3,4], [5,6,7], [8]])
                              [1, 2, 3, 4, 5, 6, 7, 8, 9]

                              почему не делает?
                              • 0
                                Вот конкретно это можно написать проще:

                                import itertools
                                listmerge = lambda lst: list(itertools.chain(*lst))

                                listmerge([[1,2], [3,4]])

                                а не вводить лишнюю звёздочку, чтобы потом от неё избавляться.
                      • 0
                        Подозреваю, что по скорости это будет на уровне с List comprehensions вариантом (№5)
                    • +1
                      По-простому

                      def merge(lst, res=[]):
                        for el in lst:
                          merge(el) if isinstance(el, list) else res.append(el)
                        return res

                      С извратом ;)

                      merge = lambda lst: reduce(lambda a, b: a.extend(merge(b)) or a if isinstance(b, list) else a.append(b) or a, lst, [])
                      • 0
                        Только вот хотел узнать — не нашел — переменных а-ля static в php в чистом виде нельзя создавать в питоньих функциях? Ну кроме «моего» способа через значение по умолчанию.
                        • 0
                          Нельзя. Способ через связывание с анонимным изменяемым объектов вполне себе нормальный и питонячий.
                        • 0
                          Ага, хотя я бы не назвал второй вариант большим извратом, тк рекурсивные алгоритмы в форме лямбд записываются более элегантно. Вот чисто итеративный вариант будет извратом.

                          единственный комментарий: можно убрать «or» из цикла:
                          mergeto = lambda dst,lst: reduce(lambda a,b: a.extend(b) if type(b) is list else a.append(b), lst, dst) or dst
                          merge = lambda lst: mergeto([], lst)
                          • 0
                            опечатался
                            mergeto = lambda dst,lst: reduce(lambda none,b: dst.extend(b) if type(b) is list else dst.append(b), lst, dst) or dst
                            merge = lambda lst: mergeto([], lst)
                            • 0
                              но это уже 2 строчки :)
                              • 0
                                Вторую можно выкинуть) Или обернуть первую еще одной лямбдой. Все из-за того, что питоновские in-place методы возвращают None вместо объекта…
                          • 0
                            mutables в определении функции — зло
                            • 0
                              Еслм быть точнее, то они зло в определении умолчальных аргументов.
                            • 0
                              А вот подобную штуку вряд ли удастся раскрыть:
                              a = [1]
                              a.append(a)
                            • 0
                              Чисто из любопытства: в питоне нет рубишного .flatten?
                              • 0
                                Вы расскажите что это.
                                • 0
                                  В ruby:

                                  a = [1, [2,3], [4,5]]
                                  a.flatten
                                  p a

                                  В результате: [1, 2, 3, 4, 5]

                                  • 0
                                    В Python ближайший эквивалент — chain из пакета itertools:

                                    from itertools import chain
                                    a = [1, [2,3], [4,5]]

                                    a = list(chain(*a))

                                    print a

                                    Поскольку chain вернёт итератор, мы из него делаем список, передав итератор в качестве аргумента конструктора list.
                                    • 0
                                      Fandorin забыл восклицательный знак после flatten, иначе вызывается метод, который результат не сохраняет в массив, и пропадает он по концу вычисления.

                                      bolk, кстати, если интересно, стандартный метод flatten в руби 1.9 имеет еще и параметр глубины, на какую «уплощать»:

                                      irb(main):001:0> [1,[2,3],[4,[5,6]]]
                                      => [1, [2, 3], [4, [5, 6]]]
                                      irb(main):002:0> [1,[2,3],[4,[5,6]]].flatten
                                      => [1, 2, 3, 4, 5, 6]
                                      irb(main):003:0> [1,[2,3],[4,[5,6]]].flatten 0
                                      => [1, [2, 3], [4, [5, 6]]]
                                      irb(main):004:0> [1,[2,3],[4,[5,6]]].flatten 1
                                      => [1, 2, 3, 4, [5, 6]]
                                      irb(main):005:0> [1,[2,3],[4,[5,6]]].flatten 2
                                      => [1, 2, 3, 4, 5, 6]
                                      • 0
                                        Забавно :) В Python это придётся делать рекурсией.
                                        • 0
                                          Забавно :) В Python это придётся делать рекурсией.
                                • –5
                                  ruby: a = [1,2,3]; b = [3,4,5]; c = a+b # => [1,2,3,3,4,5]
                                  • +1
                                    python: a=[1,2,3]; b = [3,4,5]; c=a+b # => [1,2,3,4,5]

                                    задача из a=[[1,2,3], [3,4,5], [6]] сделать [1,2,3,4,5,6]
                                    • 0
                                      Фигня, ща разрулим.
                                      a=[[1,2,3], [3,4,5], [6]]; a.flatten #=> [1,2,3,4,5,6]
                                      • 0
                                        В Python только немного сложнее получается (chain импортируется из itertools):

                                        a = list(chain(*a))
                                    • 0
                                      python: a = [1,2,3]; b = [3,4,5]; c = a+b # => [1,2,3,3,4,5]

                                      ваш код делает явно не то что подразумевалось автором топика.
                                    • +1
                                      >>> a = [[1,2,3], [4,5,6], [7,8,9]]
                                      >>> l = [x for lst in a for x in lst]
                                      >>> l
                                      [1, 2, 3, 4, 5, 6, 7, 8, 9]

                                      или я неправильно понял что надо сделать?
                                      • 0
                                        Нет, всё правильно.
                                        • +1
                                          а, пардон. это и есть способ 5 =))
                                        • +1
                                          На лиспе это делать надо, на лиспе =)
                                          • 0
                                            Вот конкретно это нафиг делать не надо ни на чем: ) То есть если это и есть собственно цель.
                                            Ну и хотя бы по примеру любителя ruby написали бы мега шустрый пример что ли.
                                            • 0
                                              (defun listmerge (list)
                                              (if (null list)
                                              nil
                                              (append (car list) (listmerge (cdr list)))
                                              )
                                              )

                                              (listmerge '((1 2) (3) (5) (4 6)))
                                              (1 2 3 5 4 6)
                                              • 0
                                                Вот ещё на хаскелле, там точно проще.
                                                merge = foldr [] (++)

                                                main = print ( merge [ [1, 2], [3, 4], [5, 6] ] )
                                                >[1,2,3,4,5,6]
                                                • 0
                                                  в чем разница? Кроме того Хаскелль статически типизированный язык и для списков произвольной вложенности надо будет изобретать тип наподобие деревьев, и это будет уже далеко не 1 строчка.
                                            • +2
                                              Решение задачки:

                                              def iter_flatten(iterable):
                                                it = iter(iterable)
                                                for e in it:
                                                  if isinstance(e, (list, tuple)):
                                                    for f in iter_flatten(e):
                                                      yield f
                                                  else:
                                                    yield e
                                              


                                              Вернется конечно генератор, а не список, но так даже практичнее.

                                              А вот в руби насколько я помню есть нативный метод для этой задачи.
                                              • 0
                                                Я бы поостерегся возвращать генератор, зависящий от мутируемых объектов. Можно получить ерунду если программа продолжит изменять данные.
                                                • 0
                                                  Для чего вводится переменная it?
                                                • +1
                                                  Code Golf? :)
                                                  • +5
                                                    На питоне быстрее всего будет с lambda, map или filter
                                                    Оффтоп. Когда я начал изучать Erlang, я был поражен, как просто и быстро там делаются подобные вещи. Вот сейчас, мне стало интересно, как быстро эрланг смержит большие списки. Накидал небольшой бенч

                                                    L1 = [random:uniform(1000) || N <- lists:seq(1, 1000000)].
                                                    

                                                    Это список из миллиона чисел < 1000
                                                    L2, L3, L4 генерируются подобным образом(да, ощутимо по времени)

                                                    timer:tc(lists, flatten, [L1, [L2, L3], L4]).
                                                    >{250000,
                                                     [93,444,724,946,502,312,598,916,667,478,597,143,210,698,160,
                                                      559,215,458,422,6,563,476,401,310,59,579,990|...]}
                                                    

                                                    4 списка по 1000000 элементов сливались четверть секунды на среднем ноуте. Я бы побоялся запустить такое на питоне или руби, хотя сам питоновод. Жду unladen swallow.
                                                    • 0
                                                      0.15 сек. (Отсутствие рандомных чисел сути не меняет)

                                                      Код list.py:

                                                      def listmerge(lstlst):
                                                          all=[]
                                                          for lst in lstlst:
                                                            all.extend(lst)
                                                          return all	
                                                      
                                                      list_over_9000 = listmerge([list(xrange(1000))*1000, list(xrange(1000))*1000, list(xrange(1000))*1000, list(xrange(1000))*1000])
                                                      
                                                      print "len = %s" % len(list_over_9000)
                                                      


                                                      Что сказал профайлер:

                                                      C:\Users\user\Desktop\pff>python -m cProfile list.py
                                                      len = 4000000
                                                               10 function calls in 0.155 CPU seconds
                                                      
                                                         Ordered by: standard name
                                                      
                                                         ncalls  tottime  percall  cumtime  percall filename:lineno(function)
                                                              1    0.000    0.000    0.155    0.155 <string>:1(<module>)
                                                              1    0.081    0.081    0.155    0.155 list.py:1(<module>)
                                                              1    0.000    0.000    0.073    0.073 list.py:1(listmerge)
                                                              1    0.001    0.001    0.155    0.155 {execfile}
                                                              1    0.000    0.000    0.000    0.000 {len}
                                                              1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
                                                              4    0.073    0.018    0.073    0.018 {method 'extend' of 'list' objects}
                                                      


                                                      Я бы еще написал пару слов про disco (реализация MapReduce на языке Erlang для параллельных вычислений на больших наборах данных с интерфейсом для Питона), но похоже уже в другой раз, ибо очень хочется спать.
                                                      • +1
                                                        Извините, но Ваш пример некорректен. Во-первых, ваш listmerge не мержит вложенные списки; во-вторых, Вы сгенерировали кучу мусора: 4 списка, в каждом по 1000 нормальных элементов из 1000000. Остальные 999000 элементов — 999 копий первой тысячи

                                                        >>>a = list(xrange(1000))*1000
                                                        >>>a[999] is a[1999]
                                                        True
                                                        

                                                        или
                                                        >>>a = list(xrange(1000))*1000
                                                        >>>id(a[999]) == id(a[1999) == id(2999) == ...
                                                        True
                                                        
                                                        • 0
                                                          упс, опечатка последнем примере, но смысл, я думаю, понятен
                                                          • 0
                                                            Да это правда — объекты идентичны. Но для списков с числами до 1 млн ситуация меняется не критично: 0.291 s

                                                            def test(l1, l2, l3, l4):	
                                                            	list_over_9000 = listmerge([l1, l2, l3, l4])
                                                            
                                                            	print "len = %s" % len(list_over_9000)
                                                            	
                                                            l1, l2, l3, l4 = list(xrange(1000000)), list(xrange(1000000)), list(xrange(1000000)), list(xrange(1000000))
                                                            test(l1, l2, l3, l4)
                                                            
                                                            • 0
                                                              «В два раза» это «не критично»?
                                                              • 0
                                                                Во-первых они сравнивают на разных машинах, так что это ничего не значит. Во-вторых зависит от задачи, если список из 10 элементов, то не критично)
                                                                • 0
                                                                  Я говорил про разницу в двух вышеуказанных примерах хабраюзера habrcut.
                                                            • 0
                                                              Что касается не вложенности списков тут пример с функцией варианта №7, время чуть больше чем показал Erlang — 0.342 сек.
                                                      • 0
                                                        ну это ж не перл чтобы однострочки тут выписывать, третий самый быстрый и самый простой, в чем проблема.
                                                        • 0
                                                          всё равно, руки за «ll» на до отрывать!
                                                          • +1
                                                            Если оно встречается два раза в короткой строке, которую можно охватить взглядом, почему нет?)
                                                            Тем более, что с нормальными шрифтами (какие должны использоваться в программировании) все выглядит не так ужасно.
                                                            • –1
                                                              вы идиот?

                                                              потому что так делать нельзя! есть правила хорошего тона в обзывании переменных. нарушать их нельзя, потому что их нельзя нарушать никогда!
                                                              • 0
                                                                Фанатичное следование Code Conventions полезный скилл для рядового кодера, с чем вас и поздравляю.
                                                                • –1
                                                                  а отступление от них в публичных публикациях — явный признак неуважения к аудитории и тяги к самолюбованию, с чем поздравляю вас

                                                                  достаточно было использовать общепринятые foo, bar, etc, чтобы избежать обвинений в ламерстве и отвращения со стороны людей, которые видят каждый день тысячи строк хорошего кода.
                                                                  • +1
                                                                    Задачи «избежать обвинений в ламерстве» от аудитории, которой не понятна строка «lambda ll: sum(ll, [])» у меня не было и никогда не будет. Рекомендую впредь мои посты пропускать, заменяя просмотром «тысяч строк хорошего кода». Тема закрыта.
                                                                    • –3
                                                                      вообще я ваши посты и не собирался читать, тема была интересна, а внутри обычное говно оказалось

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