Введение
Несколько месяцев назад в поисках идей по ускорению кода я изучал множество научных статей по computer science. Не буду притворяться, что хорошо их понимал, но меня не пугает непонятное, и я готов признать своё невежество1. Я обнаружил статью, написанную пятнадцать лет назад2, в которой было множество новых для меня концепций. Мне никак не удавалось в них разобраться.
Что же делать дальше? Можно искать другие статьи, чтобы они заполнили мои пробелы. Это рискованное предприятие, потому что они могут запутать ещё больше, но избежать этого нельзя. Я нашёл статью с нужной структурой данных, в которой упоминался исходный код с веб-сайта. Код был написан на C++, а я работаю на Rust, но решил, что всё равно стоит на него взглянуть. Однако зайдя на сайт, я не обнаружил там ресурс, поэтому я написал владельцу веб-сайта, который оказался преподавателем computer science.
Этот преподаватель (Гонсало Наварро) очень тепло меня принял и сразу же ответил мне3 4. И только в процессе общения с ним я осознал, что видел его фамилию на множестве статей в этой области. Оказалось, я познакомился с одним из специалистов мирового уровня в области компактных структур данных (succinct data structure). Невежество может завести очень далеко.
Что же такое компактные структуры данных? Если вы изучали в последние десятилетия computer science, то могли сталкиваться с ними, но мне не доводилось встречаться с ними в процессе работы программистом, а если и доводилось, то я сразу же о них забыл. Но я считаю, что эти структуры данных обладают потрясающими свойствами.
Все мы пользуемся массивами и хэш-таблицами5, популярны также различные деревья. Нам не нужно полностью понимать их устройство, чтобы эффективно пользоваться их свойствами. А теперь я задаюсь вопросом, почему же люди не используют компактные структуры данных чаще.
Я решил, что стоит немного о них рассказать.Читать полностью »
