forma más rápida de ordenar las entradas de un “suavizar” matriz 2D

Question

¿Cuál es la manera más rápida para ordenar los valores en una matriz 2D suavizar?

La entrada es una imagen filtrada pequeña:

• alrededor de 60 por 80 píxeles
• solo canal
• flotante de precisión simple o doble
• fila de almacenamiento importante, secuencial en la memoria
• Los valores tienen signo mixto
• a trozos "suave", con regiones del orden de 10 píxeles de ancho

salida es una plana (aproximadamente 4.800 valor) matriz de los valores ordenados, junto con los índices de ese tipo la matriz original.

Answer 1

Me elaboraron una referencia rápida y sucia en algunas imágenes usando rutinas de ordenación de numpy en la matriz plana. Esto se promedia en unos pocos cientos de imágenes al azar y unos pocos cientos de imágenes de rostros humanos. Ambos son de precisión simple.

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 los algoritmos parecen beneficiarse de la ordenación parcial existente, especialmente la clasificación rápida. Numpy no parecen tener una función de lista de combinación ordenada, así que no puedo tratar de preclasificación de las filas, por desgracia.

Answer 2

yo esperaría Timsort para ganar esto, ya que se aprovecha de "corre" en los datos.

ordenación rápida será normalmente ser rápido, pero existe el riesgo de que te encuentras con un peor de los casos. p.ej. Algunas versiones de quickshort son O (n ^ 2) cuando se administra de entrada ya ordenados. Lo cual no sería muy agradable si alguien le dio el tipo incorrecto de la imagen con relleno degradado ......

Esta es una idea un poco loco - también se podría tratar de un pase orden Z ( Wikipedia enlace ) que podría permitir aprovechar colores similares adyacentes en ambas dimensiones.

Answer 3

Yo empezaría con la clasificación rápida en el lugar. comparaciones en coma flotante son rápidos en la mayoría de los procesadores (sin duda mucho más rápido que la asignación necesaria para un mergesort).

Answer 4

Hay timsort, pero he visto en varios lugares que se quiere decir para aplicaciones con compara lenta; la numpy proyectos de desarrollo aparentemente decidió no siquiera se molesta su aplicación:

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

Answer 5

Se podría mergesort las filas de forma individual, y luego fusionar los registros ordenados.

Esto haría al menos apalancamiento parte de la estructura especial de la matriz 2D, es decir, el hecho de que monótonos carreras típicamente comenzar y terminar en el borde de la matriz. También expone otro par de niveles de paralelismo.