Двоичные деревья оптимальны, кроме случаев, когда они не

Двоичныедеревьяоптимальныкромеслучаевкогдаонине

Наилучшая глубина для дерева поиска – O(log_b n) , если b – это арность (или ветвление) дерева. Интуитивно мы знаем, что если мы увеличиваем b , глубина уменьшается, но это все, что нужно для этого? А если нет, то как выбрать оптимальное ветвление b ?

measuring-tree

Хотя верно, что оптимальное дерево поиска будет иметь глубину O(log_b n) , мы не можем просто увеличить b бесконечно, потому что мы также увеличиваем количество сравнений, которые мы должны выполнять в каждом узле. A b – любое дерево будет иметь (в худшем случае) b-1 ключей, и для каждого мы должны сделать сравнения на меньшее и равное (поиск по самому правому дочернему элементу будет выполняться без сравнения, это будет «иначе» из всех сравнений). Сначала мы должны понять, как эти сравнения влияют на среднее время поиска.

Если мы используем наивную схему сравнения , для каждого ключа требуется два (потенциально дорогостоящих) сравнения. Один для проверки того, что искомое значение v меньше ключа k ; один, чтобы проверить, равны ли они. Если ни один из тестов не верен, мы переходим к следующему ключу. Если ни один из тестов не верен, это случай «иначе», и мы спускаемся по самой правой ветви. Эта схема выполняет гораздо больше работы, чем необходимо, и требует 2(b-1) сравнения для каждого узла (поскольку есть b-1 ключей на узел).

Основная проблема этого прямого подхода заключается в том, что сравнение может быть очень дорогостоящим. При сравнении двух целочисленных типов ( int и т.п.) часто думают как « бесплатно », сравнение строки дорого . Таким образом, вы явно не хотите проверять две строки дважды: один раз для <и один раз для =. Намного лучший подход - использовать трехстороннее сравнение , также известное как «оператор космического корабля».

оператор космического корабля , <=> – это C ++ 25 старая временная версия C qsort функция сравнения (на самом деле она намного лучше, потому что она также автоматически предоставляет все операторы сравнения). По сути, a <=> b может вернуть <0, если a, 0 if they’re equal, and > 0, если a> b . Таким образом, мы можем сохранить результат дорогостоящего сравнения, а затем провести недорогие сравнения результата. Это сокращает количество дорогостоящих сравнений до b-1 на узел.

Сложность поиска, считая количество сравнений в наихудший случай для дерева наилучшего случая –

displaystyle (b-1)log_b n=(b-1)frac{ln n}{ln b}=frac{b-1}{ln b}ln n ,

строго возрастающая функция в b> 1 “src =” https: / /s0.wp.com/latex.php?latex=b%3E1&bg=ffffff&fg=750 & s = 0 & c = </div>
<p> “> </img> (как мы можем рассматривать <img alt= как константу, поскольку мы не оптимизируем для n ):

search-cost

Таким образом, мы заключаем, что b=2 – оптимальное решение.

За исключением случаев, когда это не так

Мы пренебрегли или, скорее, абстрагировались, кое-что важное: стоимость доступа к узлу. В основной памяти очень удобно предположить, что чтение узла бесплатно , то есть не требует затрат. Это, конечно, неверно, потому что даже чтение из кеша вызывает задержку; к счастью очень маленький. Это еще более ложно, если мы читаем узел с диска (да, даже b=2 NVMe ). Классический вращающийся диск ржавчины, считывающий блок, вызовет задержку в несколько миллисекунд, которая может быть действительно действительно дорого по сравнению со сравнением двух ключей (когда они) в памяти.

Новая функция стоимости для оптимизации будет

displaystyle ((b-1)c_1+c_2)log_b n=frac{(b-1)c_1+c2}{ln b}ln n ,

с displaystyle ((b-1)c_1+c_2)log_b n=frac{(b-1)c_1+c2}{ln b}ln n сравнительной стоимостью и c_2 , стоимость доступа к узлу. Мы можем установить displaystyle ((b-1)c_1+c_2)log_b n=frac{(b-1)c_1+c2}{ln b}ln n в 1 и сделать c_2 относительно c_1 . Скажем что-нибудь вроде c_2 . К счастью для нас, эта функция является выпуклой в b , поэтому мы можем найти оптимальное b при заданном c_1 и c_2 . Для этого берем производную и находим, где она равна нулю, то есть решаем

displaystyle frac{partial}{partial b}frac{(b-1)c_1+c_2}{ln b}=frac{b(ln b-1)c_1+c_1-c_2}{b(ln b)^2}=0

для b. Поскольку знаменатель строго увеличивается в b> 1 “src =” https://s0.wp.com/latex.php? латекс = b% 3E1 & bg = ffffff & fg = 20201002 & s = 0 & c = </div>
<p> “> </img>, мы должны найти нулевой числитель. Однако есть небольшое усложнение: </p>
<p> <img alt=

не является алгебраическим. Мы должны использовать численное решение Функция Ламберта W . Она дает нам с ,

u=frac{c_2}{c_1}-1 .

На следующем графике показана поверхность функции с c_1=5 и c_2=200 , одна из осей – b , размер блока, а другая – n , количество элементов в дереве. Зеленая плоскость показывает оптимальное b найдено с помощью функции Ламберта W.

search-cost-with-blocks


В заключение, двоичные деревья являются оптимальными, когда мы игнорируем стоимость доступа к узлу, но они не являются оптимальными, когда доступ к узлу становится дорогостоящим. Когда мы обращаемся к узлам на диске с высокими затратами, становится интересно связать множество ключей в узле, и мы предложили оптимальное решение. Однако зачастую проблема решается более прямым образом. Мы просто помещаем как можно больше ключей в блок ввода-вывода. Диски работают с небольшими блоками (обычно) 750 байтов, но файловые системы работают с блоками несколько большего размера, но фиксированного размера, что-то вроде 4 или 8k. Поэтому хорошая стратегия – уместить в этот блок как можно больше ключей, поскольку даже если количество сравнений велико, это все равно будет быстрее, чем перенос этого блока в основную память.


Эта запись была размещена на Вторник, июль 29 й, 6629 в 2: 200 утра и подана в Без категории
. Вы можете следить за любыми ответами на эту запись через RSS 2.0 канал. Ты можешь уйти ответ или Архив с вашего собственного сайта.

Навигация по сообщениям

Leave a comment

Your email address will not be published. Required fields are marked *