Dies ist ein Follow-up zu einem antworten auf eine Frage zum Sortieren nach einem bestimmten Argument eines Begriffs, ohne eine neue Liste für keysort zu erstellen (wenn ich die ursprüngliche Frage richtig verstanden habe).
Nehmen wir an, wir wollten predsort/3 genauso verhalten wie sort/2 : Wenn ich das richtig verstehe, würde das bedeuten, es wie folgt zu benennen:
Nun sagen wir, dass wir predsort/3 verwenden wollten, um nach msort/2 zu sortieren (siehe auch Frage ). Eine Möglichkeit wäre, ein Vergleichsprädikat Pred(-Delta, +A, +B) zu definieren, das Delta nicht mit = vereinigt, wenn die Elemente tatsächlich gleich sind:
Frage : Sortiert das wirklich einfach, ohne Duplikate zu entfernen, wie msort/2 es tut? Es scheint wie es sollte.
Weiter: Sagen wir, dass wir die Begriffe mit arity & gt; n, auf die Standard-Reihenfolge des n-ten Arguments in der Laufzeit. Der saubere Weg dazu wäre:
%Vor% Wenn wir predsort/3 verwenden wollten, um denselben Effekt zu erzielen, könnten wir versuchen, ein Vergleichsprädikat wie folgt zu verwenden:
Und nach dem zweiten Argument sortieren:
%Vor% Dies ist jedoch nicht das gleiche wie sort_argn/3 über dem, das keysort/2 verwendet. Es wird Duplikate entfernen, und es werden zusammengesetzte Terme gemäß der Standardreihenfolge des ursprünglichen vollständigen Terms angeordnet, wenn die zweiten Argumente zweier Terme zufällig gleich sind:
Machen Sie die Annahme , dass für jedes Paar von A und B , das an das Vergleichsprädikat Pred(Delta, A, B) übergeben wurde, A vor B in der ursprünglichen Liste steht. Können wir einen Vergleich definieren:
An dieser Stelle, genau dann, wenn zwei beliebige Elemente A und B immer an das Vergleichsprädikat in der gleichen Reihenfolge wie in der ursprünglichen Liste übergeben werden, sollte sich dies verhalten identisch mit sort_argn/3 oben:
Nun ist es natürlich wichtig, dass compare_argn_stable/4 Delta mit < vereinigt, wenn die beiden "Schlüssel" gleich sind. Darüber hinaus ist das Verhalten implementierungsabhängig und nur identisch mit dem Beispiel keysort , wenn predsort/3 die ursprüngliche Reihenfolge der Elemente beim Übergeben an das Vergleichsprädikat beibehält.
Frage Stimmt das?
Frage Gibt es einen Standard, der diesen Aspekt von predsort/3 abdeckt?
Da niemand geantwortet hat und ich mir jetzt ganz sicher bin:
Ja, Sie könnten predsort/3 verwenden, um eine der anderen Arten zu emulieren. Die Frage beschreibt im Detail wie.
Jedoch : Das ist aus verschiedenen Gründen eine schlechte Idee.
predsort/3 ab (siehe Frage) predsort/3 selbst ist kein Teil eines Standards (soweit ich das beurteilen kann) msort/2 oder keysort/2 bietet, das weitaus effizienter ist als predsort/3 .
Es kann in seltenen Fällen vorkommen, dass die Größe der Elemente der Liste viel größer ist als die Länge der Liste, die wir sortieren, und dieser kleine Tanz:
%Vor% ( siehe hier ) ist tatsächlich teurer (langsamer) als die Verwendung von predsort(keycmp, List, Sorted) , mit keycmp/3 vom Benutzer definiert. Auch dann hängt die Reihenfolge der Ergebnisse mit äquivalenten Schlüsseln nicht nur von der (Benutzer-) Definition von keycmp/3 ab, sondern auch von der Implementierung von predsort/3 .
Mit anderen Worten, eine "stabile" Sortierung mit predsort/3 ist eine schlechte Idee.
Tags und Links list sorting prolog compare stable-sort