Wie schnell eine Liste aller Paare aus einer großen Anzahl von Zahlen zu generieren?

Question

ich erstellen Sie eine Liste mit den Nummern 0-131072:

x = [i for i in range(131072)] 

Dann alle Paare, mit Ausnahme der Paare von den gleichen Zahlen:

pairs = [] 
append_pairs = pairs.append 
for i in range(len(x)): 
    for j in range(len(x)): 
     if x[i]!=x[j]: 
      x2 = [x[i], x[j]] 
      append_pairs(x2) 

die gibt:

pairs = [[0, 1], [0, 2], [0, 3], ... [131071, 131070]] 

Aber In dieser Syntax dauert es sehr lange. Kann es schneller gemacht werden?

Answer 1

Sie können itertools.combinations verwenden, aber das wird wohl auch eine Weile dauern, etwa so:

import itertools as it 

n = 131072 
pairs = it.combinations(range(n), 2) 

Beachten Sie, dass der Code oben wird nicht geben Ihnen die Liste aller Paare, sondern einen Generator über Paare:

>>> pairs 
<itertools.combinations at 0x7fb939a72a48> 

Sie können die Liste bekommen mit

pairs = list(it.combinations(range(n), 2) 

i mit numpy s wahrscheinlich schneller:

import numpy as np 

pairs = np.transpose(np.triu_indices(n, 1)) 

jedoch die Anzahl von Paaren Sie generieren wollen, ist enorme und die Nummern im Speicher nicht gespeichert werden kann (es sei denn, Sie eine sehr leistungsfähige Maschine haben). Insbesondere erhalten Sie n * (n - 1)/2 Paare. Wenn Sie die Zahlen als 8-Byte-Ganzzahlen speichern, sehen Sie knapp 70 GB Speicher.

Für n = 5000:

• itertools: 818 ms ± 15,8 ms pro Schleife (Mittelwert ± STD dev von 7 verläuft, 1-Schleife jeweils..)
• Numpy: 254 ms ± 30,8 ms pro Schleife (Mittelwert ± STD dev von 7 verläuft, 1 loop each)
• Originalmethode:.... 3,72 s ± 72,6 ms pro Schleife (Mittelwert ± STD dev von 7 verläuft, 1-Schleife jeweils)

Hinweis: Weil es mehr eingebauten Code gibt, habe ich generiert d verschiedene Paare.