Bei sortierten Daten liegt die Suchlösung auf der Hand. Bei unsortierten Daten sind sinnvolle Optionen Sortieren, Suchen oder nur lineare Suchen.
Bei dieser Frage geht es darum, was zu tun ist, wenn die Daten etwas sortiert sind, aber nicht neu organisiert werden können (Schreibvorgänge erfordern das Löschen von Sektoren, und Sektoren passen nicht in den RAM).
die Details:
Datensätze werden nacheinander mit einem Zeitstempel protokolliert . Die Zeitstempeluhr wird jedoch von Zeit zu Zeit für eine Weile auf Epoche zurückgesetzt, bevor sie synchronisiert wird, oder sie wird aufgrund der Sommerzeit usw. einfach zurückgesetzt.
Das Suchergebnis sollte der Protokolldatensatz sein, dessen Zeitstempel der angegebenen Zeit am nächsten kommt. Während einer binären Suche nach Datensätzen zu einem bestimmten Zeitstempel ist es möglich, auf einem Patch nicht zusammenhängender Protokolldaten zu landen und in die falsche Richtung zu schwenken.
Gibt es neben einer brachialen linearen Methode eine Heuristik, die wir hier nutzen können? zB eine Simplex-Suche, die gegen lokale Minima immun ist?
aktualisieren:
Wir können davon ausgehen, dass etwa 95% der Datensätze in sortierter Reihenfolge vorliegen. Etwa 5% (im Baumstamm verstreut) sind die schmutzigen Schluckaufe. Der Beginn des Schluckaufs kann identifiziert werden, wenn der Zeitstempel zeitlich rückwärts geht und einen früheren Stempel als der Beginn des Protokolls hat
quelle
Antworten:
Zusätzliche Annahmen
Diese Antwort basiert auf den folgenden zusätzlichen Annahmen:
Suchalgorithmus
Die Suche ist wirklich in zwei verschiedene Algorithmen unterteilt. Wenn Sie nach einem Protokoll mit einem Zeitstempel suchen, der nach dem Beginn des Protokolls liegt, wissen Sie, dass es im Schluckauf nicht gefunden wird, und verwenden die unten stehende Suche ohne Schluckauf . Wenn Sie vor dem Beginn des Protokolls nach einem Zeitstempel suchen, verwenden Sie stattdessen die Schluckaufsuche . Wenn Sie nicht nach dem Zeitstempel, sondern nach anderen Kriterien suchen, versuchen Sie zuerst die Suche ohne Schluckauf aufgrund der 95% igen Abdeckung und dann die Suche nach Schluckauf, wenn Sie nichts gefunden haben.
Optional können Sie die Suche ohne Schluckauf durch einen Vorverarbeitungsschritt beschleunigen.
Vorverarbeitung (optional)
Wenn möglich, analysieren Sie Ihre Daten vorab mit einer linearen Suche, um die Positionen der Schluckaufdaten herauszufinden. Dies hängt ganz davon ab, ob es möglich ist, diese Bereiche zu speichern. Dies ist möglicherweise möglich, da sie nur 5% Ihrer Protokolle ausmachen (oder auch nicht, in welchem Fall sich die Leistung verschlechtert).
Beachten Sie, dass die entsprechende Datenstruktur jedes Mal aktualisiert werden sollte, wenn Sie neue Protokolle schreiben, oder zumindest in der Lage sein sollte, Ihnen mitzuteilen, bis zu welchem Punkt der Protokolle die Vorverarbeitung durchgeführt wurde.
Suche ohne Schluckauf
Das Durchsuchen der Nicht-Schluckauf-Daten ist über eine Kombination aus binärer und linearer Suche möglich. Sie führen eine normale binäre Suche durch. Wenn Ihr Pivot-Element jedoch vor dem Beginn des Protokolls mit einem Zeitstempel versehen ist, dh das Pivot-Element ein Schluckauf ist, müssen Sie den ersten Protokolleintrag vor dem Pivot-Element ermitteln und als echtes Pivot-Element verwenden Ihrer binären Suche.
Dieser erste Protokolleintrag mit einem Zeitstempel nach dem Beginn des Protokolls wird über eine lineare Suche ausgehend vom Hiccup-Pivot-Element gefunden. Wenn Sie aus der Vorverarbeitung oder inkrementellen Aktualisierungen Ihrer zwischengespeicherten Probleme wissen, wo sich das entsprechende Pivot-Element befindet, können Sie in konstanter Zeit dorthin springen. Wenn Sie die vollständige lineare Suche ausführen mussten, aktualisieren Sie eine Datenstruktur, um zu speichern, dass diese Positionen durch Schluckaufdaten abgedeckt sind, sodass Sie beim nächsten Mal schnell das richtige Pivot-Element ermitteln können.
Schluckauf-Suche
Dies hängt davon ab, ob Sie die Vorverarbeitung durchgeführt haben. Wenn nicht, handelt es sich um eine lineare Suche durch alle Ihre Daten (und Sie können die Vorverarbeitungsteile auch zu diesem Zeitpunkt durchführen). Andernfalls kann Ihre vorverarbeitete Datenstruktur Ihnen die Positionen der Schluckaufdaten mitteilen und Sie können diese direkt durchsuchen, dh eine lineare Suche nur durch die 5% der Schluckaufdaten durchführen.
Performance
Bei einer Suche ohne Probleme mit vollständig vorverarbeiteten Daten erhalten Sie fast die Leistung einer standardmäßigen binären Suche. Anstelle eines einfachen Vergleichs bei jedem Schritt benötigen Sie jedoch einen zusätzlichen Vergleich, um festzustellen, ob Sie auf ein Schluckaufelement stoßen, und wenn ja, benötigen Sie Zugriff auf Ihre Datenstruktur, um das eigentliche Pivot-Element zu finden. Diese zusätzliche Arbeit wird jedoch leicht durch die Tatsache gemildert, dass Sie nicht nur die Hälfte Ihres Datensatzes ausschließen, sondern auch den Schluckauf-Datenteil ausschließen.
Wenn Sie auf die lineare Suche zurückgreifen müssen, verschlechtert sich dies natürlich entsprechend.
Die Schluckaufsuche ist ein schlechter Fall, wenn Sie keine Informationen über vorhandene Schluckaufe haben und alle Daten linear durchsuchen müssen.
Wenn Sie nicht nach einem Zeitstempel suchen, sondern nach einigen anderen Kriterien und ohne einen solchen Protokolleintrag, ist dies der schlimmste Fall. Wenn Sie keine Datenstruktur für die Schluckaufe haben, ist diese langsamer als die lineare Suche, da beide Suchläufe möglicherweise linear die gleichen Schluckaufpositionen scannen (obwohl sie immer noch O (n) ist).
Wenn die Datenstruktur verfügbar und vollständig vorverarbeitet ist, beträgt die Laufzeit im ungünstigsten Fall O (max (log (M) * log (N), M)), wobei M die Menge der Schluckaufdaten ist, die linear durchsucht werden. und vorausgesetzt, Sie können das Ende der Schluckaufdaten bei einer beliebigen Schluckaufposition aus Ihrer Datenstruktur in O (log (M)) nachschlagen.
quelle