Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 20
Интересно было бы увидеть сравнение скорости выполнения на наборах данных разной длинны и сравнение с аналогичным алгоритмом на CPU.
Пишут про О большое, а не пишут, что будет, когда оперативной памяти не хватает.
Шейдерная реализация более параллельна чем CUDA`вская? Или в чём смысл изврата?
Шейдерная как минимум будет работать на amd
Проанализировав блог автора, я увидел, что он просто любитель программировать шейдеры и делает это очень хорошо.
Оставлю ссылку на статью Параллельная сортировка методом пузырька на CUDA.
Наверное, задам совсем глупый вопрос. Но как понять, что сортировка окончена?
Если каждый элемент был сравнен с каждым другим, то сортировка завершена. n-1 шагов.
А если изначально список не так сильно перепутан? Например, только два соседних элемента местами поменяны, то что, всё равно ждать n-1 шагов?
А за какое количество сравнений вы сможете проверить что массив отсортирован?
Очевидно, что за n-1. Изначально я давал оценку сверху. Если исхитриться, думаю можно намутить какой-нибудь флаг (например в первом "пикселе" строки вычислять, отсортирована ли входная информация. Мне, кстати, не до конца понятно, почему автор не прерывает вычисления. Похоже, что он таким образом отказывается от ветвления. Ну, я ему доверяю, так что наверное так эффективно. Или как минимум, легко реализовать и объяснить.
Собственно, у меня поэтому и появился этот вопрос. Потому как в статье об окончании сортировки ничего не говорится, но когда-то же надо остановиться. И если делать какие-то проверки массива на то, отсортирован ли он, то вырастет сложность алгоритма. Производить же гарантированное количество шагов сортировки мне в голову не пришло.
Ответ, как мне кажется, заложен в самом вашем вопросе. Вы говорите, что "… только два соседних элемента местами поменяны...". У меня вопрос: как вы можете это определить в общем случае? Я подчёркиваю: в общем случае, а не на одном шаге сложного алгоритма, где вы уже многое знаете о данных.
Я совершенно не разбираюсь в алгоритмах сортировки, да и программист из меня так себе, так, пару скриптов на bash'е написал. Ход мысли у меня был такой: если мы будем работать по подобному алгоритму в один поток, т.е. сначала сравним первый и второй элемент массива, потом второй и третий… То с минимальной перепутанностью (поменяны местами два соседних элемента) нам понадобится пройти по массиву всего два раза — на втором проходе мы замечаем, что не выполнили ни одной перестановки. Но если мы действуем по тому алгоритму, что описан в статье на большом количестве потоков, то уже так просто не узнать, закончена ли сортировка. Надо либо придумывать какие-то алгоритмы межпоточного взаимодействия, либо, как мне выше подсказали, ждать гарантированное количество итераций. Даже мне, далёкому от анализа и оценки сложности алгоритмов, понятно, что любое межпоточное взаимодействие будет сложнее простого счётчика. Но в случае с минимальной перепутанностью алгоритм выглядит не очень оптимальным, зато очень предсказуемым. Мы точно знаем, сколько нам понадобится времени на сортировку. В некоторых задачах, как мне кажется, это может быть полезно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Параллельная сортировка данных в GPU