我可以使用什么数据结构来存储和检索离散值的范围

What data structure can I use to store and retrieve ranges of discrete values?

本文关键字：检索范围存储可以使什么数据结构我可以更新时间：2023-09-26

我有一个JavaScript程序，我将在其中管理很多整数范围。在此上下文中，范围只是开始值和结束值（或任何等效值，如开始值和长度值），并引用另一个对象。范围可以重叠，并且可以相同（尽管引用的对象会有所不同）。

可能的开始值和结束值介于 0 和 4294967295 之间（2³² - 1 或 0xFFFFFFFF ），尽管域中有几个大的"漏洞"，任何范围都不会覆盖，即使是部分。与可能性领域相比，大多数范围将非常小：我预计绝大多数范围的长度将小于 2000。

对于此结构，我最重要的用例是查找包含给定整数值的所有范围。大多数时候，我希望查找失败（不会有包含给定值的范围）。

否则，我显然还需要（经常）向其添加元素并从中删除元素（很少）。偶尔，我也需要查找与给定范围重叠的所有范围，而不是包含单个值的所有范围。

我可以使用哪种数据结构？在范围列表中进行线性搜索是不切实际的，因为查找大多数时候都会失败;我需要非常非常频繁地进行查找。

二叉树，其中键是起始（低）值。找到钥匙后，您可以相当轻松地查看宽（更高和更低）。

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

如果范围是连续的，则可以轻松地将开始和结束整数作为元组元组数字 =（开始，结束

），否则将具有开始-结束的元组作为元组的第一个条目，将列表作为第二个条目可能适合您，元组数字 = （（开始，结束），列表）。

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

尝试 1：

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

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

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

尝试 2：

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

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

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

乍一看，在我看来，平均而言，对于您获得的每次点击，一半将是误报，但如果点击次数很少，并且键越大，它应该获得的命中次数就越少，这并不重要。

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