Цена излишних усилий: расширяющиеся деревья

Это перевод The cost of trying too hard: Splay trees. Автор: Реймонд Чен.

Часто, быть умным - это игра, которая не стоит свеч. К примеру, в 1980-х, мне сказали, что группа файловых систем работала над тем, какие структуры данных в памяти будут представлять содержимое каталогов, так что поиск файлового имени был бы быстрым. Одним из экспериментов, который они попробовали, заключался в использовании расширяющихся деревьев (splay tree). Расширяющиеся деревья были изобретены в Робертом Тарьяном и Даниелем Слейтором в 1985 г. как вид само-балансирующегося дерева, которое даёт амортизационную стоимость O(log n) для операции поиска элемента в дереве, где n - число узлов в дереве (амортизированная стоимость грубо означает, что стоимость M операций равна O(M log n). Стоимость одной операции - O(log n) в среднем, но индивидуальная операция может быть очень "дорогой")

Если вы знакомы с расширяющимися деревьями, то вы уже можете видеть, что должно случиться.

Одна из частных операций в каталоге - это перечисление всех файлов в нём, потому что, скажем, вы выполняете поиск файлов по содержимому или создаёте окно предпросмотра каталога. К сожалению, когда вы последовательно обращаетесь ко всем файлам (узлам в дереве) по порядку, это приводит к полностью разбалансированному дереву. Если вы перечисляете все файлы в папке и открываете каждый, то вы получите линейный связанный список, отсортированный в обратном порядке. Поиск первого файла в каталоге теперь стоит O(n).

С чисто алгоритмической точки зрения, поведение O(n) открытия этого файла не является темой для беспокойства. В конце концов, если вы дошли до этой точки, то вы уже выполнили n операций, так что очень дорогостоящая операция уже была "оплачена" большим числом предыдущих операций. Однако на практике люди не любят, когда стоимости операций варьируются в таких широких пределах. Если вы приходите на работу на пять минут раньше каждый день, а потом опоздаете на 90 минут, то ваше объяснение "Ну, я так много приходил рано, так что у меня всё ещё есть переработка, согласно амортизированной стоимости", вероятно, не будет убедительным.

Мораль истории: иногда большие затраченные усилия не оправданы.

(Постскриптум: да, позднее были выполнены исследования, показывающие наихудшую оценку времени выполнения для расширяющихся деревьев, но эти результаты не были доступны в 1980-х. Также, не забудьте, что нам важна равномерность времени доступа)