Быстрый алгоритм для нахождения самых больших значений в 2d массиве

Question

У меня есть двумерный массив (на самом деле изображение) размером N x N. Мне нужно найти индексы M самых больших значений в массиве (M << N x N).Линеаризованный индекс или 2D-координаты в порядке.Массив должен оставаться неизменным (так как это изображение).Я могу сделать копию на пустом месте, но сортировка массива вызовет увеличение индексов. </p>

Я в порядке, когда делаю полный проход по массиву (т. Е. O (N ^ 2) хорошо).У кого-нибудь есть хороший алгоритм, позволяющий сделать это максимально эффективно?

Answer 1

Выбор - строгая сестра сортировки (повторите это десять раз подряд).Алгоритмы выбора менее известны, чем алгоритмы сортировки, но тем не менее полезны.

Вы не можете сделать лучше, чем O (N ^ 2) (в N), поскольку ничто не указывает на то, что вы не должны посещать каждый элементмассив.

Хорошим подходом является сохранение очереди приоритетов , состоящей из М самых больших элементов.Это делает что-то O (N x N x log M).

Вы пересекаете массив, ставя в очередь пары (элементы, индекс) по мере продвижения.В очереди сохраняются элементы, отсортированные по первому компоненту.

Как только в очереди есть M элементов, вместо того, чтобы ставить вас в очередь:

1. Запросите элемент min очереди
2. Если текущий элемент массива больше, вставьте его в очередь и отбросьте элемент min очереди
3. В противном случае ничего не делайте.

Если M больше, сортировкамассив является предпочтительным.

ПРИМЕЧАНИЕ: @ Энди Финкенштадт делает хорошее замечание (в комментариях к вашему вопросу): вам определенно следует пройтись по массиву в «направлении локальности данных»: makeубедитесь, что вы читаете память непрерывно.

Кроме того, это тривиально распараллеливается, единственная непараллелизуемая часть - это когда вы объединяете очереди при присоединении к подпроцессам.

Answer 2

Сколько раз вы ищете наибольшее значение из массива? Если вы выполняете поиск только 1 раз, просто отсканируйте его, сохранив самые большие значения M.

Если вы делаете это много раз, просто вставьте значения в отсортированный список (вероятно, лучше всего реализовать в виде сбалансированного дерева).

Answer 3

Ваша задача не использует эти 2 измерения каким-либо интересным способом, проще сопоставить эквивалентную проблему в 2d массиве.

Существует 2 основных способа решения этой проблемы:

1. Содержит набор из M самых больших элементов и выполняет итерацию по массиву.(Использование кучи позволяет сделать это эффективно).

   Это просто и, вероятно, лучше в вашем случае (M << N) </p>

2. Использовать выбор, (следующий алгоритм является адаптацией быстрой сортировки):

   • Создайте вспомогательный массив, содержащий индексы [1..N].
   • Выберите произвольный индекс (и соответствующее значение),и разделите массив индексов так, чтобы индексы, соответствующие элементам меньше, уходили влево, а более крупные элементы - вправо.
   • Повторяйте процесс, стиль двоичного поиска, пока не сузите M самых больших элементов.

   Это хорошо для случаев с большим M. Если вы хотите избежать проблем наихудшего случая (тот же самый quicksort), тогда посмотрите на более продвинутые алгоритмы (как выбор медианы выбора)

Answer 4

Если вы собираетесь сделать копию входного массива, чтобы выполнить сортировку, это намного хуже, чем просто проходить линейно через все это, чтобы выбрать числа.

Итак, вопрос в том, насколько велика твоя М? Если оно мало, вы можете хранить результаты (то есть структуры с двумерными индексами и значениями) в виде простого массива или вектора. Это сведет к минимуму операции с кучей, но когда вы найдете большее значение, чем в вашем векторе, вам придется все изменить.

Если вы ожидаете, что M станет действительно большим, тогда вам может потребоваться более совершенная структура данных, например, двоичное дерево (std :: set) или использование sorted std :: deque. std :: set уменьшит количество раз, которое элементы должны быть сдвинуты в памяти, в то время как если вы используете std :: deque, это сделает некоторое смещение, но это сократит количество раз, когда вы должны значительно перейти в кучу, что может дать вам лучшую производительность.

Answer 5

Вы можете скопировать массив в одномерный массив кортежей (значение, оригинал X, оригинал Y) и построить из него базовую кучу за (O (n) время), при условии, что куча реализована в виде массива.

Затем вы можете получить М наибольших кортежей за O (M lg n) и сослаться на их исходные x и y из кортежа.