Самый быстрый способ сортировки записей «плавного» 2D-массива

Question

Каков самый быстрый способ сортировки значений в гладкой 2D-матрице?

Входной небольшой отфильтрованного изображения:

• около 60 по 80 пикселей
• одноканальные
• одинарной или двойной точности с плавающей точкой
• строки из основных хранения, последовательные в памяти
• значения имеют смешанный знак
• кусочно-гладкий, с областями порядка 10 пикселей в ширину

Выход - это плоское (около 4800 значений) массив отсортированных значений, а также индексы, сортирующие исходный массив.

Answer 1

Я забил быстрый и грязный бенчмарк на некоторых изображениях, используя процедуры сортировки numpy на плоском массиве. Это усредняется на несколько сотен случайных изображений и несколько сотен изображений человеческих лиц. Оба являются одинарной точностью.

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. 

Все алгоритмы, похоже, приносят пользу из существующего частичного заказа, особенно для быстрой сортировки. У Numpy нет функции сортировки списка сортировки, поэтому я не могу попробовать предварительно отсортировать строки, увы.

Answer 2

Существует timsort, но я видел в нескольких местах, что он предназначен для приложений с медленными сравнениями; что Numpy разработчики, видимо, решили не беспокоить даже его реализации:

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

Answer 3

Можно слияние строк по отдельности, а затем объединить отсортированные строки.

Это, по крайней мере, будет использовать некоторую специальную структуру 2D-массива, то есть тот факт, что монотонные прогоны обычно начинаются и останавливаются на краю массива. Он также предоставляет еще пару уровней параллелизма.

Answer 4

Я бы начал с быстрой сортировки на месте. Сравнение с плавающей точкой выполняется на большинстве процессоров (конечно, намного быстрее, чем распределение, необходимое для объединения).

Answer 5

Я бы ожидал, что Timsort выиграет это, так как он использует преимущества «прогонов» в данных.

Quicksort обычно будет быстрым, но существует риск, что вы попадете в наихудший сценарий. например некоторые версии quickshort - это O (n^2), если заданы уже отсортированные данные. Который не был бы очень дружелюбным, если бы кто-то дал вам неправильный тип заполненного градиентом изображения ...

Вот немного сумасшедшая идея - вы также можете попробовать пропуск Z-порядка (Wikipedia link), который мог бы вам помочь чтобы использовать соседние аналогичные цвета в обоих измерениях.