moyen le plus rapide pour trier les entrées d'un tableau 2D « lisse »

Question

Quel est le meilleur moyen de trier les valeurs dans un tableau 2D lisse?

L'entrée est une petite image filtrée:

• environ 60 par 80 pixels
• un seul canal
• simple ou double flotteur de précision
• rangée de stockage principal, séquentielle dans la mémoire
• les valeurs ont signe mixte
• piecewise "lisse", avec des régions de l'ordre de 10 pixels de large

La sortie est une matrice plate (environ 4.800 valeur) des valeurs triées, ainsi que les indices trier le tableau d'origine.

Answer 1

Je martelés une référence rapide et sale sur certaines images en utilisant les routines de tri de numpy sur le tableau plat. Ceci est en moyenne sur quelques centaines d'images aléatoires et quelques centaines d'images de visages humains. Les deux sont simple précision.

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.

Tous les algorithmes semblent bénéficier de la commande partielle existante, en particulier quicksort. Numpy ne semble pas avoir une fonction de fusion de liste triée, donc je ne peux pas essayer de pré-tri des lignes, hélas.

Answer 2

J'attends Timsort à gagner ce car il profite des « runs » dans les données.

Quicksort sera normalement être rapide mais il y a un risque que vous frappez un pire scénario. par exemple. certaines versions de quickshort sont O (n ^ 2) lorsque les entrées sont déjà triés. Ce qui ne serait pas très sympathique si quelqu'un vous a donné le mauvais type d'image remplie gradient ......

Voilà une idée un peu folle - vous pouvez également essayer une passe Z-commande ( lien Wikipedia ) qui pourrait vous permettre de profiter de couleurs similaires adjacentes dans les deux dimensions.

Answer 3

Je commencerai par quicksort en place. comparaisons à virgule flottante sont rapides sur la plupart des processeurs (certainement beaucoup plus rapide que l'allocation nécessaire pour un mergesort).

Answer 4

Il y a timsort, mais je l'ai vu dans plusieurs endroits qu'il est conçu pour des applications avec lenteur compare; les numpy devs ont apparemment décidé de ne pas même pas la peine mise en œuvre:

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

Answer 5

On pourrait mergesort les lignes individuellement, puis fusionner les lignes triées.

Ce serait au moins tirer parti de certaines de la structure spéciale du tableau 2D, à savoir le fait que fonctionne monotones commencent généralement et arrêter au bord du tableau. Il expose aussi un autre niveau de parallélisme couple.