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

Python本身没有专门的工具来处理这个问题，不过它有一个叫做bisect的模块，可以帮助你用高效的方法保持一个有序的列表。

如果你有一个已经排好序的键的列表，可以把它和collections.defaultdict(list)结合起来，这样就能实现类似多重映射的功能。

Answer 2

你应该使用 sort(key=...)。
你用的这个 key 函数会和你现在用的 cmp 有关系。这样做的好处是，key 函数只会被调用 n 次，而 cmp 函数会被调用 nlog n 次，通常来说，key 函数的工作量是 cmp 函数的一半。

如果你能提供你的 __cmp__() 函数，我们可以帮你看看怎么把它转换成一个 key 函数。

如果你在修改数据时需要进行很多次迭代，建议你缓存一下排序后的结果。

Answer 3

对于有序字典，你可以利用Python的timsort排序算法的稳定性。简单来说，就是保持一些项目是部分排序的，当需要添加新项目时，就把它们放到最后，同时切换一个“脏”标记，然后在遍历之前对剩下的项目进行排序。想了解更多细节和实现方法，可以查看这个链接（这是Martelli的回答）： Python中的键有序字典