Enchaînement de nombreuses listes en Python

Question

Supposons que j'ai une fonction comme ceci:

def getNeighbors(vertex) 

qui retourne une liste de sommets qui sont voisins du sommet donné. Maintenant, je veux créer une liste avec tous les voisins des voisins. Je fais cela comme ceci:

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

Y a-t-il une façon plus pythonique de le faire?

Answer 1

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

ou

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

Answer 2

listes L'ajout peut être fait avec + et somme():

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

Answer 3

Comme d'habitude, le module itertools contient une solution:

>>> 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] 

Answer 4

Si la vitesse compte, il peut être préférable d'utiliser ceci:

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

Le point de ce code est dans toute concaténer listes par list.extend où la compréhension de la liste ajouterait un élément par un, comme si vous appelez list.append. Cela économise un peu de frais généraux, rendant le premier (selon mes mesures) environ trois fois plus rapide. (L'opérateur iadd est normalement écrit += et fait la même chose que list.extend.)

compréhensions (la première solution par Ignacio) est encore le plus souvent dans le bon sens, il est plus facile à lire.

Mais évitez absolument d'utiliser sum(..., []), car il s'exécute en temps quadratique. C'est très peu pratique pour beaucoup de listes (plus d'une centaine).

Answer 5

J'aime l'approche itertools.chain car elle s'exécute en temps linéaire (somme (...) s'exécute en temps quadratique) mais @Jochen n'a pas montré comment traiter les listes de longueur dynamique. Voici une solution pour la question de l'OP.

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

Vous pouvez vous débarrasser de list(...) appel si itérables est suffisant pour vous.

Answer 6

Trié par vitesse:

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 

Answer 7

à l'aide .extend() (mise à jour en place) combinée à réduire au lieu de la somme () (nouvel objet à chaque fois) devrait cependant être plus efficace je m trop paresseux pour tester cela :)

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