|
Размер: 4311
Комментарий:
|
Размер: 5598
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 23: | Строка 23: |
| 1. Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка] на 10**5 элементов. Измерить (например, с помощью функции `times()` из модуля `os`) время поиска элемента по 1000 поисковых проб в этих данных, представленных в виде 1. линейного списка 1. хешированной таблицы 1. двоичного дерева (заполняемого с балансировкой и без балансировки) 1. стандартного словаря (dict) |
1. Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка без пробелов] на N = 10**5 элементов. Использовать эти данные (как набор пар "ключ-значение") в качестве входных для программы, которая тестирует производительность следующих структур данных: 1. линейный список 1. хешированная таблица 1. двоичное дерева (заполняемого с балансировкой и без балансировки) 1. стандартный словарь (dict) Тестирует она их следующим образом. Для каждого шага измеряется общее и среднее время выполнения операции со структурой, например,с помощью функции `times()` из модуля `os`. 1. Загружает все данные в изначально пустую структуру. 1. Составляет случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней встречаются. 1. Составляет случайную выборку из M = 1000 значений ключей, которые заведомо '''не''' встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней '''не''' встречаются. |
Тема занятия: структуры данных и поиск
— тема по 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)] -- несколько ключей. Соответственный показатель степени и основание логарифма для количества узлов и уровней.
Домашнее задание
— теоретическое задание 
— новая тема
Почитать про индексные массивы, списки и ассоциативные массивы, хэширование, двоичные деревья поиска и более ветвистые B-деревья, AVL-, красно-черные и декартовы деревья.
- Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка без пробелов] на N = 10**5 элементов. Использовать эти данные (как набор пар "ключ-значение") в качестве входных для программы, которая тестирует производительность следующих структур данных:
- линейный список
- хешированная таблица
- двоичное дерева (заполняемого с балансировкой и без балансировки)
- стандартный словарь (dict)
Тестирует она их следующим образом. Для каждого шага измеряется общее и среднее время выполнения операции со структурой, например,с помощью функции times() из модуля os.
- Загружает все данные в изначально пустую структуру.
- Составляет случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней встречаются.
Составляет случайную выборку из M = 1000 значений ключей, которые заведомо не встречаются в структуре (эту подоперацию можно не измерять). Делает поиск этих элементов, проверяя, что они действительно в ней не встречаются.