The primary question was about performance. But let me point out a few things that may be considered as "subjective", but that I consider as rather important:
Commenting
Comments are important. And I understand that you inserted comments to make things easier (maybe for you as well as for the reviewers). And I think that // Inline comments can really help you to identify relevant parts of the code when quickly skimming over it. These may be short, like
// Check row to the right
...
// Check column to the bottom
...
// Check diagonal to the bottom right
...
// Check diagonal to the bottom left
These really can help to quickly find the relevant loop (as the loops look very similar otherwise).
(Note, however, that some people consider such comments as a "code smell". They argue that, when you think that you have to write a comment, then you should try to make the code clearer. In this particular case, they might recommend introducing additional methods like checkRow, checkColumn, checkDiagonal etc. But I think that inline comments have their justification, as stated above.)
Nevertheless: You can go too far. In practice, comments like these are basically just noise:
// This is the current element in our matrix
int element = matrix[row][col];
They don't really convey information or make clearer what is happening there.
Additionally, I strongly suggest to avoid /* block comments */ in methods. These should be reserved for either implementation notes (outside of methods), or for JavaDoc method- and class comments. (This may be a bit subjective, though)
Formatting
No, this is not about the question of whether the { should be in the same line or in the next line ;-) This is about consistency: In most cases, you wrote
if(...)
return true;
but in one case, you wrote
if(...)
{
return true;
}
In most coding guidelines that I have read so far, the recommendation was to always use the { brackets } even for single-line blocks.
Similarly, you sometimes wrote matrix.length-4 and sometimes matrix.length - 4. Yes, I think that the spaces matter.
Your mileage may vary.
Testability
Although the task was to allow the user to enter the matrix, I cannot imagine how you tested this more than once or twice. Didn't it become boring to enter the same values again and again? The first thing that I did was replacing the contents of your main method with this:
int matrix[][] = new int[][] {
{ 0, 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9,10,11 },
{12,13,14,15,16,17 },
{18,19,20,21,22,23 },
{24,25,26,27,28,29 },
};
// Find identical fours and print true if found, false otherwise
System.out.println( checkForIdenticalFour(matrix) );
This allows you to quickly test different border cases. And this helped me to verify...
a bug!
As pointed out in the comments: The condition in the last if-statement is wrong. It should not be col >= matrix[row].length-4, but col >= 3. Otherwise, it crashes with the following matrix
int matrix[][] = new int[][] {
{ 0, 1, 2, 3, 4, 5 },
{ 6, 7, 1, 9,10,11 },
{12, 1,14,15,16,17 },
{ 1,19,20,21,22,23 },
{24,25,26,27,28,29 },
};
causing an ArrayIndexOutOfBoundsException.
Coming to the core: Performance
This, in fact, is difficult. It's nearly impossible to say how the performance could be improved here. One could argue about the last three if-blocks in the loop...
if( row <= matrix.length - 4 && element == ... ) { ... }
if( row <= matrix.length - 4 && col <= matrix[row].length-4 ) { ...}
if( row <= matrix.length - 4 && col >= 3 ) { ... }
that could obviously be condensed into one. But it's nearly impossible that this will have a measurable performance impact, even if this is executed millions of times.
Similarly, one could argue that the expression matrix[row] is repeated several times, and could be pulled out into a int currentRow[] = matrix[row]; to avoid repeated dereferencing.
But it might be that the JIT does this sort of optimization internally.
So first, a disclaimer:
Without profiling and looking at the resulting assembly, this sort of optimization is just guesswork.
But if I had to make sure that the performance is as high as possible for this particular code snippet, then I would try something that you already mentioned in the question:
On paper, we could toss out the bottom right 3x3 block because there's nothing there for us to check
This can be done. One could write the checks as follows:
private static boolean checkRows(int[][] matrix)
{
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row][col + 1] &&
element == matrix[row][col + 2] &&
element == matrix[row][col + 3])
{
return true;
}
}
}
return false;
}
private static boolean checkColumns(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col] &&
element == matrix[row + 2][col] &&
element == matrix[row + 3][col])
{
return true;
}
}
}
return false;
}
private static boolean checkMainDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col + 1] &&
element == matrix[row + 2][col + 2] &&
element == matrix[row + 3][col + 3])
{
return true;
}
}
}
return false;
}
private static boolean checkCounterDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 3; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col - 1] &&
element == matrix[row + 2][col - 2] &&
element == matrix[row + 3][col - 3])
{
return true;
}
}
}
return false;
}
public static boolean checkForIdenticalFour(int[][] matrix)
{
return checkRows(matrix) ||
checkColumns(matrix) ||
checkMainDiagonal(matrix) ||
checkCounterDiagonal(matrix);
}
(In fact, the four methods could be combined into one again, that receives additional parameters for the loop limits and the row- and column step size - but this would undermine the point here)
The reasoning of why this might have a better performance is
- The methods are shorter. When you look at the Java HotSpot VM options, you will see the option
-XX:MaxInlineSize=35 which indicates the maximum bytecode size of a method to be inlined, so shorter methods can be advantageous
- The loops are tailor-made for the checks that have to be done. Note that the
if queries that you used to detect whether a certain check can be done are no longer necessary. The loops are fitting exactly to what has to be tested.
- The pattern is more regular. This does not only look nice ;-) it is also not unlikely that this is beneficial in terms of caching. But this is tremendously hard to verify profoundly.
So again, the disclaimer:
Without profiling and looking at the resulting assembly, this sort of optimization is just guesswork.
In order to obtain reliable results, you should use a profiler like JMH.
But also keep in mind: The actual performance may depend on factors that are beyond the implementation. Imagine that you had to check a few million matrices. And imagine that all these matrices contained
- 4 equal values in the last checked diagonal OR
- 4 equal values in the first checked row
The performance would vary wildly depending on where the equal values are found, and you could seemingly(!) affect the performance just by changing the order of your loops, to cause the method to return true earlier for one of both cases.
Update
I was curious about the performance, and went an extra mile here.
I created a "microbenchmark". As usual, such microbenchmarks should be taken with a grain of salt. But I took into account several basics for this: The different implementations are run alternatingly, in several passes, with different inputs, several times, to give the JIT a chance to kick in. The results of the computations are used and printed, to avoid dead code elimination.
The tl;dr is: Your original approach already was pretty fast. The Improvements that can be achieved with my initial suggestsion are hardly measurable, and in the range of a few percent.
About the microbenchmark
As stated above, the "performance" of one approach may heavily depend on the combination of
- where the four equal values are contained in the matrix
- in which order the possible appearances of the four values are checked
To compensate for that, I created a method that generates all possible matrices with all possible appearances of four equal elements. The printMatrices flag may be enabled to print these matrices:
26 1 2 3 4
26 6 7 8 9
26 11 12 13 14
26 16 17 18 19
20 21 22 23 24
0 26 2 3 4
5 26 7 8 9
10 26 12 13 14
15 26 17 18 19
20 21 22 23 24
...
0 1 2 3 4
5 6 7 8 26
10 11 12 26 14
15 16 26 18 19
20 26 22 23 24
You can see that the equal values appear
- As a column, in row 0, column 0
- As a column, in row 0, column 1
- ...
- As a counter-diagonal in row 1, column 4
So these are simply all possible matrices, stored in a list.
The code of this micromenchmark and the tested approaches are at the bottom. The approaches are implemented in the classes FourIdenticalA (your approach), FourIdenticalB (my modified approach), and FourIdenticalC a new approach:
The new approach
First of all: The new approach is slower than the others, but included here nevertheless.
When looking at your initial approach, one can see that it seems to be redundant and repetitive. For example, when checking for 4 equal elements in a row, then you acually check the following matrix elements for equality:
column: 0 1 2 3 4 5 6 7
---------------
row 0 values: 8 2 5 5 5 5 9 1
checked values:
row 0, check for 4 elements starting at column 0: X X X X
row 0, check for 4 elements starting at column 1: X X X X
row 0, check for 4 elements starting at column 2: X X X X
(return "true", because "5 5 5 5" was found)
My idea was that this could be ""optimized"". I thought that it could be beneficial to simply check the whole row, and count how many equal elements are found
column: 0 1 2 3 4 5 6 7
---------------
row 0 values: 8 2 5 5 5 5 9 1
counter how many equal elements are found: 1 1 1 2 3 4
(return "true", because four equal elements are found)
But again, this turned out to be slower. It seems that the "loop unrolling" that you did by manually accessing the entries r[col], r[col+1], r[col+2], r[col+3] causes a higher performance in the end.
The whole code of the microbenchmark:
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
public class FourIdenticalPerformance
{
public static void main(String[] args)
{
int minRows = 5;
int maxRows = 15;
int minCols = 5;
int maxCols = 15;
int times = 4;
System.out.println("Generating...");
List<int[][]> matrices = generateMatrices(
minRows, maxRows, minCols, maxCols, times);
System.out.println("Generating DONE, " + matrices.size() + " matrices");
boolean printMatrices = false;
//printMatrices = true;
if (printMatrices)
{
for (int matrix[][] : matrices)
{
print(matrix);
}
}
int passes = 10;
int runs = 50;
for (int pass=0; pass < passes; pass++)
{
long before = 0;
long after = 0;
int countA = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalA.checkForIdenticalFour(matrix);
if (b)
{
countA++;
}
}
}
after = System.nanoTime();
System.out.printf(Locale.ENGLISH, "A duration %8.3fms count %d\n",
(after - before) / 1e6, countA);
int countB = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalB.checkForIdenticalFour(matrix);
if (b)
{
countB++;
}
}
}
after = System.nanoTime();
System.out.printf(Locale.ENGLISH, "B duration %8.3fms count %d\n",
(after - before) / 1e6, countB);
int countC = 0;
before = System.nanoTime();
for (int matrix[][] : matrices)
{
for (int run = 0; run < runs; run++)
{
boolean b = FourIdenticalC.checkForIdenticalFour(matrix);
if (b)
{
countC++;
}
}
}
after = System.nanoTime();
System.out.printf(Locale.ENGLISH, "C duration %8.3fms count %d\n",
(after - before) / 1e6, countC);
}
}
// Generate all matrices in the given size range that contain all
// possible configurations of 'times' equal values, horizontally,
// vertically and diagonally
private static List<int[][]> generateMatrices(
int minRows, int maxRows, int minCols, int maxCols, int times)
{
List<int[][]> matrices = new ArrayList<int[][]>();
int directions[][] = {
{ 1, 0 },
{ 0, 1 },
{ 1, 1 },
{ 1, -1 },
};
for (int rows = minRows; rows <= maxRows; rows++)
{
for (int cols = minCols; cols <= maxCols; cols++)
{
for (int dir = 0; dir < directions.length; dir++)
{
int value = rows * cols + 1;
int dr = directions[dir][0];
int dc = directions[dir][1];
int minRow = 0;
int maxRow = rows;
int minCol = 0;
int maxCol = cols;
if (dr < 0)
{
minRow = times - 1;
}
if (dr > 0)
{
maxRow = rows - times + 1;
}
if (dc < 0)
{
minCol = times - 1;
}
if (dc > 0)
{
maxCol = cols - times + 1;
}
for (int r = minRow; r < maxRow; r++)
{
for (int c = minCol; c < maxCol; c++)
{
int[][] matrix = createMatrix(rows, cols);
placeValue(matrix, r, c, dr, dc, times, value);
matrices.add(matrix);
}
}
}
}
}
return matrices;
}
private static void print(int matrix[][])
{
int rows = matrix.length;
int cols = matrix[0].length;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
System.out.printf("%5d", matrix[r][c]);
}
System.out.println();
}
System.out.println();
}
// Place the given value at the specified position, the given number
// of times, making a step of (dr,dc) each time
private static void placeValue(
int matrix[][], int row, int col, int dr, int dc, int times, int value)
{
int r = row;
int c = col;
for (int i = 0; i < times; i++)
{
matrix[r][c] = value;
r += dr;
c += dc;
}
}
// Create a matrix with the given size, with values 0...(r*c-1)
private static int[][] createMatrix(int rows, int cols)
{
int matrix[][] = new int[rows][cols];
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
int index = r * cols + c;
matrix[r][c] = index;
}
}
return matrix;
}
}
class FourIdenticalA
{
/*
* This method checks if there are four identical elements in a matrix
* either horizontally, vertically, or diagonally
*/
public static boolean checkForIdenticalFour(int[][] matrix)
{
/* We traverse each element in the matrix */
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
// This is the current element in our matrix
int element = matrix[row][col];
/*
* If there are 3 elements remaining to the right of the current
* element's position and the current element equals each of
* them, then return true
*/
if (col <= matrix[row].length - 4
&& element == matrix[row][col + 1]
&& element == matrix[row][col + 2]
&& element == matrix[row][col + 3])
return true;
/*
* If there are 3 elements remaining below the current element's
* position and the current element equals each of them, then
* return true
*/
if (row <= matrix.length - 4 && element == matrix[row + 1][col]
&& element == matrix[row + 2][col]
&& element == matrix[row + 3][col])
{
return true;
}
/*
* If we are in a position in the matrix such that there are
* diagonals remaining to the bottom right of the current
* element, then we check
*/
if (row <= matrix.length - 4 && col <= matrix[row].length - 4)
{
// If the current element equals each element diagonally to
// the bottom right
if (element == matrix[row + 1][col + 1]
&& element == matrix[row + 2][col + 2]
&& element == matrix[row + 3][col + 3])
return true;
}
/*
* If we are in a position in the matrix such that there are
* diagonals remaining to the bottom left of the current
* element, then we check
*/
if (row <= matrix.length - 4 && col >= 3)
{
// If the current element equals each element diagonally to
// the bottom left
if (element == matrix[row + 1][col - 1]
&& element == matrix[row + 2][col - 2]
&& element == matrix[row + 3][col - 3])
return true;
}
}
}
/*
* If all the previous return statements failed, then we found no such
* patterns of four identical elements in this matrix, so we return
* false
*/
return false;
}
}
class FourIdenticalB
{
private static boolean checkRows(int[][] matrix)
{
for (int row = 0; row < matrix.length; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row][col + 1] &&
element == matrix[row][col + 2] &&
element == matrix[row][col + 3])
{
return true;
}
}
}
return false;
}
private static boolean checkColumns(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col] &&
element == matrix[row + 2][col] &&
element == matrix[row + 3][col])
{
return true;
}
}
}
return false;
}
private static boolean checkMainDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 0; col < matrix[row].length - 3; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col + 1] &&
element == matrix[row + 2][col + 2] &&
element == matrix[row + 3][col + 3])
{
return true;
}
}
}
return false;
}
private static boolean checkCounterDiagonal(int[][] matrix)
{
for (int row = 0; row < matrix.length - 3; row++)
{
for (int col = 3; col < matrix[row].length; col++)
{
int element = matrix[row][col];
if (element == matrix[row + 1][col - 1] &&
element == matrix[row + 2][col - 2] &&
element == matrix[row + 3][col - 3])
{
return true;
}
}
}
return false;
}
public static boolean checkForIdenticalFour(int[][] matrix)
{
return checkRows(matrix) ||
checkColumns(matrix) ||
checkMainDiagonal(matrix) ||
checkCounterDiagonal(matrix);
}
}
class FourIdenticalC
{
public static boolean checkForIdenticalFour(int[][] matrix)
{
int rows = matrix.length;
int cols = matrix[0].length;
int times = 4;
// Check rows, starting at column 0 of each row
for (int r = 0; r < rows; r++)
{
if (check(matrix, r, 0, 0, 1, cols))
{
return true;
}
}
// Check columns, starting at row 0 of each column
for (int c = 0; c < cols; c++)
{
if (check(matrix, 0, c, 1, 0, rows))
{
return true;
}
}
// Check diagonals, starting at column 0 of each row
for (int r = 0; r < rows - times + 1; r++)
{
int steps = Math.min(cols, rows - r);
if (check(matrix, r, 0, 1, 1, steps))
{
return true;
}
}
// Check diagonals, starting at row 0 of each column
for (int c = 0; c < cols - times + 1; c++)
{
int steps = Math.min(rows, cols - c);
if (check(matrix, 0, c, 1, 1, steps))
{
return true;
}
}
// Check counter-diagonals, starting at last column of each row
for (int r = 0; r < rows - times + 1; r++)
{
int steps = Math.min(cols, rows - r);
if (check(matrix, r, cols - 1, 1, -1, steps))
{
return true;
}
}
// Check counter-diagonals, starting at row 0 of each column
for (int c = times - 1; c < cols; c++)
{
int steps = Math.min(rows, c + 1);
if (check(matrix, 0, c, 1, -1, steps))
{
return true;
}
}
return false;
}
private static boolean check(
int matrix[][], int row, int col, int dr, int dc, int steps)
{
int previous = matrix[row][col];
int r = row + dr;
int c = col + dc;
int counter = 1;
for (int i = 1; i < steps; i++)
{
int current = matrix[r][c];
if (current != previous)
{
previous = current;
counter = 1;
}
else
{
counter++;
if (counter == 4)
{
return true;
}
}
r += dr;
c += dc;
}
return false;
}
}
col >= matrix[row].length-4is incorrect. It should be something likecol >= 3. I.e.col - 3has to be at least zero. \$\endgroup\$ – mdfst13 Dec 21 '16 at 23:31