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

user_2869092 0
Viewed 159

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},
};
multidimensional-array matrix search arrays java
3 Answers

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 ...
user_60530840

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];
  }
}
user_3184930

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

Admin1
Related