寻找数字范围的交集

Question

什么是查找两个数字范围是否相交的最佳方法？

我的数字范围是3023-7430，现在我想测试以下哪些数字范围与它相交：<3000, 3000-6000, 6000-8000, 8000-10000, >10000。答案应该是3000-6000和6000-8000。

在任何编程语言中，有什么好的、高效的数学方法来实现这一点？

- deceze

---

这是一个类似的问题，可以参考这里的解答：https://dev59.com/KXVC5IYBdhLWcg3w7V1q - Paul Dixon

Answer 1

只是一个假代码的猜测：

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest)
{
  Set<Range> results;
  foreach (rangeToTest in setofRangesToTest)
  do
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range
    results.add(rangeToTest);
  done
  return results;
}

- Chris Kimpton

Answer 2

我会创建一个范围类，并给它一个方法 boolean intersects(Range)。然后你可以执行以下操作：

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) }

或者，如果您为了清晰度使用了一些 Java 8 风格的函数式编程：

rangeset.stream().filter(range::intersects).collect(Collectors.toSet())

交集本身就像是一个：

this.start <= other.end && this.end >= other.start

- hstoerr

---

Hans-Peter 的条件应该为 OR 而不是 AND，因为您的示例检测到包含而不是交集。 - TomaszSobczak

@sbczk 我不这么认为。你能举个例子说明结果是错误的吗？请注意，我是在比较开头和结尾 - 包含会比较开头和开头，结尾和结尾。 - Hans-Peter Störr

Answer 3

这在很大程度上取决于您的范围。 范围可以是大或小的，聚集或非聚集的。 如果您有大型的、聚集的范围（想想“所有可被2整除的正32位整数”），那么使用Range(lower, upper)的简单方法将无法成功。

我想我可以这样说： 如果您有小范围（聚类或不聚类都无所谓），请考虑使用位向量。 这些小家伙在联合、交集和成员测试方面非常快速，尽管迭代所有元素可能需要一段时间，具体取决于大小。 此外，因为它们仅为每个元素使用单个位，所以它们相当小，除非您向它们投掷大范围。

如果您有较少但更大的范围，则像其他人描述的那样使用Range类就足够了。 该类具有下限和上限属性，并且intersection(a,b)基本上是b.upper < a.lower或a.upper > b.lower。 单个范围的并集和交集可以在常量时间内实现，对于复合范围，时间随子范围数量增加而增长（因此您不希望有太多的小范围）。

如果您有一个巨大的空间，其中可以放置数字，并且范围以讨厌的方式分布，则应查看二进制决策图（BDDs）。 这些巧妙的图表具有两个终端节点True和False，每个输入位都有一个决策节点。 决策节点具有它所查看的位和两个后续图形节点——一个用于“位为1”，另一个用于“位为0”。 在这些条件下，您可以在小空间中编码大范围。 所有正整数可以在图中的3个节点中编码，基本上是最不显著位的单个决策节点，它在1上转到False并在0上转到True。

交集和并集是相当优雅的递归算法，例如，交集基本上需要在每个BDD中获取两个对应节点，遍历1边缘直到出现某个结果并检查：如果其中一个结果是False-Terminal，请在结果BDD中创建一个1-branch到False-terminal。 如果两个都是True-Terminal，请在结果BDD中创建一个1-branch到True-terminal。 如果是其他东西，请在结果BDD中创建一个1-branch到此其他东西。 之后，一些最小化会发生作用（如果节点的0和1分支都指向同一个目标BDD / 终端，则删除该节点并将传入转换引导到目标），然后您就完成了。 我们甚至走得更远，我们在BDD上模拟了整数集合的加法，以增强值预测以优化条件。

这些考虑意味着您的操作受到数字范围中位数的限制，即log_2(MAX_NUMBER)。 想想看，您可以以几乎恒定的时间交集任意64位整数集合。

更多信息可以在维基百科和参考文献中找到，例如：二元决策图。

另外，如果可以容忍假阳性，并且只需要进行存在性检查，则可以查看布隆过滤器。布隆过滤器使用哈希向量来检查元素是否包含在表示的集合中。交集和并集是常数时间。主要问题在于，如果填充布隆过滤器太多，则会增加错误阳性率。 更多信息可以在维基百科中找到，例如：布隆过滤器。

哈希集合表示是一个有趣的领域。 :)

- Tetha

Answer 4

在Python中

class nrange(object):
    def __init__(self, lower = None, upper = None):
        self.lower = lower
        self.upper = upper
    def intersection(self, aRange):
        if self.upper < aRange.lower or aRange.upper < self.lower:
            return None
        else:
            return nrange(max(self.lower,aRange.lower), \
                          min(self.upper,aRange.upper))

- Andrea Ambu

Answer 5

如果你正在使用Java，Commons Lang Range有一个overlapsRange(Range range)方法。

- TAN70