[Python, Совершенный код, ООП] В поисках упорядоченного множества в Python: разбираемся с теорией и выбираем лучшую реализацию
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Множество (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% скидку на первый месяц аренды сервера любой конфигурации!
оригинал
===========
Источник:
habr.com
===========
Похожие новости:
- [Perl, Ruby, PHP, Python, JavaScript] Насколько вам наплевать на фичи последней версии языка?
- [Программирование, Совершенный код] Практическое руководство по именованию классов, функций и переменных (перевод)
- [Python, Программирование, Совершенный код, Научно-популярное] Разукрашиваем вывод в консоли: теория и практика
- [Python, Программирование, Работа с 3D-графикой, Учебный процесс в IT] 3D teeth instance segmentation. В темноте, но не один
- [Графический дизайн, Медийная реклама, Дизайн] Почему вся реклама сегодня выглядят одинаково? (перевод)
- [Open source, Программирование, Геоинформационные сервисы, Визуализация данных, Научно-популярное] Легенды и мифы геофизики
- [C++, Серверная оптимизация] Многопоточный HTTP-сервер с ThreadPool’ом и конечным автоматом
- [Разработка веб-сайтов, HTML, ReactJS] Немного о том, как работает виртуальный DOM в React (перевод)
- [Управление персоналом, Карьера в IT-индустрии] Не ищите лучших; нанимайте людей, исходя из слабых сторон команды (перевод)
- [Научно-популярное] Робозвери 90х
Теги для поиска: #_python, #_sovershennyj_kod (Совершенный код), #_oop (ООП), #_python, #_python3, #_set, #_struktury_dannyh (структуры данных), #_optimizatsija (оптимизация), #_uskorenie_koda (ускорение кода), #_vds, #_vps, #_bystryj_vds (быстрый vds), #_blog_kompanii_maklaud (
Блог компании Маклауд
), #_python, #_sovershennyj_kod (
Совершенный код
), #_oop (
ООП
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:17
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Множество (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. Как будем тестировать скорость работы структур данных Для оценки времени работы я написал программу, которая будет выполнять последовательно несколько типов операций:
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% скидку на первый месяц аренды сервера любой конфигурации!  оригинал =========== Источник: habr.com =========== Похожие новости:
Блог компании Маклауд ), #_python, #_sovershennyj_kod ( Совершенный код ), #_oop ( ООП ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:17
Часовой пояс: UTC + 5