Как эффективнее всего сделать плоский (flatten) список из списка списков?

Question

Интересно найти самый эффективный по скорости способ преобразования список во flatten с сохранением порядка:

[
    [5, 6],
    [7, 8, 9],
    [10, 11, 12, 13, 14],
    [15, 16, 17, 18]
]

Результат [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]?

Answer 1

А чем вас простое сложение списков не устраивает? Я пробовал и в Numpy переводить, но как выяснилось, само преобразование обычных списков в массивы Numpy съедает всю возможную выгоду от того, что Numpy работает быстро со своими родными типами данных. Вот если бы у вас данные уже были в формате массивов Numpy, тогда имело бы смысл пользоваться встроенными методами Numpy и это было бы быстрее, чем чистый Питон.

%%time
lst = [
    [5, 6] * 1_000,
    [7, 8, 9] * 1_000,
    [10, 11, 12, 13, 14] * 1_000,
    [15, 16, 17, 18] * 1_000
] * 1_000

result = []
for item in lst:
    result += item
print(len(result))

Вывод:

14000000
CPU times: total: 344 ms
Wall time: 360 ms

14 миллионов элементов собралось за 0.3 секунды.

P.S. Да, при добавлении элементов в список периодически происходит ресайз заготовленного под список массива, но он делается с запасом (в 2 раза от предыдущего размера, ну или может в 1.5 для уже очень больших списков - я точно не помню детали реализации в Питоне и могу путать со списком в C#, если возьмём 2, то это всего примерно 20 ресайзов с начального размера списка 16 и до 14 миллионов). Поэтому затратный по времени ресайз с копированием всего списка происходит не так уж и часто, а просто разместить элемент в очередную свободную ячейку списка стоит дёшево, Питон довольно оптимизирован для типичных операций с коллекциями.

P.P.S. По заявкам телезрителей посчитал зависимость от размера и числа массивов при сохранении общего количества элементов.

import time

n = 100_000_000
print(f'Всего {n:,} элементов')
for i in range(7, 0, -1):
    k = 10**i
    m = n // k
    lst = [[42] * k] * m
    t = time.time()
    result = []
    for item in lst:
        result += item
    print(f'Конкатенация {m:,} списков по {k:,} элементов: {time.time() - t:.2f}с')

Вывод:

Всего 100,000,000 элементов
Конкатенация 10 списков по 10,000,000 элементов: 1.80с
Конкатенация 100 списков по 1,000,000 элементов: 2.72с
Конкатенация 1,000 списков по 100,000 элементов: 2.98с
Конкатенация 10,000 списков по 10,000 элементов: 3.21с
Конкатенация 100,000 списков по 1,000 элементов: 3.04с
Конкатенация 1,000,000 списков по 100 элементов: 3.26с
Конкатенация 10,000,000 списков по 10 элементов: 3.88с

Как видно из этого теста, меньше списков -> меньше ресайзов -> меньше времени занимает процесс конкатенации списков при том же суммарном числе элементов.

БЛОГ НА HUSL

Как эффективнее всего сделать плоский (flatten) список из списка списков?

Ответы (1 шт):