Listen Manipulation Code-Optimierung mit Python

Question

Ich habe einen einfachen Code zu gruppieren und Inhalt der Liste zu berechnen. Ich bin besorgt über die Zeit, die es braucht, um den Job zu erledigen. Mit weniger als 100 Gegenständen ist es schnell genug, aber mehrere hundert Gegenstände lassen meinen Mac zum Schreien kommen. Und ich habe bis zu 10000 Punkte auf einer Liste von realen Daten. Also muss ich wissen, wie es möglich ist, diesen Code zu optimieren:

v = [1,2,3,4,5,6,7,8,9,10] 
v1 = v[:5] 
l = len(v1) 
a = [sum(v1[x:y]) for y in range(l+1) for x in range(y)] 
d = {x:a.count(x) for x in a} 

so auf v gibt es eine Liste von ganzen Zahlen. Ziffer kann von 1 bis 4000 sein. Die Listenlänge bei Beispiel ist 10, aber wie oben erwähnt, wird es gehen zu 10000 gehen. v1 ist nur eine Split-Liste mit kleineren Testdaten arbeiten.

ein bekommt jedes Element als eine einzelne Instanz und alle vorhergehenden Artikel als Beispiele:

[1, 3, 2, 6, 5, 3, 10, 9, 7, 4, 15, 14, 12, 9, 5] 

d alle Elemente Gruppen und zählt sie als Schlüsselwertpaar Wörterbuch:

{1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 9: 2, 10: 1, 12: 1, 14: 1, 15: 1} 

Es scheint, dass die Berechnung ein bereits nach 100 + Elemente sehr schwer wird. Mit 500 Artikeln auf ein bekomme ich 276813 Instanzen für d. Also, wenn es 10000 Artikel auf einer Liste gibt, erwarte ich bis zu 5559333 Artikel auf d und vielleicht 100-mal mehr auf ein.

UPDATE

Basierend auf Kommentare und Antworten unten eine gewisse Verbesserung ist unten über die Umsetzung getan:

def t5(v1): 
    l = len(v1) 
    d = {} 
    for x in range(0, l): 
     s = sum(v1[x:]) 
     if s in d: 
      d[s] += 1 
     else: 
      d[s] = 1 
     for y in range(1, l-x): 
      s -= v1[-y] 
      if s in d: 
       d[s] += 1 
      else: 
       d[s] = 1 
    return d 

Ich habe keine Ahnung, wie numpy zu verwenden und/oder numba für weitere Optimierung. Vielleicht gut für verschiedene separate Frage ...

Answer 1

Sie berechnen ständig Summen für Schichten, die Sie bereits zuvor berechnet (jeder sum() rufen eine redundante Schleife), und Sie erstellen viele neue Listenobjekte durch Schneiden die ganze Zeit.

Sie können dynamische Berechnung verwenden, um stattdessen die Summen zu berechnen, indem Sie vom Ende Ihrer Eingabeliste ausgehen; Sie müssen nur den ‚aktuellen‘ Wert auf die Summen für den nächsten Wert in der Liste hinzuzufügen:

für Teilsequenzen auf die nächste länger Teilfolge

