Технотрек: Промышленное программирование. Занятие 07: Внезапно лаба (хеши и списки)
(Копия блога на Технотреке)
Summary
Односвязные и двусвязные списки и хеш-таблицы - классика структур данных, но для них важны правильная реализация и правильное использование. Список возникает как решение противоречия между физически линейным непрерывным размещением объектов в памяти (массив) и необходимостью быстрой вставки/удаления в среднюю часть последовательности. При этих операциях элементы массива неотвратимо надо сдвигать; на это уходит время. Мы отказываемся от того, что логически последовательные элементы будут физически последовательно (смежно) лежать в памяти, теряем формулу быстрого вычисления номера следующего элемента (n+1) и заменяем ее номером или указателем, хранящимся в самом элементе. Теперь мы можем размещать элемент в памяти где угодно, не заботясь о смежности с другими элементами и не делая сдвиги. Это и есть идея списка.
Заметим, что если нужны быстрые вставки/удаления только в начало или конец последовательности, то подойдет обычный массив. Если нужны быстрые вставки/удаления только с началом и с концом последовательности (но не с ее средней частью), достаточно кольцевого буфера. Если все же нужно реализовывать список, то лучше сразу двусвязный: памяти это займет немного больше, но все операции у него быстрые, не зависят от длины последовательности.
Одна из ужасных ошибок использования списков - непонимание того, что индексация у них кошмарно медленная. Это линейный поиск элемента в плохо кешируемом цикле, что практически так же медленно, чем поиск элемента по значению. Как у strlen(), только значительно хуже. Вот пример такого плохого кода:
for (int i = 0; i < List_Size (&list); i++) { const ListElement* elem = List_ElementAt (i); // Та самая индексация ListElement_Dump (elem); } Этот цикл - квадратичный по времени. Квадратичный, Карл! Не делайте так.
Правильно:
for (const ListElement* elem = List_Begin (&list); elem != NULL; i < List_Next (elem)) ListElement_Dump (elem); Сравнение линейных структур данных:
Структура данных Массив Кольцевой буфер Односвязный список Двусвязный список Элементы физически лежат Всегда последовательно, смежно Циклически последовательно,
т.е. могут быть разделены на 2 подпоследовательности Разбросанно по памяти, не смежно Разбросанно по памяти, не смежно Доступ, дружественный к кешу Да! Да Нет Нет Операция индексации Очень быстрая, 1-2 инструкции CPU Быстрая, 2-3 инструкции CPU Медленная.
Цикл, зависящий от длины списка Медленная.
Цикл, зависящий от длины списка Вставка/удаление только в конец Быстрая Быстрая Быстрая Быстрая Вставка/удаление только в начало Быстрая
(если перевернуть задом наперед) Быстрая Быстрая Быстрая Вставка/удаление в начало или в конец Быстрая Быстрая Быстрая Быстрая Вставка/удаление в начало и в конец Медленная Быстрая Быстрая Быстрая Вставка/удаление в среднюю часть (после заданного элемента) Медленная Медленная Быстрая Быстрая Вставка/удаление в среднюю часть (до заданного элемента) Медленная Медленная Медленная
(надо искать предыдущий элемент) Быстрая Удаление заданного элемента Медленное Медленное Медленное
(надо искать предыдущий элемент) Быстрое Функция получения следующего элемента NEXT (N) = N + 1 NEXT (N) = (N + 1) % size
NEXT (N) = (N + 1) & (size - 1),
если size = 2n (почему? и откуда size-1?) NEXT (A) = A -> next NEXT (A) = A -> next Чем задана эта функция? Формулой Формулой Таблицей Таблицей
Обозначения:
N - номер элемента
A - адрес элемента
size - размер буфера
Хеш-таблицы - простые структуры данных, сильно ускоряющие операции поиска, и поэтому применяются чуть более, чем везде. Хеш-таблицы, реализованные методом цепочек, используют списки. Распределяют данные по ячейкам в хеш-таблице хеш-функции. Хорошая хеш-функция должна быть функцией :), т.е. обладать однозначностью, считаться быстро, равномерно распределять данные по ячейкам. Последнее свойство реализовать немного труднее всех, поэтому мы его исследуем (см. домашнее задание).
Для дампа списков и хеш-таблиц удобно использовать graphviz, который умеет рисовать графы на основе простого языка их описания.
Домашнее задание
1. Реализуйте двусвязный список с операциями:
- конструкции
- деструкции
- тихой и медленной верификации
- дампа
- получения указателя на первый элемент списка
- получения указателя на последний элемент списка
- получения указателя на элемент, следующий за данным
- получения указателя на элемент, предшествующий данному
- вставки элемента в начало списка
- вставки элемента в конец списка
- вставки элемента перед заданным элементом
- вставки элемента после заданного элемента
- удаления заданного элемента
- поиска элемента по его значению
- поиска элемента по его номеру в последовательности (операция индексации)
- убийства всех человеков удаления всех элементов
Названия операций лучше всего выбрать одноименно с классом list из стандартной библиотеки C++.
2. На основе реализованного списка постройте хеш-таблицу методом цепочек с операциями:
- конструкции
- деструкции
- тихой и еще более медленной верификации
- дампа
- поиска элемента по его значению
- вставки элемента
- удаления элемента
- убийства всех роботов удаления всех элементов
Названия операций, как вы уже поняли, лучше выбирать согласно этому.
3. Исследуйте несколько хеш-функций на то, насколько они хорошо распределяют элементы в таблице. Загрузите в таблицу слова из большого текста и постройте график зависимости длины списка, растущего из ячейки хеш-таблицы, от номера этой ячейки. Идеально хороший график должен быть горизонтальной прямой, идеально плохой - вертикальной. Хеш-функции возьмите такие:
- H (str) = 0
- H (str) = str[0]
- H (str) = strlen (str)
- H (str) = сумма всех ASCII-кодов строки str
- H (str) = { H0 (str) = 0; Hi (str) = rol (H i-1) ^ str[i]. }
- H (str) = что-нибудь еще
Графики удобно строить, выводя в текстовый файл с расширением .CSV длины списков в строчку через точку с запятой, по одной строке на каждую хеш-функцию, и с именем хеш-функции в начале каждой строки. Такие файлы могут открывать MS Excel и OpenOffice, где можно построить диаграммы. Если импорт данных с разделителями в виде точек с запятой не сработает, используйте обычные запятые (это зависит от региональных настроек операционной системы). Либо через gnuplot, это даже проще для тех, кто привык к Linux.
Сдача этого задания в какой-то мере будет напоминать сдачу лабы: вы должны сравнить хеш-функции по качеству разделения и обосновать выбор лучшей из них. Погрешности считать не надо. :)
4*. Захватите мир с помощью ваших списков и захешируйте печеньки. :)
***
Удачи, и May the Source be with you! :)