modo veloce di stringhe di attraversamento in una lista

Question

Se hanno una lista in questo modo:

shops=['A','B','C','D'] 

e vorrebbe creare i seguenti nuovi elenchi (io attraverso ogni elemento con tutti gli altri e creare una stringa in cui prima parte è alfanumerico prima del secondo):

['A-B', 'A-C', 'A-D'] 

['A-B', 'B-C', 'B-D'] 

['A-C', 'B-C', 'C-D'] 

['A-D', 'B-D', 'C-D'] 

ho qualcosa di simile a questo:

for a in shops: 
    cons = [] 
    for b in shops: 
     if a!=b: 
      con = [a,b] 
      con = sorted(con, key=lambda x: float(x)) 
      cons.append(con[0]+'-'+con[1]) 
    print(cons) 

Tuttavia, questo è pr lento per grandi elenchi (ad es. 1000 dove ho 1000 * 999 * 0,5 uscite). Stavo cercando un modo più efficiente per farlo?

Avrei potuto usare una clausola if-else per l'ordinamento, ad es.

for a in shops: 
    cons = [] 
    for b in shops: 
     if a<b: 
      cons.append(a+"-"+b) 
     elif a>b: 
      cons.append(b+"-"+a) 
    print(cons) 

Il che, non ho ancora cronometrato - ma ho pensato che il principale rallentamento è stato il doppio ciclo for

Answer 1

È possibile creare una lista annidata-di comprensione con alcuni controlli aggiuntivi:

>>> shops=['A','B','C','D'] 
>>> [["-".join((min(a,b), max(a,b))) for b in shops if b != a] for a in shops] 
[['A-B', 'A-C', 'A-D'], 
['A-B', 'B-C', 'B-D'], 
['A-C', 'B-C', 'C-D'], 
['A-D', 'B-D', 'C-D']] 

Si noti che questo non sarà probabilmente molto più veloce di codice, come si devono ancora generare tutte quelle combinazioni. In pratica, si potrebbe fare un generatore di espressione, quindi gli elementi non vengono generati tutti in una volta, ma solo "se necessario":

gen = (["-".join((min(a,b), max(a,b))) for b in shops if b != a] for a in shops) 
for item in gen: 
    print(item) 

---

Aggiornamento: Ho fatto qualche analisi temporale mediante IPython di %timeit. La tua seconda implementazione è la più veloce. Testato con un elenco di 100 stringhe (map(str, range(100))) e dopo aver trasformato ciascuno dei metodi in generatori.

In [32]: %timeit list(test.f1())   # your first implementation 
100 loops, best of 3: 13.5 ms per loop 

In [33]: %timeit list(test.f2())   # your second implementation 
1000 loops, best of 3: 1.63 ms per loop 

In [34]: %timeit list(test.g())   # my implementation 
100 loops, best of 3: 3.49 ms per loop 

È possibile accelerarlo utilizzando un semplice if/else invece di min/max, come nel tuo secondo implementazione, allora sono circa altrettanto veloci.

(["-".join((a,b) if a < b else (b,a)) for b in shops if b != a] for a in shops) 

Answer 2

In base a quello che hai detto:

io attraverso ogni elemento con ogni altro e creare una stringa in cui prima parte è alfanumerico prima della seconda

è possibile utilizzare 2 combinazione come segue:

>>> form itertools import combinations 
>>> list(combinations(['_'.join(i) for i in combinations(shops,2)],3) 
...) 
[('A_B', 'A_C', 'A_D'), ('A_B', 'A_C', 'B_C'), ('A_B', 'A_C', 'B_D'), ('A_B', 'A_C', 'C_D'), ('A_B', 'A_D', 'B_C'), ('A_B', 'A_D', 'B_D'), ('A_B', 'A_D', 'C_D'), ('A_B', 'B_C', 'B_D'), ('A_B', 'B_C', 'C_D'), ('A_B', 'B_D', 'C_D'), ('A_C', 'A_D', 'B_C'), ('A_C', 'A_D', 'B_D'), ('A_C', 'A_D', 'C_D'), ('A_C', 'B_C', 'B_D'), ('A_C', 'B_C', 'C_D'), ('A_C', 'B_D', 'C_D'), ('A_D', 'B_C', 'B_D'), ('A_D', 'B_C', 'C_D'), ('A_D', 'B_D', 'C_D'), ('B_C', 'B_D', 'C_D')] 
>>> 

In un primo momento si può utilizzare una combinazione all'interno di una lista di comprensione per creare le coppie ordinate e concatenare utilizzando str.join. Quindi usa altre combinazioni per creare i set di trina.

Answer 3

Se la lista è ordinata e non ci sono duplicati, è possibile tenere traccia della posizione nella lista per evitare di dover fare i confronti per ottenere l'ordine.

from itertools import chain, islice 

combos = [] 
for i, s in enumerate(shops): 
    combo = ['{0}-{1}'.format(a, b) for a, b in chain(
     ((c, s) for c in islice(shops, None, i), 
     ((s, c) for c in islice(shops, i+1))] 
    combos.append(combo) 

EDIT: aggiornato per utilizzare generatori