Поиск пальцем

В информатике поиск пальцем по структуре данных — это расширение любой операции поиска, поддерживаемой структурой, где вместе с запросом дается ссылка (палец) на элемент в структуре данных. Хотя время поиска элемента чаще всего выражается как функция количества элементов в структуре данных, время поиска пальца является функцией расстояния между элементом и пальцем.

В наборе из n элементов расстояние d ( x , y ) (или просто d , если оно однозначно) между двумя элементами x и y является их разницей в ранге. Если x и y — i -й и j- й по величине элементы в структуре, то разница в рангах равна | я - j |. Если обычный поиск в некоторой структуре обычно занимает время O(f( n )), то поиск x с помощью пальца y в идеале должен занимать время O(f( d )). Обратите внимание: поскольку d ≤ n , из этого следует, что в худшем случае поиск пальцем так же плох, как и обычный поиск. Однако на практике этот уродливый поиск пальцами выполняет больше работы, чем обычный поиск. Например, если f( n ) равно log( n ), и в худшем случае поиск пальцем выполняет в два раза больше сравнений, чем обычный поиск, из этого следует, что поиск пальцем происходит медленнее, когда d > √ n . Таким образом, поиск по пальцу следует использовать только тогда, когда можно разумно ожидать, что цель действительно окажется близко к пальцу.

Реализации

Некоторые популярные структуры данных поддерживают поиск пальцами без каких-либо дополнительных изменений фактической структуры. В структурах, где поиск элемента x выполняется путем сужения интервала, в котором x может быть найден , поиск пальца от y обычно выполняется путем обратного процесса поиска от y до тех пор, пока интервал поиска не станет достаточно большим, чтобы содержать x , после чего поиск продолжается в обычном режиме.

Сортированные связанные списки

В связанном списке элемент обычно ищется линейно, проходя от одного конца к другому. Если связанный список отсортирован и у нас есть ссылка на некоторый узел, содержащий y , то мы можем найти x за время O( d ), начав поиск с y .

Сортированные массивы

В отсортированном массиве A обычно ищут элемент x в A с помощью двоичного поиска . Поиск пальцем осуществляется путем выполнения одностороннего поиска из A [ j ] = y . В то время как двоичный поиск уменьшает пространство поиска вдвое после каждого сравнения, односторонний поиск удваивает пространство поиска после каждого сравнения. В частности, на k- й итерации одностороннего поиска (при условии, что x > y ) рассматриваемый интервал равен A [ j , j +2 ^{к -1}]. Расширение останавливается, как только A [ j + 2 ^{к -1}] ≥ x , после чего в этом интервале выполняется двоичный поиск x .

Если односторонний поиск требует k итераций, чтобы найти интервал, содержащий x , то из этого следует, что d > 2 ^{к -2}. Двоичный поиск в этом диапазоне также займет еще k итераций. Следовательно, поиск x по y пальцем занимает время O( k ) = O(log d ).

Пропустить списки

В списке пропуска можно выполнить поиск x пальцем из узла, содержащего элемент y , просто продолжив поиск с этой точки. Обратите внимание, что если x < y , то поиск продолжается назад, а если x > y , то поиск продолжается вперед. Обратный случай симметричен обычному поиску в списке пропуска, но прямой случай на самом деле более сложен. Обычно ожидается, что поиск в списке пропуска будет быстрым, поскольку контрольный элемент в начале списка имеет такую же высоту, как и самый высокий узел. Однако наш палец может быть узлом высотой 1. Из-за этого мы можем время от времени подниматься вверх при попытке поиска; то, что никогда не происходит обычно. Однако даже с этим усложнением мы можем достичь O(log d ). ожидаемого времени поиска ^[1]

Вкусности

