Сканирование бинарного дерева поиска и массива

Question

Каким образом поиск элемента (хода) в BST будет медленнее, чем линейное сканирование его в массиве?

Ответ предположительно связан с кэшированием. Может ли кто-нибудь объяснить, что именно это означает и почему оно верно?

Как именно вы "кэшируете это", используя массив вместо кэширования с помощью BST?

Спасибо

Answer 1

Я предполагаю, что кеширование относится к кешам ЦП, которые поставляются с предварительным выборщиком, который предсказывает ваш следующий доступ к памяти. Поэтому, если вы выполняете последовательный поиск в массиве, ваш предварительный выборщик распознает шаблон доступа к памяти и загружает память в кэш ЦП, прежде чем ваш ЦП получит к нему доступ. Когда ЦП фактически получает доступ к следующему элементу памяти, он уже находится в кэше и может быть быстро доступен. Без кеширования и предварительной выборки вашему ЦП пришлось бы ждать, пока контроллер памяти извлечет данные из ОЗУ, что довольно медленно по сравнению с кешем ЦП.

В BST вы не делаете последовательный доступ. В худшем случае ваш BST не находится в смежной памяти, но каждый узел находится в некотором произвольном месте в памяти. Ваш предварительный сборщик не может предсказать это. Затем ЦП должен ждать извлечения каждого элемента из памяти.

А без предварительных загрузчиков касается строки кэша. На x86_64 длина строки кэша составляет 64 байта. Каждое целое число составляет 4 или 8 байт, поэтому вы можете сканировать 16 или 8 записей массива на строку кэша. Первый доступ к ячейке памяти извлекает всю строку, поэтому вы платите доступ к памяти только один раз за 8 сравнений. Для BST применяется тот же аргумент, что и выше. Память узла, скорее всего, находится не в одной строке кэша, поэтому для каждого сравнения приходится обращаться к памяти.

Подводя итог: A) Доступ к памяти занимает значительно больше времени, чем сравнение; Б) если поиск по массиву или BST быстрее, зависит от количества элементов.

Answer 2

Я предполагаю, что использование BST не дает вам никаких преимуществ, поскольку, даже если вы кэшируете данные (что означает, что есть какая-то локальность, вы можете получить доступ к тому же элементу позже, например), операция вставки Операция find всегда стоит O (h) , где h - высота дерева. В худшем случае даже O (n) .

Принимая во внимание, что использование массива для кэширования означает, что, конечно, сначала он может быть линейным, но всякий раз, когда вы впоследствии получаете доступ к одному и тому же элементу массива, если есть пространственная и временная локальность, вы можете получить прямой доступ к тем же блокам непрерывная память неоднократно, потому что вы уже знаете ее индекс, что означает, что у вас есть постоянный доступ по времени.