maneira mais rápida de classificar as entradas de uma matriz 2D "suave"

Question

Qual é a maneira mais rápida de classificar os valores em uma matriz 2D suave?

A entrada é uma pequena imagem filtrada:

• cerca de 60 por 80 pixels
• canal único
• Float de precisão única ou dupla
• Linha de armazenamento importante, sequencial na memória
• Os valores têm sinal misto
• "suave", com regiões da ordem de 10 pixels de largura

A saída é uma matriz plana (cerca de 4800 valor) dos valores classificados, juntamente com os índices que classificam a matriz original.

Answer 1

Eu marterei uma referência rápida e suja em algumas imagens usando as rotinas de classificação de Numpy na matriz plana. Isso é calculado em média por algumas centenas de imagens aleatórias e algumas centenas de imagens de rostos humanos. Ambos são uma única precisão.

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.

Todos os algoritmos parecem se beneficiar da ordem parcial existente, especialmente do Quicksort. Numpy não parece ter uma função de mesclagem de lista classificada, então não posso tentar pré-classificar as linhas, infelizmente.

Answer 2

Eu esperaria que o TimSort vencesse isso, pois aproveita as "corridas" nos dados.

O Quicksort normalmente será rápido, mas há um risco de você atingir o pior cenário. Por exemplo, algumas versões do QuickShort são O (n^2) quando recebidas informações já classificadas. O que não seria muito amigável se alguém lhe desse o tipo errado de imagem cheia de gradiente ......

Aqui está uma ideia um pouco louca - você também pode tentar um passe de ordem Z (Link da Wikipedia) que podem permitir que você aproveite as cores semelhantes adjacentes em ambas as dimensões.

Answer 3

Eu começaria com o Quicksort no local. As comparações de pontos flutuantes são rápidos na maioria dos processadores (certamente muito mais rápidos que a alocação necessária para um mesclado).

Answer 4

Há Timsort, mas eu vi em vários lugares que ele se destina a aplicações com comparação lenta; Os desenvolvedores Numpy aparentemente decidiram nem se incomodar em implementá -lo:

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

Answer 5

Pode -se mesclar as linhas individualmente e, em seguida, mesclar as linhas classificadas.

Isso aproveitaria pelo menos parte da estrutura especial da matriz 2D, ou seja, o fato de que as corridas monotônicas normalmente começarão e param na borda da matriz. Também expõe outros dois níveis de paralelismo.