Heapq mit benutzerdefiniertem Vergleichsprädikat

80

Ich versuche, einen Heap mit einem benutzerdefinierten Sortierprädikat zu erstellen. Da die darin enthaltenen Werte vom Typ 'Benutzerdefiniert' sind, kann ich das integrierte Vergleichsprädikat nicht ändern.

Gibt es eine Möglichkeit, etwas zu tun wie:

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

Oder noch besser, ich könnte die Heapq-Funktionen in meinen eigenen Container packen, damit ich das Prädikat nicht weiter übergeben muss.

vsekhar
quelle
1
Mögliches Duplikat von stackoverflow.com/questions/679731/min-heap-in-python
Rajendran T
Mögliches Duplikat von Wie kann Heapq den Heap eines bestimmten Attributs bewerten?
Cristian Ciupitu

Antworten:

118

Gemäß der Heapq-Dokumentation besteht die Möglichkeit, die Heap-Reihenfolge anzupassen, darin, dass jedes Element auf dem Heap ein Tupel ist, wobei das erste Tupelelement eines ist, das normale Python-Vergleiche akzeptiert.

Die Funktionen im Heapq-Modul sind etwas umständlich (da sie nicht objektorientiert sind) und erfordern immer, dass unser Heap-Objekt (eine Heapified-Liste) explizit als erster Parameter übergeben wird. Wir können zwei Fliegen mit einer Klappe schlagen, indem wir eine sehr einfache Wrapper-Klasse erstellen, mit der wir eine keyFunktion angeben und den Heap als Objekt präsentieren können.

Die folgende Klasse führt eine interne Liste, in der jedes Element ein Tupel ist, dessen erstes Mitglied ein Schlüssel ist, der zum Zeitpunkt des Einfügens des Elements unter Verwendung des keyParameters berechnet wird und bei der Heap-Instanziierung übergeben wird:

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

(Der zusätzliche self.indexTeil besteht darin, Konflikte zu vermeiden, wenn der ausgewertete Schlüsselwert ein Unentschieden ist und der gespeicherte Wert nicht direkt vergleichbar ist. Andernfalls könnte heapq mit TypeError fehlschlagen.)

jsbueno
quelle
4
Sehr schön! Sie können sogar noch weiter gehen und Tripel (self.key (item), id, item) verwenden, wobei id eine Ganzzahl sein kann, die als Klassenattribut behandelt und nach jedem Push inkrementiert wird. Auf diese Weise vermeiden Sie die Ausnahme, die ausgelöst wird, wenn Schlüssel (Element1) = Schlüssel (Element2). Weil Schlüssel einzigartig wären.
Zeycus
3
Ich habe tatsächlich versucht, dies (oder etwas, das darauf basiert) in Pythons stdlib zu verschieben, und der Vorschlag wurde abgelehnt.
Jsbueno
1
Schade, passt zum objektorientierten Stil der meisten Python-Funktionen, und das Hauptargument bietet zusätzliche Flexibilität.
Zeycus
Ich habe list anstelle von tuple für zB [self.key (item), id, item] verwendet und es funktioniert einwandfrei, solange der erste Index der Schlüssel ist.
Deepak Yadav
5
Dies würde fehlschlagen, wenn die Elemente nicht vergleichbar sind und die Schlüsselwerte miteinander verknüpft sind. Ich würde id(item)als mittleres Element des Tupels setzen, um Krawatten zu brechen.
Georgi Yanchev
37

Definieren Sie eine Klasse, in der die __lt__()Funktion überschrieben wird. Siehe Beispiel unten (funktioniert in 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]

Fanchen Bao
quelle
3
Dies scheint bei weitem die sauberste Lösung zu sein!
Roymunson
Stimmen Sie den beiden vorherigen Kommentaren absolut zu. Dies scheint eine bessere und sauberere Lösung für Python 3 zu sein.
Chiraz BenAbdelkader
Hier ist auch eine sehr ähnliche Lösung für eine ähnliche Frage: stackoverflow.com/questions/2501457/…
Chiraz BenAbdelkader
Ich habe dies __gt__stattdessen mit getestet und es funktioniert auch. Warum spielt es keine Rolle, welche magische Methode wir verwenden? Ich kann nichts in heapqder Dokumentation finden. Vielleicht hängt es damit zusammen, wie Python Vergleiche im Allgemeinen durchführt?
Josh Clark
Beim Vergleich in heapqsucht Python __lt__()zuerst nach. Wenn es nicht definiert ist, wird es suchen __gt__(). Wenn beides nicht definiert ist, wird geworfen TypeError: '<' not supported between instances of 'Node' and 'Node'. Dies kann bestätigt werden, indem sowohl __lt__()als auch definiert __gt__()wird, jeweils eine Druckanweisung eingefügt wird und eine __lt__()Rückgabe erfolgt NotImplemented.
Fanchen Bao
19

Die Heapq-Dokumentation schlägt vor, dass Heap-Elemente Tupel sein können, bei denen das erste Element die Priorität hat, und definiert die Sortierreihenfolge.

Relevanter für Ihre Frage ist jedoch, dass die Dokumentation eine Diskussion mit Beispielcode enthält, wie man seine eigenen Heapq-Wrapper-Funktionen implementieren kann, um die Probleme der Sortierstabilität und Elemente mit gleicher Priorität (unter anderem) zu lösen.

Kurz gesagt, ihre Lösung besteht darin, dass jedes Element im Heapq ein Tripel mit der Priorität, der Anzahl der Einträge und dem einzufügenden Element ist. Die Anzahl der Einträge stellt sicher, dass Elemente mit derselben Priorität in der Reihenfolge sortiert werden, in der sie dem Heapq hinzugefügt wurden.

srgerg
quelle
Dies ist die richtige Lösung, sowohl Heappush als auch Heappushpop arbeiten direkt mit Tupeln
Daisy
2

Die Einschränkung bei beiden Antworten besteht darin, dass sie nicht zulassen, dass Bindungen als Bindungen behandelt werden. Im ersten Fall werden Bindungen durch Vergleichen von Elementen unterbrochen, im zweiten Fall durch Vergleichen der Eingabereihenfolge. Es ist schneller, Krawatten einfach Krawatten sein zu lassen, und wenn es viele davon gibt, könnte dies einen großen Unterschied machen. Aufgrund der obigen Ausführungen und der Dokumente ist nicht klar, ob dies in heapq erreicht werden kann. Es scheint seltsam, dass heapq keinen Schlüssel akzeptiert, während von ihm im selben Modul abgeleitete Funktionen dies tun.
PS: Wenn Sie dem Link im ersten Kommentar folgen ("mögliches Duplikat ..."), gibt es einen weiteren Vorschlag, le zu definieren, der wie eine Lösung erscheint.

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

Verwenden Sie diese Option, um Werte von Objekten in heapq zu vergleichen

Ritika Gupta
quelle