Best performance to search a number in a column of a 2d array without cloning the array

Question

I am trying to search for a number in a particular column of a two dimensional array. I tried a few different approach and would like to use stream in Java 8. However, it doesn't seem to be the best performance. Wonder if someone can help?

boolean isInColumn(int col, int number) {
    return IntStream.range(0, board.length)
        .map(i -> board[i][col])
        .filter(num -> num == number )
        .findFirst()
        .isPresent();
}

trying to search in a block as well. Any hints?

public boolean isInBlock(int row, int col, int number) {
    int r = row - row % 3;
    int c = col - col % 3;

    for (int i = r; i < r + 3; i++) {
        for (int j = c; j < c + 3; j++) {
            if (board[i][j] == number)
                return true;
        }
    }
    return false;
}

the input data is the following array.

public static int[][] PUZZLE = {
    {9,0,0,1,0,0,0,0,5},
    {0,0,5,0,9,0,2,0,1},
    {8,0,0,0,4,0,0,0,0},
    {0,0,0,0,8,0,0,0,0},
    {0,0,0,7,0,0,0,0,0},
    {0,0,0,0,2,6,0,0,9},
    {2,0,0,3,0,0,0,0,6},
    {0,0,0,2,0,0,9,0,0},
    {0,0,1,9,0,4,5,7,0},
};

What seems to be your performance issue? I checked the stream version compared to a naive way and the difference is only milliseconds which most likely due to measuring it the wrong way. However, the naive way was always faster though. `static boolean isInColumn2(int col, int number) { for (int[] ints : PUZZLE) { if (ints[col] == number) return true; } return false; } ` — SzaPe, Mar 01 '21 at 07:42
@SzaPe What if the amount of data will be much larger, and you will need to process it in real-time? Even a difference of milliseconds can be crucial (of course if they are not the result of an error in the measurement of time). — jubnzv, Mar 01 '21 at 07:45
In case the data could be much larger, you should have mentioned that in the first place. I tested it with a 30000x30000 array, running both methods 1000 times. The naive way comes out around 3-4 times faster — SzaPe, Mar 01 '21 at 08:03
If you are doing really large arrays, then maybe using `parallelStream()` could be interesting. But rest assured: for anything below the "many thousands rows/columns" order of magnitude, the plain old school naive code will beat stream-ish solutions. You have to understand that "streams" means establishing a complex hierarchy of objects. They give you easy to read and maintain code, that *can* give you good performance if you know what you are doing. But they aren't a silver bullet *designed* for mac performance! — GhostCat, Mar 01 '21 at 15:24

Turo · Answer 1 · 2021-03-01T20:16:01.660

1

This 'stream'-version seems a little bit optimzed, but I think searching for a hit in an array will always be faster the old fashioned way, see Java performance tutorial – How fast are the Java 8 streams?

boolean isInColumn(int col, int number) {
    return IntStream.range(0, board.length)
        .anyMatch(i -> (board[i][col] == number) );
}

I made a short attempt with a parallel stream, but the overhead made it far worse. I think it would be different if the action wasn't a simple compare...

If it's only about speed for a Sudoku-solver/generator maybe you shouldn't loop at all but write the 9 conditions in one return statement

return board[0,col] == number || board[1,col] == number ...

edited Mar 01 '21 at 20:16

answered Mar 01 '21 at 10:45

Turo

4,724
2
14
27

Well, unless you can get to parallel streams, then you might get to faster results on really large data and systems with many CPUs at hand. But only then – GhostCat Mar 01 '21 at 15:25
@GhostCat : I agree, I used always carelessly, but the comment about big data wasn't from the author himself, the question is about a 9x9 array. – Turo Mar 01 '21 at 16:34
Sure, but asks about performance at the same time. I wouldnt be surprised if the 9x9 naive solution is orders of magnitudes faster than a stream solution here. – GhostCat Mar 01 '21 at 17:29
@GhostCat : Right again, but assuming it's abaot a Sudoku-solver(or generator, I think RoToRA is right) there will be lots of calls of isInColumn and isInBlock. – Turo Mar 01 '21 at 19:18
Which makes things ... worse? – GhostCat Mar 01 '21 at 20:02
Kindof, so I added "don't loop at all for Sudoku" to my answer – Turo Mar 01 '21 at 20:29

score 0 · Answer 2 · answered Mar 01 '21 at 11:39

Since this seems to be Sudoku what you could do is store the data redundantly. Don't only store the numbers in "normally" in a two dimensional array, but also have two-dimensional boolean arrays, where you store whether the row/column/block contains the number.

class Sudoku {

  private final int[][] puzzle = new int[9][9];
  
  private final boolean[][] rows = new boolean[9][9];
  private final boolean[][] columns = new boolean[9][9];
  private final boolean[][] blocks = new boolean[9][9];

  public void setCell(int row, in column, int number) {
    puzzle[row][column] = number;
    
    rows[row][number - 1] = true;
    columns[column][number - 1] = true;
    blocks[calcBlockId(row, column)][number - 1] = true;
 }

  // returns a number (0 - 8) identifying a block 
  // 0 - 2 is first line, 3 - 5 second line, etc.
  private int calcBlockId(int row, int column) {
    // Left as an exercise to the reader
  }
 
  public boolean isInColumn(int col, int number) {
     return columns[col][number - 1];
  }
 
  public boolean isInBlock(int row, int column, int number) {
    return blocks[calcBlockId(row, column)][number - 1];
  }
}

score 0 · Answer 3 · 2021-03-01T16:22:15.977

This code searches for an element in a 2d array and returns the coordinates of the first match, if such an element is present, or null otherwise:

public static int[] findElement(int[][] arr, int element) {
    return IntStream
            // iterate through the indexes
            // of the rows of the array
            .range(0, arr.length)
            // for each row
            .mapToObj(i -> {
                // look for the element in this row
                int j = IntStream
                        // iterate through the indexes
                        // of the elements of the row
                        .range(0, arr[i].length)
                        // filter a matching element
                        .filter(el -> arr[i][el] == element)
                        // take first match
                        .findFirst().orElse(-1);
                // if element is present
                if (j >= 0)
                    // return its coordinates
                    return new int[]{i, j};
                else
                    // or null otherwise
                    return null;
            })
            // take first non-null coordinates, if they are present
            .filter(Objects::nonNull).findFirst()
            // or null otherwise
            .orElse(null);
}

// test
public static void main(String[] args) {
    int[][] puzzle = {
            {9, 0, 0, 1, 0, 0, 0, 0, 5},
            {0, 0, 5, 0, 9, 0, 2, 0, 1},
            {8, 0, 0, 0, 4, 0, 0, 0, 0},
            {0, 0, 0, 0, 8, 0, 0, 0, 0},
            {0, 0, 0, 7, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 2, 6, 0, 0, 9},
            {2, 0, 0, 3, 0, 0, 0, 0, 6},
            {0, 0, 0, 2, 0, 0, 9, 0, 0},
            {0, 0, 1, 9, 0, 4, 5, 7, 0}};

    int[] coordinates = findElement(puzzle, 7);

    System.out.println(Arrays.toString(coordinates)); // [4, 3]
}

^{See also:

• Difference between anyMatch and findAny in java 8

• First unique character in a string using LinkedHashMap}

Best performance to search a number in a column of a 2d array without cloning the array

3 Answers3