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

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

dictionary data-structures performance python c++

EMP · 技术社区 · 15 年前

我正在把一个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 回复 | 直到 15 年前

Community CDub 8 年前

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

John La Rooy 15 年前

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

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

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

Mike Graham 15 年前

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

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

Tim Pietzcker 15 年前

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

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

3 月前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

3 月前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

3 月前

user29715306 · from_users=和chats=电视节目中的差异

3 月前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

4 月前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

4 月前

prayner · 更新嵌套字典包含列表中的项

4 月前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

4 月前

Dave · 如何在for循环中修改列表值

4 月前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

4 月前