사용자 지정 비교 술어가 포함된 힙큐

사용자 지정 비교 술어가 포함된 힙큐

사용자 지정 정렬 술어로 힙을 구축하려고 합니다.입력되는 값이 "사용자 정의" 유형이기 때문에 기본 제공되는 비교 술어를 수정할 수 없습니다.

다음과 같은 작업을 수행할 수 있는 방법이 있습니까?

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

아니면 더 좋게도, 내가 포장해 줄 수도 있습니다.heapq술어를 계속 전달할 필요가 없도록 내 컨테이너에 기능합니다.

힙큐 문서에 따르면 힙 순서를 사용자 지정하는 방법은 힙의 각 요소를 튜플로 만드는 것이며 첫 번째 튜플 요소는 일반적인 파이썬 비교를 허용하는 것입니다.

힙큐 모듈의 함수는 객체 지향적이지 않기 때문에 약간 번거로우며 항상 힙 객체(히프화된 목록)를 첫 번째 매개 변수로 명시적으로 전달해야 합니다.우리는 매우 간단한 포장지 클래스를 만들어서 우리가 특정할 수 있게 함으로써 두 마리 토끼를 죽일 수 있습니다.keyfunction, 그리고 힙을 객체로 표시합니다.

아래 클래스는 각 요소가 튜플이고 첫 번째 구성원은 키이며 다음을 사용하여 요소 삽입 시간에 계산되는 내부 목록을 유지합니다.key힙 인스턴스화 시 전달된 매개 변수:

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
    def __init__(self, initial=None, key=lambda x:x):
        self.key = key
        self.index = 0
        if initial:
            self._data = [(key(item), i, item) for i, item in enumerate(initial)]
            self.index = len(self._data)
            heapq.heapify(self._data)
        else:
            self._data = []

    def push(self, item):
        heapq.heappush(self._data, (self.key(item), self.index, item))
        self.index += 1

    def pop(self):
        return heapq.heappop(self._data)[2]

()self.indexpart는 평가된 키 값이 무승부이고 저장된 값이 직접 비교할 수 없을 때 충돌을 방지하는 것입니다. 그렇지 않으면 heapq가 TypeError와 함께 실패할 수 있습니다.)

클래스를 정의합니다. 클래스를 재정의합니다.__lt__()기능. 아래 예제 (Python 3.7에서 아래 예제 참조(Python 3.7에서 작동):

import heapq

class Node(object):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f'Node value: {self.val}'

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

heap = [Node(2), Node(0), Node(1), Node(4), Node(2)]
heapq.heapify(heap)
print(heap)  # output: [Node value: 0, Node value: 2, Node value: 1, Node value: 4, Node value: 2]

heapq.heappop(heap)
print(heap)  # output: [Node value: 1, Node value: 2, Node value: 2, Node value: 4]

힙큐 문서는 힙 요소가 첫 번째 요소가 우선 순위이고 정렬 순서를 정의하는 튜플일 수 있음을 암시합니다.

그러나 이 문서에는 정렬 안정성 문제와 (다른 문제 중) 동등한 우선 순위를 가진 요소를 처리하기 위해 자체 힙큐 래퍼 함수를 어떻게 구현할 수 있는지에 대한 샘플 코드가 포함되어 있습니다.

간단히 말해서, 그들의 해결책은 힙큐의 각 요소가 우선순위, 엔트리 수 및 삽입할 요소와 함께 세 배가 되도록 하는 것입니다.항목 수를 사용하면 우선 순위가 같은 요소가 순서대로 정렬되어 힙큐에 추가됩니다.

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

힙큐의 개체 값을 비교할 때 사용합니다.

두 답변 모두 넥타이가 넥타이로 취급되는 것을 허용하지 않는다는 것이 한계입니다.첫 번째는 항목을 비교하여 동점을 끊는 것이고, 두 번째는 입력 순서를 비교하여 끊는 것입니다.인연은 그냥 인연으로 두는 것이 빠르고, 인연이 많으면 큰 변화를 가져올 수 있습니다.위의 내용과 문서에 근거하여, 이것이 힙큐(heapq)에서 달성될 수 있는지는 확실하지 않습니다.hapq가 키를 받지 않는 반면, 같은 모듈에서 파생된 함수는 키를 받지 못하는 것이 이상해 보입니다.
추신: 첫번째 댓글의 링크를 따라가면 ("중복 가능..").) 해결책처럼 보이는 le를 정의하자는 또 다른 제안이 있습니다.

