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

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

В наборе из n элементов расстояние d ( x , y ) (или просто d в однозначном случае) между двумя элементами x и y равно их разнице в рангах. Если x и y являются i - м и j - м наибольшими элементами в структуре, то разность в рангах равна | i - 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 ^{k -1} ]. Расширение останавливается, как только A [ j + 2 ^{k -1} ] ≥ x , после чего этот интервал подвергается бинарному поиску для x .

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

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

Дерево — это рандомизированное двоичное дерево поиска (BST). Поиск в дереве аналогичен поиску элемента в любом другом BST. Однако у деревьев есть свойство, что ожидаемая длина пути между двумя элементами на расстоянии 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 равно . Развернутые деревья обладают этим свойством для любого выбора f без дополнительной обработки на достаточно больших последовательностях доступов. ^[4]${\displaystyle O\left(\sum _{i=1}^{m}\log d(f,a_{i})\right)}$

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

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