Quand je faisais de la programmation de compétition et que j'essayais d'implémenter Dijkstra en Python, je voulais que heapq soit trié par distance en insérant quelque chose comme ("nom vertical", distance), mais j'étais un peu inquiet du comportement à ce moment-là. C'est un article mémo que je viens de confirmer.
Je me suis demandé si quelque chose comme un opérateur personnalisé pouvait être mis en place, mais cela ralentit généralement si je le fais moi-même, donc je voulais l'éviter autant que possible.
Je pense que c'est une spécification heapq ou une spécification d'opérateur de comparaison Python, mais je vais la résumer car c'est un gros problème.
Si vous plongez la liste dans heapq, ** Ordre croissant du premier élément → Ordre croissant du deuxième élément **. Il semble que l'évaluation de chaque élément se fasse indépendamment, il est donc normal de mélanger des nombres et des chaînes de caractères.
En bref
[[1,4],[2,0],[0,1],[0,3]]
↓
[[0,1],[0,3],[1,4],[2,0]]
Ce sera comme.
import heapq
import random
a = []
heapq.heapify(a)
for i in range(5):
heapq.heappush(a,[random.randint(0,10) for i in range(2)])
while a:
print(heapq.heappop(a))
[0, 10]
[2, 7]
[2, 7]
[2, 10]
[5, 0]
for i in range(5):
heapq.heappush(a,[random.randint(0,10),chr(random.randint(97,97+26))])
while a:
print(heapq.heappop(a))
[0, 'k']
[4, 'd']
[4, 'l']
[5, 'c']
[7, 'o']
c'est tout. J'aime Python parce que ça me fait du bien, mais je n'aime pas ça parce que j'ai parfois des accidents (contradiction).
Recommended Posts