Пересортируйте вектор после изменения небольшого количества элементов.

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

Например, если N= 10 и M= 2, вход может быть

10 20 30 40 999 60 70 80 90 -1

Примечание: индексы модифицированных элементов неизвестны (пока мы не сравним их с окружающими элементами.)

Вот пример, где я знаю решение, потому что размер ввода мал, и я смог найти его с помощью перебора:

если N = 5 и M равно 1, это будут действительные входные данные:

0 0 0 0 0     0 0 1 0 0     0 1 0 0 0     0 1 1 1 0     1 0 0 1 1     1 1 1 1 0

0 0 0 0 1     0 0 1 0 1     0 1 0 0 1     0 1 1 1 1     1 0 1 1 1     1 1 1 1 1

0 0 0 1 0     0 0 1 1 0     0 1 0 1 1     1 0 0 0 0     1 1 0 1 1

0 0 0 1 1     0 0 1 1 1     0 1 1 0 1     1 0 0 0 1     1 1 1 0 1

Например, вход может быть 0 1 1 0 1 если ранее отсортированный вектор был 0 1 1 1 1 и 4-й элемент был изменен, но нет способа сформировать 0 1 0 1 0 как допустимый вход, потому что он отличается по крайней мере на 2 элемента от любого отсортированного вектора.

Это будет действительная сеть сортировки для повторной сортировки этих входных данных:

>--*---*-----*-------->
   |   |     | 
>--*---|-----|-*---*-->
       |     | |   |
>--*---|-*---*-|---*-->
   |   | |     |
>--*---*-|-----*---*-->
         |         |
>--------*---------*-->

Нам не важно, что этой сети не удается отсортировать некоторые неверные данные (например, 0 1 0 1 0.)

И эта сеть имеет глубину 4, экономия 1 по сравнению с общим случаем ( глубина 5 обычно необходима для сортировки вектора из 5 элементов).

К сожалению, метод грубой силы невозможен для больших входных размеров.

Есть ли известный способ построения сети для повторной сортировки большего вектора?

Мои значения N будут порядка нескольких сотен, причем M не намного больше, чем √N.

Источник

2 ответа

Хорошо, я публикую это как ответ, так как ограничение комментариев по длине сводит меня с ума:)

Вы должны попробовать это:

  • реализовать простую последовательную сортировку, работающую с локальной памятью (вставка сортировки или что-то подобное). Если вы не знаете как - я могу помочь с этим.
  • иметь только один рабочий элемент, выполняющий сортировку на части N элементов
  • рассчитать максимальный размер локальной памяти на рабочую группу (вызов clGetDeviceInfo с CL_DEVICE_LOCAL_MEM_SIZE) и получить максимальное количество рабочих элементов на рабочую группу, поскольку при таком подходе количество рабочих элементов, скорее всего, будет ограничено объемом локальной памяти.

Я думаю, это будет работать довольно хорошо, потому что:

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

Дайте мне знать, если у вас есть проблемы с моими идеями.

РЕДАКТИРОВАТЬ 1:

Я только что понял, что использовал технику, которая может сбивать с толку других: мое предложение об использовании локальной памяти не предназначено для синхронизации или использования нескольких рабочих элементов для одного входного вектора / массива. Я просто использую его, чтобы получить низкую задержку чтения / записи памяти. Так как мы используем довольно большие куски памяти, я боюсь, что использование частной памяти может привести к обмену, чтобы замедлить глобальную память без нашего осознания этого. Это также означает, что вы должны выделить локальную память для каждого рабочего элемента. Каждый рабочий элемент будет иметь доступ к собственному фрагменту локальной памяти и использовать его для сортировки (исключительно). Я не уверен, насколько хороша эта идея, но я читал, что использование слишком большой частной памяти может привести к переключению в глобальную память, и единственный способ заметить это - посмотреть на производительность (не уверен, что я прав в этом).

Источник

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

  1. хранить (или иметь в наличии) предварительно вычисленные сети для n < 16
  2. отсортировать самые большие 2^k элементов с оптимальной сетью. Например: битовая сортировка для наибольшей степени 2 меньше или равна n.
  3. для остальных элементов повторите #2 до m < 16, где m - количество несортированных элементов
  4. использовать известную оптимальную сеть из #1 для сортировки любых оставшихся элементов
  5. сортировка слиянием наименьшего и второго наименьшего подсписков с использованием сети сортировки слиянием
  6. повторять #5, пока не останется только один отсортированный список

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

Стоит отметить, что (битовые) сети из #2 могут работать параллельно, а меньшие будут заканчиваться первыми. Это хорошо, потому что, когда они закончат, сети с #5-6 могут начать работать.

Источник
Другие вопросы по тегам