Различия между версиями 19 и 20
Версия 19 от 2011-05-07 02:58:04
Размер: 5712
Редактор: PavelSutyrin
Комментарий:
Версия 20 от 2011-05-07 02:58:42
Размер: 5743
Редактор: PavelSutyrin
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 28: Строка 28:
  Тестирует она каждую из них следующим образом. Для каждого из указанных ниже шагов измеряется общее (на весь шаг) и среднее (на каждый элемент) время выполнения операции со структурой (например, с помощью функции `times()` из модуля `os`).
   1. Загружает все данные в изначально пустую структуру.
   1. Составляет случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней встречаются.
   1. Составляет случайную выборку из M = 1000 значений ключей, которые заведомо '''не''' встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней '''не''' встречаются.
  Тестирует она каждую из них следующим образом. Для каждого из указанных ниже шагов измеряется общее (на весь шаг) и среднее (на каждый элемент) время выполнения операции со структурой (например, с помощью функции `times()` из модуля `os`). Шаги тестирования:
   1. Загрузить все данные в изначально пустую структуру.
   1. Составить случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней встречаются.
   1. Составить случайную выборку из M = 1000 значений ключей, которые заведомо '''не''' встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней '''не''' встречаются.

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

  • {o} — тема по Linux

  • <!> ­— необязательная тема

  • массив -- прямой доступ: быстро, но требует памяти (если неплотный набор ключей)
  • список -- ассоциативный доступ: разумно по памяти, медленный поиск
  • хеш-таблицы, в Питоне функция 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)] -- несколько ключей. Соответственный показатель степени и основание логарифма для количества узлов и уровней.

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

  • {i} — теоретическое задание

  • {*} — новая тема

  1. Почитать про индексные массивы, списки и ассоциативные массивы, хэширование, двоичные деревья поиска и более ветвистые B-деревья, AVL-, красно-черные и декартовы деревья.

  2. Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка без пробелов] на N = 10**5 элементов. Использовать эти данные (как набор пар "ключ-значение") в качестве входных для программы, которая тестирует производительность следующих структур данных:
    1. линейный список
    2. хешированная таблица
    3. двоичное дерева (заполняемого с балансировкой и без балансировки)
    4. стандартный словарь (dict)

    Тестирует она каждую из них следующим образом. Для каждого из указанных ниже шагов измеряется общее (на весь шаг) и среднее (на каждый элемент) время выполнения операции со структурой (например, с помощью функции times() из модуля os). Шаги тестирования:

    1. Загрузить все данные в изначально пустую структуру.
    2. Составить случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней встречаются.
    3. Составить случайную выборку из M = 1000 значений ключей, которые заведомо не встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней не встречаются.

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

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


CategoryClass CategoryVmsh

LecturesVMSH/2011-05-04 (последним исправлял пользователь FrBrGeorge 2011-05-11 14:52:26)