AVL trees

[vak]

Состряпал реализацию map<string, int> на скорую руку на Си, не без помощи ИИ. Грок неленивый программист, если ему прямо говорить что делать.

• Интерфейс: string_map.h
• Реализация: avlmap.c
• Тесты: avlmap_test.cpp

Выбрано представление в виде AVL деревьев. Они компактнее по памяти и вроде эффективнее красно-чёрных деревьев на всех операциях. Хэш был бы неплох, но вычисление хэш функций на словном процессоре типа БЭСМ-6 неэффективно.

Заодно узнал, что AVL деревья представляют собой наследие советской науки. Изобретены в 1962 году Адельсон-Вельским и Ландисом, на десять лет раньше красно-чёрных деревьев.

Георгий Максимович Адельсон-Вельский стоял у истоков шахматной программы Каисса. В 1992 году эмигрировал в Израиль.

Евгений Михайлович Ландис родом из Харькова. В 1968 году подписал нашумевшее письмо в защиту А. С. Есенина-Вольпина.

Comments

[spamsink]

Хэш-функцию можно выбрать любую, в т. ч. быстро вычисляемую на БЭСМ-6. Она совершенно не обязана быть криптографически стойкой или достигать avalanche. Мучиться с деревьями не имеет смысла.

[vak]

Деревья кушают меньше памяти, а алгоритмически не сложнее.

[spamsink]

Угадай с трех раз, почему в Паскаль-компиляторе используется хэш.

[vak]

Может Пирин тоже был не в курсе про AVL деревья. 😀

[spamsink]

В СССР про AVL деревья в курсе были все. Главный ответ: потому что идентификаторы были однословные!

Побочные ответы: потому, что реализация сбалансированных деревьев занимает безумное количество кода по сравнению с реализацией хэша, и потому, что удалять элементы из контейнера при закрытии scope тривиально, в отличие от дерева.

[vak]

Однословные идентификаторы плюс, конечно. Но у меня-то длина идентификатора не ограничена, и вообще UTF-8. Вовсе не безумное количество кода нужно. Хэш компактнее, конечно: 130 строчек. AVL дерево 200 строчек кода той же плотности.

Вот тут товарищ тестировал hash map против AVL, к примеру: https://medium.com/@ugurdilber1/hash-tables-vs-binary-search-trees-the-ultimate-search-battle-74e20a92c206

Когда парсер заработает, можно будет устроить бенчмарк. Подменить реализацию словаря с ALV tree на hash map и прогнать исходники ядра Юникса. Сравнить объём памяти и количество strcmp супротив вычислений хэша. Узнаем что-то новое.

[vak]

В дереве узлы тоже очень просто удаляются по концу scope. Заканчивается однократной перебалансировкой всего дерева.

Я добавил отдельный метод, который удаляет узлы по заданному критерию. В компиляторе переделаю на проверку уровня scope:

https://github.com/sergev/vak-opensource/blob/master/languages/c-language/map/avlmap.c#L296