TypeError: '<' not supported between instances of 'Nod' and 'Nod'
Ai pus în heapq tupluri (prioritate, obiect), iar două elemente au aceeași prioritate, așa că heapq a încercat să compare obiectele, care nu știu să se compare. Adaugă un contor unic între ele: (prioritate, contor, obiect).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
heapq păstrează elementele ordonate comparându-le cu <. Tuplurile se compară element cu element: dacă primele valori sunt egale, se compară a doua valoare, și tot așa. Când pui (distanta, nod) și două intrări au aceeași distanță, Python ajunge să compare nod < nod. Pentru numere și texte merge, dar obiectele unei clase proprii (Nod, NodArbore, Comanda) nu au operatorul < definit, de unde mesajul.
Eroarea apare doar când există egalități de prioritate, deci poate lipsi pe teste mici și apare pe date reale. În Dijkstra, la interclasarea a k liste sortate (cu noduri de listă înlănțuită) sau la planificarea de sarcini, egalitățile sunt foarte frecvente.
Reparația standard este un contor unic pus între prioritate și obiect: (prioritate, i, obiect). Contorul nu se repetă niciodată, deci comparația se oprește la el. Bonus: la egalitate de prioritate, elementele ies în ordinea în care au fost adăugate.
De ce apare: cauzele frecvente
1Prioritate egală, obiecte necomparabile
import heapq
heap = []
for nod in capete:
heapq.heappush(heap, (nod.val, nod))import heapq
heap = []
for i, nod in enumerate(capete):
heapq.heappush(heap, (nod.val, i, nod))Contorul i e diferit pentru fiecare intrare, deci la valori egale comparația se oprește la el și nu ajunge la obiecte.
2Dicționare în heap
heapq.heappush(heap, (comanda['termen'], comanda))heapq.heappush(heap, (comanda['termen'], comanda['id'], comanda))Nici dicționarele nu se compară cu <. Orice câmp unic (id, contor) pus înainte rezolvă egalitățile.
3Alternativa: definește comparația în clasă
class Sarcina:
def __init__(self, prioritate):
self.prioritate = prioritateclass Sarcina:
def __init__(self, prioritate):
self.prioritate = prioritate
def __lt__(self, alta):
return self.prioritate < alta.prioritateCu __lt__ definit, obiectele pot fi puse direct în heap. E util când ordinea ține de obiect, dar contorul e mai simplu în algoritmi.
Repară eroarea, direct în pagină
Funcția interclaseaza(liste) unește mai multe liste înlănțuite sortate într-una singură, folosind un heap. Când două liste au aceeași valoare la început, codul dă TypeError: '<' not supported between instances of 'Nod' and 'Nod'. Repar-o ca să afișeze [1, 1, 2, 3, 4, 4, 5, 6] și [].
import heapq
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def construieste(valori):
cap = None
for v in reversed(valori):
cap = Nod(v, cap)
return cap
def interclaseaza(liste):
heap = []
for cap in liste:
if cap:
heapq.heappush(heap, (cap.val, cap))
rezultat = []
while heap:
val, nod = heapq.heappop(heap)
rezultat.append(val)
if nod.urm:
heapq.heappush(heap, (nod.urm.val, nod.urm))
return rezultat
print(interclaseaza([construieste([1, 4, 5]), construieste([1, 3, 4]), construieste([2, 6])]))
print(interclaseaza([]))[1, 1, 2, 3, 4, 4, 5, 6] []
Indiciu
Pune între valoare și nod un număr care nu se repetă niciodată.
Reparația
import heapq
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def construieste(valori):
cap = None
for v in reversed(valori):
cap = Nod(v, cap)
return cap
def interclaseaza(liste):
heap = []
contor = 0
for cap in liste:
if cap:
heapq.heappush(heap, (cap.val, contor, cap))
contor += 1
rezultat = []
while heap:
val, _, nod = heapq.heappop(heap)
rezultat.append(val)
if nod.urm:
heapq.heappush(heap, (nod.urm.val, contor, nod.urm))
contor += 1
return rezultat
print(interclaseaza([construieste([1, 4, 5]), construieste([1, 3, 4]), construieste([2, 6])]))
print(interclaseaza([]))De ce merge
Primele două liste încep amândouă cu 1, deci heap-ul compara (1, nod_a) cu (1, nod_b): prima valoare e egală, așa că trecea la noduri, iar clasa Nod nu are <. Cu (val, contor, nod) contorul e unic, deci comparația se oprește mereu înainte de nod. Fiecare push primește un contor nou. Complexitatea rămâne O(N log k), unde N e numărul total de noduri și k numărul de liste.
Alte forme ale mesajului
TypeError: '<' not supported between instances of 'dict' and 'dict'TypeError: '<' not supported between instances of 'NodArbore' and 'NodArbore'TypeError: '<' not supported between instances of 'str' and 'int'
Cum o eviți pe viitor
Când pui în heap altceva decât numere sau texte, folosește din start forma (prioritate, contor, obiect), cu un contor global (itertools.count()) sau cu indicele din enumerate. Testează cu date care au prioritate egală, nu doar cu valori distincte: acolo apare eroarea. Contorul are și avantajul că face ordinea de ieșire stabilă și previzibilă.
Întrebări frecvente
De ce eroarea apare doar uneori?
Obiectele sunt comparate doar când prioritățile sunt egale. Pe teste cu valori distincte, comparația se oprește la primul element al tuplului și nu ajunge niciodată la obiecte.
La Dijkstra cu noduri ca texte am nevoie de contor?
Nu, (distanta, 'A') se compară corect, pentru că textele se pot compara. Contorul e necesar doar când al doilea element nu suportă <, de exemplu obiecte, dicționare sau None.
Erori înrudite
IndexError: index out of range la heapq.heappop heapq.heappop(heap) pe un heap gol aruncă IndexError: index out of range (fără „list”). Verifică while heap: sau if heap: înainte să scoți, iar la „cele mai mari k” nu scoate de mai multe ori decât elemente ai. AttributeError: 'NoneType' object has no attribute 'stanga' Funcția recursivă pe arbore a coborât într-un copil care nu există (None) și a cerut .stanga sau .val. Pune cazul de bază la început: if nod is None: return 0 (sau valoarea potrivită), înainte de orice acces la atributele nodului. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
