Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Эффективное представление множеств


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

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

Если рассматриваются маленькие множества и необходимы операции пересечения и объединения, то можно порекомендовать представление множеств в виде битовых векторов. При этом подмножества основного множества представляются векторами битов, длина которых соответствует мощности основного множества. Если какой-либо элемент принадлежит множеству, то в соответствующий бит заносится значение true, в противном случае—значение false. Такое представление плохо подходит для очень большого основного множества, поскольку теряется много памяти, особенно в том случае, когда должны представляться подмножества с относительно малой мощностью. В этом случае предлагается рассматриваемое ниже представление, а именно методика хэширования.

Вычислительная структура множеств с доступом по ключу

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

sort key.

fct key=(data) key.

Выше приведенная функция осуществляет доступ к порциям данных типа data, содержащих в себе компоненту типа key.

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


- Начало -  - Назад -  - Вперед -