Адаптивные алгоритмы сортировки по сравнению с сетями сортировки для сортировки списка из 32 случайных элементов

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

Оптимальных сетей (пока) для n=32 элементов не существует. С практической точки зрения, если мы хотим минимизировать количество тактовых циклов процессора, лучше всего разделить 32 элемента на четыре подсписка n = 8 и применить оптимальную сеть сортировки к каждому подсписку, а затем объединить списки вместе?

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

Подсчитав цифры имеем следующее:

Сортировка списка размера n:

  • Минимальное количество сравнений для n=2 равно 1.

  • Минимальное количество сравнений для n=4 равно 5.

  • Минимальное количество сравнений для n=8 равно 19.

Объединение двух списков размера n:

  • Объединить два списка n = 2 - это 2 * n - 1 = 3 сравнения

  • Слияние двух списков n = 4 равно 2 * n - 1 = 7 сравнений

  • Слияние двух списков n=8 равно 2*n - 1 = 15 сравнений.

  • Слияние двух списков n=16 равно 2*n - 1 = 31 сравнению.

Общее количество сравнений, если мы разделим n=32 на шестнадцать n=2 подсписков:

  • Сортировка: 1*16 = 16
  • Слияние: 3*8 + 7*4 + 15*2 + 31*1 = 113
  • Всего: 129

Общее количество сравнений, если мы разделим n=32 на восемь подсписков n=4:

  • Сортировка: 5*8 = 40
  • Слияние: 7*4 + 15*2 + 31*1 = 89
  • Всего: 129

Общее количество сравнений, если мы разделим n=32 на четыре подсписка n=8:

  • Сортировка: 19*4 = 76
  • Слияние: 15*2 + 31*1 = 61
  • Всего: 137

Теперь можно подумать, что было бы лучше разделить n=32 элемента на n=2 или n=4 подсписка, так как общее количество сравнений меньше. Но слияние требует хранения частей массива «не на своем месте», что может свести на нет преимущество меньшего количества сравнений?

Моя интуиция подсказывает мне, что в среднем неадаптивная сеть сортировки похожа на алгоритм с точки зрения общего количества сравнений, но сеть сортировки выигрывает из-за меньших накладных расходов, я прав?

Я пытаюсь отсортировать n=32 элемента в среднем менее чем за 1200 тактов. Я работаю на простой последовательной машине с простой 256 слов * 16-битной памятью и всего четырьмя регистрами, поэтому сеть/алгоритм должен быть простым, быстрым и не требовать много места. ALU имеет только функции сложения, вычитания, сдвига на один бит, поворота на один бит, И и ИЛИ. Операции с памятью и ALU занимают один такт каждая.


