Near Sortieralgorithmen - Wann zu verwenden?

Es gibt viele "gierige" Heuristiken, bei denen Sie regelmäßig das Minimum eines Satzes auswählen. Die gierige Heuristik ist nicht perfekt, also selbst wenn Sie das Minimum wählen, werden Sie nicht garantiert die beste endgültige Antwort zu bekommen. In der Meta-Heuristik GRASP wird absichtlich ein zufälliger Fehler eingeführt, sodass Sie mehrere endgültige Lösungen erhalten und den besten auswählen können . In diesem Fall wäre es ein guter Kompromiss, einen Fehler in Ihrer Sortierroutine als Gegenleistung für die Geschwindigkeit einzuführen.

Das ist eine absolute fliegende Vermutung, aber angesichts der inhärenten Subjektivität von "Relevanz" -Maßstäben beim Sortieren von Suchergebnissen würde ich behaupten, dass es nicht wirklich wichtig ist, ob sie perfekt sortiert sind oder nicht. Das gleiche könnte für Empfehlungen gesagt werden. Wenn Sie irgendwie ordnen können, dass jeder andere Teil Ihres Algorithmus für diese Dinge O (n) ist, dann könnten Sie versuchen, eine Sortierung zu vermeiden.

Beachten Sie auch, dass Ihre "fast sortierten" Daten im schlimmsten Fall nicht einer möglichen intuitiven Idee von "fast sortiert" entsprechen, nämlich dass sie nur eine kleine Anzahl von Inversionen aufweist. Der Grund dafür ist nur, dass, wenn Ihre Daten nur O (n) Inversionen haben, können Sie die Sortierung in O (n) Zeit mit Insertion Sortierung oder Cocktail-Sortierung (d. H. Zwei-Wege-Blasensortieren) beenden. Daraus folgt, dass Sie diesen Punkt möglicherweise nicht vollständig unsortiert in O (n) Zeit erreicht haben (mit Vergleichen). Sie suchen also nach Anwendungen, bei denen eine Majoritätsuntermenge der Daten sortiert ist und der Rest verstreut ist, nicht für Anwendungen, die erfordern, dass sich jedes Element in der Nähe seiner korrekten Position befindet.

Ich spekuliere nur hier, aber eine Sache, die ich mir vorstelle, ist die Datenbankabfrageoptimierung.

Eine Datenbankabfrage in einer deklarativen Sprache wie SQL muss in ein Schritt-für-Schritt-Programm übersetzt werden, das als "Ausführungsplan" bezeichnet wird. Eine SQL-Abfrage kann typischerweise in eine Anzahl solcher Ausführungspläne übersetzt werden, die alle das gleiche Ergebnis liefern, aber sehr unterschiedliche Leistungen haben können. Der Abfrageoptimierer muss den schnellsten oder zumindest einen relativ schnellen suchen.

Kostenbasierte Abfrageoptimierer haben eine "Kostenfunktion", mit der sie die Ausführungszeit eines bestimmten Plans schätzen. Erschöpfende Optimierer durchlaufen alle möglichen Pläne (für einen Wert von "alles möglich") und wählen den schnellsten aus. Bei komplizierten Abfragen kann die Anzahl möglicher Pläne zu groß sein, was zu überlangen Optimierungszeiten führt (bevor Sie überhaupt mit der Suche in der Datenbank beginnen!), So dass es auch nicht erschöpfende Optimierer gibt. Sie schauen sich nur einige der Pläne an, vielleicht mit einem zufälligen Element bei der Auswahl der Pläne. Dies funktioniert, da es normalerweise eine große Anzahl von "guten" Plänen gibt und es möglicherweise nicht so wichtig ist, das absolut beste zu finden - es ist wahrscheinlich besser, einen 5-Sekunden-Plan anstelle des optimalen 2-Sekunden-Plans zu wählen , wenn es einige Minuten der Optimierung benötigt, um den 2-Sekunden-Plan zu finden.

Einige Optimierungsalgorithmen verwenden eine sortierte Warteschlange von "vielversprechenden" (Teil-) Plänen. Wenn es nicht wirklich wichtig ist, wenn Sie den absolut besten Plan finden, könnten Sie vielleicht eine fast-sortierte Warteschlange verwenden?

Eine andere Idee (und ich spekuliere immer noch) ist ein Scheduler für Prozesse oder Threads in einem Time-Sharing-System, wo es nicht wichtig sein kann, wenn ein bestimmter Prozess oder Thread seinen Zeitschlitz einige Millisekunden später bekommt sortiert nach Priorität.

Eine häufige Anwendung für die Neusortierung ist, wenn ein Mensch den paarweisen Vergleich durchführt und Sie nicht so viele Fragen stellen müssen.

Angenommen, Sie haben viele Artikel, die ein Mensch über einen paarweisen Vergleich sortieren soll. Sie können die Anzahl der Vergleiche erheblich reduzieren, die Sie benötigen, wenn Sie bereit sind zu akzeptieren, dass die Bestellung nicht exakt ist. Es kann beispielsweise nicht darauf ankommen, dass benachbarte Elemente so lange ausgetauscht werden, wie die bevorzugten Elemente oben liegen.

Überall

1. Sie sollen schnell reagieren,
2. Sie versprechen dem Kunden kein genaues Verhalten,
3. aber intern hast du einige Regeln

Sie können es verwenden. Wie wäre es mit einer "nicht so strengen" regelbasierten Prioritätswarteschlange? Wo wäre das nützlich? Vielleicht Thread / Prozess / Ressourcenplanung. In der Thread- / Prozessterminierung versprichst du wirklich nicht, dass ein Thread als erster, zweiter oder letzter geht, aber generell möchtest du jedem eine Chance geben. Vielleicht möchten Sie lockere Regeln erzwingen, so dass sie präventiv, priorisiert, blabla ..

Ein Ressourcenplanbeispiel würde auf Pizzalieferungen oder Versandschachteln von Büchern an Leute etc. reagieren. Sie können es nicht verwenden, wo deterministisches Ergebnis erwartet wird, aber es gibt viele Beispiele im wirklichen Leben, wo Dinge nicht so deterministisch sind / vorhersehbar.

O (n log n) ist schon ziemlich schnell. Ich glaube nicht, dass irgendjemand jemals mit einem Near-Sort-Algorithmus anfangen würde. Sie würden mit Code beginnen, der nur eine vollständige Sortierung durchführt (da Ihre bevorzugte Programmiersprache wahrscheinlich eine sort -Funktion und keine nearsort -Funktion bereitstellt), und wenn Sie empirisch gefunden haben, dass die Sortierung zu lange dauert, würden Sie das tun fange an zu bezweifeln, ob deine Daten wirklich vollständig sortiert sein müssen, und erwäge, eine Near-Sort zu verwenden.

Grundsätzlich würden Sie niemals eine nahe Sortierung in Erwägung ziehen, es sei denn, Sie hätten zuerst festgestellt, dass das Sortieren ein schwerwiegender Engpass in Ihrem Programm ist.