Исходное сообщение
"Выпуск языка программирования Rust 1.48" Отправлено Ordu, 20-Ноя-20 21:37
Красно-чёрные деревья, как и вся эта linked машинерия довольно плохо показывает себя на современных процессорах, в связи с тем что она не может в локализацию размещения в памяти. Кеш-промахи на кеш-промахах. Если тебе не нужны какие-то особые свойства сортированных деревьев, и всё что тебе нужно ассоциативный массив, то лучше хеш-табличку брать, она локализует. Красно-чёрные деревья тогда взлетели в популярности на фоне DoS'ов на хеш-таблички нацеленных, но это быстро кончилось, потому как проще в хеш-табличку запилить хеш-функцию с умом сделанную -- потеряешь чуть больше на вычислении хеша, зато память почём зря грузить не будешь работой.