Описание тега sorting-network
Сеть сравнений / компараторов для наиболее эффективных программ сортировки, где количество элементов массива невелико.
3
ответа
Как исправить этот нерекурсивный алгоритм сортировки нечетных и четных слияний?
Я искал нерекурсивный алгоритм сортировки нечетных и четных слияний и нашел 2 источника: книга от Седжвик Р. этот ТАК вопрос Оба алгоритма идентичны, но неверны. Результирующая сеть сортировки не является сеткой сортировки с нечетным четным слиянием…
22 дек '15 в 23:42
0
ответов
Четно-нечетная сортировка слиянием 64 входов в 64 выхода сортированных 32-битных слов работает частично
У меня есть модуль в VHDL, который делает то, что состояние в заголовке. Дело в том, что эта строка безупречна в отсортированном наборе чисел, в отсортированном по убыванию множестве и в полу-смешанном наборе чисел, но с действительно случайными чис…
01 май '14 в 02:03
0
ответов
Сортировка слиянием в регистре simd
Может кто-нибудь придумать способ выполнить сортировку слиянием на 8 элементах регистра simd за 3 шага и 4 сравнения на каждом шаге? Заранее спасибо!
30 мар '18 в 16:45
12
ответов
Самый быстрый способ сортировки 10 номеров? (числа 32 битные)
Я решаю проблему, и она включает в себя сортировку 10 чисел (int32) очень быстро. Мое приложение должно сортировать 10 чисел в миллионы раз как можно быстрее. Я выбираю набор данных из миллиардов элементов, и каждый раз мне нужно выбрать из него 10 …
23 авг '15 в 22:23
1
ответ
Оптимальная 9-элементная сеть сортировки, которая сводится к оптимальной сети с медианой 9?
Я изучаю сети сортировки и медианного выбора для девяти элементов, основанные исключительно на операциях с двумя входами минимума / максимума. Кнут, TAOCP Vol. 3, 2-е изд. утверждает (стр. 226), что для сортировочной сети из девяти элементов требует…
02 авг '17 в 06:54
1
ответ
Разъяснение по верхним и нижним границам размера сортировочных сетей
Ссылаясь на эту статью в Википедии: https://en.wikipedia.org/wiki/Sorting_network, с акцентом на параграфе " Создание сетей сортировки". Можете ли вы объяснить, что Size, upper bound а также Size, lower bound (в таблице) есть? Я ожидаю, что lower bo…
02 сен '16 в 09:08
1
ответ
Оптимальные нечетно-четные сети слияния Батчера для размеров, отличных от 2^n
В эти дни я пытался реализовать сортировку сетей до размера 32 с минимальным количеством единиц сравнения-обмена (оптимальных по размеру, а не по глубине). На данный момент я могу использовать следующие ресурсы для создания своих сетей: Сортировка с…
24 окт '15 в 16:20
2
ответа
Список компараторов в сортировочных сетях
У меня есть вопрос в моем домашнем задании, и мне трудно вовремя визуализировать и понять вопрос. Вопрос в следующем: Мы можем представить сеть сравнения с n-входами с c компараторами в виде списка из c пар целых чисел в диапазоне от 1 до n. Если дв…
22 май '14 в 12:02
1
ответ
Сокращение сети сортировки
Сортировочная сеть - это компоновка из 2 входных компараторов, которые могут сортировать входную последовательность из n элементов. Например, вот сортировочная сеть для 9 элементов ввода: Каждая из вертикальных линий представляет собой 2 входных ком…
12 фев '17 в 21:21
1
ответ
Сортировка сетей - какие сети позволяют пропустить сравнение?
GCC реализация qsort использует медиану-3, чтобы выбрать точку разворота. При этом 3 элемента отсортированы с помощью сортировочной сети. Сортировочная сеть для 3 элементов обычно требует 3 сравнений. Но в этой конкретной реализации последнее сравне…
06 окт '16 в 20:38
4
ответа
Очень быстрая сортировка массивов фиксированной длины с использованием компараторных сетей
У меня есть некоторый критичный к производительности код, который включает в себя сортировку очень короткого массива фиксированной длины с примерно 3-10 элементами в C++ (параметр изменяется во время компиляции). Мне пришло в голову, что статическая…
05 ноя '13 в 13:48
1
ответ
Битоновая сортировочная сеть против Thrust::sort_by_key
Я реализовал алгоритм, который использовал сортировку. Я попробовал Thrust::sort_by_key, который занял около 0,4 с, чтобы отсортировать массив с 10^7 элементами. Я думал, что сеть битовой сортировки должна быть быстрее, чем Thrust::sort_by_key. Одна…
15 авг '11 в 05:54
3
ответа
Стандартные сортировочные сети для малых значений n
Я ищу реализацию сети сортировки с 5 элементами, но так как я не смог найти хорошую ссылку на SO, я хотел бы попросить сети сортировки для всех небольших значений n, по крайней мере, n=3 через n=6, но более высокие значения также были бы хорошими. Х…
11 окт '10 в 01:56
2
ответа
Пересортируйте вектор после изменения небольшого количества элементов.
Если у нас есть вектор размера N, который был ранее отсортирован, и заменить до M элементов произвольными значениями (где M намного меньше, чем N), существует ли простой способ их повторной сортировки с меньшими затратами (т.е. создать сортировку се…
15 сен '14 в 19:31
1
ответ
Сеть бабочек в сортировке
Я изучаю четные нечетные слияния в алгоритмах Роберта Седвика в C++. В качестве части текста автор упомянул о том, как нечетно-четная сортировка слиянием может использоваться для реализации параллельной сортировки в сети сортировки. В этом контексте…
18 ноя '13 в 07:18
2
ответа
Как сортировка сетей строится вручную
Есть много 4-элементных, 6-элементных (входных) ... 16-входных сетей сортировки, но мне нужна 32-входная версия, чтобы иметь алгоритм сортировки сдвига 32x32 (который я планирую как вспомогательную функцию Opencl), чтобы иметь сдвиг 1024x1024 алгори…
14 сен '14 в 22:25
1
ответ
Параллелизированная малая сеть
Я работал над сетью (для массивов меньше 8) и заметил, что все алгоритмы сосредоточены на его способности разрешать параллельные операции. Вот один такой набор для массива размером 5. #define SWAP(x,y) if (data[y] < data[x]) { int tmp = data[x]; …
12 июл '15 в 21:46
0
ответов
Динамическая настройка размера сети сортировки - простой способ увеличить на единицу
Insetion sort, переписанный как сеть sort, производит что-то вроде этого: Он сортирует шесть элементов, например, используя следующие сравнения: [0,1] [1,2][0,1] [2,3][1,2][0,1] [3,4][2,3][1,2][0,1] [4,5][3,4][2,3][1,2][0,1] Теперь допустим, у меня …
22 янв '14 в 08:54
6
ответов
Как сеть сортировки превосходит универсальные алгоритмы сортировки?
Что касается самого быстрого вида массива int с фиксированной длиной 6 , я не совсем понимаю, как эта сеть сортировки превосходит алгоритм, подобный сортировке вставкой. В этом вопросе приведено сравнение количества циклов ЦП, использованных для зав…
10 окт '10 в 16:17
1
ответ
Сортировка сетей по затратам и задержкам
Из того, что я прочитал, я не мог понять, как рассчитывается стоимость и задержка. Стоимость: количество палочек или блоков сравнения-обмена. Задержка: количество сравнений-обменов в последовательности. Я разместил свой пример ниже
19 июн '15 в 07:15