close

Вход

Забыли?

вход по аккаунту

?

Алгоритмы и структуры данных. Лекция 6

код для вставкиСкачать
Хеш-поиск.
Лекция 6
План лекции
1. Внешний поиск с использованием B-деревьев.
2. Ещё раз об абстракции Отображение.
3. Обобщённый быстрый поиск.
4. Хеш-функции.
5. Хеш-таблица с прямой адресацией.
6. Хеш-таблица с открытой адресацией.
7. О параллельных алгоритмах поиска. Списки с пропусками.
8. Пример использования алгоритмов и структур данных
Внешний поиск с использованием B-деревьев
I
Основной носитель информации — жёсткий диск.
I
Информация на жёстком диске располагается в секторах,
которые логически расположены на дорожках.
I
Размер сектора типично 512/2048/4096 байт.
I
Информация считывается и записывается головками
чтения/записи.
I
Для чтения/записи информации требуется подвести
головку чтения записи к нужной дорожке и дождаться
подхода нужного сектора.
I
Типичные скорости вращения жёстких дисков —
5400/7200/10033/15000 оборотов в минуту.
I
Один оборот совершается время от 1/90 до 1/250 секунды.
I
Операция перехода на соседнюю дорожку примерно
1/1000 секунды.
Работа с внешними носителями
I
Внешние сортировки используют многократный
последовательный проход по данным, расположенным на
носителях информации.
I
Последовательное считывание информации с жёсткого
диска 100-150 мибибайт в секунду.
Смена позиции в файле часто требует:
I
I
I
ожидания подвода головки на нужную дорожку;
ожидания подхода нужного сектора к головкам
чтения/записи;
I
Операция последовательного чтения 4096 байт занимает
4096
≈ 40 × 10−6 секунд
100×106
I
Операция случайного чтения 4096 байт занимает не менее
5 − 10 × 10− 3 секунд.
Работа с внешними носителями
I
Второй носитель — SSD диск.
I
Информация хранится в энергонезависимой памяти на
микросхемах.
I
Операции производятся блоками размером 64-128
кибибайт.
I
Время доступа к блоку ≈ 10−6 секунд.
I
HDD и SSD используют буферизацию для ускорения
работы.
I
Алгоритмы поиска во внешней памяти должны
минимизировать число обращений к внешней памяти.
Оценка применимости внешнего поиска
I
Пусть имеется бинарное дерево поиска, состоящее из:
1. Данных размером 64 байта.
2. Ключа размером 8 байт.
3. Указателей left и right размером 8 байт.
I
Общий размер узла — 88 байт.
I
В оперативную память размером 16 гибибайт поместится
16×23 0
≈ 195 × 106 узлов.
88
I
Как хранить словарь из 109 элементов?
B-деревья
I
B-дерево — сбалансированной дерево поиска, узлы
которого хранятся во внешней памяти.
I
В оперативной памяти хранятся часть узлов.
B-деревья: свойства
135
86
27
46
105
88
165
113
143
152
160
189
213
I
Высота дерева не более O(log N), где N— количество
узлов.
I
Каждый узел может содержать 1 ключ и больше.
I
Количество детей узла равно K + 1, где K — количество
ключей в узле.
B-деревья: свойства
K1-K128
1
129
2
…
K1-K128
…
K1-K128
…
I
Пусть в узле помещается 128 ключей.
I
Высота дерева — 3
I
Тогда общее количество узлов
1 + 129 + 1292 = 16771
I
Общее количество ключей
16771 × 128 = 2146688
…
B-деревья: определение
I
B-дерево — корневое дерево, обладающее свойствами:
1. Каждый узел содержит:
I
I
I
I
2.
3.
4.
5.
6.
7.
8.
количество ключей n, хранящихся в узле.
индикатор листа final.
n ключей в порядке возрастания.
n + 1 указатель на детей, если узел не корневой.
Ключи есть границы диапазонов ключей в поддеревьях.
Все листья расположены на одинаковой глубине h.
Имеется показатель t — минимальная степень дерева.
В корневом узле от 1 до 2t − 1 ключей.
Во внутренних узлах минимум t − 1 ключей.
Во внешних узлах максимум 2t − 1 ключей.
Заполненный узел имеет 2t − 1 ключ.
B-деревья: высота
I
I
Теорема: Высота B-дерева с n > 1 ключами и
минимальной степенью t > 2 в худшем случае не
n+1
превышает logt
2
Доказательство. В максимально высоком дереве высоты
h в каждом узле, кроме корневого, содержится t − 1 ключ.
Тогда общее количество ключей в дереве есть
1 + 2 + 2t + 2t 2 + · · · + 2t h−1 =
= 1 + 2(t − 1)(1 + t + t 2 + · · · + t h−1 ) =
= 1 + 2(t − 1)
Отсюда
h = logt
th − 1
t −1
n+1
2
B-деревья: операции
I
Используем операции Load и Store.
I
Корень сохраняем в оперативной памяти.
I
Минимизируем количество операций.
B-деревья: операция find поиска ключа k
1. Операцией бинарного поиска ищем самый левый ключ
keyi > k
2. Если keyi = k, то узел найден.
3. Исполняем Load для дочернего узла и рекурсивно
повторяем операцию.
4. Если final = true, то ключ не найден.
Количество операций Tload = O(h) = O(logt n)
Добавление ключа
1. Операцией find находим узел для вставки.
2. Если лист не заполнен, сохраняя упорядоченность
вставляем ключ.
3. Если лист заполнен (2t-1 ключей), разбиваем его на два
листа по t-1 ключу поиском медианы.
4. Медиана рекурсивно вставляется в родительский узел.
Сложность в худшем случае: каждый раз разбивается узел на
каждом уровне, O(t logt n)
Количество операций: Text = O(h) = O(logt n)
Разновидности B-деревьев
I
B+ -дерево содержит информацию только в листьях,
ключи только во внутренних узлах.
I
Используется в файловых системах XFS, JFS, NTFS, Btrfs,
HFS, ...
I
Используется для хранения индексов в базах данных
Oracle, Microsoft SQL, IBM DB2, Informix, ...
Обобщённый быстрый поиск
Абстракция отображение
Интерфейс абстракции отображение как ассоциативного
массива.
I
m[key] = value — добавить элемент с ключом key и
значением value
I
value = m[key] — найти элемент с ключом key и вернуть
его.
I
m[key] = nil — удалить элемент с ключом key
I
for (auto x: m) — получить все ключи (или все пары
ключ/значение) в каком-либо порядке.
Абстракция отображение
Алгоритм
операция
BST: Вставка
BST: Поиск
Худшее время
Среднее время
O(N log N)
O(N log N)
O(N log N)
O(N log N)
Обобщённый быстрый поиск
I
Требуется:
I
I
Уменьшить амортизационную стоимость поиска
Уменьшить функцию (например, O(log N) → O(log log N))
Обобщённый быстрый поиск
I
База данных названий городов и их численности.
А
Б
…
Абакан
Брянск
165000
415000
Астрахань
Бийск
520000
210000
Амурск
Бологое
43000
23000
33 связных списка.
М
…
Ы
…
Я
Ытык-Куёль
Якутск
6700
270000
Ярославль
590000
Обобщённый быстрый поиск
I
База данных названий городов и их численности.
А
Б
…
Абакан
Бийск
165000
210000
М
…
Ы
…
Я
Ытык-Куёль
Якутск
6700
270000
Ярославль
Амурск
Астрахань
Бологое
Брянск
43000
520000
23000
415000
33 сбалансированных дерева.
590000
Обобщённый быстрый поиск
I
Основная идея — разбиение пространства ключей на
независимые подпространства (partitioning ).
I
При независимом разбиении на M подпространств
сложность уменьшается.
Для разбиения множества N ключей на примерно равные M
подмножеств сложность вычисляется по главной теореме о
рекурсии при числе подзадач M, коэффициенте размножения 1
и консолидации O(1).
C
O(N)
M
C
C · O(N log N) → O(N log N)
M
C · O(N) →
Обобщённый быстрый поиск
I
При увеличении M
lim T (N, M) = O(1)
K →∞
lim Mem(N, M) = ∞
K →∞
I
Имеется зона оптимальности при M ≈ N
Обобщённый быстрый поиск
I
Требуется иметь детерминированный способ разбиения
пространства ключей на M независимых подпространств.
I
Условия разбиения:
|K1 | ≈ |K2 | ≈ · · · ≈ |KM |
M
X
|Ki | = |K |
i=1
I
Эврика! Создаём функцию H(K ), удовлетворяющую
некоторым условиям.
Хеш-поиск
Хеш-поиск
I
Функция преобразования:
H(K ) → V
|D(V )| = M
Требуемые свойства:
I Эффективность.
T (H(K )) 6 O(L(K )),
I
где L(K ) — мера длины ключа K .
Равномерность. Каждое выходное значение равновероятно.
pH(K1 ) = pH(K2 ) = · · · = pH(KM )
I
Лавинность. При изменении одного бита во входной
последовательности изменяется значительное число
выходных битов.
Хеш-поиск
Следствия их требуемых свойств.
I
Функция не должны быть непрерывной. Для близких
значений аргумента должны получаться сильно
различающиеся результаты.
I
В значениях функции не должно образовываться
кластеров, множеств близко стоящих точек.
Определение непрерывности для дискретных функций может
быть дано неформально.
Хеш-поиск
Примеры плохих функций:
I
H = K 2 mod 10000 для K < 100
Функция монотонно возрастает.
I
H=
s.size()−1
P
s[i] для строки s.
i=0
Функция даёт одинаковые значения для строк abcd и abdc
и отличающиеся на единицу для строк abcd и abde.
Хеш-функции
I
Не столь отвратительная функция
h=
n
X
si × 8i
mod HASHSIZE
i=0
Схема Горнера:
unsigned
hash_sum(string s, unsigned HASHSIZE)
{
unsigned sum = 0;
for (size_t i = 0; i < s.size(); i++) {
sum <<= 3;
sum += s[i];
}
return sum % HASHSIZE;
}
Хеш-функции
I
Хеш-функция получше
unsigned
hash_sedgwick(string s, unsigned HASHSIZE)
{
unsigned h, i, a = 31415, b = 27183;
for (h = 0, i = 0; i < s.size();
i++, a = a * b % (HASHSIZE-1)) {
h = (a * h + *v) % HASHSIZE;
}
return h;
}
Хеш-функции
I
I
Лучшие по статистическим показателям функции —
криптографические.
Недостатки:
I
I
длинный код
медленные
Хеш-функции
I
Очень хорошие хеш-функции.
I
Применяется полиномиальная арифметика или
арифметика полей Галуа.
I
В полях Галуа определены операции сложения и
умножения.
I
Пример: операции в поле GF (23 ), оно состоит из чисел
0...7
I
Операция сложение есть побитовое исключающее или
XOR.
I
Для умножения требуется число представить как полином.
5 = 1012 = 1 · x 2 + 0 · x 1 + 1 · x 0 = x 2 + 1
I
Умножение чисел есть умножение полиномов.
5 ∗ 5 = (x 2 + 1) · (x 2 + 1) = x 4 + x 2 + x 2 + 1 = x 4 + 1 = 17
I
Но ведь 17 не входит в поле GF (23 ).
I
Вводится понятие производящий полином, который
должен быть неприводимым, то есть, не должен иметь
полиномов-делителей, отличных от него и единицы.
I
Один из таких полиномов для GF (23 ) есть x 3 + x + 1.
I
Результатом умножения будет остаток от деления x 4 + 1
на производящий полином x 3 + x + 1, что будет равно
x2 + x + 1 = 7
Хеш-функции
I
P(x) - исходное сообщение длины M битов
I
G (x) - производящий полином длины N битов
I
R(x) есть остаток от деления P(x) на G (x) в GF (2N )
I
Длина R(x) ровно N битов.
I
Если производящий полином G (x) неприводим, то
множество R(x) имеет мощность 2N .
Для GF (232 один из неприводимых полиномов
x 32 +x 26 +x 23 +x 22 +x 16 +x 12 +x 11 +x 10 +x 8 +x 7 +x 6 +x 4 +x 2 +x+1
Хеш-функции
Примитивный член поля GF (2N ) есть тот, степени
которого содержат все ненулевые элементы поля.
I Алгоритм умножения чисел становится элементарным.
I Составляется таблица степеней примитивного члена.
I Например, для GF (23 ) 26 = 5. Тогда
5 · 5 = 26 · 26 = 212 = 212 mod 7 = 25 = 7
Сама функция:
I
uint32 hash(uchar *ptr, unsigned length) {
uint32 c = 0xFFFFFFFF;
while (length) {
c ^= (uint32) (ptr[0]);
c = (c >> 8) ^ _table[c & 0xFF];
ptr++;
length--;
}
return c ^ 0xFFFFFFFF;
}
Хеш-функции
Распределение значений для случайных идентификаторов.
Плохая функция.
SUM hash, HASHSIZE=400
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Хеш-функции
Распределение значений для случайных идентификаторов.
Плохая функция.
SUM hash, HASHSIZE=401
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Хеш-функции
Хорошая функция.
Sedgewick hash, HASHSIZE=400
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Хеш-функции
Хорошая функция.
Sedgewick hash, HASHSIZE=401
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Хеш-функции
Отличная функция.
CRC32 hash, HASHSIZE=400
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Хеш-функции
Отличная функция.
CRC32 hash, HASHSIZE=401
3
2.5
2
1.5
1
0.5
0
0
50
100 150 200 250 300 350 400
Затраты времени на исполнение хеш-функций
Алгоритм/набор
hash_sum
hash_segewick
hash_crc
include.txt
890
2873
912
source.txt
786
2312
801
Синхронизация больших объектов
Условия применения:
I
Синхронизируемый объект имеет значительный размер
I
Объект регулярно изменяет своё содержимое
I
Размер изменяемой зоны относительно невелик
Обычное копирование расходует ресурс: пропускную
способность.
Синхронизация больших объектов
Два паттерна использования:
1. первичная пересылка объекта. Может потребовать
передачи полного объёма.
2. пересылка изменённых фрагментов.
Синхронизация больших объектов: алгоритм
Задача: клиент синхронизирует большой объект с сервера.
Условия: на клиенте и сервере имеются реплики большого
объекта, возможно, уже изменившегося на сервере.
Используется одна и та же хеш-функция.
1. клиент и сервер разбивают объект на (виртуальные)
блоки. Для каждого блока подсчитывается хеш.
2. клиент передаёт серверу номера блоков, для которых
нужно вычислить хеш
3. сервер передаёт хеш запрошенных блоков
4. клиент сравнивает хеш и обнаруживает блоки с
несовпадающем хешем
5. клиент запрашивает блоки с несовпадающем хешем
Хеш-таблицы
Хеш-таблицы
I
Простая хеш-таблица
HASHSIZE=16
nil
nil
Якутск
“Брянск”
Hash(“Брянск”)=5
270000
…
…
Брянск
415000
…
…
Абакан
165000
…
…
Амурск
…
…
…
…
43000
Хеш-таблицы
I
Простая хеш-таблица, обычная реализация в виде массива
указателей
HASHSIZE=16
nil
Якутск
nil
270000
Якутск
“Брянск”
Hash(“Брянск”)=5
…
…
Брянск
Абакан
…
165000
…
Абакан
…
Амурск
…
43000
Амурск
…
Брянск
…
415000
…
…
Указатели
Объекты
Хеш-таблицы
I
Известно количество элементов в контейнере C
I
Известен размер массива M
I
α=
I
α — главный показатель хеш-таблицы.
C
M
— коэффициент заполнения, fill-factor, load-factor.
Хеш-таблицы
I
Операция создания хеш-таблицы
HASHSIZE=16
nil
nil
nil
nil
nil
nil
“Абакан”
Hash(“Абакан”)=11
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
Хеш-таблицы
I
Операция создания хеш-таблицы требует операцию поиска.
HASHSIZE=16
nil
nil
Якутск
“Урюпинск”
Hash(“Урюпинск”)=7
270000
…
…
Брянск
415000
…
nil
Абакан
165000
…
…
Амурск
…
…
…
…
43000
Хеш-таблицы
I
Hash("Якутск") = 2
I
Hash("Мышкин") = 2
I
Это — коллизия
I
Коллизии — нежелательны.
I
Без коллизий сложность операций поиска и вставки равна
O(1)
Способы борьбы с коллизиями:
I
I
I
I
Прямая или закрытая адресация
Открытая адресация
Рехеширование
Хеш-таблицы с прямой адресацией
I
При коллизии во время создания элемента создаётся
связный список конфликтующих.
I
Технически можно создать любую поисковую структуру
данных
HASHSIZE=16
nil
nil
Якутск
“Мышкин”
Hash(“Мышкин”)=2
270000
…
…
Брянск
415000
…
Урюпинск
23000
Абакан
165000
…
…
Амурск
…
…
…
…
43000
Мышкин
15000
Хеш-таблицы с прямой адресацией
1. При поиске вычисляется хеш-функция.
2. Определяется место поиска — вторичная поисковая
структуре данных.
3. Если вторичной структуры нет, то нет и элемента.
4. Иначе элемент ищется во вторичной структуре.
Хеш-таблицы с прямой адресацией
1. При удалении вычисляется хеш-функция.
2. Определяется место поиска — вторичная поисковая
структуре данных.
3. Если вторичной структуры нет, то нет и элемента.
4. Иначе элемент удаляется из вторичной структуре.
5. Если вторичная структура пуста, удаляет точку входа.
Хеш-таблицы с открытой адресацией
I
Другой способ поиска — искать в той же таблице повторно.
HASHSIZE=16
nil
“Якутск”
Hash(“Якутск”)=2
“Мышкин”
Hash(“Мышкин”)=2
nil
Якутск
270000
Мышкин
15000
nil
Брянск
415000
nil
Урюпинск
23000
Абакан
165000
nil
nil
Амурск
nil
nil
nil
nil
43000
Хеш-таблицы с открытой адресацией
1. При поиске существующего вычисляется хеш-функция.
2. Определяется место поиска — индекс в хеш-таблице.
3. Если по индексу ничего нет, то нет и элемента.
4. Иначе по индексу — элемент с нашим ключом — элемент
найден.
5. Если по индексу — элемент с другим ключом или элемент
помечен удалённым, индекс увеличиваем на единицу и
переходим к пункту 3.
6. Следующий индекс вычисляется по формуле (index + 1)
mod M.
Хеш-таблицы с открытой адресацией
1. При вставке вычисляется хеш-функция.
2. Определяется место поиска — индекс в хеш-таблице.
3. Если по индексу ничего нет или элемент помечен
удалённым, то вставляем по индексу и выходим.
4. Если по индексу элемент с нашим ключом — меняем
данные и выходим.
5. Если по индексу элемент с другим ключом то индекс
увеличиваем на единицу и переходим к пункту 3.
6. Следующий индекс вычисляется по формуле (index + 1)
mod M.
Хеш-таблицы с открытой адресацией
1. Почему мы требуем свойства равномерности от
хеш-функции.
HASHSIZE=16
nil
nil
“Якутск”
Hash(“Якутск”)=2
“Мышкин”
Hash(“Мышкин”)=2
Мышкин
15000
Hash(“Брянск”)=2
Брянск
415000
“Брянск”
Якутск
270000
nil
nil
“Урюпинск”
Hash(“Урюпинск”)=7
Урюпинск
23000
“Абакан”
Hash(“Абакан”)=7
Абакан
165000
Амурск
43000
“Амурск”
Hash(“Амурск”)=7
nil
nil
nil
nil
nil
nil
Хеш-таблицы с открытой адресацией
1. При удалении вычисляется хеш-функция.
2. Определяется место поиска — индекс в хеш-таблице.
3. Если по индексу ничего нет, то нет и элемента.
4. Иначе по индексу — элемент с нашим ключом — элемент
найден.
5. Если по индексу — элемент с другим ключом, индекс
увеличивается на единицу и переходим к пункту 3.
6. Следующий индекс вычисляется по формуле (index + 1)
mod M.
Расширение хеш-таблиц
Когда fill-factor начинает превосходить 0.7-0.8 таблицу
расширяют.
I
Создаётся другой массив указателей с нужным размером
I
Из оригинального массива в порядке увеличения индексов
извлекаются элементы и вставляются в новый массив
(таблицу).
I
Старый массив удаляется.
Подсчёт амортизационных расходов.
I
Амортизационные расходы на закрытую адресацию
I
Амортизационные расходы на открытую адресацию
I
Амортизационные расходы на рехеширование
Рехеширование уменьшает потребность в памяти.
Открытые обычно быстрее
Хеш-таблицы с открытой адресацией
Рекомендации по использованию.
1. Всегда использовать хорошую хеш-функцию!
2. Использовать fill-factor не больше 0.5-0.6.
Quiz
http://rbtsv.ru/quiz/index
Параллельное использование
алгоритмов поиска. Списки с
пропусками.
Параллельное использование
I
При параллельном программировании к одному элементу
данных может обратиться несколько потоков.
I
Результат при этом может быть недетерминирован.
int a = 0, b = 0;
//thread 1
b = 2;
a = b + 1;
//thread 2
a = 4;
b = a - 3;
Параллельное использование
I
Критерий Бернстайна: Поместим объекты, которые
читаются в потоке i в множество Ri , а те, которые
пишутся, в множество Wi .
I
Для нашего кода R1 = {b}, W1 = {a, b}, R2 = {a},
W2 = {a, b}.
I
Критерий гласит, что если все пересечения множеств
R1 ∩ W2 , R2 ∩ W1 , W1 ∩ W2 пусты, то конфликтов (race
conditions) не возникнет.
I
В нашем случае: R1 ∩ W2 = {a}, R2 ∩ W1 = {a},
W1 ∩ W2 = {a, b}, то есть race conditions возможны.
Параллельное использование
I
Одно из средство избежать race conditions —
использование атомарных операций.
I
Существуют машинные команды типа Compare-And-Swap,
исполняющиеся атомарно.
I
Они позволяют атомарно обменять две ячейки памяти,
которые, возможно, содержат указатели.
I
При вставке в односвязный список достаточно атомарных
операций для замены цепочки указателей.
I
Односвязный список — идеальная структура данных для
параллельного программирования.
Параллельное использование
I
Операция поиска в односвязном списке T () = O(N)
I
Операции вставки и удаления в односвязном списке
T () = O(N)
I
Требуется по возможности сохранить свойства операций
вставки и удаления в лучшем случае и ускорить операцию
поиска.
Списки с пропусками
Рассмотрим следующую структуру данных:
level 5
4
level 4
4
level 3
4
level 2
4
level 1
4
nil
27
17
15
17
27
23
27
40
35
40
50
nil
50
nil
50
42
50
53
61
nil
61
nil
I
Она представляет из себя несколько списков,
организованных в виде списков.
I
Каждый следующий список примерно в два раза короче
предыдущего и он пропускает примерно половину
элементов предыдущего.
Списки с пропусками
I
Поиск существующего элемента.
4 < 42 < inf
level 5
4
level 4
4
nil
4 < 42 < 50
level 3
50
nil
50
nil
27 < 42 < 50
4
27
40 < 42 < 50
level 2
level 1
4
4
17
15
17
27
23
27
40
35
40
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Поиск несуществующего элемента.
4 < 20 < inf
level 5
4
level 4
4
nil
4 < 20 < 50
50
nil
50
nil
4 < 20 < 27
level 3
4
27
17 < 20 < 27
level 2
level 1
4
4
17
15
17
27
23
27
40
35
40
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Вставка элемента.
level 5
4
20
level 4
4
20
level 3
level 2
level 1
4
20
4
4
15
17
20
17
20
p=1/16
nil
p=1/8
p=1/4
p=1/2
23
27
27
27
40
35
40
50
nil
50
nil
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Удаление элемента. Поиск и пометка столбца.
level 5
4
level 4
4
level 3
4
level 2
4
level 1
4
nil
15
20
27
17
20
27
17
20
23
27
40
35
40
50
nil
50
nil
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Удаление элемента. Удаление из строк.
level 5
4
level 4
4
level 3
4
17
level 2
4
17
20
17
20
level 1
4
nil
15
27
27
23
40
35
40
50
nil
50
nil
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Удаление элемента. Заключительное удаление.
level 5
4
level 4
4
level 3
4
17
level 2
4
17
20
17
20
level 1
4
nil
15
40
23
35
40
50
nil
50
nil
50
42
50
53
61
nil
61
nil
Списки с пропусками
I
Вставка 106 элементов в структуру данных.
Укладывание
Случайно
По возрастанию
По убыванию
Array
127033 ms
108 ms
256337 ms
RBTree
1020 ms
457 ms
358 ms
SkipList
1737 ms
536 ms
407 ms
Списки с пропусками
Амортизационная сложность списков с пропусками:
I
Вставка — T (N) = O(log N)
I
Поиск — T (N) = O(log N)
I
Удаление — T (N) = O(log N)
Практическое использование
АСД
Практическое использование: задача триангуляции
I
Требуется соединить все точки между собой так, чтобы
сумма периметров полученных треугольников была
минимальной.
Практическое использование: задача триангуляции
Практическое использование: задача триангуляции
Практическое использование: задача триангуляции
Практическое использование: задача триангуляции
Практическое использование: задача триангуляции
Практическое использование: задача триангуляции
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Использование алгоритмов и структур данных
Требуемые для решения задачи структуры данных.
I
I
Сами точки. Массив.
Связи между точками. Свойства:
I
I
I
I
I
I
После начальной разбивки размер не изменяется
Связи, которые требуется проверить (чёрные)
Повторения не допускаются
Можно выбирать в любом порядке
Размер не превосходит общего количества связей
Вершины двух треугольников, для которых связь является
основанием.
I
I
Совпадает с количеством связей
Изменяется при изменении топологии
Использование алгоритмов и структур данных
I
Связь
I
I
I
вершины двух опорных треугольников
чёрная/зелёная
Замена чёрной связи (2,4) на зелёную (1,3)
I
I
I
Теперь связи (1,2), (2,3), (1,4), (3,4) — чёрные.
Надо их быстро найти, пометить их чёрными и поместить
в множество на обработку.
Надо удалить связь (2,4 ) и создать связь (1,3)
8
9
2
1
3
5
4
6
7
Использование алгоритмов и структур данных
I
I
Точки: массив N.
Связи: хеш-таблица.
I
I
I
Размер Θ(N) не изменяется.
Частый поиск.
Более редкое изменение.
I
Хеш-таблица связей.
I
Приоритетная очередь связей на обработку.
Спасибо за внимание.
Следующая лекция —
Динамическое
программирование.
Автор
tekhnostrim
Документ
Категория
Без категории
Просмотров
90
Размер файла
882 Кб
Теги
лекция
1/--страниц
Пожаловаться на содержимое документа