是否有一个标准的Python数据结构来保持事物的排序顺序？ [英] Is there a standard Python data structure that keeps things in sorted order?

问题描述

我有一组可能看起来像这样的范围：

I have a set of ranges that might look something like this:

[(0, 100), (150, 220), (500, 1000)]

然后我会添加一个范围，例如（250，400），列表将如下所示：

I would then add a range, say (250, 400) and the list would look like this:

[(0, 100), (150, 220), (250, 400), (500, 1000)]

然后，我尝试添加范围（399，450），它会出错，因为它与（250，400）。

I would then try to add the range (399, 450), and it would error out because that overlapped (250, 400).

添加新范围时，我需要进行搜索以确保新范围不与现有范围重叠。列表中再也没有范围会与列表中的另一个范围重叠。

When I add a new range, I need to search to make sure the new range does not overlap an existing range. And no range will ever be in the list that overlaps another range in the list.

为此，我想要一个数据结构，该结构廉价地按排序顺序维护其元素，并很快允许我在给定元素之前或之后找到该元素。

To this end, I would like a data structure that cheaply maintained its elements in sorted order, and quickly allowed me to find the element before or after a given element.

是否有更好的方法来解决此问题？是否有类似Python的可用数据结构？我知道 bisect 模块存在，这很可能是我将要使用的模块。但是我希望有更好的东西。

Is there a better way to solve this problem? Is there a data structure like that available in Python? I know the bisect module exists, and that's likely what I will use. But I was hoping there was something better.

编辑：我使用 bisect 模块。这是代码的链接。它有点长，所以我不会在这里发布：

I solved this problem using the bisect module. Here is a link to the code. It's a bit longish, so I won't post it here:

字节范围列表的实现

推荐答案

使用 SortedCollection中的.com / docs / sortedcontainers / sorteddict.html rel = noreferrer> SortedDict 。

SortedDict提供与dict相同的方法。此外，SortedDict可以按排序顺序有效地维护其键。因此，keys方法将按排序顺序返回键，popitem方法将删除具有最高键的项，依此类推。

A SortedDict provides the same methods as a dict. Additionally, a SortedDict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

我已经用过了-它有效。不幸的是，我现在没有时间进行适当的性能比较，但是从主观上讲，它似乎已经比 bisect 模块更快。

I've used it - it works. Unfortunately I don't have the time now to do a proper performance comparison, but subjectively it seems to have become faster than the bisect module.

这篇关于是否有一个标准的Python数据结构来保持事物的排序顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！