В поисках упорядоченного множества в Python: разбираемся с теорией и выбираем лучшую реализацию
Множество (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_set
import random
import time
random.seed(12345678)
numbers = ordered_set()
# adding 10 ** 6 random elements - 999936 unique
last_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 numbers
last_time = time.time()
for _ in range(10 ** 6):
is_element_in_set = random.randint(1, 10 ** 10) in numbers
print("Checking time:", round(time.time() - last_time, 3))
# for all elements
last_time = time.time()
for elem in numbers:
now_elem = elem
print("Cycle time:", round(time.time() - last_time, 3))
# getting index for all elements
last_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 times
requests = 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 one
random.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_set
numbers = ordered_set()
numbers |= ordered_set([random.randint(1, 10 ** 10)]) # добавление
numbers -= ordered_set([elem]) # удалениеПротестируем пока на множествах размера 10'000:
Как так получилось? Давайте загляем в исходный код:
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. Посмотрим же, что он нам покажет
Но, не смотря на это, кажется мы нашли то, что искали! Все операции выполняются за приличное время. По сравнению с 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).
Результаты тестирования отчётливо показывают нам, почему использовать деревья поиска на Python — плохая идея в плане производительности. А вот в интеграции с Cython всё становится намного лучше.
Оказывается, эта структура и SortedSet очень похожи по производительности. Все 3 Fast версии структур bintrees достаточно близки, поэтому будем считать, что оттуда мы используем FastAVLTree.
Как мы видим, AVL в полтора раза быстрее в скорости добавления элементов и почти в 2 раза быстрее в операциях удаления. Но он в те же 2 раза медленнее в проверке на наличие и цикле по всем элементам. К тому же не стоит забывать, что 2 операции он выполнять не умеет, то есть не является тем ordered_set, что мы ищем.
Использование:
import bintrees
numbers = 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% скидку на первый месяц аренды сервера любой конфигурации!
