Ich bin gespannt, welchen Algorithmus Lua standardmäßig table.sort
verwendet, nur weil es langsamer ist als einige andere Sortieralgorithmen, die mir begegnet sind. Ich bin auch neugierig, ob Lua table.sort
in der Engine in C geschrieben ist, oder wenn es in einer Bibliothek in Lua ist.Welchen Algorithmus verwendet table.sort?
Antwort
Welchen Algorithmus verwendet table.sort?
Die comment in tablib.c
(scrollen etwas nach oben) heißt
/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
** Addison-Wesley, 1993.)
** =======================================================
*/
Sie den Quellcode auf den Link lesen kann ich zur Verfügung gestellt.
Ich bin auch neugierig, wenn Lua's table.sort in der Engine in C geschrieben wird, oder wenn es in einer Bibliothek in Lua ist.
Zu diesem Zeitpunkt werden alle Bibliotheken, die direkt mit Lua kommen werden (io
, table
, math
, ...) in C.
table.sort
verwendet quicksort Intern geschrieben, und es in C. Hinweis geschrieben Dieser Quicksort ist nicht stabil. Und ein bisschen überraschend für mich, Lua hat C's qsort()
nicht direkt verwendet.
In Bezug auf die Leistung ist es schwer zu sagen, da es verschiedene Faktoren gibt, z. B. welche Sprache und welchen Algorithmus Sie vergleichen und welche Art von Daten getestet werden.
Mit Lua gibt es ein paar Algorithmen, die ich gefunden habe, die ein bisschen schneller sind als der Standard. Wenn Größe relevant klein ist, sind Cocktail-Sort und Bubble-Sort tatsächlich schneller als der Standard. Wenn die Größe groß ist, dann ist LSD Radix sort, zusammen mit den anderen zwei, die ich sagte, schneller. Ich teste es mit verschiedenen Arten von Daten, wie zum Beispiel umgekehrte Arrays, zufällige Arrays und sogar meist sortierte Arrays, aber für jeden Test ist die Standard-Sortierung immer noch etwas langsamer. – jocopa3
@ jocopa3 So weit ich sehe, ist das nicht Lua's Problem, eher Quicksort's. Beispielsweise führt Quicksort schlecht auf sortierten Arrays und umgekehrten Arrays aus. Wenn Sie nach bestimmten Problemen sortieren müssen und Lua's Standardsortierung nicht gut genug funktioniert, dann ist es vielleicht eine gute Idee, einen bestimmten Sortieralgorithmus in C selbst zu schreiben. –
@YuHao Aus dem Blick auf die verlinkte Quelle wählt Lua's qsort immer die Mitte als Pivot. Das sollte in der Nähe von qsorts Idealfall liegen, und es sollte nicht schlecht funktionieren. Ich vermute, dass all diese Lua-API-Aufrufe das sind, was die Dinge verlangsamt, können aber nicht sicher sein, es sei denn, es ist profiliert. – greatwolf
Beachten Sie, dass LuaJIT erwägt, zu [smoothsort] (http://en.wikipedia.org/wiki/Smoothsort) zu wechseln, und einige seiner Bibliotheksfunktionen sind jetzt in Lua-Bytecode implementiert (was tatsächlich von Vorteil ist, weil es dann möglich ist) JIT kompiliert werden besser) –