Эффективное сравнение вектора с серией чисел в Java

Question

У меня есть ряд чисел, то есть 6, 5, 7, 8, 9, 1, которые через некоторый математический процесс я в конечном итоге получу путем повторения. По этой причине я хочу использовать вектор для хранения последних шести чисел, полученных в результате этого процесса, а затем сравнить содержимое этого вектора с серией чисел выше. Если оно совпадает с последовательностью чисел, я завершу программу или, если не продолжу математическую процедуру.

У меня вопрос: как мне эффективно сравнить ряды чисел и вектор? Первоначально я собирался использовать простое условное условие if / else для сравнения каждого отдельного значения в векторе с его корреспондентом в ряду (например, где v - это вектор, заполненный шестью числами, если (v.get (0) == 6 &&) v.get (1) == 5 ...)), но, учитывая, что это будет оцениваться несколько раз, прежде чем вектор станет равным серии, я начинаю задумываться, будет ли это относительно дорогостоящим вычислением по сравнению с некоторыми альтернативная процедура.

Моя другая идея сделать это - сохранить последовательность чисел во втором векторе, а затем сравнить два вектора. Однако, будучи неопытным с векторами и Java в целом, я не уверен, как мне поступить, и как это может быть более эффективным, чем простое предложение if и else, упомянутое выше.

Какой-нибудь совет относительно того, как сравнения между группой чисел и содержимым вектора могут быть сделаны более эффективно? Или если не вектор, то, может быть, список или массив?

Answer 1

Сделайте хеш-значение из вашей последовательности чисел, например (предупреждение - эта хеш-функция предназначена только для демонстрационных целей):

[N1, N2, N3, N4, N5] -> N1 xor N2 xor N3 xor N4 xor N5.

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

Answer 2

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

Пример:

void repeatedCompute() {
    List<Integer> triggerList = new ArrayList<Integer>() {{
        add(6);
        add(5);
        add(7);
        add(8);
        add(9);
        add(1);
    }};

    List<Integer> intList = new LinkedList<Integer>();
    boolean found = false;
    while (!found) {
        int nextResult = compute();

        intList.add(0, nextResult);
        if (intList.size() > triggerList.size()) {
            intList.remove(intList.size() - 1);
        }
        if (intList.equals(triggerList)) {
            found = true;
        }
    }
}

int compute() {
    return new Random().nextInt(10);
}

Сравнение списков имеет то преимущество, что сравнение прекращается после несовпадения первого элемента, вам не нужно трогать все элементы. Сравнение списков довольно быстро!

Answer 3

Обратите внимание, что оператор && замыкает накоротко, то есть правый операнд вычисляется только в том случае, если левый операнд не определяет результат сам по себе. Следовательно, сравнение будет рассматривать только те элементы, которые необходимы.

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

Answer 4

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

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

Что бы вы ни делали, пожалуйста Измерьте!

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

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

Answer 5

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