Créez et jouez avec des files d'attente prioritaires qui peuvent mettre à jour des éléments. Pour être précis, pousser le même élément avec des priorités différentes crée une file d'attente prioritaire qui remplace les priorités.
En raison de la référence rapide de l'algorithme, j'avais besoin d'utiliser une file d'attente prioritaire, mais j'ai recherché "file d'attente prioritaire Python" et elle apparaît en haut. http://docs.python.jp/2/library/heapq.html Quand je l'ai regardé, il a dit quelque chose de terrible.
Les files d'attente prioritaires sont une utilisation courante des tas et présentent quelques difficultés de mise en œuvre:
- Stabilité du tri: Comment deux tâches d'égale priorité peuvent-elles être renvoyées dans l'ordre où elles ont été initialement ajoutées? --Dans le futur Python 3, les comparaisons taple seront divisées en paires (priorité, tâche) si les priorités sont égales et que la tâche n'a pas d'ordre de comparaison par défaut.
La solution aux deux premières difficultés consiste à enregistrer l'élément sous la forme d'une liste à trois éléments contenant la priorité, le numéro de l'élément et la tâche. Ce numéro d'article agit comme un bris d'égalité pour garantir que deux tâches de même priorité sont renvoyées dans l'ordre dans lequel elles ont été ajoutées. Et comme les deux numéros d'éléments ne sont jamais égaux, la comparaison de tapple ne peut pas essayer de comparer les deux tâches directement. La difficulté restante est principalement de trouver des tâches ouvertes, de modifier leurs priorités ou de les supprimer complètement. La recherche d'une tâche est effectuée par un dictionnaire qui pointe vers des éléments de la file d'attente. La suppression d'éléments ou la modification de leurs priorités est plus difficile car elle rompt les relations immuables de la structure du tas. Une solution possible est donc de marquer l'élément comme non valide et d'ajouter l'élément de priorité modifié si nécessaire:
Eh bien, je sais ce que vous dites. Je me suis demandé si Python ne fournissait pas de files d'attente prioritaires par défaut, car heapq dit quelque chose comme ça. Cependant, ce n'est pas le cas et il existe une file d'attente appropriée .PriorityQueue (). Cependant, bien qu'il y en ait, il semble que cela ne signifie pas que le processus de mise à jour peut être effectué immédiatement en utilisant ce PriorityQueue (). De plus, compte tenu de ce qui est écrit sur cette page, j'étais curieux de savoir à quel point la vitesse de calcul serait meilleure ou pire ~~ Je m'en fiche ~~.
Une file d'attente avec des priorités faites à la main (ci-après dénommée «file d'attente manuelle») se compose d'une liste de tapples appelée (sortkey, (valeur, génération)) et d'un dictionnaire qui contient une génération pour chaque valeur. La suppression est une image qui n'est pas réellement effectuée comme décrit ci-dessus, mais est effectuée par marquage, mais elle est contrôlée en enregistrant le numéro de dernière génération dans le dictionnaire et en n'utilisant pas les dernières données. Je vais. De plus, étant donné que les performances de recherche se détériorent lorsque les éléments sont accumulés, la suppression des données + la reconstruction du tas doivent être effectuées de manière garbage collection. En ce qui concerne le timing du "garbage collection" ici, j'ai décidé de le garder comme une constante m appropriée, et de le reconstruire lorsque le nombre d'éléments (le nombre des parenthèses les plus à l'extérieur du taple compté comme 1) dépasse m. Etc.
Dans ce design "hand cue",
--push → heapq.heappush () pour mettre à jour le dictionnaire, et si la taille dépasse m, re-tas uniquement avec la dernière génération
Je vais le faire comme ça. L'accessibilité aléatoire aux éléments de la file d'attente est quelque chose dont nous ne nous soucions pas pour l'instant. Si vous donnez une valeur au dictionnaire, il utilisera plus de mémoire, mais en théorie, vous pouvez y accéder de manière aléatoire.
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: #Reconstruire le tas
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)
Cela permet de "remplacer" la valeur correspondant à la même valeur de la même manière que celle décrite dans la conception.
Comparez avec Queue.PriorityQueue ().
Pour le moment, effectuez l'initialisation suivante.
initialize.py
#Générer une séquence aléatoire de 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__())
résultat push
('push:Queue', '0:00:00.350000')
('push:Heap', '0:00:00.086000')
('push:TeQ', '0:00:00.137000')
Ça ressemble à ça. TeQ> Heap car il existe de nombreuses comparaisons, mais c'est beaucoup plus rapide que 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__())
résultat pop
('pop:Queue', '0:00:00.484000')
('pop:Heap', '0:00:00.214000')
('pop:TeQ', '0:00:00.299000')
Ça ressemble à ça. C'est moins différent que push, mais c'est toujours la même tendance. En fait, je voulais jouer avec M en changeant le degré de duplication, mais j'ai réalisé que cela n'avait pas beaucoup de sens pour Queue et heapq, alors j'ai décidé de faire une comparaison dans la queue de la main. Lors de la comparaison avec un signal autre que manuel http://stackoverflow.com/questions/9969236/how-to-implement-priority-queues-in-python Cela semblait bon de le comparer à quelque chose, mais je l'ai rendu inférieur.
initializeA.py
#Générer une séquence aléatoire de 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__())
Résultat 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')
La raison pour laquelle 20 pops plus rapides est que 20 * 40000 et 10 * 40000 se chevauchent, de sorte qu'il se retrouve dans le même état. .. .. HM.
initializeB.py
#Générer une séquence aléatoire de 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__())
Résultat 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')
Même après avoir essayé plusieurs fois, cette tendance ne change pas grand-chose. Pourquoi. Même si l'ordre est modifié, 20 reste extrêmement plus rapide que 10. HM. .. ..
J'ai l'impression que je n'ai pas à faire l'équivalent de la réindexation ou du ramassage des ordures.
Recommended Posts