0

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

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 开始并向上计数。你会看到有很多相同的数字。这是样本的类。

在这里，我们有1 1 1 1 1 1 1 1 1 1 1 1= 12 个类别 1 的样本。

对于第 2 类，我们有2 2 2 2 2 2 2 2 2 2 2= 11 个样本。

我的问题是我想为每节课找到开始和停止。例如：第 1 类始终从索引 0 开始，在本例中以索引 11 结束。

第 2 课在第 1 课结束后直接开始。

问题：

我正在使用 EJML（Effient Java Matrix Library）并且我打算使用这个函数：

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

这等于这个 MATLAB 代码：

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

但我需要从这个y向量中找到开始和停止索引。例如，第 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);
        }
4

3 回答 3

1

我认为这有一个名称，但我不记得它可能是什么，但是您开始通过加速搜索寻找下一个边界，然后使用二进制搜索。

您知道这些数字是按升序排列的，并且可能有很多相同的数字，因此您首先检查下一个元素。但是，您不是一次只走 1 步，而是加速并走 2、4、8、16 步……直到找到更大的数字。

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

一旦你为边界提供资金，你就可以从 1, 2, 4, ... 为下一个边界重新开始。

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

我会把它留给你来实际编码。

于 2020-05-08T15:25:17.063 回答
1

以下是在 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
于 2020-05-08T19:32:35.643 回答
1

如果您想更快地做到这一点，那么二进制搜索就是您的朋友。将它快速组合在一起，它在 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
于 2020-05-12T01:50:02.920 回答