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

你应该用sort(key=...).
您使用的关键功能将与您已使用的cmp相关.优点是关键函数被调用n次,而cmp被称为nlog n次,并且通常key是cmp执行的一半工作

如果你可以包括你,__cmp__()我们可以告诉你如何将它转换为关键功能

如果在修改之间进行大量迭代,则应该缓存已排序项的值.

Answer 2

对于排序字典,您可以(ab)使用python的timsort的稳定特性:基本上,保持项目部分排序,在需要时在最后添加项目,切换"脏"标志,并在迭代之前对剩余项进行排序.有关详细信息和实现,请参阅此条目(A Martelli的答案): Python中按键排序的dict