Флейм
GameDev.ru / Флейм / Форум / Крестосвапы (3 стр)

Крестосвапы (3 стр)

Поделиться
Страницы: 1 2 3
ArochПостоялецwww11 окт. 201713:35#30
*Lain*
что толку что он работает, насколько он при этом будет быстр по сравнению с quicksort'ом тем же? Добавь одну более менее длинную строку и привет тормоза.
kiparПостоялецwww11 окт. 201714:00#31
Главное что он параллелится хорошо. А не то что эти квиксорты из олнопоточного века.
ZefickПостоялецwww11 окт. 201714:20#32
kipar
> Главное что он параллелится хорошо. А не то что эти квиксорты из олнопоточного века.
  Параллельный радикс это уже другой алгоритм. Распараллелив в лоб ты не получишь ничего хорошего. Merge Sort параллелится не хуже даже в лоб. А квиксорт сегодня уже и так практически никто не использует, хотя и его распараллелить никто не мешает.
gammakerПостоялецwww11 окт. 201718:46#33
*Lain*
> для радикс тоже универсальную хрень можно получить, но это надо вводить
> инфраструктуру выделения суб элементов
Один раз ввести на шаблонах, а дальше будет работать со всем, у чего есть итераторы.
А вместо операции сравнения будет функция извлечения ключа. Тоже вполне универсально, только требуются другие операции.

Zefick
>   Radix Sort для школоты младших классов, которая ещё не изучила действительные числа.
Нормально они сортируются, посложнее, чем целые числа, но не намного.

*Lain*Забаненwww12 окт. 20177:46#34
Aroch
ну как бы из задачи надо исходить. добавь более или менее длинный Boost.Multiprecision и получишь тормоза.
а вот если есть ограничение по длине (строк\чисел) или тебе надо trie построить, а не только сортирнуть, то радикссорт идеален
ArochПостоялецwww12 окт. 201715:13#35
*Lain*
> а вот если есть ограничение по длине (строк\чисел)
о чем и речь, что область применения весьма узкая и это надо понимать, а не брать и потом удивляться а чего это скорость просела или вообще результат не тот.
desssПостоялецwww12 окт. 201717:25#36
Zefick
> Radix Sort для школоты младших классов, которая ещё не изучила действительные числа.
Плавающие числа отлично сортируются. Сначала по знаку, затем по порядку, и далее по мантиссе. Можно отдельно обрабатывать NaNы.

Aroch
> что толку что он работает, насколько он при этом будет быстр по сравнению с
> quicksort'ом тем же? Добавь одну более менее длинную строку и привет тормоза.
Он часто встречается в гибридных алгоритмах сортировки строк, где эта проблема решена.

Я писал in place radix sort, он в 2-3 раза медленнее, но всё еще быстрее чем merge sort и память не требует.
Если нужна стабильность, скорость и есть возможность использовать radix sort, то он даже на int64 и double быстрее чем практически любая другая сортировка (на случайных данных).

А из нестабильных сортировок на сравнениях, сейчас модная эта https://github.com/orlp/pdqsort

Правка: 12 окт. 2017 17:47

FordPerfectПостоялецwww12 окт. 201718:02#37
>по порядку, и далее по мантиссе
Нет повода разделять. Порядок/мантисса - общая сортировка, же.

Правка: 12 окт. 2017 18:03

desssПостоялецwww12 окт. 201718:45#38
FordPerfect
> Нет повода разделять. Порядок/мантисса - общая сортировка, же.
Действительно - порядок в старших разрядах относительно мантиссы находится.
Страницы: 1 2 3

/ Форум / Флейм / Программирование

2001—2017 © GameDev.ru — Разработка игр