Brodal et al.в своей статье ESA '06 продемонстрировано существование чисто функциональной структуры с логарифмическим поиском, обновлением и вставкой, а также слиянием в постоянном времени.(Заметьте, я не говорю о кучах Бродала, которые представляют собой другую структуру данных, довольно широко используемую для реализации чисто функциональных очередей с приоритетами.) Это кажется очень прибыльным результатом и должно привести к эффективным чисто функциональным наборам и картам, ноЯ не вижу, чтобы они использовались где-либо:
- В
containers Хаскелла используются деревья Адамса; - Стандартная библиотека OCaml использует деревья AVL;
- неизменные отсортированные карты Scala:реализованы с использованием красно-черных деревьев.
Если деревья Brodal действительно дают такие хорошие результаты, почему они не были адаптированы в стандартные библиотеки функциональных языков программирования?На самом деле, я вообще не видел ни одной реализации деревьев Бродала!
В частности, это потому, что:
- их очень сложно (или фактически почти невозможно) реализоватьправильно;
- константы очень велики, а реальные выгоды кажутся малыми;
- другие причины;
- или комбинация вышеупомянутых?