make 2D array inequality check faster

Question

i working in school Al project it all work well but little slow.
in my project i have overridden equals method.

@Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        } else if (obj instanceof map) {
            map m = (map) obj;
            for (int i = 0; i < mapSize; i++) {
                for (int j = 0; j < mapSize; j++) {
                    if (m.board[i][j] != board[i][j])
                        return false;
                }
            }
        }
        return true;
    }

i figure out if i write for loops in a decussate way to check first half of array 80% of times get pass in first half and 20% remaining i will check afterward . so i assumed it will work 50 % faster

 for (int i = 0; i < mapSize; i++) {
                for (int j = i%2 ; j < mapSize; j+=2) {
                    if (m.board[i][j] != board[i][j])
                        return false;
                }
            }

for (int i = 0; i < mapSize; i++) {
                    for (int j = (i+1)%2 ; j < mapSize; j+=2) {
                        if (m.board[i][j] != board[i][j])
                            return false;
                    }
                }

after dividing the for loop and couple of test it seemed it getting slower i don't why only. why it take too mush time and how to make it faster
thanks in advance

Have you read https://stackoverflow.com/questions/504103 ? – Jorn Vernee Apr 12 '18 at 20:59 — Jorn Vernee, Apr 12 '18 at 20:59

score 0 · Answer 1 · answered Apr 12 '18 at 20:23

From a theoretical point of view, it is impossible to compare two 2-D arrays in time less than O(n*m), where n = # of rows, and m = # of columns.

However, it may be possible, in your case, to keep track of the 'boards' that you're using, and, assuming they start equal, it is only needed to keep track of the operations performed on each board, up until an operation changes one of the boards separately from one of the others.

score 0 · Answer 2 · answered Apr 12 '18 at 20:26

0

First of all, the default return of equals when the class does not match (last line in your first implementation) should be false, and class names in Java should be Capitalized Map.

Second, the most efficient way to compare array equality is probably Arrays.equals or Arrays.deepEquals, as they might be more optimized for the target machine.

Finally, are you sure you problem is equals being too slow? Have you used a profiler to find out where the most time is lost? Maybe you can find ways to call equals less often or track modifications to the data. Or you could use a hash to do a quick check for inequality.

answered Apr 12 '18 at 20:26

Cephalopod

14,632
7
51
70

thank for answer using Arrays.equals get my code to run about half second slower, and my equal method is called up many times i working un it make it less – nima moradi Apr 12 '18 at 20:35
If this is the correct answer, then please mark it as the answer. @nima_moradi – Andrew Lalis Apr 13 '18 at 12:44

make 2D array inequality check faster

2 Answers2