Erstellen und spielen Sie mit Prioritätswarteschlangen, mit denen Elemente aktualisiert werden können. Um genau zu sein, wird durch das Verschieben desselben Elements mit unterschiedlichen Prioritäten eine priorisierte Warteschlange erstellt, die die Prioritäten überschreibt.
Aufgrund der Kurzreferenz zum Algorithmus musste ich eine Prioritätswarteschlange verwenden, suchte jedoch nach "Prioritätswarteschlange Python" und sie wird oben angezeigt. http://docs.python.jp/2/library/heapq.html Als ich es mir ansah, sagte es etwas Schreckliches.
Prioritätswarteschlangen sind eine häufige Verwendung von Heaps und haben einige Schwierigkeiten bei der Implementierung:
- Sortierstabilität: Wie können zwei Aufgaben mit gleicher Priorität in der Reihenfolge zurückgegeben werden, in der sie ursprünglich hinzugefügt wurden?
Die Lösung für die ersten beiden Schwierigkeiten besteht darin, den Artikel als Liste mit drei Elementen zu speichern, die die Priorität, die Artikelnummer und die Aufgabe enthält. Diese Artikelnummer dient als Verbindungsunterbrechung, um sicherzustellen, dass zwei Aufgaben mit derselben Priorität in der Reihenfolge zurückgegeben werden, in der sie hinzugefügt wurden. Und da die beiden Artikelnummern niemals gleich sind, kann der Tapple-Vergleich nicht versuchen, die beiden Aufgaben direkt zu vergleichen. Die verbleibende Schwierigkeit besteht hauptsächlich darin, offene Aufgaben zu finden, ihre Prioritäten zu ändern oder sie ganz zu entfernen. Das Finden einer Aufgabe erfolgt durch ein Wörterbuch, das auf Elemente in der Warteschlange verweist. Das Löschen von Elementen oder das Ändern ihrer Prioritäten ist schwieriger, da dadurch die unveränderlichen Beziehungen der Heap-Struktur unterbrochen werden. Eine mögliche Lösung besteht darin, das Element als ungültig zu markieren und das geänderte Prioritätselement bei Bedarf hinzuzufügen:
Nun, ich weiß was du sagst. Ich habe mich gefragt, ob Python standardmäßig keine Prioritätswarteschlangen bereitstellt, da heapq so etwas sagt. Dies ist jedoch nicht der Fall, und es gibt eine ordnungsgemäße Queue.PriorityQueue (). Obwohl dies der Fall ist, scheint es nicht möglich zu sein, den Aktualisierungsprozess mit dieser PriorityQueue () sofort durchzuführen. In Anbetracht dessen, was auf dieser Seite geschrieben steht, war ich neugierig, um wie viel die Berechnungsgeschwindigkeit besser oder schlechter sein würde ~~ es ist mir egal ~~.
Eine Warteschlange mit handgefertigten Prioritäten (im Folgenden als "Handwarteschlange" bezeichnet) besteht aus einer Liste von Tapples (sortkey (Wert, Generation)) und einem Wörterbuch, das für jeden Wert eine Generation enthält. Das Löschen ist ein Bild, das nicht wie oben beschrieben ausgeführt wird, sondern durch Markieren ausgeführt wird. Es wird jedoch gesteuert, indem die Nummer der neuesten Generation im Wörterbuch gespeichert und nicht die neuesten Daten verwendet werden. Ich werde. Da sich die Suchleistung verschlechtert, wenn Elemente akkumuliert werden, muss außerdem die Datenlöschung + Heap-Rekonstruktion auf eine Garbage Collection-Weise durchgeführt werden. In Bezug auf den Zeitpunkt der "Speicherbereinigung" hier habe ich beschlossen, sie als geeignete Konstante m beizubehalten und zu rekonstruieren, wenn die Anzahl der Elemente (die Anzahl der äußersten Klammern des Taples, die als 1 gezählt werden) m überschreitet. Und so weiter.
TeQueue.py
import heapq
def tepush(l, d, m, sortkey, value):
if not value in d:
generation = 1
else:
generation = d[value] + 1
d[value] = generation
heapq.heappush(l, (sortkey, value, generation))
length = len(l)
if length > m: #Den Haufen rekonstruieren
lt = []
for n in range(0,length):
if l[n][2] == d[l[n][1]]:
heapq.heappush(lt, (l[n][0], l[n][1], 1))
d[l[n][1]] = 1
return lt
else:
return l
def tepop(l, d):
while len(l) > 0:
(sortkey, value, generation) = heapq.heappop(l)
if d[value] == generation:
return (sortkey, value, generation)
Dies ermöglicht es, den Wert zu "überschreiben", der dem gleichen Wert entspricht, der im Entwurf beschrieben ist.
Vergleiche mit Queue.PriorityQueue ().
Führen Sie vorerst die folgende Initialisierung durch.
initialize.py
#Erzeugen Sie eine zufällige Folge von N.
import random
N = 100000
M = 100000
target = range(0,N)
temp = range(0,N)
for n in range(N-1,-1,-1):
target[n] = temp.pop(random.randint(0,n))
push
pushtest.py
import Queue
import heapq
import datetime
d = datetime.datetime(1,1,1)
time1 = d.now()
t = Queue.PriorityQueue(N)
for n in range(0,N):
t.put((target[n], n))
time2 = d.now()
u = []
for n in range(0,N):
heapq.heappush(u, (target[n], n))
time3 = d.now()
v = []
dd = {}
for n in range(0,N):
v = tepush(v, dd, 2*M, target[n], n)
time4 = d.now()
print('push:Queue',(time2 - time1).__str__())
print('push:Heap',(time3 - time2).__str__())
print('push:TeQ',(time4 - time3).__str__())
Ergebnis drücken
('push:Queue', '0:00:00.350000')
('push:Heap', '0:00:00.086000')
('push:TeQ', '0:00:00.137000')
Es sieht aus wie das. TeQ> Heap, weil es viele Vergleiche gibt, aber es ist viel schneller als Queue.
pop
poptest.py
import Queue
import heapq
import datetime
time1 = d.now()
for n in range(0,M):
t.get()
time2 = d.now()
for n in range(0,M):
heapq.heappop(u)
time3 = d.now()
for n in range(0,M):
tepop(v, dd)
time4 = d.now()
print('pop:Queue',(time2 - time1).__str__())
print('pop:Heap',(time3 - time2).__str__())
print('pop:TeQ',(time4 - time3).__str__())
Pop-Ergebnis
('pop:Queue', '0:00:00.484000')
('pop:Heap', '0:00:00.214000')
('pop:TeQ', '0:00:00.299000')
Es sieht aus wie das. Es ist weniger anders als Push, aber es ist immer noch der gleiche Trend. Eigentlich wollte ich mit M spielen, indem ich den Grad der Duplizierung änderte, aber mir wurde klar, dass es für Queue und Heapq nicht viel Sinn macht, und so beschloss ich, einen Vergleich im Hand-Cue anzustellen. Beim Vergleich mit anderen als Hand Cue http://stackoverflow.com/questions/9969236/how-to-implement-priority-queues-in-python Es schien gut, es mit etwas zu vergleichen, aber ich machte es minderwertig.
initializeA.py
#Erzeugen Sie eine zufällige Folge von N.
import random
N = 1000000
M = 40000
target = range(0,N)
for n in range(N-1,-1,-1):
target[n] = random.randint(0,M-1)
testA.py
d = datetime.datetime(1,1,1)
for m in [2,5,10,20]:
time1 = d.now()
v = []
dd = {}
for n in range(0,N):
v = tepush(v, dd, m*M, n, target[n])
time2 = d.now()
for n in range(0,M):
tepop(v, dd)
time3 = d.now()
print('push:TeQ_' + str(m),(time2 - time1).__str__())
print('pop:TeQ_' + str(m),(time3 - time2).__str__())
Ergebnis A.
('push:TeQ_2', '0:00:02.731000')
('pop:TeQ_2', '0:00:00.193000')
('push:TeQ_5', '0:00:01.794000')
('pop:TeQ_5', '0:00:00.527000')
('push:TeQ_10', '0:00:01.667000')
('pop:TeQ_10', '0:00:00.711000')
('push:TeQ_20', '0:00:01.605000')
('pop:TeQ_20', '0:00:00.581000')
Der Grund, warum 20 Pops schneller sind, ist, dass sich das zweite Mal 20 * 40000 und 10 * 40000 überlappen, was bedeutet, dass sie sich immerhin im selben Zustand befinden. .. .. HM.
initializeB.py
#Erzeugen Sie eine zufällige Folge von N.
import random
N = 1000000
M = 4000
target = range(0,N)
for n in range(N-1,-1,-1):
target[n] = random.randint(0,M-1)
testB.py
d = datetime.datetime(1,1,1)
for m in [2,5,10,20]:
time1 = d.now()
v = []
dd = {}
for n in range(0,N):
v = tepush(v, dd, m*M, n, target[n])
time2 = d.now()
for n in range(0,M):
tepop(v, dd)
time3 = d.now()
print('push:TeQ_' + str(m),(time2 - time1).__str__())
print('pop:TeQ_' + str(m),(time3 - time2).__str__())
Ergebnis B.
('push:TeQ_2', '0:00:02.927000')
('pop:TeQ_2', '0:00:00.013000')
('push:TeQ_5', '0:00:02.035000')
('pop:TeQ_5', '0:00:00.018000')
('push:TeQ_10', '0:00:01.929000')
('pop:TeQ_10', '0:00:00.093000')
('push:TeQ_20', '0:00:01.846000')
('pop:TeQ_20', '0:00:00.026000')
Auch nach mehrmaligem Versuch ändert sich an dieser Tendenz nicht viel. Warum. Selbst wenn die Reihenfolge geändert wird, bleiben 20 überwiegend schneller als 10. HM. .. ..
Ich habe das Gefühl, dass ich nicht das Äquivalent einer Speicherbereinigung oder Neuindizierung tun muss.