Множество (Set) структура данных, которая позволяет
достаточно быстро (в зависимости от реализации) применить операции
add
, erase
и is_in_set
. Но
иногда этого не достаточно: например, невозможно перебрать все
элементы в порядке возрастания, получить следующий / предыдущий по
величине или быстро узнать, сколько элементов меньше данного есть в
множестве. В таких случаях приходится использовать
Упорядоченное множество (ordered_set). О том, как
оно работает, и какие реализации есть для питона далее.
Стандартный Set
В языке Python есть стандартная стукрура set,
реализованная с помощью хэш-таблиц. Такую структуру обычно называют
unordered_set
. Данный метод работает так: каждый
элемент присваивается какому-то классу элементов (например, класс
элементов, имеющих одинаковый остаток от деления на модуль). Все
элементы каждого класса хранятся в одтельном списке. В таком случае
мы заранее знаем, в каком списке должен находиться элемент, и можем
за короткое время выполнить необходимые операции. Равновероятность
каждого остатка от деления случайного числа на модуль позволяет
сказать, что к каждому классу элементов будет относиться в среднем
size / modulo
элементов.
Но хэш-таблица не позволяет выполнить операцию
count_lower
или подобные, поэтому придётся
использовать другие структуры данных.
Что есть в других языках
В языке c++ есть структура std::set
, которая
поддерживает операции изменения, проверку на наличие, следующий /
предыдущий по величине элемент, а также for
по всем
элементам. Но тут нет операций получения элемента по индексу и
индекса по значению, так что надо искать дальше (индекс элемента
количество элементов, строго меньших данного)
И решение находится достаточно быстро: tree
из
pb_ds
. Эта структура в дополнение к возможностям
std::set
имеет быстрые операции
find_by_order
и order_of_key
, так что эта
структура именно то, что мы ищем.
Она реализована с помощью красно-чёрных деревьев. Смысл этой струкруты в том, что все элементы образуют собой двоичное дерево поиска, которое балансируется так, чтобы высота не превышала логарифм. Нам это даёт возможность с помощью одного спуска по дереву выполнить необходимые операции. Также с этой задачей может справиться Декартово дерево (Дерамида) по неявному ключу или AVL дерево.
Таким образом, целью этой статьи станет поиск аналога этой структуры в Python.
Как будем тестировать скорость работы структур данных
Для оценки времени работы я написал программу, которая будет выполнять последовательно несколько типов операций:
- Добавление в множество миллиона случайных чисел (при данном сиде среди них будет 999'936 различных)
- Проверка миллиона случайных чисел на присутствие в множестве
- Прохождение циклом по всем элементам в порядке возрастания
- В случайном порядке для каждого элемента массива узнать его индекс (а, соответственно, и количество элементов, меньше данного)
- Получение значения i-того по возрастанию элемента для миллиона случайных индексов
- Удаление всех элементов множества в случайном порядке
from SomePackage import ordered_setimport randomimport timerandom.seed(12345678)numbers = ordered_set()# adding 10 ** 6 random elements - 999936 uniquelast_time = time.time()for _ in range(10 ** 6): numbers.add(random.randint(1, 10 ** 10))print("Addition time:", round(time.time() - last_time, 3))# checking is element in set for 10 ** 6 random numberslast_time = time.time()for _ in range(10 ** 6): is_element_in_set = random.randint(1, 10 ** 10) in numbersprint("Checking time:", round(time.time() - last_time, 3))# for all elementslast_time = time.time()for elem in numbers: now_elem = elemprint("Cycle time:", round(time.time() - last_time, 3))# getting index for all elementslast_time = time.time()requests = list(numbers)random.shuffle(requests)for elem in requests: answer = numbers.index(elem)print("Getting indexes time:", round(time.time() - last_time, 3))# getting elements by indexes 10 ** 6 timesrequests = list(numbers)random.shuffle(requests)last_time = time.time()for _ in range(10 ** 6): answer = numbers[random.randint(0, len(numbers) - 1)]print("Getting elements time:", round(time.time() - last_time, 3))# deleting all elements one by onerandom.shuffle(requests)last_time = time.time()for elem in requests: numbers.discard(elem)print("Deleting time:", round(time.time() - last_time, 3))
SortedSet.sorted_set.SortedSet
Пакет с многообещающим названием. Используем pip install
sortedset
К сожалению, автор не приготовил нам функцию add
и
erase
в каком-либо варианте, поэтому будем
использовать объединение и вычитание множеств
Использование:
from SortedSet.sorted_set import SortedSet as ordered_setnumbers = ordered_set()numbers |= ordered_set([random.randint(1, 10 ** 10)]) # добавлениеnumbers -= ordered_set([elem]) # удаление
Протестируем пока на множествах размера 10'000:
Задача | Время работы |
---|---|
Добавление | 16.413 |
Проверка на наличие | 0.018 |
Цикл по всем элементам | 0.001 |
Получение индексов | 0.008 |
Получение значений по индексам | 0.015 |
Удаление | 30.548 |
Как так получилось? Давайте загляем в исходный код:
def __init__(self, items=None): self._items = sorted(set(items)) if items is not None else []def __contains__(self, item): index = bisect_left(self._items, item)
Как оказалось, это обычный массив, в котором наличие элемента определяется бинпоиском. Это действительно отсортированное множество, но очень ленивое.
Вывод: почти бесполезно, несколько строчек кода завернули в класс
sortedcontainers.SortedSet
Внеший пакет, для установки можно использовать pip install
sortedcontainers
. Посмотрим же, что он нам покажет
Задача | Время работы |
---|---|
Добавление | 3.924 |
Проверка на наличие | 1.198 |
Цикл по всем элементам | 0.162 |
Получение индексов | 3.959 |
Получение значений по индексам | 4.909 |
Удаление | 2.933 |
Но, не смотря на это, кажется мы нашли то, что искали! Все
операции выполняются за приличное время. По сравнению с
ordered_set
некоторые операции выполняются дольше, но
за то операция discard выполняется не за o(n), что очень важно для
возможности использования этой структуры.
Также пакет нам предлагает SortedList
и
SortedDict
, что тоже может быть полезно.
И как же оно работает?
На странице пакета мы можем прочитать, что реализована структура не так, как мы предполагали в начале статьи.
Из-за особенностей реализации языка Python, в нём быстро
работают list
, а также bisect.insort
(найти бинарным поиском за o(log n)
место, куда нужно
вставить элемент, а потом вставить его туда за o(n)
).
Insert
работает достаточно быстро на современных
процессорах. Но всё-таки в какой-то момент такой оптимизации не
хватает, поэтому структуры реализованы как список списков. Создание
или удаление списков происходит достаточно редко, а внутри одного
списка можно выполнять операции даже за быструю линию.
Если говорить кратко, то принцип действия похож на корневую оптимизацию.
Проблема с ordered_set
Что вообще такое упорядоченное множество? Это множество, в
котором мы можем сравнить любые 2 элемента и найти среди них
больший / меньший. В течение всей статьи под операцией сравнения
воспринималась операция сравнения двух элеметнов по своему
значению. Но все пакеты называющиеся ordered_set считают что один
элемент больше другого, если он был добавлен раньше в множество.
Так что с формулировкой ordered_set нужно быть аккуратнее и
уточнять, имеется ввиду ordered set
или sorted
set
.
Bintrees
Так есть же модуль bintrees! Это же то, что нам нужно? И да, и
нет. Его разработка была приостановлена в 2020 году со словами
Use sortedcontainers instead
.
Пакет предлагает нам несколько структур. К сожалению, ни одна из
них не поддерживает операции find_by_order
и подобные,
так что эти струкруты являются аналогами std::set
.
Посмотрим же, на что они способны:
pip install bintrees
Название AVLTree
говорит само за себя,
RBTree
красно-чёрное дерево, BinaryTree
несбалансированное двоичное дерево, префикс Fast
означает реализацию на Cython
(соответственно,
необходимо наличие Visual C++
, если используется на
Windows).
Задача | AVLTree | FastAVLTree | RBTree | FastRBTree | BinaryTree | FastBinaryTree |
---|---|---|---|---|---|---|
Добавление | 21.946 | 2.285 | 20.486 | 2.373 | 11.054 | 2.266 |
Проверка на наличие | 5.86 | 2.821 | 6.172 | 2.802 | 6.775 | 3.018 |
Цикл по всем элементам | 0.935 | 0.297 | 0.972 | 0.302 | 0.985 | 0.295 |
Удаление | 12.835 | 1.509 | 25.803 | 1.895 | 7.903 | 1.588 |
Результаты тестирования отчётливо показывают нам, почему
использовать деревья поиска на Python плохая идея в плане
производительности. А вот в интеграции с Cython
всё
становится намного лучше.
Оказывается, эта структура и SortedSet
очень похожи
по производительности. Все 3 Fast версии структур
bintrees
достаточно близки, поэтому будем считать, что
оттуда мы используем FastAVLTree
.
Задача | SortedSet | FastAVLTree |
---|---|---|
Добавление | 3.924 | 2.285 |
Проверка на наличие | 1.198 | 2.821 |
Цикл по всем элементам | 0.162 | 0.297 |
Получение индексов | 3.959 | n/a |
Получение значений по индексам | 4.909 | n/a |
Удаление | 2.933 | 1.509 |
Как мы видим, AVL в полтора раза быстрее в скорости добавления
элементов и почти в 2 раза быстрее в операциях удаления. Но он в те
же 2 раза медленнее в проверке на наличие и цикле по всем
элементам. К тому же не стоит забывать, что 2 операции он выполнять
не умеет, то есть не является тем ordered_set
, что мы
ищем.
Использование:
import bintreesnumbers = bintrees.FastAVLTree()numbers.insert(value, None) # второй параметр - значение, как в словаре
Что же выбрать
Мои рекомендации звучат так: если вам нужны операции
find_by_order
и order_of_key
, то ваш
единственный вариант sortedcontainers.SortedSet
. Если
вам нужен только аналог std::map
, то выбирайте на своё
усмотрение между SortedSet
и любым из fast контейнеров
из bintrees
, опираясь на то, каких операций ожидается
больше.
Можно ли сделать что-то быстрее
Скорее нет, чем да. Использование Cython один из самых мощных
способов оптимизации, а AVL считается очень быстрым решением
исходной задачи. Про остальные операции ordered_set
можно сказать, что модификация красно-чёрного дерева так, чтобы оно
поддерживало эти операции, вряд ли будет быстрее
SortedContainers
, так что смысла изобретать велосипед
я не вижу.
Облачные VPS серверы от Маклауд быстрые и безопасные.
Зарегистрируйтесь по ссылке выше или кликнув на баннер и получите 10% скидку на первый месяц аренды сервера любой конфигурации!