Предположим, что у меня есть такая функция:
def getNeighbors(vertex)
который возвращает список вершин, которые являются соседями заданной вершины. Теперь я хочу создать список со всеми соседями соседей. Я так делаю:
listOfNeighborsNeighbors = []
for neighborVertex in getNeighbors(vertex):
listOfNeighborsNeighbors.append(getNeighbors(neighborsVertex))
Есть ли более питонический способ сделать это?
[x for n in getNeighbors(vertex) for x in getNeighbors(n)]
или
sum(getNeighbors(n) for n in getNeighbors(vertex), [])
Как обычно, модуль 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]
Добавление списков может быть выполнено с помощью + и sum():
>>> c = [[1, 2], [3, 4]]
>>> sum(c, [])
[1, 2, 3, 4]
Если скорость имеет значение, возможно, лучше использовать это:
from operator import iadd
reduce(iadd, (getNeighbors(n) for n in getNeighbors(vertex)))
Точка этого кода заключается в объединении целых списков с помощью list.extend, где понимание списка добавляет один элемент по одному, как если бы он вызывал list.append. Это экономит немного накладных расходов, что делает первые (по моим измерениям) примерно в три раза быстрее. (Оператор iadd обычно записывается как += и делает то же самое, что и list.extend.)
Использование списков (первое решение Ignacio) по-прежнему, как правило, правильное, его легче читать.
Но определенно избегайте использования sum(..., []), потому что он работает в квадратичном времени. Это очень непрактично для многих списков (более ста или около того).
Отсортировано по скорости:
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
Мне нравится подход itertools.chain, потому что он работает в линейном времени (sum (...) работает в qudratic time), но @Jochen не показывал, как обращаться со списками динамической длины. Вот решение для вопроса OP.
import itertools
list(itertools.chain(*[getNeighbors(n) for n in getNeighbors(vertex)]))
Вы можете избавиться от вызова list(...), если для вас достаточно итерации.
Использование .extend() (обновление на месте) в сочетании с сокращением вместо sum() (новый объект каждый раз) должно быть более эффективным, но я тоже ленив, чтобы проверить, что:)
mylist = [[1,2], [3,4], [5,6]]
reduce(lambda acc_l, sl: acc_l.extend(sl) or acc_l, mylist)