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

Question

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

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

Now I want to compare one and two arrays in such a way that 1) I can get the number of numbers of elements that are the same and are in the same position. 2) I can get the number of numbers that are the same, but not in the same position.

The approach I took

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

For (2) Iterating over arrays and for i != j see if these elements are the same if they 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? Especially by calculating the (2) th part of the problem. This is a basic comparison method for calculating black and white bindings for a Mastermind board game. thanks shakti

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

2) Dave Challis solution is used. Performance change for calculations 7776 X 7776

 OLD 46950 ms NEW 42887 ms 

Answer 1

Although this is probably not exactly what you are looking for, we could significantly reduce the number of operations with a very simple change.

WITH

 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 sort / search logic itself. All we do is delete automatic boxing and automatic unpacking operations. If, however, you do this on a very large scale, it can make a big difference.

Answer 2

To get the number of numbers that are the same but in 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 O (n log N) operation.

---

You can move one[i] != -1 so that it can skip this 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; } } } 

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

Answer 3

The following is O (2N) solution, does not use any additional libraries and does not modify the original arrays.

It iterates over both arrays once to get the number of integers at the same position. While he does this, he accumulates the amount of each number in the second array (and is stored in the counts array).

Then it breaks 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); 

Print

 1 2 

Answer 4

Why not use existing utility methods to compare aaarays. They are definitely faster. You can check the execution of the "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"); } 

}