schnellster Weg, um die Einträge eines „glatten“ 2D-Array zu sortieren

StackOverflow https://stackoverflow.com/questions/2557352

  •  23-09-2019
  •  | 
  •  

Frage

Was ist der schnellste Weg, um die Werte in einem glatten 2D-Array zu sortieren?

Der Eingang ist ein kleines gefilterte Bild:

  • 60 von 80 Pixel
  • Einkanal
  • einfache oder doppelte Genauigkeit float
  • Reihenhauptraum, in sequentiellen Speichern
  • Werte haben gemischte Zeichen
  • piecewise "glatt", mit Bereichen in der Größenordnung von 10 Pixel breit

Output ist eine flache (etwa 4800-Wert) Array der sortierten Werte, zusammen mit den Indizes, die die ursprüngliche sort-Array.

War es hilfreich?

Lösung 3

mit numpy die Sortierroutinen auf dem flachen Array

gehämmert ich auf einigen Bildern eine quick and dirty Benchmark aus. Dies wird gemittelt über ein paar hundert zufällige Bilder und ein paar hundert Bilder von menschlichen Gesichtern. Beide sind mit einfacher Genauigkeit. 

On random images...
quicksort took 0.000153 seconds per image.
mergesort took 0.000170 seconds per image.
heapsort took 0.000241 seconds per image.
On real images...
quicksort took 0.000136 seconds per image.
mergesort took 0.000143 seconds per image.
heapsort took 0.000230 seconds per image.

Alle diese Algorithmen scheinen Nutzen aus der bestehenden partiellen Ordnung, vor allem quicksort. Numpy scheint nicht eine sortierte Liste Merge-Funktion zu haben, so dass ich nicht die Zeilen, leider Vorsortierung kann es versuchen.

Andere Tipps

Ich würde erwarten Timsort diese zu gewinnen, da sie die Vorteile von „läuft“ in Daten nehmen.

Quicksort wird in der Regel schnell sein, aber es besteht die Gefahr, dass Sie ein Worst-Case-Szenario betroffen. z.B. Einige Versionen von quickshort sind O (n ^ 2), wenn gegeben bereits sortiert Eingabe. Die sehr wäre nicht freundlich, wenn jemand Dir die falsche Art von Gradienten gefüllt Bild gibt ......

Hier ist eine etwas verrückte Idee - Sie könnten auch versuchen, einen Z-ordering Pass ( Empfehlungen ), die Sie Vorteil von benachbarten ähnlichen Farben in beiden Dimensionen nehmen ermöglichen könnte.

würde ich mit in-place quicksort starten. Floating-Point-Vergleiche sind schnell auf den meisten Prozessoren (sicherlich viel schneller als die Zuweisung für einen mergesort erforderlich).

Es gibt Timsort, aber ich habe an mehreren Stellen gesehen, dass es für Anwendungen mit langsamen vergleicht gemeint ist; die numpy Devs sogar anscheinend beschlossen, nicht die Mühe, es Implementierung:

http://mail.scipy.org/pipermail /scipy-dev/2009-May/011929.html

Man könnte die Zeilen einzeln mergesort und dann die sortierten Zeilen verschmelzen.

Das wäre zumindest Hebel einige der besonderen Struktur des 2D-Arrays, das heißt die Tatsache, dass monotone Läufe werden in der Regel am Rande des Arrays starten und stoppen. Es macht auch noch ein paar Stufen von Parallelität.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top