测试在Ruby的重叠阵列 [英] Testing for overlapping arrays in Ruby

问题描述

说我有阵列在Ruby中的数组，

Say I have an array of arrays in Ruby,

[[100,300], 
 [400,500]]

这是我加入CSV数据的连续线建设。

that I'm building by adding successive lines of CSV data.

什么是最好的方式，增加一个新的子阵的时候，要测试是否通过子数组中的两个数字所涵盖的范围由任何previous子阵列覆盖？

What's the best way, when adding a new subarray, to test if the range covered by the two numbers in the subarray is covered by any previous subarrays?

在换言之，每个子阵列包括在上面的例子中，线性范围（100-300和400-500）。如果我想，如果我尝试添加[499501]，例如，到阵列，因为会有重叠的异常被抛出，我怎么可能这个最佳的测试？

In other words, each subarray comprises a linear range (100-300 and 400-500) in the example above. If I want an exception to be thrown if I tried to add [499,501], for example, to the array because there would be overlap, how could I best test for this?

推荐答案

由于您的子阵列应该重新present范围，它可能是实际使用的范围，而不是数组的数组的数组是一个好主意。

Since your subarrays are supposed to represent ranges, it might be a good idea to actually use an array of ranges instead of an array of array.

所以你的阵列将 [100..300，400..500] 。

有关两个范围，我们可以很容易地确定哪些检查两个范围重叠，是否一种方法：

For two ranges, we can easily define a method which checks whether two ranges overlap:

def overlap?(r1, r2)
  r1.include?(r2.begin) || r2.include?(r1.begin)
end

现在检查的范围研究是否与任何范围重叠的范围数组，你只需要检查是否重叠？（R， R2）是范围的阵列中的任何 R2 真：

Now to check whether a range r overlaps with any range in your array of ranges, you just need to check whether overlap?(r, r2) is true for any r2 in the array of ranges:

def any_overlap?(r, ranges)
  ranges.any? do |r2|
    overlap?(r, r2)
  end
end

这可以用这样的：

Which can be used like this:

any_overlap?(499..501, [100..300, 400..500])
#=> true

any_overlap?(599..601, [100..300, 400..500])
#=> false

下面 any_overlap？需要 O（N）的时间。所以，如果你使用 any_overlap？每次添加一个范围的数组时，整个事情将是为O（n ** 2）。

Here any_overlap? takes O(n) time. So if you use any_overlap? every time you add a range to the array, the whole thing will be O(n**2).

然而，有一种方法可以做你想做的，不检查每一个范围：

However there's a way to do what you want without checking each range:

您添加的所有范围的阵列，不检查重叠。然后检查数组中的任何范围是否与其他任何重叠。您可以通过排序每个范围的开始的数组，然后检测是否两个相邻的范围在高效地做到这一点为O（n log n）的时间上重叠：

You add all the ranges to the array without checking for overlap. Then you check whether any range in the array overlaps with any other. You can do this efficiently in O(n log n) time by sorting the array on the beginning of each range and then testing whether two adjacent ranges overlap:

def any_overlap?(ranges)
  ranges.sort_by(&:begin).each_cons(2).any? do |r1,r2|
    overlap?(r1, r2)
  end
end

这篇关于测试在Ruby的重叠阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！