Практика 10
Множество (Set)
Множество - это набор различных объектов. Это означает, что в нём нет повторяющихся объектов. [1,2,3] - множество, а [1,2,2,3,1] - не удовлетворяет определению.
Множество - это абстрактная структура данных и её можно реализовать несколькими способами. Но для начала определим поведения для этой абстракции.
Базовые операции:
Этот набор поведений определяет саму абстракцию.
- добавить элемент в множество
- объединить множества
- пересечь множества
- проверка принадлежности элемента множеству
Вспомогательные:
Это дополнительные функции. Они просто помогают пользоваться этой абстракцией.
- вычислить длину
- итерация по множеству
- создать множество из списка элементов
- сконвертировать множество в список
Реализации
По определению, множество предоставляет только одну услугу - хранит только разные элементы. Порядок хранить оно не обязано, доступа по индексу тоже нет. Тогда на основе чего можно построить эту абстракцию?
Список
Мы можем создать множества на основе списка и просто проверять при каждой вставке в него то, есть ли в нём уже этот элемент или нет.
Преимущества:
- легко сделать
Недостатки:
- долгий поиск принадлежности и вставки O(n)
- очень долгое пересечение O(n^2)
Упорядоченный список
А что если хранить все элементы в списке упорядоченно? Тогда вставка будет занимать меньше времени в среднем: O(n/2). Но это тот же порядок.
Деревья поиска
Существует такая структура данных как дерево. Оно было создано специально для решения задачи поиска. В сбалансированном дереве поиск элемента имеет сложность O(log_2(n)), что очень хорошо. Сравните её с O(n):
картинка взята из статьи bigocheatsheet.com
Условия бинарного дерева поиска:
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.
Статья на wiki.
Хэш таблицы
Основная идея заключается в использовании некоторой хэш функции, которая возвращает некоторое число. Это число используется как индекс в массиве. Поэтому операция поиска принадлежности будет O(1). В случае коллизии хэш функции, то есть когда для разных элементов было вычислено одно и то же значение хэш функции, предусматривается некоторое специальное поведение. Например, можно по индексу хэш функции хранить не один элемент, а несколько. Если коллизий очень мало, то поиск принадлежности будет всё тот же O(1) + O(n), где n - количество элементов с одним хешем. Такой метод называется методом цепочек.
Статья на wiki
Задание в классе
Множества на основе списка
Используя рекурсивный связный список из прошлой практики постройте абстрактный типа данных множество. Вы можете делать это с помощью классов или на основе функций. Но главное, чтобы у вас были 4 базовые функции и вспомогательные.
Напишите бенчмарк(замер скорости выполнения) для базовых функций вашего множества.
Множество на основе хеш-таблицы
Используйте массивы python как базовую структуру.
Реализуйте какую-нибудь функцию хеширования: например, остаток от деления на N или mur-mur. Для начала, чтобы тестировать свой код, можете использовать функцию hash.
Напишите бенчмарк(замер скорости выполнения) для базовых функций вашего множества.
Тесты
Напишите сами тесты на все базовые функции, вспомогательные методы. Должно быть не меньше 8 тестов.
Домашнее задание
Множество на основе дерева
Реализуйте множество на основе бинарного дерева поиска. Если вам понадобится массив, то используйте только ваш список из предыдущей практики.
Напишите бенчмарк(замер скорости выполнения) для базовых функций вашего множества.
Сравните скорость работы каждой реализации множества.