Ich habe mir die Methode max in Ruby angeschaut Enumerable mixin (v2.4.1).
Es ist eine recht einfache Methode, aber wie sie Objekte anordnet, wenn Duplikate vorhanden sind, ist ein wenig verwirrend.
Zum Beispiel:
%Vor% Wie wird 7 als zweiter Artikel ausgewählt? Warum wird es überhaupt nicht gewählt, wenn drei Werte genommen werden?
Wenn Sie noch mehr Zahlen verwenden, ist die Reihenfolge nicht konsistent (obwohl die Elemente in der Menge sind).
Ich habe einen Blick auf den Quellcode geworfen, aber es scheint normal zu sein Vergleich; Die hier gezeigte Reihenfolge ist aus diesem Code nicht ersichtlich.
Kann jemand erklären, wie diese Bestellung zustande kommt? Ich weiß, dass die obigen Anordnungen alle "gültig" sind, aber wie werden sie erzeugt?
Ihr Beispiel kann vereinfacht werden, indem Sie mit max_by ein ähnliches Ergebnis erzielen:
10.times{|y| p x.max_by(y) {|t| t%2}}
Ich habe einige Zeit mit der Quelle verbracht, kann aber kein Loch finden.
Nachdem ich mich an eine Veröffentlichung namens % co_de erinnert habe % (Dissertation von Manuel Mayr) Ich habe die Antwort gefunden.
Wo auf Seite 104 finden Sie die Antwort für Switch: A Deep Embedding of Queries into Ruby :
... Hier der Wert in der Eingabeliste, der das Maximum wann annimmt ausgewertet von der Funktion zurückgegeben wird. Wenn mehr als ein Wert ergibt das Maximum, die Wahl für ein Ergebnis unter diesen Werten ist beliebig. ...
Ähnlich für:
max_by & amp; sort aus den Kommentaren @ emu.c
Das Ergebnis ist nicht garantiert stabil. Wenn zwei Schlüssel gleich sind, Die Reihenfolge der entsprechenden Elemente ist nicht vorhersehbar.
Erster, zweiter Schnitt - "wir müssen tiefer gehen" = & gt; Ich hoffe, Sie werden die "Fahrt" genießen.
Die kurze Antwort:
Der Grund dafür, dass die Sortierung so aussieht, ist die Kombination von max_by block (bewirkt, dass die Sortierung mit sort_by -Werten von max beginnt, was %2 ist, dann weiter mit 1 ) und qsort_r (BSD Quick-Sort) implementiert @ruby.
Die lange Antwort:
Alles basiert auf dem Quellcode von Ruby 2.4.2 oder aktuell 2.5.0 (der gerade entwickelt wird).
Der Schnellsortieralgorithmus kann sich je nach verwendetem Compiler unterscheiden. Sie können qsort_r verwenden: GNU-Version, BSD-Version (Sie können die configure.ac überprüfen) für mehr. Das Visual Studio verwendet die BSD-Version von 2012 oder später.
%Vor%
Wenn Sie GNU qsort_r aber nicht BSD haben:
Nur die interne Implementierung von ruby_qsort wird verwendet. Überprüfen Sie util.c für die interne Implementierung der Funktion Quick-sort ( 0 ) von Tomoyuki Kawamura.
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
Wenn HAVE_GNU_QSORT_R = 1 dann @util.h :
Wenn der BSD-Stil erkannt wird:
Dann wird der folgende Code verwendet (zu finden unter util.c ). Beachten Sie, wie der #define ruby_qsort qsort_r vor cmp_bsd_qsort aufgerufen wird. Der Grund? Wahrscheinlich Standardisierung, Stack-Platz und vielleicht Geschwindigkeit (habe es nicht selbst getestet - müsste Benchmark erstellen, und das ist ziemlich zeitaufwendig).
Der Stapelspeicherplatz wird im BSD-Quellcode qsort.c angegeben:
%Vor%Der BSD-Zweig im Ruby-Quellcode:
%Vor%Wenn Sie MSYS2 verwenden, um Ihren Ruby unter Windows zu kompilieren (kein DevKit mehr, sondern MSYS2 für Windows Installer, den ich die meiste Zeit benutze) NetBSD Version von qsort_r (die seit 02-07-2012 da ist). Das neueste NetBSD qsort.c (Revision: 1.23) .
Nun zu den realen Beispielen - "wir müssen noch tiefer gehen"
Die Tests werden an zwei Rubinen durchgeführt:
Erster Ruby: basiert auf ruby_qsort version DevKit (wurde am 13. April 2015 veröffentlicht) und enthält nicht die BSD qsort-Implementierung.
Zweiter Ruby: basiert auf 2.2.2p95 version ruby MSYS2 tool-chain (die am 15. September 2017 veröffentlicht wurde) und enthält einen Patch (siehe oben) für die BSD qsort-Implementierung.
Der Code:
%Vor% Ruby 2.4.2-p198 :
Ruby 2.2.2p95 :
Jetzt für verschiedene 2.4.2-p198 :
x
Ruby x=[7,9,3,4,2,6,1,8,5] :
Ruby 2.2.2p95 :
Jetzt für die gleichen Elemente im Quell-Array (qsort is unstable siehe unten):
2.4.2-p198
Verarbeiten Sie es mit dem folgenden Code:
x=[1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Ruby 12.times{|y| p x.max_by(y) {|t| t%2}} :
Ruby 2.2.2p95 :
Nun zur großen Frage - & gt; Warum sind die Ergebnisse anders?
Die erste offensichtliche Antwort wäre, dass das Ergebnis bei der Verwendung von GNU- oder BSD-Implementierungen anders wäre? Recht? Nun, die Implementierungen sind unterschiedlich, aber das Ergebnis (überprüfen Sie die verlinkten Implementierungen für Details) die gleichen Ergebnisse. Der Kern des Problems ist woanders.
Das eigentliche Problem hier ist der Algorithmus selbst. Wenn Schnellsortierung verwendet wird, erhalten Sie eine instabile Sortierung (wenn Sie die zwei gleichen Werte vergleichen, bleibt ihre Reihenfolge nicht gleich). Wenn du deine [1,2,3,4,5,6,7,8,9] hast, die du dann im Block in [1,0,1,0,1,0,1,0,1] umwandelst Mit max (_by) sortieren Sie das Array nach [1,1,1,1,1,0,0,0,0]. Du beginnst mit 1, aber mit welchem?Na dann bekommst du ein unberechenbares Ergebnis. (max (_by) ist der Grund, warum die ungeraden Zahlen zuerst und dann die geraden Zahlen erhalten).
Siehe GNU qsort Kommentar:
Warnung: Wenn zwei Objekte gleich sind, ist ihre Reihenfolge nach dem Sortieren unberechenbar. Das heißt, die Sortierung ist nicht stabil. Das kann einen Unterschied machen, wenn der Vergleich nur einen Teil der Elemente. Zwei Elemente mit demselben Sortierschlüssel können sich in anderen unterscheiden respektiert.
Nun, um es wie die Engine zu sortieren:
2.4.2-p198 - & gt; Die ersten, die berücksichtigt werden, sind die ungeraden Zahlen [1,2,3,4,5,6,7,8,9] und diejenigen, die als gleich betrachtet werden mit [1,3,5,7,9] produziert max_by{|t| t%2} .
Fazit:
Was nun zu nehmen? Nun, es ist unberechenbar, in deinem Fall waren es die, die du bekommen hast. Ich werde sogar für die gleiche Ruby-Version verschiedene Versionen bekommen, da der zugrunde liegende Quick-Sort -Algorithmus von Natur aus instabil ist.