Я переношу программу на С++ на Python. Есть несколько мест, где он использует std::set для хранения объектов, которые определяют свои собственные операторы сравнения. Поскольку стандартная библиотека Python не имеет эквивалента std::set (структура данных сопоставления ключевых значений), я попытался использовать обычный словарь, а затем отсортировал его при повторении, например:
def __iter__(self):
items = self._data.items()
items.sort()
return iter(items)
Однако профилирование показало, что все вызовы от .sort() до __cmp__ являются серьезным узким местом. Мне нужна лучшая структура данных - по существу сортированный словарь. Кто-нибудь знает о существующей реализации? В противном случае, какие-либо рекомендации о том, как я должен это реализовать? Производительность чтения важнее, чем производительность записи, а время важнее памяти.
Бонусные баллы, если он поддерживает несколько значений для каждого ключа, например С++ std::multimap.
Обратите внимание, что класс OrderedDict не соответствует моим потребностям, потому что он возвращает элементы в порядке вставки, тогда как они мне нужно сортировать, используя их методы __cmp__.
Для отсортированного словаря вы можете (ab) использовать стабильную природу timsort python: в основном, сохраняйте детали частично отсортированными, добавляйте элементы в конце по мере необходимости, переключая "грязный" флаг и сортируя оставшиеся до итерации, См. Эту запись для подробностей и реализации (ответ Мартелли): Key-ordered dict в Python
Вы должны использовать sort(key=...).
Ключевая функция, которую вы используете, будет связана с cmp, который вы уже используете. Преимущество состоит в том, что ключевая функция называется n раз, тогда как cmp называется nlog n раз, и обычно ключ выполняет половину работы, которую выполняет cmp
Если вы можете включить свой __cmp__(), мы можем, вероятно, показать вам, как его преобразовать в ключевую функцию
Если вы делаете много итераций между изменениями, вы должны кэшировать значение отсортированных элементов.
Python не имеет встроенных структур данных для этого, хотя модуль bisect предоставляет функциональные возможности для хранения отсортированного списка с подходящими эффективными алгоритмами.
Если у вас есть список отсортированных ключей, вы можете связать его с collections.defaultdict(list), чтобы обеспечить многопользовательскую функциональность.
В своей книге "" Программирование на Python 3 ", Марк Саммерфилд вводит отсортированный класс словаря. Исходный код доступен в этот zip-архив - найдите SortedDict.py. Класс SortedDict подробно описан в книге (которую я очень рекомендую). Он поддерживает произвольные ключи для сравнения и несколько значений для каждого ключа (что любой словарь в Python делает, так что я не думаю, что это большая сделка).