Вопрос 40 Таблицы (1006393)

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

Текст из файла

Вопрос 40 Таблицы, способы их организации (упорядоченные таблицы, таблицы-деревья, перемешанные таблицы).

Таблица - упорядоченное множество пар (ключ,тело) ({K,T},R); R (отношение) задано по ключам, т.е. все пары различаются по ключам.

Операции:

• найти тело с заданным ключом,

• изъять из таблицы элемент с заданным ключом,

• вставить в таблицу элемент с заданным ключом,

• найти тело с min (max) ключом.

• Изменить тело у заданного ключа на новое.

Все базы данных - таблицы.

Примеры:

функция может быть представлена как пара (аргумент, результат),

таблица с записями о людях. В такой таблице ФИО - ключ, данные о человеке - тело.

Классификация таблиц:

Методы работы с таблицами распадаются на три группы относительно способа задания таблиц:

1) последовательные таблицы

Рис 1 линейная цепочка

2) древовидные таблицы

Рис 2 Дерево

n - число элементов таблицы

3) таблицы с прямым доступом: по ключу сразу получаем тело

Последовательные таблицы (не отсортированные)

Последовательные таблицы, как правило, небольшие таблицы, для которых скорость доступа не важна.

Пусть

К - количество элементов в таблице;

N - длина вектора для представления таблицы.

Векторное представление:

Линейная последовательность элементов, имеющих структуру (key, body); время поиска ~ К/2

Основные операции:

• Вставить – вставка осуществляется в конец последовательности.

• Изменить – осуществляется последовательный перебор и сравнение с ключом. Перебор прекращается, если найден элемент с заданным ключом или достигнут конец. С читается, что количество элементов задано.

Сложность этих операций К/2.

• Исключить – находиться требуемый элемент, удаляется, а все последующий за ним сдвигаются на один влево.

Сложность:

К/2 – поиск;

К/2 – сдвиг;

Общая - К/2+К/2=К, то есть сложность линейна.

Списковое представление:

Последовательность элементов, имеющих структуру (key, body, связь)

Рис 3

Последовательные таблицы (не отсортированные, списковое представление)

Операции:

Вставить – вставка в конец, зная ссылку на последний элемент, добавляем новый элемент в память, причем его ссылка = NULL, а для последнего элемента ссылка = ссылка на новый элемент. В этом случае сложность от длины не зависит.

Изменить – поиск в цикле. Сложность К/2.

Удалить – для элемента находящегося в середине списка удаление происходит путем переписи ссылки. Пусть удаляем элемент k, тогда для элемента k-1 ссылка = (ссылка на элемент k+1). После этого требуется освободить память. Если требуется удалить первый элемент, то для этого переопределяется ссылка на начало таблицы как ссылка на второй элемент. Затем освобождается память. Если удаляется последний, то ссылка предпоследнего элемента = NULL.

Сложность = сложности поиска по линейному списку ~К/2

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

Последовательные таблицы (отсортированные, упорядоченные)

(ki ,kj) R

Пусть ключи простые и упорядочены по возрастанию I(Kj )=I(K_t )+1

Операция Вставить: все элементы с ключом выше заданного сдвигаются вправо в памяти путем перезаписи, начиная с последнего. На освободившееся место записывается новый элемент.

Выводы:

1) Сложность операции вставки для отсортированных таблиц возросла, сложность остальных операций осталась линейной.

2) Основная сложность операций в таблице - поиск. Для последовательных таблиц она линейна, относительно длинны таблицы.

3) Векторное представление хорошо, когда операции удаления и вставки относительно редки, а, если же нет, то предпочтение нужно отдавать списковому представлению.

4) Операцию поиска можно сократить за счёт сокращения длины путей поиска.

5) Для последовательных таблиц понижение сложности можно достичь за счет использования информации о встречаемости ключей.

Таблицы как деревья сравнений

Все множество элементов таблицы разобьем на классы

Al < А2 < A3 < ...

Ai =

Рис 4.

А = { AXN, BIC, BJH, BJY, CMP, JSR, MOV, UHW }

А1 = { AXN, BIC, BJH }

А2 = { BJY }

A3 = { CMP, JSR, MOV, UHW }

All={AXN}

Al2 = {BIC}

А13 = {BJH}

Рис 5.

