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

Пример пальцевого поиска по трепам.

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

В комплекте п элементы, расстояние d(Икс,у) (или просто d когда однозначно) между двумя элементами Икс и у это их разница в ранге. Если Икс и у являются яй и j-го наибольшего элемента в структуре, то разница в ранге |я - j|, Если обычный поиск в какой-либо структуре обычно занимает O (f (п)) время, то пальцем искать Икс пальцем у в идеале должен принимать O (f (d)) время. Заметьте, что поскольку d ≤ п, из этого следует, что в худшем случае поиск пальцем так же плох, как и обычный поиск. Однако на практике эти вырожденные поиски пальцами выполняют больше работы, чем обычные поиски. Например, если f (п) - это журнал (п), а поиск по пальцам выполняет в два раза больше сравнений, чем обычный поиск в худшем случае, из этого следует, что поиск по пальцам выполняется медленнее, когда d > √п. Следовательно, поиск по пальцу следует использовать только тогда, когда можно разумно ожидать, что цель действительно находится близко к пальцу.

Реализации

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

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

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

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

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

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

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

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

Treaps

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

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

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

Обобщения

Если можно выполнять поиск по пальцам итеративным образом в О(ж(d)) время, где каждая итерация занимает О(1) время, затем предоставив c разными пальцами, можно выполнить поиск по пальцам О(c min {d(Икс, у₁), ..., d(Икс, у_c)}) время. Для этого нужно запустить поиск пальцем по всем c пальцы, и повторяя их вперед на один шаг каждый, пока не завершится первый.

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

Приложения

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

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