Питання Виготовлення плоского списку з списку списків у Python


Цікаво, чи існує ярлик для створення простого списку зі списку списків у Python.

Я можу зробити це за цикл, але, можливо, є якийсь прохолодний "один-вкладиш"? Я спробував це зменшити, але я отримую помилку.

Код

l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
reduce(lambda x, y: x.extend(y), l)

Повідомлення про помилку

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'extend'

2083
2018-06-04 20:30


походження


Тут відбувається поглиблене обговорення цього питання: rightfootin.blogspot.com/2006/09/more-on-python-flatten.html, обговорюючи кілька способів вирівнювання довільно вкладеного списку списків. Цікаво читати! - RichieHindle
Деякі інші відповіді є кращими, але причина вашого невдалого полягає в тому, що метод 'extend' завжди повертає None. Для списку з довжиною 2 він буде працювати, але повернути Немає. Для довшого списку він споживає перші 2 аргументи, які повертають ні. Потім він продовжується з None.extend (<third arg>), що викликає цю помилку - mehtunguh
@ shawn-chin solution тут більше pythonic, але якщо вам потрібно зберегти тип послідовності, скажімо, ви маєте набір кортежів, а не список списків, тоді ви повинні використовувати зменшення (operator.concat, tuple_of_tuples). Використання operator.concat з кортежів, здається, виконує швидше, ніж chain.from_iterables зі списком. - Meitham
numpy.array ([[1], [2]]). flatten (). tolist (), який видаляє внутрішню структуру і повертає список [1,2] - user5920660
Зараз підтримується mpu: import mpu; mpu.datastructures.flatten([1, [2, 3], [4, [5, 6]]]) дає [1, 2, 3, 4, 5, 6] - Martin Thoma


Відповіді:


flat_list = [item for sublist in l for item in sublist]

що означає:

for sublist in l:
    for item in sublist:
        flat_list.append(item)

швидше, ніж ярлики, опубліковані до цього часу. (l це список, який вирівняється.)

Ось відповідна функція:

flatten = lambda l: [item for sublist in l for item in sublist]

Для доказів, як завжди, ви можете скористатись timeit модуль у стандартній бібліотеці:

$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' '[item for sublist in l for item in sublist]'
10000 loops, best of 3: 143 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 3: 969 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 3: 1.1 msec per loop

Пояснення: ярлики на основі + (включаючи передбачуване використання в sum), є необхідністю, O(L**2) коли є підсписками L - оскільки список проміжних результатів продовжує зростати, на кожному кроці виділяється об'єкт нового проміжного результату, а всі елементи у попередньому проміжному результаті повинні бути скопійовані (а також кілька нових доданих в кінці). Отже (для простоти і без фактичної втрати загальності) кажуть, що у вас є L підрозділів I елементів кожен: перші I пункти копіюються вперед і назад L-1 разів, другий I пунктів L-2 разів і так далі; загальна кількість копій - 1 раз сума x для x від 1 до L виключена, т. е. I * (L**2)/2.

Сприйняття списку просто генерує один список один раз і копіює кожну позицію (від свого початкового місця проживання до списку результатів) також рівно один раз.


3001
2018-06-04 20:37



Я спробував тест з тими ж даними, використовуючи itertools.chain.from_iterable : $ python -mtimeit -s'from itertools import chain; l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'list(chain.from_iterable(l))'. Він працює трохи більше ніж удвічі швидше, ніж уявлення про вкладені списки, що є найшвидшим з альтернатив, показаних тут. - intuited
Я знайшов синтаксис важко зрозуміти, поки не зрозумів, що ви можете подумати про це точно так само, як вкладено для циклів. для субтитрів в l: для елемента в підпозиторій: прибутковий елемент - Rob Crowell
@БорисЧервенков: Зауважте, що я загорнув дзвінок list() реалізувати ітератор у список. - intuited
[лист для дерева в лісі для листування в дереві] може бути простіше зрозуміти і застосувати. - John Mee
@ Джоел, насправді сьогодні list(itertools.chain.from_iterable(l)) найкраще - як помітили в інших коментарях і відповідь Шона. - Alex Martelli


Ви можете використовувати itertools.chain():

>>> import itertools
>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> merged = list(itertools.chain(*list2d))

або, на Python> = 2.6, використовуйте itertools.chain.from_iterable() який не вимагає розпакування списку:

>>> import itertools
>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> merged = list(itertools.chain.from_iterable(list2d))

Цей підхід, мабуть, більш читабельний, ніж [item for sublist in l for item in sublist] і, здається, також швидше:

[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools' 'list(itertools.chain.from_iterable(l))'
10000 loops, best of 3: 24.2 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' '[item for sublist in l for item in sublist]'
10000 loops, best of 3: 45.2 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 3: 488 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 3: 522 usec per loop
[me@home]$ python --version
Python 2.7.3

1083
2018-06-04 21:06



@ShawnChin До речі, виріб, який ви мали, відповідаючи на це питання, моя поточна робоча станція наполовину так швидко, і це вже 4 роки. - Manuel Gutierrez
@alexandre див docs.python.org/2/tutorial/... - Shawn Chin
The * це складна річ, яка робить chain менш простий, ніж у розумінні списку. Ви повинні знати, що ланцюжок приєднується лише до повторюваних параметрів, переданих як параметри, а * змушує список верхнього рівня розширюватися в параметри, тому chain об'єднує разом усі ці ітерації, але не спускається далі. Я думаю, що це робить розуміння більш читабельним, ніж використання ланцюга у цьому випадку. - Tim Dierks
@TimDierks: Я не впевнений, що "це вимагає від вас розуміння синтаксису Python" є аргументом проти використання даної техніки в Python. Звичайно, складне використання може плутати, але оператор "splat" взагалі корисний у багатьох випадках, і це не використовує його особливо незрозумілим чином; відкидаючи всі мовні функції, які не завжди очевидні для початківців, означає, що ви зав'язуєте одну руку за спиною. Можна також викинути перелік сприймань, поки ви перебуваєте на ньому; користувачі з інших фонів знайдуть a forпетлі, що неодноразово appendце більш очевидно. - ShadowRanger
а як на рахунок ['abcde_', ['_abcde', ['e_abcd', ['de_abc', ['cde_ab', ['bcde_a']]]]]] - Aymon Fournier


Зауваження автора: Це неефективно. Але весело, тому що монади чудові. Це не підходить для виробничого коду Python.

>>> sum(l, [])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Це просто сума елементів iterable, що передаються в першому аргументі, розглядаючи другий аргумент як початкове значення суми (якщо не вказано) 0 використовується замість цього, і цей випадок дасть вам помилку).

Оскільки ви підсумовуєте вкладені списки, ви дійсно отримуєте [1,3]+[2,4] як результат sum([[1,3],[2,4]],[]), що дорівнює [1,3,2,4].

Зверніть увагу, що працює тільки в списках списків. Для списків списків списків вам знадобиться інше рішення.


638
2018-06-04 20:35



це досить акуратно і розумно, але я б не використовував це, тому що це заплутано читати. - andrewrk
Це шармільєв - алгоритм живописця joelonsoftware.com/articles/fog0000000319.html - непотрібно неефективно, а також непотрібно потворно. - Mike Graham
Додана операція над списками складається з a Monoid, що є одним з найбільш зручних абстракцій для мислення a + операція в загальному сенсі (не обмежуючись лише номерами). Тому ця відповідь заслуговує на +1 від мене (правильне) трактування списків як моноїд. Вистава стосується, хоча ... - ulidtko
@andrewrk Ну, деякі люди думають, що це найчистіший спосіб зробити це: youtube.com/watch?v=IOiZatlZtGU ті, хто не зрозуміє, чому це круто, просто потрібно почекати кілька десятиліть, поки всі це не робитимуть: давайте використовувати мови програмування (і абстракції), які були виявлені та не винайдені, Monoid виявляється. - jhegedus
це дуже неефективно через квадратичний аспект суми. - Jean-François Fabre


Я протестував найбільш запропоновані рішення з perfplot (тваринний проект мій, по суті обгортка навколо timeit) і знайшли

list(itertools.chain.from_iterable(a))