# v1 is the input list, l is len(v1) 
sums = [0] * (l * (l + 1) // 2) 
for x in range(l - 1, -1, -1): 
    for y in range(x, l): 
     i = (y * (y + 1) // 2) + x 
     sums[i] += v1[x] + (sums[i + 1] if x < y else 0) 

Dies summiert sich bereits berechneten Summen, eine ganze innere Schleife zu vermeiden. Dies dauert O (N^2) Zeit, und nicht Ihr O (N^3) Ansatz (wobei sum() Schleifen über jeden Sub-Slice bis zu N Elementen lang).

Es übersetzt x und y Koordinaten in Ihr endgültiges "Dreieck", um zu vermeiden, eine größere Matrix (oder ein Wörterbuch, das zusätzlichen Speicher und Hash-Overhead haben würde) zu erstellen.

Das liegt daran, dass Sie Schnitte zwischen zwei beliebigen Punkten in der Liste berechnen; Wenn Sie eine Matrix nehmen, wo die Achse sind die Start- und Zielindizes in jeder Scheibe enthalten ist, können Sie die endgültige Liste wie diese Zahl ein:

0 1 2 3 4 

0 0 1 3 6 10 

1  2 4 7 11 

2  5 8 12 

3   9 13 

4    14 

(Leerzeichen sind Reverse-Scheiben, Dubletten, nicht in der verwendeten Ausgabe). Für jede Zeile und Spalte können Sie den Ausgabe-Index berechnen, indem Sie zählen, wie viele Werte in das Dreieck vor dieser Spalte plus der Zeilennummer passen, oder ((col * col + 1) // 2) + row).

der dynamische Programmier Ansatz fügt die Summe für die bereits hergestellte Scheiben für eine spätere Werte (die Zeile unterhalb der Indizes) zum v1 Wert für die aktuelle Zeile:

v1  0 1 2 3 4 

1 > 0 1 3 6 10 15 
     ^^^^ 
2 > 1  2 5 9 14 
      ^^^
3 > 2  3 7 12 
       ^^ 
4 > 3   4 9 
       ^
5 > 4    5 

So wird der Wert in Zeile 2, Spalte 4 ist v1[2] zuzüglich der bereits berechneten Summe für Zeile 3, Spalte 4, oder in diesem Fall 2 + 12. Es gibt immer nur eine bereits berechnete Summe für jene Elemente, bei denen der Zeilenindex kleiner ist als der Spaltenindex; an Position (3, 3) gibt es keine berechnete Summe bei (4, 3).

Das nächste Problem ist, dass Ihre list.count() Ihre ganze Liste der Summen durchläuft, um zu zählen, wie oft eine Zahl erscheint. Daher erzeugt Ihr Ausdruck {x:a.count(x) for x in a} eine O (N^2) -Doppelschleife; es wird quadratische Zeit benötigen, um alle Zählungen zu verarbeiten.

Verwenden Sie ein Counter() object, dass Wörterbuch zu produzieren statt (a Counter ist eine Unterklasse von dict):

from collections import Counter 

d = Counter(sums) 

A Counter() geht durch alle Elemente nur einmal die Werte zu zählen; Es behält einfach Zähler für jeden Wert, den es gesehen hat, solange es iteriert.

Answer 2

Sie können auch versuchen, diese:

In [75]: v = [1,2,3,4,5,6,7,8,9,10, 9, 2, 1] 

In [76]: r = {} 

In [77]: for x in v: r[x] = r.setdefault(x,0) + 1 

In [78]: r 
Out[78]: {1: 2, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 2, 10: 1} 

In [79]: def func(): 
    ....:  r = {} 
    ....:  for x in v: r[x] = r.setdefault(x,0) + 1 
    ....:  return r 
    ....: 
In [80]: def func1(): 
    ....:  return Counter(v) 
    ....: 
In [81]: %timeit -q -o func() 
Out [81]: <TimeitResult : 100000 loops, best of 3: 2.25 µs per loop> 

In [82]: %timeit -q -o func1() 
Out [82]: <TimeitResult : 100000 loops, best of 3: 4.17 µs per loop> 

so Sie es, ich bin immer die endgültigen Ergebnisse als:

# t is len of v1 
r = {} 
for i, x in enumerate(v1): 
    for y in range(i, t): 
     r[(i, y)] = r.setdefault((i, y), 0) + x 
     for z in range(0, i): 
      r[(z, y)] = r.setdefault((z, y), 0) + x 
r1 = {} 
for x in r.values(): 
    r1[x] = r1.setdefault(x, 0) + 1 
print(r1) 

Ergebnis:

{1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 9: 2, 10: 1, 12: 1, 14: 1, 15: 1} 

Answer 3

Sie könnten die Kosten senken der Summierung mit einem ähnlichen Ansatz:

cache = defaultdict(defaultdict(dict)) 

def my_sum(v, x, y): 
    if y - x == 1: 
     return v[x] 
    if not y in cache[v][x]: 
     mid = (x + y)/2 
     cache[v][x][y] = my_sum(v, x, mid) + my_sum(v, mid, y) 
    return cache[v][x][y] 

dann:

a = [my_sum(v1, x, y) for y in range(l+1) for x in range(y)] 

könnte schneller sein ...

Answer 4

So etwas wie

[sum(v1[x:y]) for y in range(l+1) for x in range(y)] 

scheint mir für eine Reihe von Gründen problematisch:

1. es, dass in jedem Teilwort von v1, von denen es 1+2+3+...+n für eine Liste der Länge n, dh das sind Anzahl der Teilstrings wächst proportional zum Quadrat der Länge.
2. es erstellt eine Scheibe für jede Teilkette, und jede Scheibe ist eine Kopie.
3. es summiert jede Scheibe, obwohl es offensichtlich eine große Überlappung zwischen den Scheiben gibt (zB wenn Sie die Summe der ersten vier Zahlen kennen, sollten Sie wirklich nur eine zusätzliche Addition benötigen, um die Summe der ersten fünf Zahlen zu erhalten) anstatt die ersten fünf von Grund auf zu summieren).

Ich vermute, dass es nicht viel können Sie etwa 1 tun, aber man kann klüger sein, über die beiden anderen Elemente der Bekämpfung: es kann schneller sein, die Tatsache zu nutzen, dass die Summe der Scheibe [i:j] die nur die Summe der Scheibe [i:j-1] (dh die Scheibe beginnt an der gleichen Position, aber ein Element kürzer) und das Element an der Position j-1 (dh das Intervall [j-1:j]). Dies bedeutet, dass jede Summe als eine Summe von zwei zuvor berechneten Summen definiert werden kann.

I.e. statt

a = [sum(v1[x:y]) for y in range(l+1) for x in range(y)] 

try

sums = {(i,i+1): x for i, x in enumerate(v1)} 
for intervalLen in range(2, l + 1): 
    for i in range(l - intervalLen + 1): 
     j = i + intervalLen 
     sums[(i,j)] = sums[(i,j-1)] + sums[(j-1,j)] 
a = sums.values() 

Diese verwendet ein wenig sums Wörterbuch von Memoisation mit: es bildet Tupel bezeichnet die Intervalle (z (0,1)) zur Summe dieses Intervalls. Das Wörterbuch wird mit den trivialen Summen für Intervalle der Länge 1 initialisiert und dann für längere Intervalle aktualisiert. Jeder Schritt verwendet zuvor berechnete Summen.