Shellsort, 2.48 ^ (k-1) gegen Tokudas Sequenz

9

Einführung

Shellsort ist ein interessanter Sortieralgorithmus, auf den ich vor einiger Zeit gestoßen bin. Der erstaunlichste Teil ist, dass verschiedene Lückenfolgen die Geschwindigkeit des Algorithmus erheblich verbessern können. Ich habe ein wenig gelesen (nicht ausführlich) und es scheint, dass Tokudas Sequenz für praktische Anwendungen empfohlen wird.

Ein weiterer interessanter Teil ist, dass die Reihenfolge des Verhältnisses von 2,20 ~ 2,25 effizienter ist. Also habe ich eine kleine Suche nach der Reihenfolge des Verhältnisses von 2,20 bis 2,50 gemacht und versucht, nach dem Verhältnis zu suchen, das die Leistung durchschnittlich gut machen kann. Ich stoße auf dieses Verhältnis: 2,48, das in vielen verschiedenen Versuchen als durchschnittlich gut erscheint.

Dann kam ich mit Sequenzgenerator: 2,48 k-1 (wir nennen es 248 Sequenz) und versuchte, es mit Tokuda-Sequenz zu vergleichen. Es stellte sich heraus, dass sie im Durchschnitt gleich schnell sind. 248 Sequenzen neigen dazu, eine etwas größere Anzahl von Vergleichen zu verwenden.

Benchmark-Methoden

  • Anstatt Millisekunden als Maß zu verwenden, verwende ich die Anzahl der Vergleiche und die Anzahl der Swaps.
  • Ich habe jeweils 100 Versuche mit der folgenden Array-Größe (50.000; 100.000; 200.000; 300.000; 500.000; 1.000.000) durchgeführt und die Anzahl der Vergleiche und die Anzahl der Swaps im Auge behalten.
  • Das Folgende sind meine Daten ( hier im CSV-Format ).
  • Vollständiger Code: Ссылка

Fragen

Ich weiß, dass ich mich irren könnte, deshalb komme ich hierher, um hier mehr erfahrene Programmierer zu finden. Falls Sie die Frage nicht bekommen, hier ist meine Frage kurz:

  • Ist 2.48 k-1 so gut wie Tokudas Sequenz?
  • Wenn es so gut wie Tokudas Sequenz ist, wäre es praktischer, es zu verwenden, da die 2.48 k-1 -Sequenz einfacher zu erzeugen ist als Tokudas Sequenz.
%Vor%

Als @woolstar schlug ich vor, auch mit Randfällen wie umgekehrt und sortiert zu testen. Wie erwartet, ist die 248-Sequenz in Edge-Fällen schneller, weil die 248-Sequenzlücke größer ist, so dass sie die Inverse schneller bewegt.

Shellsort Implementierung

%Vor%     
invisal 02.02.2014, 08:35
quelle

1 Antwort

4

Nach dieser Forschung : (Ciura, Marcin (2001) " Bester Zuwachs für den durchschnittlichen Fall von Shellsort. "In Freiwalds, Rusins. Proceedings des 13. Internationalen Symposiums über Grundlagen der Computationstheorie. London: Springer-Verlag. Pp. 106-117) die dominierende Operation in Shell-Sortierung für Arrays mit einer Größe von weniger als 10 8 Elementen sollten die Vergleichsoperation sein, nicht swap:

  

Knuths Diskussion setzt voraus, dass die Laufzeit als 9 × Anzahl der Züge angenähert werden kann,   während die 3 und 4 zeigen, dass für jede Sequenz die Anzahl der Schlüsselvergleiche ein besseres Maß für die Laufzeit ist als die Anzahl der Züge. Das asymptotische Verhältnis von 9 Zyklen pro Bewegung ist nicht zu genau für N ≤ 10 8 , und wenn eine hypothetische Sequenz Θ (NlogN) bewegt, wird sie niemals erreicht. Analoge Plots für andere Computerarchitekturen würden zu derselben Schlussfolgerung führen.

     

Das Behandeln von Bewegungen als dominierende Operation führt zu falschen Schlussfolgerungen   über die optimalen Sequenzen.

In diesem Zusammenhang ist die Antwort auf Ihre Frage nein: Die Sequenz 248 ist schlechter, weil sie mehr Vergleiche verwendet. Sie könnten auch Ihre Sequenz mit der Sequenz von Ciura vergleichen, die in diesem Artikel vorgestellt wird, da diese Forschung zu beweisen scheint, dass sie besser ist als Tokudas Sequenz.

    
BartoszKP 02.02.2014, 11:04
quelle

Tags und Links