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