Treap — это рандомизированное двоичное дерево поиска (BST). Поиск в трепе аналогичен поиску элемента в любом другом BST. Однако Treaps обладают тем свойством, что ожидаемая длина пути между двумя элементами расстояния d равна O(log d ). Таким образом, для пальцевого поиска из узла, содержащего y для x , можно подняться по дереву от y до тех пор, пока не будет найден предок x , после чего обычный поиск BST продолжается как обычно. Хотя определение того, является ли узел предком другого, является нетривиальной задачей, можно дополнить дерево для поддержки запросов этой формы, чтобы обеспечить ожидаемое время поиска пальца O(log d ). ^[1]

Веревки и деревья

Реализации веревки (структуры данных) обычно реализуют итератор положения шнура для перемещения по строке. Итератор можно рассматривать как палец, указывающий на определенный символ строки. Как и большинству сбалансированных деревьев, веревкам требуется время O(log( n )) для получения данных в одном листе дерева, если задан только корень дерева. Чтение каждого листа дерева, казалось бы, потребует времени O( n *log( n )). Однако, сохранив немного дополнительной информации, итератор можно использовать для чтения «следующего» листа всего за O(1), а каждого листа дерева — всего за O( n ). Реализации связок обычно кэшируют «дополнительную информацию» обо всем пути от корня до текущей позиции узла в итераторе. Другие реализации древовидных структур данных иногда хранят «дополнительную информацию» в самом дереве. сохранение указателя в каждом узле на его родителя или его преемника (в дополнение к обычным указателям в каждом узле на его дочерние элементы) и сохранение только текущей позиции узла в итераторе. ^[2] ^[3]

Обобщения

Если можно выполнить поиск по отпечатку пальца итерационным образом за время O ( f ( d )), где каждая итерация занимает время O (1), то, предоставив c разных пальцев, можно выполнить поиск по отпечатку пальца за O ( c min { d ( x , y ₁ ), ..., d ( x , y _c )}) время. Это достигается путем запуска поиска всех пальцев c и повторения каждого из них на один шаг вперед, пока первый не завершится.

Учитывая любую последовательность A = [ a ₁ , ..., a _m ] из m доступов, говорят, что структура обладает свойством статического пальца для фиксированного пальца f , если время выполнения A равно $O\left(\sum _{i=1}^{m}\log d(f,a_{i})\right)$ . Деревья расширений обладают этим свойством для любого выбора f без дополнительной обработки достаточно больших последовательностей доступов. ^[4]

Приложения

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

Дерево поиска пальцев — это тип структуры данных, которая позволяет указывать пальцы таким образом, чтобы все или некоторые из поддерживаемых ими операций выполнялись быстрее при доступе или изменении местоположения рядом с пальцем. В отличие от поиска по пальцам, описанного в этой статье, эти пальцы не предоставляются во время запроса, а указываются отдельно, чтобы все будущие операции использовали эти пальцы. Одним из преимуществ этого является то, что пользователю не нужно манипулировать или сохранять внутренние ссылки на структуру, он может просто указать элемент в структуре.

Ссылки

^ Перейти обратно: ^а ^б «Рандомизированные деревья развертывания: теоретические и экспериментальные результаты» (PDF) .
^ «Общие проблемы проектирования итератора дерева» .
^ Стивен Дж. Зейл. «Обход деревьев с помощью итераторов». Архивировано 16 февраля 2016 г. на Wayback Machine .
^ «Джон Яконо. Ключевая независимая оптимальность. Algorithmica, 42(1):3-10, 2005» (PDF) . Архивировано из оригинала (PDF) 13 июня 2010 г.

[brodal-1] Перейти обратно: ^а ^б «Рандомизированные деревья развертывания: теоретические и экспериментальные результаты» (PDF) .

[2] «Общие проблемы проектирования итератора дерева» .

[3] Стивен Дж. Зейл. «Обход деревьев с помощью итераторов». Архивировано 16 февраля 2016 г. на Wayback Machine .

[4] «Джон Яконо. Ключевая независимая оптимальность. Algorithmica, 42(1):3-10, 2005» (PDF) . Архивировано из оригинала (PDF) 13 июня 2010 г.

[1]

[2]

[3]

[4]