Тема занятия: структуры данных и поиск

• массив -- прямой доступ: быстро, но требует памяти (если неплотный набор ключей)
• список -- ассоциативный доступ: разумно по памяти, медленный поиск

• хеш-таблицы, в Питоне функция hash(), реализация словарей

• Полиномиальное хеширование
  • H=(a0*p**0+a1*p**1+...+an*p**n)%2**16, где p -- простое число, например, 31337, а a0..an -- числа из хэшируемой последовательности (в случае строки символов -- коды символов)
• Дерево бинарного поиска [значение, поддерево-меньше, поддерево-больше]
  • оптимальное дерево: размер(поддерево-меньше)~=размер(поддерево-больше)
  • заполнение дерева с перебалансировкой
    • виды деревьев: AVL, красно-чёрное, декартово

  • дерево поиска в общем виде [значение,поддерево-<K1,поддерево-K1<k2,...,поддерево-kn-1<соответственkn,поддерево->kn)] -- несколько ключей. Соответственный показатель степени и основание логарифма для количества узлов и уровней.

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

1. Почитать про упомянутые структуры данных.
2. Сгенерировать текстовый файл со строками вида "случайная строка

   • уникальное_случайное_число" на 10**5 элементов. Измерить (например, с помощью функции times() из модуля os) время поиска присутствующих и не присутствующих в этих данных строк (по 1000 поисковых проб). Если работает слишком быстро/медленно, увеличить/уменьшить оба параметра в достаточное число раз. Данные представить в виде:

   1. линейного списка
   2. хешированной таблицы

      • использовать функцию hash()

      • использовать самодельный хеш
      • использовать MD5-хеш
   3. двоичного дерева
      • заполняемого с балансировкой
   4. стандартного словаря (dict)

3. Задача №765. Частоты появления элементов

4. Задача №744. Хеширование

CategoryClass CategoryVmsh