Алгоритм поиска наименьшего индекса в последовательности векторов, соответствующих заданным условиям

Question

Предположим, у нас есть k последовательностей фиксированной длины p . Каждая последовательность имеет двойные значения в диапазоне от 0 до 1.0 . Для простоты предположим также, что последовательности являются просто массивами; в реальной реализации они будут списком.

Теперь алгоритму необходимо найти наименьший индекс, значение которого представляет «серьезное расстройство» в данной последовательности. Это расстройство может быть значением 1,0 или значением, превышающим определенный порог (например, 0,2 ). Если, например, при переходе от j-1 к j значение превышает пороговое значение, то искомый индекс будет j-1 . * 1021. *

Расстройство 1,0 имеет приоритет над пороговым значением; например, если мы найдем индекс, соответствующий порогу, мы все равно должны проверить последовательность на наличие 1.0 .

Наконец, алгоритм должен выдавать наименьший индекс, который привел к расстройству. Я быстро собрал некоторый код, чтобы проверить концепцию и показать вам, что мне нужно. То, что я ищу, - это, возможно, более эффективная реализация, поскольку этот алгоритм будет выполняться довольно широко.

List<double[]> nearCaptures = new ArrayList<double[]>();
double threshold = 0.2;
double majorUpset = 1.0;
int[] indexes = new int[nearCaptures.size()];
for (int i = 0; i < nearCaptures.size(); i++) {
    int index = 0;
    double[] tempArray = nearCaptures.get(i);
    Arrays.sort(tempArray);
    int tempIndex = Arrays.binarySearch(tempArray, majorUpset);
    if (tempIndex > 0) {
        for (int j = 1; j < nearCaptures.get(0).length; j++) {
            if (nearCaptures.get(i)[j] == majorUpset) {
                index = j-1;
                break;
            }
        }
    } else {
        for (int j = 1; j < nearCaptures.get(0).length; j++) {
            if (nearCaptures.get(i)[j] >= nearCaptures.get(i)[j-1] + threshold) {
                index = j-1;
                break;
            }
        }
    }
    indexes[i] = index;
}
Arrays.sort(indexes);
System.out.println(indexes[0]);

Answer 1

Некоторые советы по улучшению производительности (и правильности):

• При поиске majorUpset вы выполняете сортировку и двоичный поиск, в результате чего O (n log (n))время выполнения с последующим линейным поиском (цикл for).Этот линейный поиск - это все, что вам нужно, чтобы найти, где и где находится majorUpset.

• Поскольку tempArray относится к исходному массиву, вы портите свои индексы, когда сортируете его.Если вам нужно было отсортировать, сортируйте копию.Но, как отмечено выше, вам не нужно сортировать.

• Вы получаете доступ к значению nearCaptures.get(i) несколько раз в цикле, где было бы лучше сохранить его в локальной переменной, прямо в начале i -циклов.

Добавление:

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

int p = nearCaptures.get(0).length;  // p is the common array length
// search for majorUpset
for(int j = 0; j < p; j++){
  for (double[] arr : nearCaptures) {
    if (arr[j]==majorUpset) return j; // first majorUpset
  }
}
// search for threshold
for(int j = 1; j < p; j++){
  for (double[] arr : nearCaptures) {
    if (arr[j]>arr[j-1]+threshold) return j-1; // first threshold
  }
}