Множество (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:
| Задача | Время работы |
|---|---|
| Добавление | 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 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% скидку на первый месяц аренды сервера любой конфигурации!