бути найшвидшим рішенням (якщо об'єднано більше 10 списків).

enter image description here


Код для відтворення сюжету:

import functools
import itertools
import numpy
import operator
import perfplot


def forfor(a):
    return [item for sublist in a for item in sublist]


def sum_brackets(a):
    return sum(a, [])


def functools_reduce(a):
    return functools.reduce(operator.concat, a)


def itertools_chain(a):
    return list(itertools.chain.from_iterable(a))


def numpy_flat(a):
    return list(numpy.array(a).flat)


def numpy_concatenate(a):
    return list(numpy.concatenate(a))


perfplot.show(
    setup=lambda n: [list(range(10))] * n,
    kernels=[
        forfor, sum_brackets, functools_reduce, itertools_chain, numpy_flat,
        numpy_concatenate
        ],
    n_range=[2**k for k in range(16)],
    logx=True,
    logy=True,
    xlabel='num lists'
    )

131
2017-07-26 09:38





from functools import reduce #python 3

>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> reduce(lambda x,y: x+y,l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

The extend() метод у вашому прикладі змінюється x замість того, щоб повернути корисну величину (яка reduce() чекає)

Швидший спосіб зробити це reduce версія буде

>>> import operator
>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> reduce(operator.concat, l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

100
2018-06-04 20:35



reduce(operator.add, l) буде правильним способом зробити це reduce версія Вбудовані пристрої швидше, ніж лямбда. - agf
@agf ось як: * timeit.timeit('reduce(operator.add, l)', 'import operator; l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]', number=10000)  0.017956018447875977   * timeit.timeit('reduce(lambda x, y: x+y, l)', 'import operator; l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]', number=10000)  0,025218963623046875 - lukmdo
Це алгоритм живописця Шлемієла joelonsoftware.com/articles/fog0000000319.html - Mike Graham
це можна використовувати лише для integers. Але що, якщо список містить string? - Freddy
@ Фредді: The operator.add Функція працює однаково добре для обох списків цілих чисел та списків рядків. - Greg Hewgill


Ось загальний підхід, який застосовується до номери, рядки, вкладений списки та змішаний контейнери

Код

from collections import Iterable


def flatten(items):
    """Yield items from any nested iterable; see Reference."""
    for x in items:
        if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
            for sub_x in flatten(x):
                yield sub_x
        else:
            yield x

Примітка: у Python 3 yield from flatten(x) може замінити for sub_x in flatten(x): yield sub_x

Демонстрація

lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
list(flatten(lst))                                         # nested lists
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

mixed = [[1, [2]], (3, 4, {5, 6}, 7), 8, "9"]              # numbers, strs, nested & mixed
list(flatten(mixed))
# [1, 2, 3, 4, 5, 6, 7, 8, '9']

Посилання

  • Цей розчин змінено з рецепта в Росії Бізлі, Д. і Б. Джонс. Рецепт 4.14, П'ятипакова книга 3-ї редакції, O'Reilly Media Inc. Севастополь, Каліфорнія: 2013.
  • Знайдено раніше SO post, можливо оригінальна демонстрація.

55
2017-11-29 04:14



Я просто написав майже те ж саме, тому що я не бачив вашого рішення ... ось що я шукав для "рекурсивного вирівнювання повних декількох списків" ... (+1) - Martin Thoma
@МартінТома багато оцінили. FYI, якщо для вставлених ітерабелів вирівнювання є загальноприйнятою практикою, є деякі сторонні пакети, які обробляють це добре. Це може врятувати від винаходу колеса. Я згадав more_itertools серед інших, обговорених на цій посаді. Підбадьорює - pylang
Ніцца - було просто цікаво про a yield from тип конструкції на python після дізнання про yield * в es2015. - Triptych
замінити на if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): підтримувати рядки. - Jorge Leitão
Правильно. Оригінальний рецепт кулінарної книги насправді показує, як підтримувати рядки та байти. Якщо ви редагуєте його, щоб відобразити цю підтримку. - pylang


Я повертаю своє твердження. Сума не є переможцем. Хоча це швидше, коли список невеликий. Але продуктивність істотно знижується при збільшенні списків. 

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10000'
    ).timeit(100)
2.0440959930419922

Сумарна версія все ще працює більше, ніж за хвилину, і вона ще не оброблена!

Для середніх списків:

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
20.126545906066895
>>> timeit.Timer(
        'reduce(lambda x,y: x+y,l)',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
22.242258071899414
>>> timeit.Timer(
        'sum(l, [])',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
16.449732065200806

Використовуючи невеликі списки та timeit: число = 1000000

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
2.4598159790039062
>>> timeit.Timer(
        'reduce(lambda x,y: x+y,l)',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
1.5289170742034912
>>> timeit.Timer(
        'sum(l, [])',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
1.0598428249359131

31
2018-06-04 20:46



для справді мінімального списку, наприклад один із 3 підривниками, можливо - але оскільки продуктивність суми йде з O (N ** 2), тоді як розуміння списку йде з O (N), просто збільшуючи список вхідних, трохи повернеться - фактично LC буде " нескінченно швидше ", ніж сума в межах, коли N зростає. Я був відповідальним за розробку суми і здійснення першої реалізації в середовищі виконання Python, і я все ж таки хочу, щоб я знайшов спосіб ефективно обмежити його підсумовування чисел (що це насправді добре) і блокувати "привабливі незручності", які вона пропонує людям хто хоче "сумувати" списки ;-). - Alex Martelli