arrays optimization sorting algorithm sorting-network
person SwedeGustaf    schedule 26.04.2018    source источник
comment
Большинство алгоритмов сортировки представляют собой n*log(n), т.е. 32*5 = 160. За исключением таких особенностей, как сортировка по основанию, но это зависит от того, какие значения вы сортируете (если вы хотите отсортировать значения 0-15, и вы можете используйте массив count с 16 элементами, вы можете отсортировать его всего примерно за ~ 90 инструкций (16 для нулевого массива счетчиков, 32 для подсчета элементов, 32 для вывода отсортированного массива)). И действительно ли элементы случайны, или в их случайности есть какое-то слабое место, позволяющее вам ожидать чего-то от них? (в почти отсортированном массиве некоторые алгоритмы сортировки будут работать лучше, чем другие) Что это даст?   -  person Ped7g    schedule 26.04.2018
comment
(звучит для меня немного похоже на какие-то спрайты HW или что-то подобное, так что, возможно, есть какой-то уродливый ярлык для реализации этого без полной точной сортировки)   -  person Ped7g    schedule 26.04.2018
comment
Как указано в комментариях, оптимальная сеть сортировки для 32 элементов потребует около 160 сравнений. Это означает, что вам придется в среднем 7,5 циклов на сравнение. Я не знаю, каковы тайминги инструкций вашей машины, но это кажется довольно амбициозным. Загрузить два операнда из памяти, вычесть, сравнить и выполнить переход менее чем за 7,5 тактов? Затем умножьте время подкачки (еще два доступа к памяти) на среднее количество необходимых подкачек. Вы уверены, что ваша проблема разрешима, учитывая ограничения?   -  person Jim Mischel    schedule 26.04.2018
comment
@JimMischel Каждый год в моем университете проводится соревнование с этой конкретной настройкой, и в прошлом году парню, который выиграл, удалось отсортировать пять случайных списков n = 32 со средним значением 1157 тактов на список.   -  person SwedeGustaf    schedule 26.04.2018
comment
@JimMischel С моим текущим решением я сократил до 9 тактов на сравнение, исключая свопы, и 12 тактов, включая свопы. Это не включает часть слияния подсписков, поэтому я не доволен этим решением. Аки Суихконен упомянул использование кучевой сортировки как потенциальное решение проблемы. Как вы думаете, превзойдет ли Heap оптимальную сеть сортировки в этом конкретном случае?   -  person SwedeGustaf    schedule 26.04.2018
comment
@ Ped7g Мне сказали, что списки взяты из /dev/random, что бы это ни значило, но я думаю, что они совершенно случайны. Элементы в списке находятся в диапазоне от 0000 до FFFF в шестнадцатеричном формате. Будет ли в этом случае сортировка по основанию близкой к оптимальной?   -  person SwedeGustaf    schedule 26.04.2018
comment
Да, Linux /dev/random — это максимально случайный поток байтов, так что для вас это означает равномерно распределенные 16-битные целые числа без смещения в сторону уже частично отсортированных. (В отличие от многих реальных входных данных сортировки, но хорош тем, что не склоняется к какому-либо конкретному алгоритму сортировки).   -  person Peter Cordes    schedule 26.04.2018
comment
Я не думаю, что у вас достаточно памяти или достаточно быстрого переключателя ALU для эффективной сортировки RadixSort. Однако вы можете повернуть старшие 1 или 2 бита вниз и замаскировать другие биты. Анализ только количества сравнений - совершенно ошибочный подход, когда у вас есть только 4 регистра; некоторым алгоритмам потребуется гораздо больше сброса/перезагрузки, если им нужно отслеживать больше вещей. Пожалуйста, обновите информацию о том, как ваша машина обращается к памяти: вам всегда нужно выполнять загрузку в регистр перед использованием, или у вас есть инструкции, которые вычитают операнд памяти из регистра ALU? Нравится sub reg,[mem]?   -  person Peter Cordes    schedule 26.04.2018
comment
Слияние дешево для сравнения, но обычно требует копирования обоих входных данных куда-то еще, что может занять больше машинных циклов, чем то, что иногда не меняет местами после сравнения.   -  person Peter Cordes    schedule 26.04.2018
comment
Сортировка кучей может быть хорошей альтернативой. Обязательно ознакомьтесь с некоторыми оптимизациями, которые дают очень близкое к теоретическому минимуму количество сравнений. Но сначала попробуйте простую реализацию.   -  person Jim Mischel    schedule 26.04.2018
comment
[min #]comparisons for n=8 is 19 если это из википедии о #сравнениях, необходимых для сортировки списка, есть что-то не так - должно быть 16, а всего 125.   -  person greybeard    schedule 26.04.2018
comment
не очень дикая догадка: спускаясь по пути минимальной сортировки сравнением, вы исчерпаете место для кода - подумайте или перестановку, которую вам все еще нужно выполнить, как только вы ее определили. Один из самых важных вопросов о вашей машине: 1) наличие, скажем, условных ходов 2) время, затрачиваемое на а) вызов/возврат б) условные филиалы.   -  person greybeard    schedule 26.04.2018
comment
нет, 16-битный /dev/random не является хорошим кандидатом для системы счисления, но он отлично подходит для угадывания среднего значения как половины диапазона (т.е. значение разделения для 0-15,16-31, скорее всего, будет около 0x8000, тогда следующее разделение на эти половины, вероятно, будет около 0x4000 и 0xC000 ... по крайней мере, статистически, на многих многих выборках Всего на 32 элементах и ​​только нескольких запусках это может не демонстрировать такое равномерное распределение, linux random достаточно силен.   -  person Ped7g    schedule 26.04.2018
comment
@greybeard Где я могу найти минимальную сеть для n = 8, у вас есть ссылка?   -  person SwedeGustaf    schedule 27.04.2018
comment
@PeterCordes Я постараюсь обновить свой вопрос с более подробной информацией о машине. На данный момент я могу сказать, что у машины есть регистр, который действует как указатель на память. Поэтому, если вы хотите сохранить значение из регистра в память, вы должны сначала загрузить значение указателя в регистр указателя на первом такте, а затем на втором такте вы можете отправить желаемое значение в память. Если вы хотите загрузить значение из памяти, вы сначала отправляете значение указателя в регистр указателя в первый такт, а затем во второй такт загружаете в нужный регистр.   -  person SwedeGustaf    schedule 27.04.2018
comment
@PeterCordes Важная деталь отсутствует выше: если вы хотите использовать любой из четырех регистров, вы должны отправить значение указателя в другой регистр (это называется IR, а регистр указателя для памяти называется ASR), который затем открывает данные переводите в регистр, который вы хотите.   -  person SwedeGustaf    schedule 27.04.2018
comment
@PeterCordes Однако есть два других регистра, которые я не упомянул, которые называются HR и AR, где второй используется ALU для вычислений. Поскольку вам нужно использовать указатель для использования основных четырех регистров (называемых gr0-gr3), я думаю, что быстрее использовать регистр HR, AR и IR, поскольку они не требуют указателя, вы можете отправлять значения в них напрямую либо из памяти или другие регистры. Но, как я уже сказал, память всегда требует обновления указателя для загрузки или сохранения с определенного адреса.   -  person SwedeGustaf    schedule 27.04.2018
comment
Здесь следует различать две модели сортировки: сортировка на компьютере общего назначения (часто обозначаемом как ОЗУ) против использования специальной сети сортировки. Я полагаю, что ваша машина (в то время как значительно занижена) является (намного ближе) к общей оперативной памяти. Как ни странно(?), минимальная верхняя граница количества сравнений, необходимых для сортировки значения n, выше для сетей только от 5 и выше. Стиль RAM был бы выгоден при дорогостоящих сравнениях, сети с условными ходами.   -  person greybeard    schedule 27.04.2018
comment
@greybeard Я разместил новый вопрос с дополнительной информацией о модели компьютера. Проверьте это.   -  person SwedeGustaf    schedule 29.04.2018
comment
@PeterCordes Я разместил новый вопрос с дополнительной информацией о модели компьютера. Проверьте это.   -  person SwedeGustaf    schedule 29.04.2018
comment
@ Ped7g Я разместил новый вопрос с дополнительной информацией о модели компьютера. Проверьте это.   -  person SwedeGustaf    schedule 29.04.2018
comment
Вы можете проверить этот документ, если вы еще этого не сделали: arxiv.org/pdf/1505.01962. pdf   -  person Morwenn    schedule 17.05.2019

Ответы (1)


arrow_upward
1
arrow_downward

Сортировка кучи — nlogn. Вычисление индекса тривиально — сравниваемые элементы всегда имеют индексы n, 2n+{1,2}, что делает его вычислительно эффективным с вашей архитектурой.

Рабочая лошадка сортировки кучи — это в основном рутина:

while(true){
    r=(i+1)*2; l=r-1;
    if (*l > * i) { 
       if (*r > *l) swap(i,r);
       else swap(i,l);
    }
    else { 
       if (*r >* i) swap(i,r);
       else break;
    }
 }

Операция подкачки должна в качестве побочного эффекта также обновить адрес i либо на l, либо на r. В отличие от решения из учебника, мы не проверяем правильность адресов дочерних элементов, а жертвуем пространством, чтобы ускорить выделение буфера из 32 нулей в конце массива. Как только i не больше любого из дочерних элементов, переход к нижней части кучи заканчивается.

person Aki Suihkonen    schedule 26.04.2018