sizeof (sizeof) wrote,
sizeof
sizeof

Categories:

Технотрек: Промышленное программирование. Занятие 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 - размер буфера

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

Для дампа списков и хеш-таблиц удобно использовать graphwiz, который умеет рисовать графы на основе простого языка их описания.

Домашнее задание

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! :)
Tags: Технотрек
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments