Efficiently comparing a vector to a series of numbers in Java

Question

I have a series of numbers, i.e. 6, 5, 7, 8, 9, 1, which through some mathematical process I will eventually obtain through repetition. For this reason, I want to use a vector to store the last six numbers yielded by this process and then compare the contents of that vector to the series of numbers above. If it identically matches the series of numbers, I will end the program, or if not continue the mathematical procedure.

My question is I how I might go about comparing the series of numbers and the vector efficiently. Originally I was going to use a simple if/else conditional to compare each individual value in the vector with its correspondent in the series(e.g. where v is a Vector filled with six numbers, if (v.get(0) == 6 && v.get(1) == 5 ...)), but considering that this will be evaluated a number of times before the vector equals the series, I'm beginning to wonder if that would be a relatively costly calculation compared to some alternate procedure.

My other idea to do this is to store the series of numbers in a second vector and then compare the two vectors. However, being inexperienced with vectors and Java in general, I'm not sure as to how I might go about doing this and how it might be more efficient than the simple if and else clause mentioned above.

Any advice as to how comparisons between a bunch of numbers and a vector's contents might be done more efficiently? Or if not a vector, than perhaps a list or array instead?

Answer 1

Make a hash value out of your sequence of numbers, example (warning - this hash function is only for demonstration purposes):

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

Then first you only need to check the hash values of your result vector and the original vector, and only if they match need you to compare each individual number.

Answer 2

I would guess that it wouldn't be too expensive to just keep one vector around with your target numbers in, then populate a new one with your newly generated numbers, then iterate through them comparing. It may be that you're likely to have a failed comparison on the first number, so it only costs you one compare to detect failure.

It seems that you're going to have to collect your six numbers which ever method you use, so just comparing integers won't be too expensive.

Whatever you do, please measure!

You should generate at least two algorithms for your comparison task and compare their performance. Pick the fastest.

However, maybe the first step is to compare the run time of your mathematical process to the comparison task. If your mathematical process runtime is 100 times or more than the comparison, you just have to pick something simple and don't worry.

Answer 3

If you only need to verify that against one set of numbers, then comparing the numbers directly is more efficient. Computing the hash requires you to perform some arithmetic and that is more expensive than comparison. If you need to verify that against multiple sets of numbers than the hash solution would be more efficient.

Answer 4

You should avoid Vector here, because it's implemented to be thread safe and has some overhead for this. Use LinkedList instead for maximum performance of insert and remove operations and ArrayList for maximum performance of random access.

Example:

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);
}

Comparing the lists has the advantage that comparison is stopped after the first element mismatch, you don't have to touch all elements. Comparing lists is quite fast!

Answer 5

Note that the && operator short-circuits, i.e. the right operand is only evaluated if the left operand does not determine the result by itself. Hence the comparison will only look at those elements necessary.

I do not think, however, that this will in any case overshadow the time spent on the mathematical calculations used to generate the numbers you compare. Use jvisualvm to investigate where the time is spent.