Русский
Русский
English
Статистика
Реклама

В поисках упорядоченного множества в 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.


Как будем тестировать скорость работы структур данных


Для оценки времени работы я написал программу, которая будет выполнять последовательно несколько типов операций:


  1. Добавление в множество миллиона случайных чисел (при данном сиде среди них будет 999'936 различных)
  2. Проверка миллиона случайных чисел на присутствие в множестве
  3. Прохождение циклом по всем элементам в порядке возрастания
  4. В случайном порядке для каждого элемента массива узнать его индекс (а, соответственно, и количество элементов, меньше данного)
  5. Получение значения i-того по возрастанию элемента для миллиона случайных индексов
  6. Удаление всех элементов множества в случайном порядке

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% скидку на первый месяц аренды сервера любой конфигурации!


Источник: habr.com
К списку статей
Опубликовано: 24.05.2021 10:16:39
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Блог компании маклауд

Python

Совершенный код

Ооп

Python3

Set

Структуры данных

Оптимизация

Ускорение кода

Vds

Vps

Быстрый vds

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru