<<
>>

Задача

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

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

Словарь представляет собой структуру данных, которая поддерживает следую- щие операции:

♦ MakeDictionary инициализирует словарь, способный хранить подмножество S универсального множества U; только что созданный словарь пуст.

♦ Insert(u) добавляет элемент u Uв множество S. Во многих случаях с u также связывается дополнительная информация (например, u может быть именем или табельным номером работника, а в структуре данных также сохраняется личная информация о работнике); будем считать, что эта информация сохра- няется в словаре как часть записи вместе с u. (Таким образом, в общем случае под «элементом u» будет пониматься u вместе с дополнительной информацией).

♦ Delete(u) удаляет элемент u из множества S, если он там хранится.

♦ Lookup(u) проверяет, принадлежит ли элемент u множеству S (и если принад- лежит читает дополнительную информацию, сохраненную вместе с u).

Многие реализации, рассмотренные ранее в книге, используют эти операции

(или часть из них): например, в реализациях алгоритмов обхода графа BFS и DFS велись множества S уже посещенных узлов. Тем не менее между теми задачами и текущей ситуацией существует принципиальное различие — размер U. Универ- сальное множество U в BFS и DFS представляет собой множество узлов V, уже явно заданное как часть входных данных. В таких случаях вполне допустимо хра- нить множество S !Ξ U так, как это делалось: определение массива с позициями |U|, по одной для каждого возможного элемента, и присваивание элементу в позиции, соответствующей u, 1 для u S или 0 для u ⅜ S. Такая реализация позволяет вы- полнять операции вставки, удаления и проверки с постоянным временем простым обращением к элементу массива.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