heapq z niestandardowym predykatem porównania

82

Próbuję zbudować stertę z niestandardowym predykatem sortowania. Ponieważ wartości wchodzące w to są typu „zdefiniowanego przez użytkownika”, nie mogę zmodyfikować ich wbudowanego predykatu porównania.

Czy jest sposób na zrobienie czegoś takiego:

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

Albo jeszcze lepiej, mógłbym zawinąć funkcje heapq we własnym kontenerze, więc nie muszę dalej przekazywać predykatu.

vsekhar
źródło

Odpowiedzi:

120

Zgodnie z dokumentacją heapq , sposobem dostosowania kolejności sterty jest ustawienie każdego elementu na stercie jako krotki, przy czym pierwszy element krotki to taki, który akceptuje zwykłe porównania w Pythonie.

Funkcje w module heapq są nieco kłopotliwe (ponieważ nie są zorientowane obiektowo) i zawsze wymagają, aby nasz obiekt sterty (lista sterty) był jawnie przekazany jako pierwszy parametr. Możemy upiec dwie pieczenie na jednym ogniu, tworząc bardzo prostą klasę opakowującą, która pozwoli nam określić keyfunkcję i przedstawić stertę jako obiekt.

Poniższa klasa przechowuje wewnętrzną listę, w której każdy element jest krotką, której pierwszym składnikiem jest klucz, obliczany w czasie wstawiania elementu za pomocą keyparametru, przekazywany w instancji Heap:

# -*- 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]

(Dodatkową self.indexczęścią jest uniknięcie kolizji, gdy oszacowana wartość klucza jest remisem, a przechowywana wartość nie jest bezpośrednio porównywalna - w przeciwnym razie heapq może zawieść z TypeError)

jsbueno
źródło
4
Bardzo dobrze! Możesz nawet pójść dalej i użyć trójek (self.key (item), id, item), gdzie id może być liczbą całkowitą obsługiwaną jako atrybut klasy i zwiększaną po każdym wypchnięciu. W ten sposób unikniesz zgłaszania wyjątku, gdy key (item1) = key (item2). Ponieważ klucze byłyby wyjątkowe.
zeycus
4
Właściwie próbowałem wepchnąć to (lub coś opartego na tym) do standardowego biblioteki Pythona, ale sugestia została odrzucona.
jsbueno
1
szkoda, pasuje do zorientowanego obiektowo stylu większości funkcji Pythona, a kluczowy argument zapewnia dodatkową elastyczność.
zeycus
Użyłem listy zamiast krotki dla np. [Self.key (item), id, item] i działa dobrze, o ile pierwszy indeks jest kluczem.
Deepak Yadav
5
To się nie powiedzie, jeśli elementy nie są porównywalne i istnieją powiązania w kluczowych wartościach. Umieściłbym id(item)jako środkowy element krotki, aby zerwać więzi.
Georgi Yanchev
48

Zdefiniuj klasę, w której nadpisujemy __lt__()funkcję. Zobacz przykład poniżej (działa w Pythonie 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]

Fanchen Bao
źródło
4
Wydaje się, że to zdecydowanie najczystsze rozwiązanie!
Roymunson
Całkowicie zgadzam się z dwoma poprzednimi komentarzami. Wydaje się, że jest to lepsze, czystsze rozwiązanie dla Pythona 3.
Chiraz BenAbdelkader
Również tutaj jest bardzo podobne rozwiązanie do podobnego pytania: stackoverflow.com/questions/2501457/…
Chiraz BenAbdelkader
1
Przetestowałem to za pomocą __gt__zamiast tego i działa również. Dlaczego nie ma znaczenia, której magicznej metody używamy? Nie mogę znaleźć niczego w heapqdokumentacji. Może ma to związek z tym, jak Python ogólnie wykonuje porównania?
Josh Clark
1
Dokonując porównania w programie heapq, Python szuka __lt__()najpierw. Jeśli nie jest zdefiniowany, będzie szukał __gt__(). Jeśli żadne z nich nie jest zdefiniowane, rzuca TypeError: '<' not supported between instances of 'Node' and 'Node'. Można to potwierdzić, definiując zarówno __lt__()i __gt__(), jak i umieszczając w nich instrukcję print i dokonując __lt__()zwrotu NotImplemented.
Fanchen Bao
19

Dokumentacja heapq sugeruje, że elementy sterty mogą być krotkami, w których pierwszy element jest priorytetem i definiuje kolejność sortowania.

Bardziej istotne dla twojego pytania jest jednak to, że dokumentacja zawiera dyskusję z przykładowym kodem, w jaki sposób można zaimplementować własne funkcje opakowujące heapq, aby poradzić sobie z problemami stabilności sortowania i elementami o równym priorytecie (między innymi).

W skrócie, ich rozwiązanie polega na tym, aby każdy element w heapq był potrójny z priorytetem, liczbą wpisów i elementem do wstawienia. Liczba pozycji gwarantuje, że elementy o tym samym priorytecie a posortowane w kolejności, w jakiej zostały dodane do heapq.

srgerg
źródło
To jest poprawne rozwiązanie, zarówno heappush, jak i heappushpop działają bezpośrednio z krotkami
daisy
2

Ograniczeniem obu odpowiedzi jest to, że nie pozwalają one na traktowanie krawatów jako remisów. W pierwszej więzi są rozwiązywane przez porównywanie elementów, w drugiej przez porównywanie kolejności wprowadzania. Szybciej jest po prostu pozwolić, aby krawaty były wiązaniami, a jeśli jest ich dużo, może to mieć duże znaczenie. Na podstawie powyższego i dokumentacji nie jest jasne, czy można to osiągnąć w heapq. Wydaje się dziwne, że heapq nie akceptuje klucza, podczas gdy funkcje wyprowadzone z niego w tym samym module tak.
PS: Jeśli klikniesz link w pierwszym komentarzu ("możliwy duplikat ..."), pojawi się kolejna sugestia zdefiniowania pliku, która wydaje się rozwiązaniem.

bbphd
źródło
2
setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

Użyj tego do porównania wartości obiektów w heapq

Ritika Gupta
źródło