9

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

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

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

4

5 回答 5

21

只是一个伪代码猜测：

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;
}
于 2008-10-22T08:37:21.523 回答
6

我会创建一个 Range 类并给它一个方法 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
于 2008-10-22T08:42:05.693 回答
3

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

我想我可以说以下内容：如果您的范围很小（聚类或不聚类在这里无关紧要），请考虑位向量。这些小动物在联合、交集和成员测试方面的速度非常快，尽管所有元素的迭代可能需要一段时间，具体取决于大小。此外，因为它们只为每个元素使用一个位，所以它们非常小，除非你对它们投入很大的范围。

如果您的范围更少，范围更大，那么其他人描述的 Range 类就足够了。这个类有属性lower和upper，intersection(a,b)基本上是b.upper < a.lower or a.upper > b.lower。联合和交集可以在单个范围和组合范围内以恒定时间实现，时间随着子范围的数量而增长（因此您不希望没有太多的小范围）

如果你有一个很大的空间可以存放你的数字，并且范围分布在一个令人讨厌的方式中，你应该看看二元决策图 (BDD)。这些漂亮的图有两个终端节点，True 和 False，以及输入的每一位的决策节点。一个决策节点有一个它查看的位和两个后续的图形节点——一个用于“位为一”，一个用于“位为零”。鉴于这些条件，您可以在狭小的空间中对大范围进行编码。任意大数的所有正整数都可以在图中的 3 个节点中编码 - 基本上是最低有效位的单个决策节点，在 1 上为假，在 0 上为真。

Intersection 和 Union 是非常优雅的递归算法，例如，intersection 基本上在每个 BDD 中取两个对应的节点，遍历 1-edge 直到弹出一些结果并检查：如果其中一个结果是 False-Terminal，则创建一个 1 - 分支到结果 BDD 中的 False 终端。如果两者都是真终端，则在结果 BDD 中为真终端创建一个 1 分支。如果它是其他东西，请在结果 BDD 中为这个东西创建一个 1 分支。之后，开始进行一些最小化（如果节点的 0 和 1 分支转到相同的以下 BDD / 终端，则将其删除并将传入的转换拉到目标），你就很成功了。我们甚至更进一步，我们致力于在 BDD 上模拟整数集的加法，以增强价值预测以优化条件。

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

更多信息可以在例如维基百科 和参考论文中。

此外，如果误报是可以忍受的并且您只需要进行存在性检查，则可以查看 Bloom 过滤器。布隆过滤器使用哈希向量来检查元素是否包含在表示的集合中。Intersection and Union 是常数时间。这里的主要问题是，如果布隆过滤器填得太多，误报率就会增加。再次，例如，在Wikipedia中的信息。

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

于 2008-10-22T09:49:53.730 回答
1

在蟒蛇

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))
于 2008-10-22T09:55:27.823 回答
0

如果你使用 Java Commons Lang Range 有一个 overlaysRange(Range range) 方法。

于 2011-11-16T22:43:05.897 回答