How do I make a flat list out of a list of lists?

У меня есть список списков, таких как

[
    [1, 2, 3],
    [4, 5, 6],
    [7],
    [8, 9]
]

Как я могу сгладить его, чтобы получить[1, 2, 3, 4, 5, 6, 7, 8, 9]?

_{Если ваш список списков основан на понимании вложенного списка, проблему можно решить проще / напрямую, исправив понимание; пожалуйста, смотрите Как я могу получить плоский результат из понимания списка вместо вложенного списка?.}

_{Наиболее популярные решения здесь обычно выравнивают только один "уровень" вложенного списка. Смотрите в разделе Сглаживание нерегулярного (произвольно вложенного) списка списков для решений, которые полностью сглаживают глубоко вложенную структуру (рекурсивно, в общем случае).}

Список списков с именем xss может быть уменьшен с помощью понимания списка:

flat_list = [
    x
    for xs in xss
    for x in xs
]

Вышесказанное эквивалентно:

flat_list = []

for xs in xss:
    for x in xs:
        flat_list.append(x)

Вот соответствующая функция:

def flatten(xss):
    return [x for xs in xss for x in xs]

Это самый быстрый метод.
В качестве доказательства, используя timeit модуль в стандартной библиотеке, мы видим:

$ python -mtimeit -s'xss=[[1,2,3],[4,5,6],[7],[8,9]]*99' '[x for xs in xss for x in xs]'
10000 loops, best of 3: 143 usec per loop

$ python -mtimeit -s'xss=[[1,2,3],[4,5,6],[7],[8,9]]*99' 'sum(xss, [])'
1000 loops, best of 3: 969 usec per loop

$ python -mtimeit -s'xss=[[1,2,3],[4,5,6],[7],[8,9]]*99' 'reduce(lambda xs, ys: xs + ys, xss)'
1000 loops, best of 3: 1.1 msec per loop

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

Понимание списка генерирует один список только один раз и копирует каждый элемент (из его первоначального места жительства в результирующий список) также ровно один раз.

Вы можете использовать itertools.chain():

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

Или вы можете использовать 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], и, похоже, также быстрее:

$ python3 -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools' 'list(itertools.chain.from_iterable(l))'
20000 loops, best of 5: 10.8 usec per loop
$ python3 -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 5: 21.7 usec per loop
$ python3 -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 5: 258 usec per loop
$ python3 -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;from functools import reduce' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 5: 292 usec per loop
$ python3 --version
Python 3.7.5rc1

Примечание от автора: Это очень неэффективно. Но весело, потому что моноиды потрясающие.

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

sum суммирует элементы итерируемого xss и использует второй аргумент в качестве начального значения [] для суммы. (Начальное значение по умолчанию - 0, которое не является списком.)

Поскольку вы суммируете вложенные списки, вы фактически получаете [1,3]+[2,4] в результате sum([[1,3],[2,4]],[]), что равно [1,3,2,4].

Обратите внимание, что это работает только со списками списков. Для списков списков списков списков вам понадобится другое решение.

Я протестировал большинство предлагаемых решений с помощью perfplot (мой любимый проект, по сути, оболочка вокруг timeit) и нашел

import functools
import operator
functools.reduce(operator.iconcat, a, [])

это самое быстрое решение, как при объединении множества небольших, так и нескольких длинных списков. (operator.iadd одинаково быстро.)

Более простой и приемлемый вариант - это

out = []
for sublist in a:
    out.extend(sublist)

Если количество подсписков велико, это работает немного хуже, чем приведенное выше предложение.

Код для воспроизведения графика:

import functools
import itertools
import operator

import numpy as np
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 functools_reduce_iconcat(a):
    return functools.reduce(operator.iconcat, a, [])


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


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


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


def extend(a):
    out = []
    for sublist in a:
        out.extend(sublist)
    return out


b = perfplot.bench(
    setup=lambda n: [list(range(10))] * n,
    # setup=lambda n: [list(range(n))] * 10,
    kernels=[
        forfor,
        sum_brackets,
        functools_reduce,
        functools_reduce_iconcat,
        itertools_chain,
        numpy_flat,
        numpy_concatenate,
        extend,
    ],
    n_range=[2 ** k for k in range(16)],
    xlabel="num lists (of length 10)",
    # xlabel="len lists (10 lists total)"
)
b.save("out.png")
b.show()