Поиск осуществляется либо в правом поддереве (если ключ корня больше заданного), либо в левом (наоборот).

Таблицы как деревья сравнений (ДС), векторная память

Смотри рис 5.

Рис 6.

Диапазон индексов в векторе: 2-9

Ищем BJY

9+2 div 2 = 5 → BJY

2-5

2+ 5 div 2 = 3 → BIC

3-5

3+ 5 div 2 = 4 → BJN

и т.д.

Вставка: найти нужное место и сдвинуть всю оставшуюся часть вектора, сохранив дерево.

Пример: в дерево вставить элемент с ключом KCR.

1-ый способ: находим ближайший элемент, больший чем данный ключ и совершаем следующее преобразование:

СМР

2-ой способ:

• если вставляемый ключ > корневого, то двигаемся вправо, иначе влево;

• дойдя до листа, вставляем ключ в левое поддерево, если он < листа, и в правое, если наоборот, т.е.

Сложность поиска: надо просмотреть не более самого длинного пути - высоты дерева. Для совершенного двоичного дерева log₂ (K+l)-l ~ log₂K, где К - количество компонентов в таблице.

log₂2K=l+log₂K

Операция вставки (удаления) - сдвиг надлежащей части вектора.

Вывод: ДС в векторной памяти хороши когда основными операциями являются поиск и изменить. Должны хранить вектор максимальной длины, независимо от заполнености дерева.

Таблицы как ДС в списковой памяти

Как понизить сложность операции вставки и удаления в векторной памяти?

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

ПРИМЕР: Пусть элементы поступают в следующем порядке:

{ AXN, UHW, MOV, JSR, BIC, CMP, BJY }

Сложность К/2

Сложность зависит от порядка поступления элементов.

Можно сделать ребалансировку дерева.

Операция ИСКЛЮЧЕНИЯ.

1. Найти удаляемую запись и отметить ее родителя; (Удаление корня особый случай).

1. Найти запись, которой можно заменить удаляемый элемент. Это либо ближайший больший (самый левый справа), либо ближайший меньший (самый правый слева).

2. Модифицировать поля левый, правый у родителя удаляемой и у родителя замещающей записей.

Есть опасность нарушить балансировку дерева, а следовательно увеличить сложность операций поиска.

Сложность операции вставки и удаления в среднем по всем возможным порядкам поступления:

Таблицы с прямы доступом

Раньше мы сравнивали ключ заданного элемента с ключами других элементов таблицы.

Но по ключу можно сразу вычислять номер элемента таблицы.

т.е. имеем некоторую функцию:

F(K) = код (n) 26ⁿ + код (n-1) 26^n-1+...+ код(О) 1

f(MOV)=12 14 21 ... = 8497

f(CMP) = 2 12 15 ... = 1679

и т.д.

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

Перемешанные таблицы

Пусть имеем К ключей.

n - количество индексов таблицы с непосредственным доступом.

Выбирается N: К < N << n

Проблема: что делать, если f(k₁) = f(k₂), k₁= k₂, где f() - функция перемешивания.

В нашем случае к=8. Пусть N=10, f = f(k) mod 10.

Способ борьбы с коллизиями - применение функции перемешивания

ФУНКЦИЯ ПЕРВИЧНОГО ПЕРЕМЕШИВАНИЯ

Три способа построения функции первичного перемешивания:

1. Размер таблицы выбирается как степень двойки, ключ представляется в виде некоторого числа [ключ]2. Полученное число записывается в двоичном виде и берется серединная вырезка и эта величина и берется, как значение HASH-функции. Такой способ обладает хорошим свойством равномерности распределения по входам таблицы.

1. метод основанный на операции деления:

[ключ] - некоторое число [ключ]/D, где D - взаимно простое к N Этот метод применяется, если количество элементов невелико.

1. умножение ключа на некоторую константу М

ФУНКЦИЯ ВТОРИЧНОГО ПЕРЕМЕШИВАНИЯ.

1. Линейное перемешивание

Значение функции rehash вычисляется как: rehash(ref) = ref + h

1. Квадратичное повторное перемешивание

Функция вычисляется как значение a*i²+ b*i + с, где i - количество применений функции. Сложность: выбор а,b,с.

1. Случайное перемешивание

Вычисляется следующим образом: ref + £, где £, - случайная величина.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)