Задача поиска и хранения информации

Аннотация

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

Здесь рассмотрен простейший тип информации — таблица и запросы "Добавить строчку", "Удалить строчку" и "Извлечь строчку, в первом столбце которой стоит X".

Для этой задачи мы попробуем оценить эффективность нескольких классических структур данных

Неупорядоченный массив
Упорядоченный массив
Неупорядоченный список
Двоичное дерево поиска
Сбалансированные деревья

Содержание:

Постановка задачи

Задачу поиска и хранения информации приходится решать практически во всех приложениях.

Мы рассмотрим один из простых вариантов этой задачи: Есть список фамилий людей с укзанием года рождения, то есть архив записей с двумя полями : name и year. К нам приходят запросы:

запрос	описание
add ( name, year)	Добавить новую запись в хранилище
del ( name)	Добавить запись на человека `name`
find ( name)	Найти запись на человека `name`

Считайте, что запросы всех трех типов приходят в случайном порядке и примерно в одном и том же количестве.

Нужно спроектировать хранилище для указанных данных, которое будет выполнять эти запросы за разумное время (менее 1 сек. на запрос) и способно хранить до 100 000 000 записей. Если запись имеет размер 30 байт, то хранилище будет иметь размер 3Gb. Возможно ли это?

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

Тип структуры хранилища	add	del	find
Неупорядоченный массив	1	N	N
Упорядоченный массив	N	N	log N
Неупорядоченный список	1	1	N
Двоичное дерево поиска	H	H	H
Сбалансированные деревья	log N	log N	log N

Неупорядоченный массив

Самый простой вариант, это хранить все записи в памяти (или на диске) друг за другом.

Новую запись будем добавлять в конец массива — это будет делаться за время O(1), то есть некоторое конечное небольшое время, независимое от N.

Зато оперции поиска find и удаления del будут долгими. Единственный способ в неупорядоченном массиве найти нужный элемент — это перебирать последовательно его элементы и сравнивать ключи элементов с нужным нам ключем (в начем случае ключ — это фамилия; ключем называют поле, по которому осуществляется поиск; обычно ключ является уникальным идентификатором записи). Таким образом, пока не найдется нужная запись алгоритм переберёт в среднем половину записей, то есть затрат время порядка N/2. Часто бывает так, что то, что ищут, в хранилище отсутствует, и алгоритму приедтся пробежаться по всему массиву записей и затратить время порядка N. Примерная оценка скорости компьютера такая: за одну секунду просматривается 1 000 000 записей.

Если у нас 100 000 000 записей, то операция поиска может занять 100 секунд, а это много.

Тоже самое касается операции удаления. Чтобы удалить, мы сначала должны найти удаляемую запись. Затем нужно сместить идущие за ней записи на единицу влево, чтобы убрать отразовавшуюся дырку. Если удаляется первый элемент массива, то нужно второй переместить на место первого, третий на место второго и так далее, всего N-1 перемещений. В среднем перемещений будет N/2, и они более трудоемкие, нежели чтение.

Получаем такой результат:

Тип структуры хранилища	add	del	find
Неупорядоченный массив	1	N	N

Для нас важно лишь то, что время на поиск и удаление растёт с N линейно. Коэффициент перед N не так важен, поэтому мы его не пишем (да и не можем его вычислить, не имея конкретной машины и реалицации алгоритма) .

Упорядоченный массив

Идея — если записи упорядоченны, то искать проще.

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

Этот метод поиска называется поиск делением попалам (binary search, метод деления попалам, дихотомия).

Пусть искомый элемент имеет индекс $i\in[l,r)$ . Тогда программа для его поиска методом деления попалам выглядит так

int c,l,r;
...
while( r - l > 1) {
   c = (l + r) / 2;
   if( less (x, data[c]) ) r = c; 
   else l = c;
}
return l;

Каждая итерация while уменьшает область поиска в два раза. Если в начале у нас 100 элеменов, то на следующем шаге будет 50, а на следующем — 25 и так далее. Так как $2^{10}=1024 \approx 10^3$ , то поиск в упорядоченном массиве из 10^6 элементов требует 20 итераций, а если элементов 10^8 , то требуется 27 итераций ( $\log_2 10^8 = 26.5754...$ ).

26 операций на современных компьютерах выполняются мгновенно.

Давайте теперь посмотрим, сколько нам потребуется времени на операции добавления и удаления записи.

Удаление из упорядоченного массива будет быстрее, так как мы быстрее найдем удаляемый элемент. Но затем снова нужно выполнить в среднем N/2 операций сдвига эдементов для удаления образовавшейся "дырки" в массиве, поэтому ассимптотика среднего времени операции удаления будет прежняя — O(N).

Операцией добавления элемента в упорядоченный массив тоже оказывается трудоемкая — при добавлении мы хотим сохранить свойство упорядоченности. Мы не можем просто добавить элемент в конец массива. Нужно найти для него место в массиве, а затем раздвинуть его, чтобы освободить для нового элемента место (то есть начиная с последнего элемента перемещать элементы на один вправо). В среднем снова получим N/2 сдвигов, а значит ассимптотика равна O(N).

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

Тип структуры хранилища	add	del	find
Неупорядоченный массив	1	N	N
Упорядоченный массив	N	N	log N

Вывод: Хранить в упорядоченном массиве данные эффективно только тогда, когда они не меняются, то есть запросов del и add не приходит.

Неупорядоченный список

Идея: Мы много времени в массивах тратим на перемещение хвоста массива. Это можно избежать, если пользоваться списками.

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

Определение. Список называется двусвязным если каждый элемент содержит информацию о местах, где находятся следующий и предыдущий элемент списка. Если в элементе хранится информация только о следующем элементе, то список называется односвязным.

Для того, чтобы вставить элемент внутрь оносвязного списка, нужно разорвать одну стрелочку и добавить две новых (для двусвязного списка нужно разорвать две стрелочки и добавить свои четыре):

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

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

Итак, операция добаления и удаления элемента из списка занимает O(1) времени. Поиск элемента, как и в неупорядоченном массиве займет в среднем O(N) времени.

Тип структуры хранилища	add	del	find
Неупорядоченный массив	1	N	N
Упорядоченный массив	N	N	log N
Неупорядоченный список	1	1	N

Двоичное дерево поиска

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

Эта идея позволяет создавать в пямяти компьютера самые разнообразные структуры данных — всевозможные графы, к вершинам и ребрам которых прикреплены какие-то данные.

Первое простейшее приложение этой идеи — двоичное дерево. В этой структуре данных каждый элемент имеет три стрелочки: к родителю, к правому ребенку и к левому ребенку:

На рисунке узел A есть родитель узлов B и C; узел B — его левый ребенок, узел C — правый.

Некоторые узлы этого дерева не имеют детей — они называются листья дерева (висячие вершины), некоторые имеют только одного ребенка. Только одна вершина не имеет родителя (на рисунке это вершина A), она называется корнем дерева. Обычно двоичное дерево рисуют сверху вниз, то есть стрелки указывающие на детей направлены вниз. Корень дерева — это самая верхняя вершина (в теории алгоритмов деревья растут вниз, а не вверх).

Двоичным деревом поиска называется двоичное дерево, в котором выполнено следующее свойство:

Для любой вершины X ключи всех элементов из правого поддерева X больше ключа X, а ключи всех элементов из левого поддерева X меньше ключа X.

В частности,

$key(p\rightarrow left) < key(p) \leslant key(p \rightarrow right),$

то есть ключ родителя находится между ключами левого и правого детей.