代码之家 › 专栏 › 技术社区 › EMP

python等价于std::set和std::multimap

dictionary data-structures performance python c++

EMP · 技术社区 · 14 年前

我正在把一个C++程序移植到Python。有一些地方可以使用 std::set 存储定义自己的比较运算符的对象。因为python标准库没有等价的 标准::设置 (排序后的键值映射数据结构)我尝试使用普通字典,然后在迭代时对其进行排序,如下所示:

def __iter__(self):
    items = self._data.items()
    items.sort()
    return iter(items)

但是,分析显示 .sort() 到 __cmp__ 是一个严重的瓶颈。我需要一个更好的数据结构——本质上是一个分类字典。有人知道现有的实现吗?如果失败了,我应该如何实施这一点有什么建议吗?读性能比写性能更重要,时间比内存更重要。

如果它支持每个键的多个值,比如C++ std::multimap .

请注意 OrderedDict 类不符合我的需要,因为它按插入顺序返回项,而我需要使用 α-CMPa 方法。

4 回复 | 直到 14 年前

Community noseratio 7 年前

对于已排序的字典,您可以(ab)使用python的timsort的稳定特性:基本上,保留部分排序的项,在需要时在末尾附加项,切换“dirty”标志,并在迭代之前对剩余项进行排序。有关详细信息和实现,请参见此条目(martelli的答案): Key-ordered dict in Python

John La Rooy 14 年前

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

如果你能把你的 __cmp__() 我们可能会向您展示如何将其转换为键函数

如果您在修改之间进行了大量的迭代,那么应该缓存已排序项的值。

Mike Graham 14 年前

虽然python没有内置的数据结构, bisect 模块提供了用适当有效的算法保存排序列表的功能。

如果您有一个排序键列表,可以将其与 collections.defaultdict(list) 提供多映射类功能。

Tim Pietzcker 14 年前

在他的书中 Programming in Python 3 “,Mark SummerField引入了一个排序字典类。源代码在 this zip archive -寻找Sorteddict.py。书中详细描述了SortedDict类(我非常推荐)。它支持用于比较的任意键和每个键的多个值(这是Python中任何字典都支持的,所以我认为这没什么大不了的)。

推荐文章

patrick · 从boost::绑定1和2占位符运行make失败。。。?

1 年前

rookie · 检查函数模板的所有参数包参数是否属于int

1 年前

ivaigult · -W转换和隐式字符串到布尔类型转换

1 年前

David Bien · declval<_Xp(&)()>()()-这在下面的上下文中意味着什么?

1 年前

khallad sayed · 在%上,C++表达式必须具有整型或无范围枚举类型

1 年前

rainer · 后台插入程序的初始化

1 年前

Community wiki · 以理智、安全和高效的方式复制文件

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Prakritish Ghosh · 现在显示正确输出的函数中的Infix到Postfix错误[重复]

1 年前

Ma Joonyoung · 粗粒度和细粒度链表的时间比较

1 年前