高效存储多个数字范围以供将来搜索的方法

Question

我有一个文本文件，里面充满了IP地址范围。我使用ip2long将地址转换为长整型，以便轻松检查给定的地址是否在范围内。但是，我正在寻找一种有效的方法来存储这些范围，然后搜索以查看IP地址是否存在于任何范围内。

我目前考虑的方法是创建一个对象，该对象具有范围的低端和高端，并具有检查值是否在范围内的函数。我将把这些对象存储在列表中并逐个检查。但是，我觉得这可能有点低效，并且随着列表增加会变得很慢。

是否有比我想的更好的方法？

- user2132167

---

你可以使用Guava RangeSet... - Louis Wasserman

Answer 1

以下数据结构可能会对您有所帮助:

线段树

来自维基百科 (实现):

是一种用于存储区间或段的树形数据结构。它允许查询存储的哪些段包含给定点。

---

区间树

来自维基百科 (实现)：

是一种用于保存区间的树形数据结构。具体而言，它允许高效地找到与任何给定区间或点重叠的所有区间。

---

范围树

来自 维基百科 (实现)：

是一种有序的树形数据结构，用于存储点列表。它可以高效地报告给定范围内的所有点。

- Arturo Menchaca

Answer 2

假设这些范围没有重叠，否则您可以将它们合并成一个范围。

然后创建一个按递增顺序排序的数组 begin1，end1，begin2，end2，...。其中 begini 包含在范围内，endi 刚好在范围之后。

现在进行二分查找并：

int pos = ... .binarySearch ...
boolean found = pos >= 0;
if (!found) {
    pos = ~pos;
}
boolean atBegin = pos % 2 == 0;
boolean insideRange = (found && atBegin) || (!found && !atBegin);
//Equivalent: boolean insideRange = found == atBegin;

查找测试的时间复杂度为O(log N)。创建初始数组要复杂得多。

Java二分查找返回找到内容的索引，若未找到则返回补码(~index)，其值小于0。

---

补充：我认为以上内容可以被“聪明地”概括。

boolean insideRange = (Arrays.binarySearch(...) & 1) == 0;

尽管需要一些解释性的评论，但我将把这留给读者。

- Joop Eggen

---

它几乎肯定不是O(log N)。你说要对范围进行排序，这意味着如果它们在文本文件中没有完全排序，则至少为O(N log N)。此外，即使扫描每个范围以创建数组也是O(N)。我知道二分搜索是O(log N)，但是这样说（在我看来）是误导性的，因为它似乎你正在谈论你的解决方案是O(log N)。否则，解决方案非常好。 - nhouser9

@nhouser9 我的意思是关于检索，考虑到提前构建的IP数组。但是你的评论很好。 - Joop Eggen

@nhouser9 我认为Joop Eggen的意思是查找。 - Palcente

当然，他的意思是查找（我甚至在我的评论中说过我知道他的意思）。但是，如果你的解决方案实际上不是O(log N)，告诉别人“这是O(log N)”是具有误导性的。反正，算法最快的部分是O(log N)又有什么用呢？任何关心时间复杂度的人都关心算法最慢的部分。最好的情况下，“这是O(log N)”这句话是无关紧要的——最坏的情况下，它会非常误导人。 - nhouser9

我不能保证范围不会重叠。我不管理列表，所以任何事情都有可能发生。此外，这些范围并非按顺序排列，因此我还需要进行排序。 - user2132167

范围在查找方面需要经常更新吗？需要删除范围吗？那么树状结构确实更好。只有当范围更新得不太频繁时，我的解决方案才是可行的。合并重叠的范围很容易，但是无法删除旧范围。 - Joop Eggen