Я переношу программу на С++ на Python. Есть несколько мест, где он использует std::set для хранения объектов, которые определяют свои собственные операторы сравнения. Поскольку стандартная библиотека Python не имеет эквивалента std::set (структура данных сопоставления ключевых значений), я попытался использовать обычный словарь, а затем отсортировал его при повторении, например:
def __iter__(self):
items = self._data.items()
items.sort()
return iter(items)
Однако профилирование показало, что все вызовы от .sort() до __cmp__ являются серьезным узким местом. Мне нужна лучшая структура данных - по существу сортированный словарь. Кто-нибудь знает о существующей реализации? В противном случае, какие-либо рекомендации о том, как я должен это реализовать? Производительность чтения важнее, чем производительность записи, а время важнее памяти.
Бонусные баллы, если он поддерживает несколько значений для каждого ключа, например С++ std::multimap.
Обратите внимание, что класс OrderedDict не соответствует моим потребностям, потому что он возвращает элементы в порядке вставки, тогда как они мне нужно сортировать, используя их методы __cmp__.
