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__方法排序。

- EMP

Answer 1

对于排序字典，你可以（滥用）Python的timsort算法的稳定性：基本上，部分排序，当需要时在末尾添加项，切换“脏”标志，并在迭代之前排序其余项。请参见此条目以获取详细信息和实现（A Martelli的答案）：Python中键排序字典

- LeMiz

Answer 2

你应该使用sort(key=...)。使用的键函数将与你已经使用的cmp相关。优点是键函数被调用n次，而cmp被调用nlog n次，通常key所做的工作是cmp的一半。

如果你可以包含你的__cmp__()函数，我们可能可以向你展示如何将其转换为键函数。

如果在修改之间进行了大量迭代，则应缓存排序项的值。

- John La Rooy

---

虽然没有直接回答关于数据结构的问题，但这肯定有助于提高性能。+1 - EMP

Answer 3

Python没有内置此功能的数据结构，但是bisect模块提供了保持排序列表并具备适当高效算法的功能。

如果您有一个已排序键列表，可以将其与collections.defaultdict(list)结合使用，以提供类似于多重映射的功能。

- Mike Graham

Answer 4

在他的书 "Programming in Python 3" 中，Mark Summerfield介绍了一个排序字典类。源代码可以在this zip archive中找到 - 寻找SortedDict.py。 SortedDict类在书中有详细描述（我非常推荐这本书）。它支持任意键进行比较和每个键多个值（Python中的任何字典都可以做到，所以我认为这不是什么大问题）。

- Tim Pietzcker

Answer 5

这是一篇晚期的帖子，但如果有人现在正在寻找，这里有一个链接：https://grantjenks.com/docs/sortedcontainers/ 这不是内置的，只需要通过pip安装即可。它具有排序字典和列表，支持插入、删除、索引和二分查找。大多数操作的平摊复杂度为O(log(n))。

- Soumyajit