有没有一个标准的Python数据结构将事情按顺序排序？ [英] Is there a standard Python data structure that keeps thing 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.htmlrel =nofollow> 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屋！