如何找到 Java 向量的停止和开始索引？

Question

我有一个看起来像这样的矢量：

y =

 Columns 1 through 19:

   1   1   1   1   1   1   1   1   1   1   1   1   2   2   2   2   2   2   2

 Columns 20 through 38:

   2   2   2   2   3   3   3   3   3   3   3   3   3   3   3   4   4   4   4

 Columns 39 through 57:

   4   4   4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5   6

 Columns 58 through 67:

   6   6   6   6   6   6   6   6   6   6

向量y总是从1开始向上计数。你看到有很多相同的数字。这是示例的 classes。

这里我们有 1 1 1 1 1 1 1 1 1 1 1 1 = 12 个样本用于 class 数字 1。

我们有 2 2 2 2 2 2 2 2 2 2 2 = 11 个样本用于 class 数字 2。

我的问题是我想为每个 class 找到开始和停止。例如：Class 1 总是从索引 0 开始，到索引 11 结束。

Class 2 在 class 1 结束后直接开始。

问题：

我正在使用 EJML（Effient Java 矩阵库）并且我打算使用这个函数：

C = A.extractMatrix(1,4,2,8)

相当于这个 MATLAB 代码：

C = A(2:4,3:8)

但我需要从这个 y 向量中找到开始和停止索引。例如 class 3 在哪个索引中停止和启动？你有什么聪明的想法如何做到这一点？

当然，我可以使用 for 循环来执行此操作，但是 Java 中的 for 循环非常慢，因为我将有一个非常非常大的 y 向量。

建议？

编辑：

这是一个建议。这样好吗，还是可以做得更好？

private void startStopIndex(SimpleMatrix y, int c, Integer[] startStop) {
    int column = y.numCols();
    startStop[0] = startStop[1] + 1; // Begin at the next class
    for(int i = startStop[0]; i < column; i++) {
        if(y.get(i) != c) {
            break;
        }else {
            startStop[1] = i;
        }
    }

}

假设我们从以下位置调用方法：

        Integer[] startStop = new Integer[2];
        for(int i = 0; i < c; i++) {
            startStopIndex(y, c, startStop);
        }

Answer 1

我想这个有个名字，但我记不起它可能是什么了，但是你开始用加速搜索寻找下一个边界，然后使用二分搜索。

你知道数字是按升序排列的，并且可能有很多相同的数字，所以你首先检查下一个元素。但是，您不是一次继续前进 1 步，而是加速并步进 2、4、8、16 ...，直到找到更大的数字。

一旦你找到了一个更大的数字，你就走得太远了，但最后一步有初始数字，所以你知道边界在最后两个步骤之间的某个地方，然后你应用二分查找为边界。

一旦您为边界提供资金，您就可以重新开始步进 1、2、4、... 以获得下一个边界。

如果您希望大多数数字的出现次数大致相同，则可以保持运行平均计数，并以该平均值迈出第一步，以运行开始。

我会留给你实际编码。

Answer 2

下面是MATLAB中的。 for 循环将遍历存储在 x1 中的每个唯一值，然后找到该值的第一次和最后一次出现。

x = [ 1 1 1 2 2 3 3 3 3 3 4 4 4 4 5 5 5 ]
x1 = unique(x)'

for k1 = 1:length(x1)
    x1(k1,2:3) = [find(x == x1(k1,1),1,"first"), find(x == x1(k1,1),1,"last")];
end

以上代码将 x1 生成为 3 列矩阵

 1     1     3
 2     4     5
 3     6    10
 4    11    14
 5    15    17

Answer 3

如果你想做的更快，那么二进制搜索是你的朋友。非常快地将它们组合在一起，它在 O(log n) 时间内完成事情，而线性搜索在 O(n) 内完成。它非常基础，并假设您的数据看起来与您描述的非常相似。给它提供奇怪的数据，它就会崩溃。:

int[] breakPoints(int[] arr, int low, int high){
    int[] rtrn = new int[high];
    for(int i=low;i<high;i++){
        rtrn[i]=binarySearch(arr, i, 0, arr.length-1);
    }
    return rtrn;
}

int binarySearch(int[] arr, int k, int start, int end){
    int mid = (start+end)/2;
    if(mid==arr.length){
        return -1;
    }
    if(arr[mid]==k && arr[mid+1]==k+1){
        return mid+1; //or just mid if you want before breakpoint
    }
    if(arr[mid]<=k){
        return binarySearch(arr, k, mid+1, end);
    }
    return binarySearch(arr, k, start, mid-1);
}

你可以这样称呼它：

int[] data = {1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,5,5,6,6,6,6};
int[] bp = breakPoints(data,1,6);
//return 0, 3, 8, 13, 16, 18

如何找到 Java 向量的停止和开始索引？

How can I find the stop and start index for a Java vector?

java

matlab

vector

matrix

ejml