лекция 9 (1161104), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

В языке Ада множеств уже нет.

Множества похожи на структуру данных Map (таблица) или Dictionary( наличие элемента проверяется по ключу).

Основные понятия множества: содержится элемент или не содержится. Отсюда множество - частный случай таблицы.

Самый эффективный способ реализации таблицы – массив(x[i] ключ- № элемента). Но массивы очень требовательны к размерам памяти (ключ-строкамножество значений- множество слов в данном алфавите).

Следующий способ по эффективности - хэш-таблицы( требует хорошую функцию-расстановки).

Поэтому множества реализуют ещё и в виде двоичных деревьёв (Map'ов - они обязаны давать логарифмическую сложность => они используют деревья).

Для эффективной работы Dictionary(хэш-таблица) каждый объект может переопределить свою функцию(С#) GetHashCode()- функкция-расстановки основана на адресе, которая унаследована ещё от общего класса Object.

Стандартная реализация хэш-таблицы и пользовательская реализация функкции-расстановки. ( в Java есть аналогичная функция).

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

В Си++ стандартной реализации словаря нет (так как там GethashCode для каждого объекта, т.к. нет универсального типа Object).

Тоже самое относится к типу файл (до определенного времени (до С) включались специальные средства ввода/вывода, похожие на процедуры, но таковыми они не являются).

Начиная с языка Си все средства ввода-вывода вынесены в стандартную библиотеку.

Эволюция множеств:

В Паскаль множества есть.

В Модуле-2 множества есть, но они в виде BITSET = SET OF [0...N-1]; // N - разрядность машины

X:BITSET;

i in x;- установлен i-ый бит?

C помощью операций над множествами в этих языках мы манипулируем битами. В С, С++, Java множества не нужны, т.к. есть сдвиги и побитовые операции.

В Обероне остался единственный тип множества SET(аналог BITSET)(т.к. есть только целочисленный тип).

Особый тип данных – строки.

9

Характеристики

Список файлов лекций