Wie Cache Oblivious schnelle Sortierung ist?

Question

In Burst sort Papierautor behauptet, dass schnelle Sortierung ist nicht sehr Cache effiziente Sortieralgorithmus. Als Autor erwähnte

sind jedoch einige der Nachteile des quicksort noch present.Each Charakter wird mehrmals überprüft, bis es in einem gleich Schwenk partition.Each Zeichenfolge wird erneut zugegriffen jedesmal, wenn ein Zeichen in Es wird inspiziert, und nach der ersten Partitionierung sind diese Zugriffe effektiv zufällig. Bei einer großen Anzahl von Strings ist die Rate des Caches wahrscheinlich zu hoch.

Ich fand auch ppt die schnelle Art sagt und Art sind Oblivious Algorithmus Cache fusionieren aber Wikipedia und few paper Behauptung, dass eine schnelle Art sehr Cache effizient ist.

Ich bin nicht in der Lage, Fälle zu verstehen, in denen schnelle Sortierung Cache-Miss außer Zwangsmeldung für Integer-Daten zu bekommen.Kann jemand schnelle Cache-Miss im Detail erklären?

Answer 1

Die von Ihnen zitierte Stelle bezieht sich hauptsächlich auf Probleme beim Sortieren von Strings. Wenn ein Array von Strings während Quicksort als ein Array als Zeiger gespeichert wird (was im Prinzip der einzige einfache Weg ist), dann ist es nach dem ersten Durchlauf von Quicksort möglich, dass Zeiger, die an nahegelegenen Positionen im Array gespeichert sind, auf Speicher zeigen Orte, die weit voneinander entfernt sind, auch wenn das ursprüngliche Array von Strings im konsekutiven Speicher zugewiesen wurde. Es erscheint plausibel, dass das Sortieren von Strings als ein spezielles Problem behandelt werden kann und spezialisierte Algorithmen dafür mehr Cache-effizient sein könnten.

Wenn Sie stattdessen ein Array von beispielsweise Ganzzahlen sortieren, vergleichen Sie die Daten im Array und tauschen sie während des Quicksorts um. Wenn Sie auf nahegelegene Positionen im Array zugreifen, erhalten Sie Cache-Vorteile. In diesem Fall ist mein Verständnis dasselbe wie das, was Sie in Wikipedia und anderswo gefunden haben, nämlich, dass quicksort ziemlich Cache-effizient ist. Grundsätzlich ist dies so, weil jeder Durchlauf von Quicksort seinen Teil des Arrays auf sehr lokale Weise verarbeitet.