6

I have a JavaScript program in which I will be managing a lot of ranges of integers. In this context, a range is simply a start and an end value (or anything equivalent, like a start and a length value), with a reference to another object. The ranges can overlap, and can be identical (although the referenced object will be different).

The possible start and end values are between 0 and 4294967295 (232 - 1 or 0xFFFFFFFF), although there are several big "holes" in the domain that no range will ever cover, even partially. Most ranges will be very small compared to the domain of possibilities: I expect that the overwhelming majority will have a length smaller than 2000.

My most important use case for this structure will be to look up all ranges that contain a given integer value. Most of the time, I expect the lookup to fail (there will be no range containing the given value).

Otherwise, I will obviously also need to add elements to it (often) and delete elements from it (seldom). Once in a while, too, I'll need to find all ranges that overlap a given range, rather than all ranges that contain a single value.

What kind of data structure can I use for that? A linear search in a list of ranges is impractical because the lookups fail most of the time; and I need to do lookups very, very often.

4

4 回答 4

1

键是开始（低）值的二叉树。一旦你找到一个键，你可以很容易地看起来很宽（更高和更低）。

于 2012-04-24T23:55:51.490 回答
0

如果您将所有范围的开始和结束存储在一个列表中作为映射回范围索引，您可以按顺序 n 执行此操作。即 mylist = [ {45: range1}, {47: range2}, {55: range1}, {57:range2} ] 然后您可以扫描列表并在您第一次看到标签时设置布尔值 true 和 false第二次看到它。当你找到一个比你高的数字时，你可以知道你在哪个范围内。您可以使用 bisect 插入 O(logn)，而删除和插入是 O(n)。祝你好运！〜本

于 2012-04-24T23:29:38.007 回答
0

我喜欢 System.Tuple 之类的东西 [或 F# 列表，但很少有人知道 F#]。

如果范围是连续的，那么将开始和结束整数作为元组很简单 Tuple nums = (start, end)，否则将具有开始结束的元组作为元组的第一个条目，将列表作为第二个条目可能对你有用，Tuple nums = ((start, end), List)。

于 2012-04-24T23:23:00.253 回答
0

尝试 1：

保留两棵二叉树，一棵用于起始值，一棵用于结束值。让两棵树的节点（或只是“结束”）具有通过某个 id（范围的起始值）引用唯一范围的属性。

在“开始”树上进行二分搜索，将列表缩小到开始小于或等于您的搜索值的范围。在值大于或等于搜索值的“结束”树上执行相同操作。从两棵树中找到节点的交集，这些范围包含您的搜索值。

您可以使用哈希映射/集找到交集以获得最佳性能。

尝试 2：

如果您为键是第一个但由开始值和结束值共享的许多位的间隔保留一个哈希列表怎么办？

因此，如果 start 是 '11001101' 并且 end 是 '11010010'，那么 key 是 '110'。每个键将映射到共享该键的范围（开始和结束）列表。

当搜索一个值以查看它们的范围时，例如“00101111”，您必须在哈希列表中搜索 n 个不同的值左右，其中 n 是位数（在您的情况下为 32）。在这种情况下，您将搜索“00101111”、“0010111”、“001011”等。对于每次点击，您都必须实际检查搜索值是否在范围内。

乍一看，在我看来，平均而言，对于您获得的每次命中，一半将是误报，但如果命中数很少，这无关紧要，而且键越大，它应该得到的命中越少.

有一个小问题，比如说“00101110”的开头和“01100111”的结尾，因为键是“0”，这意味着会有大量的“误报”。如果有 2 个不同的键“001”和“01”会更好，尽管我不确定您需要为此优化编码的特定算法。如果范围足够小并且可以解决或忽略此问题，那么您可以获得非常快速的查找，因为大多数键将相对较长并且与搜索不匹配。

于 2012-04-25T00:16:26.440 回答