1 декабря я в очередной раз поучаствовал в Advent of Code, написав программу на Rust. Если интересно — код можно найти на GitHub. Тут мне хотелось бы рассказать о моём решении задачи, предлагавшейся во 2 день мероприятия, так как это решение, с одной стороны, сверх всякой меры оптимизировано, а с другой — демонстрирует кое-какие полезные приёмы. Чтобы не усложнять себе жизнь — мы рассмотрим лишь первую часть задачи, но те же приёмы можно применить и к её второй части.
Мы начнём входить в курс дела не спеша, но я предлагаю вам не отклоняться от заданного мной курса, так как, после того, как вы полностью прочтёте этот материал, у вас должно появиться понимание того, что именно делает следующая функция, как она работает, как такую функцию написать, и того, почему это — самая маленькая в мире хеш-таблица:
pub fn phf_shift(x: u32) -> u8 {
let shift = x.wrapping_mul(0xa463293e) >> 27;
((0x824a1847u32 >> shift) & 0b11111) as u8
}Rus https://habr.com/ru/companies/wunderfund/articles/723536/
Eng https://orlp.net/blog/worlds-smallest-hash-table/
👉 @rust_lib