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

Question

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

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

• примерно 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 выиграет это дело, поскольку он использует преимущества «прогонов» данных.

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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