Конкатенация многих списков в Python

Предположим, что у меня есть такая функция:

def getNeighbors(vertex)

который возвращает список вершин, которые являются соседями заданной вершины. Теперь я хочу создать список со всеми соседями соседей. Я так делаю:

listOfNeighborsNeighbors = []
for neighborVertex in getNeighbors(vertex):
    listOfNeighborsNeighbors.append(getNeighbors(neighborsVertex))

Есть ли более питонический способ сделать это?

Ответы

Ответ 1

[x for n in getNeighbors(vertex) for x in getNeighbors(n)]

или

sum(getNeighbors(n) for n in getNeighbors(vertex), [])

Ответ 2

Как обычно, модуль itertools содержит решение:

>>> l1=[1, 2, 3]

>>> l2=[4, 5, 6]

>>> l3=[7, 8, 9]

>>> import itertools

>>> list(itertools.chain(l1, l2, l3))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Ответ 3

Добавление списков может быть выполнено с помощью + и sum():

>>> c = [[1, 2], [3, 4]]
>>> sum(c, [])
[1, 2, 3, 4]

Ответ 4

Если скорость имеет значение, возможно, лучше использовать это:

from operator import iadd
reduce(iadd, (getNeighbors(n) for n in getNeighbors(vertex)))

Точка этого кода заключается в объединении целых списков с помощью list.extend, где понимание списка добавляет один элемент по одному, как если бы он вызывал list.append. Это экономит немного накладных расходов, что делает первые (по моим измерениям) примерно в три раза быстрее. (Оператор iadd обычно записывается как += и делает то же самое, что и list.extend.)

Использование списков (первое решение Ignacio) по-прежнему, как правило, правильное, его легче читать.

Но определенно избегайте использования sum(..., []), потому что он работает в квадратичном времени. Это очень непрактично для многих списков (более ста или около того).

Ответ 5

Отсортировано по скорости:

list_of_lists = [[x,1] for x in xrange(1000)]

%timeit list(itertools.chain(*list_of_lists))
100000 loops, best of 3: 14.6 µs per loop

%timeit list(itertools.chain.from_iterable(list_of_lists))
10000 loops, best of 3: 60.2 µs per loop

min(timeit.repeat("ll=[];\nfor l in list_of_lists:\n ll.extend(l)", "list_of_lists=[[x,1] for x in xrange(1000)]",repeat=3, number=100))/100.0
9.620904922485351e-05

%timeit [y for z in list_of_lists for y in z]
10000 loops, best of 3: 108 µs per loop

%timeit sum(list_of_lists, [])
100 loops, best of 3: 3.7 ms per loop

Ответ 6

Мне нравится подход itertools.chain, потому что он работает в линейном времени (sum (...) работает в qudratic time), но @Jochen не показывал, как обращаться со списками динамической длины. Вот решение для вопроса OP.

import itertools
list(itertools.chain(*[getNeighbors(n) for n in getNeighbors(vertex)]))

Вы можете избавиться от вызова list(...), если для вас достаточно итерации.

Ответ 7

Использование .extend() (обновление на месте) в сочетании с сокращением вместо sum() (новый объект каждый раз) должно быть более эффективным, но я тоже ленив, чтобы проверить, что:)

mylist = [[1,2], [3,4], [5,6]] 
reduce(lambda acc_l, sl: acc_l.extend(sl) or acc_l, mylist)