самый быстрый способ сортировки записей "гладкого" 2D-массива

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

Я разработал быстрый и грязный тест для некоторых изображений, используя процедуры сортировки 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 3

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

Answer 4

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

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

Answer 5

Timsort есть, но я видел в нескольких местах, что он предназначен для приложений с медленным сравнением; Разработчики NumPy, по-видимому, решили даже не беспокоиться о его реализации:

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