用于查找区间之间的交点的Java算法 [英] Java algorithm for find intersection between intervals

问题描述

我有这样一个时间间隔：

I have a time interval like this:

[5,10]

，而我有更多的时间点列表，长度不同，例如：

and I have more list of time point, with different length, for example:

t1=[3,6,9,10] 
t2=[2,4,5,6,10]
..

其中， t1 [3,6] 是第一个间隔， [6,9] 秒，以此类推。

where in t1 [3,6] is the first interval, [6,9] the second and so on.

t2 和其他列表。

现在，我需要保存与第一个时间间隔相交的列表和特定间隔。例如，在 t1 中，我有 [3,6] 与 [5,10 ]，[6,9] 与 [5,10] 等相交。

Now I need to save the list, and the specific interval, that intersect with first time interval. For example in t1 I have [3,6] that intersect on [5,10], [6,9] that intersect with [5,10], etc.

我已经制定了一种算法，但是我需要处理更多数据，因此我需要一种快速算法。
例如，如果我处理300.000个列表，并且每个列表都有200个时间点，则算法1的罚款时间为5-10秒。但是如果我有10.000或更多的时间点，该算法将非常慢。

I have made an algorithm but I work with more data and I need a fast algorithm. For example if I work with 300.000 list and every list have 200 time points my algorithm 1 fine in about 5-10sec. But if I have 10.000 or more time point the algorithm is very slow.

我的算法是这样的：

First time interval <- [t1,t2]
For each list
  For each time interval [s1,s2] in list
     if(s1>= t1 && s2 <= t2)
     {
         saveIntervall()
     }
     else if (s1<= t2 && s2 > t2)
     {
         saveIntervall()
     }
     else if(s1 <  t1 && s2 >= t1)
     {
        saveIntervall()
     }
     else if (s1 < t1 && s2 > t2)
     {
        saveIntervall()
     }

Edit1：是的，我已订购列表。

Yes I have ordered list.

Edit2：我还有另一个问题，当我发现互动时，我需要计算交集的大小在0到1之间。
我用这个：

I have another problem, when i find the intersaction i need to calclulate a score between 0 and 1 of how the intersection is large. I use this:

            double score = 0.0d;
        if(s1>= t1 && s2 <= t2)
        {
            score = (s2-s1) / (t2-t1);
        }
        else if(t2 >= s2 && t1 > s1)
        {
            score = (s2-t1) / (t2-t1);
        }
        else if(t2 < s2 && t1 <= s1)
        {
            score = (t2-s1) / (t2-t1);
        }
        else
        {
            score = 1;
        }

我也可以加快速度吗？

推荐答案

首先，您的数据结构令人困惑-如果您要谈论离散的时间间隔，请像这样构造数据；例如 int [] [] ，其中内部数组的长度始终为2，因此您的 t1 变为：

First and foremost, your data structure is confusing - if you're trying to talk about discrete intervals of time, structure your data like so; for instance int[][] where the inner array is always length 2, so your t1 becomes:

int[][] t1 = {{3,6}, {6,9}, {9,10}};

使用正确的结构可能会帮助您简化算法并使其更易于使用。

Using the right structure will probably help you simplify your algorithm and make it easier to work with.

但是，比结构正确的数组更好的方法是使用专用类型来表示这些间隔，以便您可以绕过 List< Interval> 对象，并对它们进行某种包含检查。但不要重新发明轮子。很棒的 Guava库提供了强大的 范围 的类可以使用。更好的是，它还提供了 RangeSet 和 RangeMap 类，可让您轻松地完成您正在谈论的事情。另请参见其解释范围文章，其中介绍了基础知识。

Better than properly structured arrays, however, would be to use a dedicated type to represent these intervals, such that you could pass around List<Interval> objects and do some sort of contains check on them. But don't reinvent the wheel. The awesome Guava library provides a robust Range class that you can use. Even better though, it also provides RangeSet and RangeMap classes, which let you easily do the things you're talking about. See also their Ranges Explained article which covers the basics.

请注意，如果您不能在外部重新设计数组结构，则可以很容易地在内部将当前设计转换为 Range 对象。

Note that you could pretty easily transform your current design into Range objects internally, if you can't redesign the array structure externally.

曾经尝试过构建我自己的 IntervalSet 类，让我告诉你，这是一个棘手的问题，使用它们精心设计和高度测试的范围实用程序，您将省去很多麻烦。

Having tried at one point to build my own IntervalSet class, let me tell you that it's a tricky problem to get right and you'll save yourself a lot of headaches using their well designed and highly tested range utilities.

这就是我用番石榴描述您所要描述的方式-注意我们甚至无需考虑所涉及的数学-范围为我们做正确的事情：

Here's the way that I would do what you're describing with Guava - notice that we avoid even needing to think about the math involved - Range does the right thing for us:

/**
 * Given a Range and an group of other Ranges, identify the set of ranges in
 * the group which overlap with the first range.  Note this returns a Set<Range>
 * not a RangeSet, because we don't want to collapse connected ranges together. 
 */
public static <T extends Comparable<?>> Set<Range<T>>
        getIntersectingRanges(Range<T> intersects, Iterable<Range<T>> ranges) {
    ImmutableSet.Builder<Range<T>> builder = ImmutableSet.builder();
    for(Range<T> r : ranges) {
        if(r.isConnected(intersects) && !r.intersection(intersects).isEmpty()) {
            builder.add(r);
        }
    }
    return builder.build();
}

/**
 * Given a 2-length array representing a closed integer range, and an array of
 * discrete instances (each pair of which therefore represents a closed range)
 * return the set of ranges overlapping the first range.
 * Example: the instances array [1,2,3,4] maps to the ranges [1,2],[2,3],[3,4].
 */
public static Set<Range<Integer>> getIntersectingContinuousRanges(int[] intersects,
        int[] instances) {
    Preconditions.checkArgument(intersects.length == 2);
    Preconditions.checkArgument(instances.length >= 2);
    ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
    for(int i = 0; i < instances.length-1; i++) {
        builder.add(Range.closed(instances[i], instances[i+1]));
    }
    return getIntersectingRanges(Range.closed(intersects[0], intersects[1]),
                                 builder.build());
}

使用示例：

public static void main(String[] args)
{
    int[] interval = {5,10};
    int[] t1 = {3,6,9,10};
    int[] t2 = {2,4,5,6,10};

    System.out.println(getIntersectingContinuousRanges(interval, t1));
    System.out.println(getIntersectingContinuousRanges(interval, t2));
}

上面打印出：

[[3‥6], [6‥9], [9‥10]]
[[4‥5], [5‥6], [6‥10]]

这篇关于用于查找区间之间的交点的Java算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！