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

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

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

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

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

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

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

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

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

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

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

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

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

    Подобрать параметры M и N так, чтобы вся программа работала не быстро и не медленно (от 1 до 3 минут) и не вызывала подкачки памяти.


CategoryClass CategoryVmsh

LecturesVMSH/2011-05-04 (last edited 2011-05-11 11:52:26 by FrBrGeorge)