Как я могу найти индекс остановки и начала для вектора Java? - PullRequest
Новая
       25

Как я могу найти индекс остановки и начала для вектора Java?

0 голосов
/ 08 мая 2020

У меня есть вектор, который выглядит так: 

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 = 11 образцов для класса номер 2.

Моя проблема в том, что я хочу найти начало и конец для каждого класса. Например: класс 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-l oop, чтобы сделать это, но циклы for в Java работают довольно медленно, потому что я собираюсь иметь очень-очень большой вектор 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);
        }

Ответы [ 3 ]

1 голос
/ 08 мая 2020

Ниже в MATLAB. for l oop будет go через каждое уникальное значение, хранящееся в 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
1 голос
/ 12 мая 2020

Если вы хотите сделать это быстрее, то двоичный поиск - ваш друг. Сложил это очень быстро, и он делает вещи за время O (log n), тогда как линейный поиск делает это за O (n). Это довольно просто c и предполагает, что ваши данные выглядят примерно так, как вы их описываете. Подайте ему странные данные, и он сломается.: 

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
1 голос
/ 08 мая 2020

Думаю, у этого есть название, но я не могу вспомнить, что это могло быть, но вы начинаете искать следующую границу с ускоренным поиском, а после этого используете бинарный поиск.

Вы знаете, что числа расположены в порядке возрастания, и потенциально может быть много одинаковых чисел, поэтому вы начинаете с проверки следующего элемента. Но вместо того, чтобы продолжать делать один шаг за раз, вы ускоряетесь и делаете шаги 2, 4, 8, 16, ... пока не найдете большее число.

Как только вы найдете большее число, вы ' Мы зашли слишком далеко, но на последнем шаге был начальный номер, поэтому вы знаете, что граница находится где-то между двумя последними шагами, и затем применяете двоичный поиск границы.

После того, как вы профинансировали границы, вы начинаете с шага 1, 2, 4, ... для следующей границы.

Если вы ожидаете, что у большинства чисел будет примерно одинаковое количество вхождений, вы можете сохранить текущее среднее значение и сделать первый шаг с этим усреднением, чтобы начать разбег.

...