python3에서는 사용할 수 있습니다.cmp_to_key부터functools모듈.cpython 소스 코드.

트리플렛의 우선순위 대기열이 필요하다고 가정하고 마지막 속성을 사용하여 우선순위를 지정합니다.

from heapq import *
from functools import cmp_to_key
def mycmp(triplet_left, triplet_right):
    key_l, key_r = triplet_left[2], triplet_right[2]
    if key_l > key_r:
        return -1  # larger first
    elif key_l == key_r:
        return 0  # equal
    else:
        return 1


WrapperCls = cmp_to_key(mycmp)
pq = []
myobj = tuple(1, 2, "anystring")
# to push an object myobj into pq
heappush(pq, WrapperCls(myobj))
# to get the heap top use the `obj` attribute
inner = pq[0].obj

성능 테스트:

환경

python 3.10.2

코드

from functools import cmp_to_key
from timeit import default_timer as time
from random import randint
from heapq import *

class WrapperCls1:
    __slots__ = 'obj'
    def __init__(self, obj):
        self.obj = obj
    def __lt__(self, other):
        kl, kr = self.obj[2], other.obj[2]
        return True if kl > kr else False

def cmp_class2(obj1, obj2):
    kl, kr = obj1[2], obj2[2]
    return -1 if kl > kr else 0 if kl == kr else 1

WrapperCls2 = cmp_to_key(cmp_class2)

triplets = [[randint(-1000000, 1000000) for _ in range(3)] for _ in range(100000)]
# tuple_triplets = [tuple(randint(-1000000, 1000000) for _ in range(3)) for _ in range(100000)]

def test_cls1():
    pq = []
    for triplet in triplets:
        heappush(pq, WrapperCls1(triplet))
        
def test_cls2():
    pq = []
    for triplet in triplets:
        heappush(pq, WrapperCls2(triplet))

def test_cls3():
    pq = []
    for triplet in triplets:
        heappush(pq, (-triplet[2], triplet))

start = time()
for _ in range(10):
    test_cls1()
    # test_cls2()
    # test_cls3()
print("total running time (seconds): ", -start+(start:=time()))

결과.

사용하다list대신에tuple:,:

• 포장지 Cls1 : 16.2ms
• ( Cls1 )__slots__: 9.8ms
• 포장지 Cls2: 8.6ms
• 우선순위 속성을 첫 번째 위치로 이동(사용자 지정 술어를 지원하지 않음): 6.0ms

따라서 이 메서드는 재정의된 사용자 지정 클래스를 사용하는 것보다 약간 빠릅니다.__lt__()과.__slots__기여하다.

단순 및 최근

간단한 해결책은store entries as a list of tuples각 튜플에 대해 원하는 순서로 우선순위를 정의합니다. 튜플 내의 각 항목에 대해 다른 순서가 필요하다면 내림차순에 대해 음수로 만듭니다.

이 항목의 공식 힙큐 파이썬 문서를 참조하십시오. 우선순위 대기열 구현 참고

간단한 속임수:

다음과 같은 (이름, 나이) 목록을 가지고 있다고 가정합니다.

a = [('Tim',4), ('Radha',9), ('Rob',7), ('Krsna',3)]

사용자 지정 비교 항목을 모두 작성하는 대신 큐에 넣기 직전에 튜플의 내용 순서를 뒤집으면 나이에 따라 연령에 따라 이 목록을 정렬하려면 사용자 지정 비교 항목을 추가해야 합니다.이는 힙큐.heappush()가 기본적으로 튜플의 첫 번째 요소를 기준으로 정렬되기 때문입니다.다음과 같은 경우:

import heapq
heap = []
heapq.heapify(heap)
for element in a:
    heapq.heappush(heap, (element[1],element[0]))

이렇게 하면 사용자 지정 비교기를 엉망으로 쓸 필요가 없을 경우 간단한 조작이 가능합니다.

마찬가지로 기본적으로 오름차순으로 값을 정렬합니다.나이순으로 정렬하려면 내용을 뒤집어서 튜플의 첫번째 요소 값을 음수로 만듭니다.

import heapq
heap = []
heapq.heapify(heap)
for element in a:
    heapq.heappush(heap, (-element[1],element[0]))

언급URL : https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate