schnelle Art und Weise der Überquerung Strings in einer Liste

Question

Wenn haben Sie eine Liste wie folgt:

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

Und möchte folgende neue Listen erstellen (I überqueren jedes Element mit jedem anderen und einen String erstellen, in dem ersten Teil ist alphanummerisch vor dem zweiten):

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

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

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

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

ich so etwas wie dieses:

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) 

dies ist jedoch pr langsam für große Listen (z.B. 1000, wo ich 1000 * 999 * 0,5 Ausgänge habe). Ich suchte nach einer effizienteren Methode, dies zu tun?

Ich hätte eine if-else-Klausel für die Sortierung, z.

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) 

Which, habe ich noch nicht abgelaufen - aber ich die Haupt dachte Verlangsamung der Doppel for-Schleife

Answer 1

Sie können eine verschachtelte Liste Verständnis mit einigen zusätzlichen Kontrollen erstellen:

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

Beachten Sie, dass dies wahrscheinlich der Code nicht viel schneller als, wie Sie noch alle diese Kombinationen zu erzeugen haben. In der Praxis könnte man ihm einen Generator Ausdruck machen, so werden die Elemente nicht alle auf einmal erzeugt, sondern nur „nach Bedarf“:

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) 

---

Update: Ich habe einige Analyse Timing IPython die mit %timeit. Es stellt sich heraus, dass Ihre zweite Implementierung am schnellsten ist. Getestet mit einer Liste von 100 Strings (map(str, range(100))) und nachdem jede der Methoden in Generatoren umgewandelt wurde.

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 

Sie können es beschleunigen, indem Sie einen einfachen if/else statt min/max verwenden, wie in Ihrem zweiten Implementierung, dann sind sie etwa gleich schnell.

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

Answer 2

Basierend auf das, was Sie gesagt haben:

ich jedes Element überqueren mit jeder anderen und einen String erstellen, in dem erste Teil ist alphanummerisch vor dem zweiten

können Sie 2 Kombination wie folgt vor:

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

Zunächst können Sie eine Kombination innerhalb einer Liste Verständnis verwenden, um die geordneten Paare zu erstellen und verketten sie str.join verwenden. Verwenden Sie dann eine andere Kombination, um die Trinalsätze zu erstellen.

Answer 3

Wenn die Liste sortiert ist und es gibt keine Duplikate, können Sie den Überblick über Ihre Position in der Liste zu halten, um zu vermeiden Vergleiche zu tun, um den Auftrag zu bekommen.

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: aktualisiert Generatoren verwenden