...
Eroare Algoritmi și structuri de date · Arbori și heap-uri

TypeError: '<' not supported between instances of 'Nod' and 'Nod'

Pe scurt

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

Greșit
PYTHON
import heapq
heap = []
for nod in capete:
    heapq.heappush(heap, (nod.val, nod))
Corect
PYTHON
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

Greșit
PYTHON
heapq.heappush(heap, (comanda['termen'], comanda))
Corect
PYTHON
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ă

Greșit
PYTHON
class Sarcina:
    def __init__(self, prioritate):
        self.prioritate = prioritate
Corect
PYTHON
class Sarcina:
    def __init__(self, prioritate):
        self.prioritate = prioritate
    def __lt__(self, alta):
        return self.prioritate < alta.prioritate

Cu __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ă tu

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 [].

Codul care dă eroarea
PYTHON
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([]))
După reparație, programul afișează
[1, 1, 2, 3, 4, 4, 5, 6]
[]
Indiciu

Pune între valoare și nod un număr care nu se repetă niciodată.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.