The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

Дэниэл Бернштейн опубликовал новую библиотеку djbsort, opennews (??), 11-Июл-18, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


9. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Michael Shigorinemail (ok), 12-Июл-18, 00:35 
> используются только простые арифметические инструкции
> без применения условного ветвления

Ого.

Ответить | Правка | Наверх | Cообщить модератору

12. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +9 +/
Сообщение от angra (ok), 12-Июл-18, 01:28 
Код не смотрел, но с точки зрения математики в самой идее сортировки без ветвлений ничего сложного, на уровне продвинутой школы. По сути нам надо реализовать min и max без условий. Сразу приходит идея использовать модуль числа и стандартный трюк с добавлением. Получаем что для произвольных a и b
a+( |b-a| + (b-a) )/2 раскладывается в два случая
a>b тогда |b-a| = a-b   и  a+( |b-a| + (b-a) )/2 = a+( a-b + b-a )/2 = a+0 = a
a<=b тогда |b-a| = b-a  и  a+( |b-a| + (b-a) )/2 = a+( b-a + b-a )/2 = a+(2b-2a)/2= a+b-a=b

Получили функцию max без ветвлений, аналогично делается функция min, после чего два подряд идущих числа заменяются на min и max от них, то бишь получаем правильный порядок для двух чисел, ну а дальше хоть пузырьком.

Само собой от математической идеи до эффективного кода очень долгий путь.

Ответить | Правка | Наверх | Cообщить модератору

16. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Аноним (16), 12-Июл-18, 02:11 
2.5 цикла CPU на байт данных
Ответить | Правка | Наверх | Cообщить модератору

17. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  –1 +/
Сообщение от Anonymous1 (?), 12-Июл-18, 02:26 
Нет, если a=b будет a, а значит

a>=b тогда ... = a
a<b тогда ..... =b

Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

19. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от backbone (ok), 12-Июл-18, 04:18 
А от деления / нельзя избавится?
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

21. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от bOOster (ok), 12-Июл-18, 05:36 
А если "слово" сдвинуть на 1 бит левее?
Ответить | Правка | Наверх | Cообщить модератору

22. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +2 +/
Сообщение от bOOster (ok), 12-Июл-18, 05:38 
Ну или правее?
Ответить | Правка | Наверх | Cообщить модератору

47. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от backbone (ok), 12-Июл-18, 09:46 
> Ну или правее?

Да, точно, дошло чуть позже, целые числа ведь.

Кстати, от ещё одной операции можно избавиться: a + b + |b - a| >> 1

Ответить | Правка | Наверх | Cообщить модератору

26. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +4 +/
Сообщение от angra (ok), 12-Июл-18, 07:29 
Я написал с точки зрения математики, а не кода на ассемблере. При оптимизации кода операции могут несколько отличаться от математического выражения. Например вычисление модуля числа делается путем операций сложения/вычитания и xor, а для деления на 2 используется сдвиг.

Ну и повторю еще раз, я не смотрел код и не говорил, что используется этот способ. Эта была просто первая пришедшая мне в голову идея на тему замены условных переходов на арифметические операции.

Ответить | Правка | К родителю #19 | Наверх | Cообщить модератору

20. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от bOOster (ok), 12-Июл-18, 05:34 
Ну в лучших традициях Брезенхема )
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

25. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +1 +/
Сообщение от нона (?), 12-Июл-18, 06:25 
Круто.
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

63. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Нанобот (ok), 12-Июл-18, 11:08 
т.е. это не будет работать для пар чисел вроде 1e+308 и 1e-308 и заявленое "может быть адаптирован для чисел с плавающей запятой" не соответствует действительности
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

218. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от angra (ok), 13-Июл-18, 20:59 
Сколько еще раз надо повторить, что я не смотрел код и не утверждал, что там используется такой алгоритм. Я всего лишь привел пример как можно сделать сортировку без ветвлений.
Ответить | Правка | Наверх | Cообщить модератору

97. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Sw00p aka Jerom (?), 12-Июл-18, 13:57 
>>По сути нам надо реализовать min и max без условий.

у минимаксового сортинга - квадратичная сложность во всех случаях.

Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

138. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +1 +/
Сообщение от anonymous (??), 12-Июл-18, 15:29 
вот только модуль без ветвлений вычислить нетривиально
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

217. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от angra (ok), 13-Июл-18, 20:57 
Да тем же принципом он вычисляется. Есть инструкция, которая знаковым битом eax заполняет edx,  дальше делается комбинация xor со сложением или вычитанием. Для полноценного понимания надо расписать то, как процеесор хранит отрицательные числа, а мне сейчас лень.
Ответить | Правка | Наверх | Cообщить модератору

182. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Александрemail (??), 12-Июл-18, 18:13 
уже начиная с p4 ненужно париться с арифметикой для этих min/max. интеловые процы имеют специальную инструкцию загрузки числа по выбору - она без ветвления кода исполняет сравнение и загрузку. если мне не изменяет склероз, АРМ и МИПС тоже так умеют. возня с арифметикой по модулю нужна для лютых процов которые такого не умеют.
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

184. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Аноним (183), 12-Июл-18, 18:38 
"Алгоритмические трюки для программистов", Генри С. Уоррен мл.

Учитесь, cуки, пока я живой и могу подсказать нужную литературу.

Взять можно, например, тут: https://proklondike.net/books/thalg/genri_warren_hack_deligh...

Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

200. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от Sw00p aka Jerom (?), 13-Июл-18, 03:57 
Колмогорова почитай лучше, циркач
Ответить | Правка | Наверх | Cообщить модератору

48. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +1 +/
Сообщение от Cradle (?), 12-Июл-18, 09:46 
не все так розово - у него там в разделе speed можно посмотреть производительность, алгоритм выдает O(n) только между 256 до 1024 элементов, на остальных случаях хуже. Так что, весьма ограниченное у него примемнение.
Ответить | Правка | К родителю #9 | Наверх | Cообщить модератору

99. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +1 +/
Сообщение от Sw00p aka Jerom (?), 12-Июл-18, 14:00 
сортировка за  O(n) - О_о, вы серьёзно?
Ответить | Правка | Наверх | Cообщить модератору

62. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от someone (??), 12-Июл-18, 11:01 
Там есть условные ветвления
Ответить | Правка | К родителю #9 | Наверх | Cообщить модератору

189. "Дэниэл Бернштейн опубликовал новую библиотеку djbsort"  +/
Сообщение от mikhailnov (ok), 12-Июл-18, 20:50 
То есть _в теории_ хорошо соптимизируется компилятором под VLIW e2k?
Ответить | Правка | К родителю #9 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру