The OpenNET Project / Index page

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



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

Оглавление

Выпуск языка программирования Rust 1.48, opennews (ok), 19-Ноя-20, (0) [смотреть все]

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


7. "Выпуск языка программирования Rust 1.48"  +15 +/
Сообщение от Аноним (7), 19-Ноя-20, 22:26 
а в планах чё? как жизнь вообще?
Ответить | Правка | Наверх | Cообщить модератору

77. "Выпуск языка программирования Rust 1.48"  +1 +/
Сообщение от Аноним (15), 20-Ноя-20, 02:10 
Математические подсчёты, максимальная клика графа и некоторые другие подобные вещи
Ответить | Правка | Наверх | Cообщить модератору

181. "Выпуск языка программирования Rust 1.48"  +/
Сообщение от Lex (??), 20-Ноя-20, 11:34 
ну это скучно. Айда какие-нибудь красно-черные деревья хотя б
Ответить | Правка | Наверх | Cообщить модератору

248. "Выпуск языка программирования Rust 1.48"  +2 +/
Сообщение от Ordu (ok), 20-Ноя-20, 21:37 
Красно-чёрные деревья, как и вся эта linked машинерия довольно плохо показывает себя на современных процессорах, в связи с тем что она не может в локализацию размещения в памяти. Кеш-промахи на кеш-промахах. Если тебе не нужны какие-то особые свойства сортированных деревьев, и всё что тебе нужно ассоциативный массив, то лучше хеш-табличку брать, она локализует.

Красно-чёрные деревья тогда взлетели в популярности на фоне DoS'ов на хеш-таблички нацеленных, но это быстро кончилось, потому как проще в хеш-табличку запилить хеш-функцию с умом сделанную -- потеряешь чуть больше на вычислении хеша, зато память почём зря грузить не будешь работой.

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

276. "Выпуск языка программирования Rust 1.48"  +1 +/
Сообщение от Аноним (-), 21-Ноя-20, 10:01 
> Красно-чёрные деревья тогда взлетели в популярности

Вот и выросло поколение хрустов. У них особые хеш таблички работающие быстрее деревьев. Ура товарищи, поколение готовое к уборке польской клубники - готово войти в строй !

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

278. "Выпуск языка программирования Rust 1.48"  –1 +/
Сообщение от Ordu (ok), 21-Ноя-20, 11:08 
А ты веришь в то, что деревья работают быстрее? У тебя какие-то измерения на руках есть, или может ты читал кого-то, кто намерял такое, или ты просто так веришь, религиозно?
Ответить | Правка | Наверх | Cообщить модератору

289. "Выпуск языка программирования Rust 1.48"  +3 +/
Сообщение от Ordu (ok), 21-Ноя-20, 16:13 
Я посчитал за тебя. Я взял 10M пар рандомных u64 и использовал их как ключ/значение для внесения в native-american/afro-american деревья и те же ключи/значения в хеш-таблички. Прошёлся несколько раз по этим парам, деля их поровну между разным количеством ассоциативных массивов. Например, в первый раз был миллион хештабличек и миллион деревьев, каждое из которых содержало 10 пар ключ/значение. На последней итерации было по сто хештабличек и деревьев, в каждом из которых было 100k пар.

При этом на каждой такой итерации я замерял суммарное время создания и время суммирования всех значений хранящихся в контейнерах.

Хештаблички использовали дефолтную хешсумму стандартной растовой реализации хештабличек, то есть с устойчивостью к HashDoS. Память под хештаблички я не предвыделял (размеры можно было посчитать заранее и предвыделить, но я решил, что это будет нечестно по-отношению к деревьям).

Так же, я НЕ пытался намеренно создавать деревья таким образом, чтобы их элементы были бы максимально ровным слоем размазаны по куче -- все пары ключ/значение каждой таблички я вбрасывал серией, чтобы все выделения памяти связанные с деревом были бы последовательны и ничто бы не затёсывалось между ними.

Подробности по ссылке[1]. Ниже результаты (ах, да, euclidian distance нужно игнорить, это типа для грубой проверки одинаковости содержимого получившихся структур).

generated 1000000 + 1000000 maps of size 10
Euclidian distance between sums: 0
htable: (1.4651s, 0.2207s) (GenTime, SumTime)
rtable: (1.2479s, 0.3766s) (GenTime, SumTime)
generated 100000 + 100000 maps of size 100
Euclidian distance between sums: 0
htable: (1.1254s, 0.1540s) (GenTime, SumTime)
rtable: (1.1358s, 0.4749s) (GenTime, SumTime)
generated 10000 + 10000 maps of size 1000
Euclidian distance between sums: 0
htable: (1.3795s, 0.1816s) (GenTime, SumTime)
rtable: (1.4985s, 0.5023s) (GenTime, SumTime)
generated 1000 + 1000 maps of size 10000
Euclidian distance between sums: 0
htable: (1.2782s, 0.2284s) (GenTime, SumTime)
rtable: (2.0798s, 0.5645s) (GenTime, SumTime)
generated 100 + 100 maps of size 100000
Euclidian distance between sums: 0
htable: (1.4600s, 0.2728s) (GenTime, SumTime)
rtable: (6.1659s, 1.3407s) (GenTime, SumTime)

Как видишь, на размерах до сотни пар (ключ, значение) хеш-табличка может создаваться чуть медленнее, но к размеру в 100k пар, дерево создаётся в разы медленнее. Суммирование же всех значений по этим контейнерам всегда быстрее на хеш-табличке. То есть, можно предположить, что при заполнении map'а высчитывание хеша плюс-минус компенсируется кеш-промахами, пока этих кеш-промахов не становится совсем уж много (по нескольку штук на каждую вносимую пару, их ведь O(log(N)) где N -- это количество элементов в дереве). При итерации по всем элементам, когда хештабличке уже не нужно считать хеши, она работает быстрее, хотя дерево продолжает так же мазать мимо кеша.

Я тебе реально говорю, деревья могут быть лучше, если тебе нужно, скажем, сортировать элементы, то есть нужны какие-то особые свойства деревьев. И то, стоит подумать, нельзя ли как-нибудь на хеш-табличке выкрутиться. Но если тебе нужен просто ассоциативное отображение, то деревья в помойку летят сразу.

[1] https://github.com/v-creizer/compare-rbtree-and-hashmap

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

317. "Выпуск языка программирования Rust 1.48"  +1 +/
Сообщение от InuYasha (??), 22-Ноя-20, 12:12 
Спасибо, познавательно.
Ответить | Правка | Наверх | Cообщить модератору

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

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




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

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