[파이썬] TypeError: < not supported

파이썬에서 힙(heap)이나 우선순위 큐(PriorityQueue)를 사용하다 보면 다음과 같은 에러를 만날 수 있습니다.

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

이번 포스팅에서는 위 에러를 해결하는 방법에 대해서 알아보록 하겠습니다.

객체 정렬 기준

힙과 우선순위 내부적으로 이진 트리를 이용해서 데이터를 정렫된 상태로 유지하고 있습니다. 그런데 이 정렬이라는 게 가능하려면 원소 간의 대소 비교가 가능해야합니다. 예를 들어, 숫자나 문자와 같은 기본형 데이터는 대소 비교가 간단합니다. 1보다 2가 크고, a보다 b가 크다는 것은 일반적으로 알려진 사실이기 때문에 자료구조에게 알려주지 않더라도 됩니다.

하지만 객체를 힙과 우선순위 큐에 추가할 경우에는 정렬의 기준이 무엇인지, 즉 어떻게 대소 비교를 해야할지를 명시적으로 알려줘야 합니다.

에러 발생 원인

먼저 구제적으로 어떤 상황에서 에러가 발생하는지 보기 위해, 다음과 같이 과일을 표현하기 위한 클래스를 작성합니다.

class Fruit:
    def __init__(self, name, price):
        self.name = name
        self.price = price

그리고 다음과 같이 PriorityQueue(우선순위 큐) 안에 과일 객체를 추가해봅니다.

from queue import PriorityQueue

fruit1 = Fruit("Apple", 300)
fruit2 = Fruit("Banana", 100)

que = PriorityQueue()
que.put(fruit1)
que.put(fruit2)  # TypeError: '<' not supported between instances of 'Fruit' and 'Fruit'

그러면 첫 번째 객체를 추가할 때는 문제가 없는데 두 번째 객체를 추가할 때 에러가 발생하는 것을 알 수 있습니다. 데이터를 정렬된 상태로 보관해야하는 우선순위 큐는 두 번째 객체가 추가될 때 첫 번째 객체와 대소 비교를 시도합니다. 하지만 우선순위 큐는 이 과일 객체 간에 어떻게 대소 비교를 해야하는지 모르기 때문에 에러가 발생시키고 맙니다.

파이썬의 PriorityQueue 클래스를 통해 우선순위 큐를 사용하는 자세한 방법은 관련 포스팅를 참고 바랍니다.

heapq 모듈을 사용할 때도 마찬가지 동일한 문제가 발생합니다.

from heapq import heapify

heap = [fruit1, fruit2]
heapify(heap)  # TypeError: '<' not supported between instances of 'Fruit' and 'Fruit'

파이썬의 heapq 내장 모듈을 통해 힙을 사용하는 자세한 방법은 관련 포스팅를 참고 바랍니다.

대소비교 메소드 추가

가장 간단한 해결 방법은 객체 간 대소비교가 가능하도록 __lt__() 메서드를 클래스에 추가해주는 것입니다. less than의 약자를 이름으로 갖는 __lt__() 메서드는 객체 자신과 다른 객체를 대소 비교 결과를 리턴해야 합니다. 힙과 우선순위 큐는 내부적으로 < 연산자로 대소비교를 하며, 이 __lt__() 메서드는 그 때 호출이 됩니다.

class Fruit:
    def __init__(self, name, price):
        self.name = name
        self.price = price

    def __lt__(self, other):
        return self.price < other.price

위와 같이 Fruit 클래스에 __lt__() 메서드를 추가하면, price 필드를 기준으로 정렬 기준으로 정의하였기 때문에, 가격이 제일 싼 과일부터 비싼 순으로 객체들이 정렬될 것입니다.

Wrapper 클래스 활용

클래스에 수정을 가하기 어려운 상황이라면 Wrapper 클래스 사용할 수 있습니다. Wapper 클래스의 생성자는 과일 클래스를 인자로 받고, __lt__() 메서드를 대신 구현해줘야 합니다.

class Wrapper:
    def __init__(self, fruit):
        self.fruit = fruit

    def __lt__(self, other):
        return self.fruit.price < other.fruit.price

힙이나 우선순위 큐에 객체를 추가 전에, 이 Wrapper 클래스 한 번 감싸줘야 합니다. 그리고 힙이나 우선순위 큐에서 제거한 후에는, 반대로 Wrapper 클래스에서 본래 객체를 꺼낸 후에 사용하면 됩니다.

from queue import PriorityQueue

fruit1 = Fruit("Apple", 300)
fruit2 = Fruit("Banana", 100)

que = PriorityQueue()
que.put(Wrapper(fruit1))
que.put(Wrapper(fruit2))

print(que.get().fruit.name)  # Banana
print(que.get().fruit.name)  # Apple