CODEWITHSUNDEEP
javaarraysperformance
Shakti
Shakti

Reputation: 2033

Is there a faster way to compare two Int arrays in Java?

I have two integer array each of same size say n ( n is variable, so I can have two arrays of size say 4 or 5 or 6 etc ) and the range of values that each digit can take is in the range of 0-9. Example 

Integer[] one = {1,9,3,4} 
Integer[] two = {1,1,9,3}

Now, I want to compare array one & two such that 1) I can get the count of numbers of elements which are same and at the same position. 2) I can get the count of number which are same but not at the same position .

The approach I have taken is

For (1) Iterate through array one and for each index i check one[i] == two[i]. - simple .

For (2) Iterate over both the arrays and for i != j see if the elements are same , if same mark them with -1 to avoid future conflicts.

for(int i =0;i<one.length;i++){
    for(int j=0;j<two.length;j++){
        if(i != j && one[i] != -1 && two[j] !=-1)){
            if(one[i] == two[j]){
                whiteCount++
                one[i] = -1;
                two[j] = -1;
            }
        }
    }
}

Question : Now I want to know if there is a faster way to do the same thing ? Esp. calculating the (2)nd part of the problem. This is a basic comparison method to get black and white pegs calculation for Mastermind board game . Thanks Shakti

UPDATE 1: 1) Rudi's suggestion changed Integer[] to int[]

2) Used Dave Challis's solution Change in performance for 7776 X 7776 calculations 

OLD 46950 ms
NEW 42887 ms

Upvotes: 7

Views: 6072

Answers (4)

Peter Lawrey
Peter Lawrey

Reputation: 533510

To get the count of the number of number which are the same, but at different positions, you can do this.

public static long[] encode(int... nums) {
    long[] ret = new long[nums.length];
    for (int i = 0; i < nums.length; i++) {
        ret[i] = ((long) nums << 32) + i;
    }
    Arrays.sort(ret);
}

// encode both arrays and do a merge sort, skipping matches which have the same index.

This is an O(n log N) operation.

You could move the one[i] != -1 check out so it can skip that value.

int[] one = {1,9,3,4}; // Using int is faster and clearer.
int[] two = {1,1,9,3};

for (int i = 0; i < one.length; i++){
    if (one[i] == -1) continue;
    for (int j = 0; j < two.length; j++){
        if (one[i] == two[j] && i != j && two[j] != -1) {
            whiteCount++
            one[i] = -1;
            two[j] = -1;
        }
    }
}

Putting the one[i] == two[j] first improves performance because it will usually be false so the other things don't need to be checked.

Upvotes: 3

Dave Challis
Dave Challis

Reputation: 3906

The solution below is O(2N), doesn't use any additional libraries, and doesn't modify the initial arrays.

It loops through both arrays once to get a count of integers at the same position. While it does this, it builds up a count of each number in the 2nd array (and stores in the counts array).

It then loops through the first array again, getting the total number of times each number was found in the 2nd array:

final Integer[] one = {1,9,3,4};
final Integer[] two = {1,1,9,3};

int samePositionCount = 0;
int sameNumberCount = 0;

// tracks number of times an int is in the 2nd array
final Integer[] counts = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

for (int i = 0; i < one.length; i++) {
    if (one[i].equals(two[i])) {
        samePositionCount++;
        counts[one[i]] = -1; // mark as seen in same position count
    } else if (counts[two[i]] != -1) {
        counts[two[i]]++;
    }
}

for (int i : one) {
    if (counts[i] > 0) {
        sameNumberCount += counts[i];
        counts[i] = 0; // avoid adding twice
    }
}

System.out.println(samePositionCount + " " + sameNumberCount);

Prints:

1 2

Upvotes: 3

Rudi Kershaw
Rudi Kershaw

Reputation: 12972

Although this probably isn't exactly what your looking for, we could reduce the number of operations significantly with a very simple change.

From

Integer[] one = {1,9,3,4} 
Integer[] two = {1,1,9,3}

to

int[] one = {1,9,3,4} 
int[] two = {1,1,9,3}

This will speed up the process by a small amount, but not by optimizing the sorting/searching logic itself. All we're doing there is removing the auto-boxing and auto-unboxing operations. If however your doing this on a very large scale then this can make a substantial difference.

Upvotes: 5

Ranjeet
Ranjeet

Reputation: 403

Why not use the existing utility methods for comparing the aaarays. They are definitely faster. You can check the implemetation of "equals" method and confirm.

import java.util.Arrays;

class Test {
public static void main(String[] args) {
    int inarr1[] = {1, 2, 3};
    int inarr2[] = {1, 2, 3};
    Object[] arr1 = {inarr1};
    Object[] arr2 = {inarr2};
    if (Arrays.deepEquals(arr1, arr2))
        System.out.println("Same");
    else
        System.out.println("Not same");
   }

}

Upvotes: 0

Related Questions