HashSets bzw. Python Dictionaries

Teil 3 einer Serie über performantes Programmieren mit Bezug auf Operations Research. In diesem Beitrag geht es um HashSets bzw. Dictionaries und der mit diesen verbundene geringe Suchaufwand.

Ausgangslage

In vielen Situationen müssen wir prüfen, ob sich ein Element in irgendeiner Form von Datenstruktur befindet. Mögliche Anwendungsszenarien sind die nachfolgenden:

• Prüfung, ob ein Knoten (bzw. eine Teillösung) in einem Branch-and-Bound Baum bereits erzeugt wurde
• Befindet sich ein Kunde bereits in einer Tour?
• Wurde ein Job bereits berücksichtigt?
• Ist ein Move innerhalb einer Tabusuche tabu?

Für die zuvor genannten Szenarien entwerfen wir im Rahmen der objektorientierten Programmierung oftmals eigene Datenkonstrukte (Klassen). Im Gegensatz zu beispielsweise Zahlen, ist nicht sofort klar, Ob zwei Instanzen der selben Klasse identisch sind. Aus diesem Grund verwenden wir nachfolgend den Hash-Wert.

HashWert

Ein Hashwert ist eine eindeutige numerische Darstellung von Daten. Der Hashwert wird normalerweise aus einer beliebigen Anzahl von Daten erstellt, indem eine mathematische Funktion verwendet wird, um den Hashwert zu generieren. Der Hashwert wird dann verwendet, um Daten zu identifizieren und zu vergleichen, ohne auf die tatsächlichen Daten zugreifen zu müssen.

In Python kann die Funktion hash() verwendet werden, um einen Hashwert zu generieren. Wenn ein Objekt gehasht wird, gibt es einen eindeutigen Hashwert zurück, der auf dieses Objekt zeigt.

HashSets / Dictionaries

TL;DR

Mit binärer Suche sinkt der Prüfaufwand hier von maximal 9900 auf log₂(9900), d.h. ca. 11 Prüfungen. Dafür muss die Liste aber gemäß irgendeiner Metrik sortiert sein.

Erläuterung

Diese Suchmethode funktioniert nur bei sortierten Listen. Hierbei ist es unerheblich, ob die Listen nach Zahlen (auf- oder absteigend) sortiert sind, oder einer selbst definierten lexikographischen Sortierung folgen. Eine lexikographische Sortierung ist beispielsweise der Medaillenspiegel bei den olympischen Spielen: eine Goldmedaille ist immer besser als eine beliebige Anzahl Silbermedaillen, eine Silbermedaille ist immmer besser als eine beliebige Anzahl Bronzemedaille. Eine zwei Goldmedaillen sind besser als Eine usw.

Die Idee hierbei ist, dass wir in einer sortierten Liste das Suchintervall, in dem sich der Suchwert befinden müsste, schrittweise eingrenzen können. In jeder Iteration des Verfahrens wird der Wert in der Mitte des aktuellen Suchintervalls (das sich schrittweise verkleinert) betrachtet. Ist dieser Wert kleiner als unser Suchwert, können wir ableiten, dass sich der Suchwert rechts davon befinden muss. Ist der Wert in der Mitte des Suchintervalls größer als der Suchwert, wissen wir, dass sich der Suchwert links von der soeben ermittelten Mitte befindet. Wir passen dann die untere- (Wert in der Mitte < Suchwert) bzw. obere (Wert in der Mitte > Suchwert) Grenze des Suchintervalls an und führen anschließend eine weitere Iteration durch. Für den Fall, dass der Wert in der Mitte genau unserem Suchwert entspricht stoppt das Verfahren. Entspricht die linke Seite des Suchintervalls der rechten Seite, wissen wir, dass wir den Suchwert nicht gefunden haben. Der formale Ablauf des Verfahrens ist im Folgenden dargestellt.

funktion binäre_suche(liste, suchwert):
    # Gibt den Index des Suchwerts in der Liste zurück. Ist dieser
    # nicht enhalten, wird -1 zurück gegeben
    index = -1
    links = 0 # erster Wert in der Liste
    rechts = len(liste)-1 # letzter Wert in der Liste

    solange links <= rechts:
        mitte = aufrunden((rechts+links)/2)
        wenn liste[mitte] == suchwert:
            return mitte

        wenn liste[mitte] < suchwert:
            # Die Mitte des Betrachungsintervalls ist kleiner als der Suchwert
            links = mitte + 1
        sonst:
            # Die Mitte des Betrachungsintervalls ist größer als der Suchwert
            rechts = mitte - 1

    return index

Wir gehen nachfolgend davon aus, dass wir die Zahlen 0 bis 9 und 9909 bis 9999 aus der Liste entfernt hätten und jetzt nach der Position der Zahl 9800 suchen möchten. In diesem Fall ist das erste Suchintervall [10,9909]. Die nachfolgende Tabelle zeigt die Iterationen des Verfahrens.

HashSets

TL;DR

Mit einem HashSet sinkt der Prüfaufwand von maximal 9900 auf 1. Dafür muss aber jedes Element eindeutig mit einem Hash-Wert identifizierbar sein. In den meisten Programmiersprachen entspricht die Iterationsreihenfolge der Elemente im HashSet nicht der Hinzufügereihenfolge.

Erläuterung

lorem ipsum