Python-эквивалент std :: set и std :: multimap

Question

Я портирую программу на 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__.

Answer 1

Для отсортированного словаря вы можете (ab) использовать стабильную природу тимсорта python: в основном, сохранять элементы частично отсортированными, добавлять элементы в конце, когда это необходимо, переключая «грязный» флаг и сортировать оставшиеся до итерации , Смотрите эту запись для деталей и реализации (ответ Мартелли): Диктофон с ключами в Python

Answer 2

Вы должны использовать sort(key=...).
Используемая вами ключевая функция будет связана с уже используемым cmp. Преимущество состоит в том, что ключевая функция вызывается n раз, тогда как cmp вызывается nlog n раз, и обычно key выполняет половину работы, которую выполняет cmp

Если вы можете включить __cmp__(), мы, вероятно, покажем вам, как преобразовать его в ключевую функцию

Если вы делаете много итераций между модификациями, вам следует кэшировать значение отсортированных элементов.

Answer 3

Python не имеет встроенных структур данных для этого, хотя модуль bisect предоставляет функциональные возможности для хранения отсортированного списка с помощью соответственно эффективных алгоритмов.

Если у вас есть список отсортированных ключей, вы можете связать его с collections.defaultdict(list) для обеспечения функциональности, подобной многокарте.

Answer 4

В своей книге " Программирование на Python 3 " Марк Саммерфилд представляет отсортированный словарный класс. Исходный код доступен в этом zip-архиве - ищите SortedDict.py. Класс SortedDict подробно описан в книге (которую я очень рекомендую). Он поддерживает произвольные ключи для сравнения и несколько значений для каждого ключа (что делает любой словарь в Python, так что, думаю, это не так уж и важно).