0

I have a program where I need to remove a set of rows from a byte[][] array. I want to remove every row that has no zeroes in it. Right now I'm using the following methods:

public byte[][] checkRows(byte[][] grid) {
    LinkedList<Integer> temp = new LinkedList<Integer>();
    boolean willRemove = false;
    for (int y = 0; y < grid.length; y++) {
        boolean tempCheck = true;
        for (int x = 0; x < grid[0].length; x++) {
            if (grid[y][x] == 0) {
                tempCheck = false;
                break;
            }
        }
        if (tempCheck) {
            temp.add(y);
            willRemove = true;
        }
    }

    if (willRemove) {
        int[] rowArray = convert(temp);
        return removeRows(grid, rowArray);
    }
    return grid;

}

public byte[][] removeRows(byte[][] grid, int[] rows) {
    int total = rows.length;
    int current = 0;
    byte[][] retGrid = new byte[grid.length][grid[0].length];
    for (int i = total; i < grid.length; i++) {
        if (current < total && i-total+current == rows[current]) {
            current++;
        }
        //retGrid[i] = grid[i-total+current].clone();
        System.arraycopy(grid[i-total+current], 0, retGrid[i], 0, xsize);

    }
    return retGrid;
}

public int[] convert(LinkedList<Integer> intList) {
    int[] retArray = new int[intList.size()];
    for (int i = 0; i < retArray.length; i++) {
        retArray[i] = intList.get(i).intValue();
    }
    return retArray;
}

This gives me a reasonably fast way of removing rows from a 2D Array and replacing them with zero rows at the top of the array. Is there any faster way to achieve the same result?

If it's unclear what the script does, it's for removing full rows in a game of Tetris.

UPDATE: Using System.arraycopy() instead of clone() provides a 5% performance boost for small arrays.

maxb
  • 625
  • 6
  • 15

3 Answers3

3

Using a linked list would give O(1) removals, see this answer, since the list must be iterated over anyway.

At first I thought multidim arrays are compact in the sense that it is one contiguous block of memory, but it seems this is not the case. So you don't loose any caching benefits that might have been in effect.

Pity Java has not value types (currently), I'd use one instead of a byte to encode information. Well this is not strictly necessary...

And from a code review perspective, having a bool willRemove in method checkRows is unnecessary since in these cases, temp will have more than one element. I'd try to eliminate that ArrayList allocation altogether if it's not needed - defer it.

Community
  • 1
  • 1
Stefan Hanke
  • 3,458
  • 2
  • 30
  • 34
  • Are you saying that I should change the `byte[][]` array to a LinkedList, or do you mean the ArrayList? And over 90% of the times that I call check for rows to remove, no rows are to be removed, which is why I added the check. And since I do not have any info about which rows should be removed, I use a LinkedList (changed it now) to keep track of which rows to remove. – maxb Feb 09 '15 at 02:19
  • I'm talking about the `byte[][]`, except in the last paragraph, which is about the `temp` array. You'd have to profile that code to be sure there is a bottleneck to begin with. If you want the removals to be fast, go with `LinkedList`. But if you're writing a Tetris clone, the main operation is inserting the individual boxes of a complete figure. This does not iterate over all lines; most efficient would be a _true_ 2D array - which Java does not offer. You could do with a 1D array and add a bit of index operation on top of it. – Stefan Hanke Feb 09 '15 at 02:32
  • At this stage, implementing a `LinkedList` instead of the `byte[][]` would mean basically rewriting the entire program. And since I have methods that iterate both over the rows and over the columns, would it be more efficient, except for removal, since `LinkedList.get()` is `O(n)`? – maxb Feb 09 '15 at 02:46
  • Just go with the `byte[][]` there's nothing wrong with it. Iteration is `O(n)` in either case, the problem is random access, which is more often needed than removals. You could encapsulate the usages of the actual representation and wrap it in a separate class; this would give you the ability to change to a `LinkedList` without the rest of the program knowing, and you can profile it. – Stefan Hanke Feb 09 '15 at 03:05
  • @maxb If there were many tens of rows, then you could possible gain faster removal using a `LinkedList`. But it's damn slow for most operations, so you'd probably lose anyway. Using arrays and doing the removal in one sweep you can be (at least) as fast as `LinkedList`. Moreover, you'd better do no removal, just rearrangement (clean a full row and reuse it at the top; see my answer). – maaartinus Feb 09 '15 at 06:45
1

This small method executes the desired functionality of the question for the one dimensional case.

private static final void onClearFilledRows(final byte[] pTetris, final int pRowLength) {
        int i = 0, j = 0;
        /* Track the last valid position of row data. */
        int lLastValidIndex = 0;
        /* Iterate through each row. */
        for(i = 0; i < pTetris.length; i += pRowLength) {
            /* Iterate through each cell in the row. */
            boolean lContainsZero = false;
            for(j = i; j < (i + pRowLength) & !lContainsZero; j++) {
                lContainsZero |= pTetris[j] == 0;
            }
            /* This row is valid. Copy it to the last valid index. */
            if(lContainsZero) {
                System.arraycopy(pTetris, i, pTetris, (lLastValidIndex++ * pRowLength), pRowLength);
            }
        }
        /* Empty the remaining rows. */
        for(i = lLastValidIndex * pRowLength; i < pTetris.length; i++) {
            /* Set the element to zero. */
            pTetris[i] = 0;
        }
    }

This logic can then be reworked for the two dimensional case:

private static final void onClearFilledRows(final byte[][] pTetris) {
        int i = 0, j = 0;
        /* Track the last valid position of row data. */
        int lLastValidIndex = 0;
        /* Iterate through each row. */
        for(i = 0; i < pTetris.length; i ++) {
            /* Iterate through each cell in the row. */
            boolean lContainsZero = false;
            for(j = 0; j < pTetris[i].length & !lContainsZero; j++) {
                lContainsZero |= pTetris[i][j] == 0;
            }
            /* This row is valid. Copy it to the last valid index. */
            if(lContainsZero) {
                System.arraycopy(pTetris[i], 0, pTetris[lLastValidIndex++], 0, pTetris[i].length);
            }
        }
        /* Empty the remaining rows. */
        for(i = lLastValidIndex; i < pTetris.length; i++) {
            for(j = 0; j < pTetris[i].length; j++) {
                /* Set the element to zero. */
                pTetris[i][j] = 0;
            }
        }
    }
Mapsy
  • 4,192
  • 1
  • 37
  • 43
  • This seems to work well, except that the new zero rows are added to the end of the array, not the beginning. – maxb Feb 09 '15 at 12:46
  • 1
    I just benchmarked it, and it's about 5 times faster from my first tests. I edited the method to count backwards through the rows instead, and got the same performance with the correct result. – maxb Feb 09 '15 at 13:02
  • 1
    It seems as if your method is a lot faster when rows need to be removed, but when no rows are to be removed, it's a bit slower. Great method, but unfortunately i don't remove any rows in >90% of all cases. – maxb Feb 09 '15 at 13:37
  • Awesome! I'd considered this. You could add a parameter so that it only searches up until the row that contains any blocks; when the rest are zero, you could exit the loop, with no need to run the `/* Empty the remaining rows. */` section. – Mapsy Feb 09 '15 at 13:44
  • You'd also only need to iterate up to this row in the `/* Iterate through each row */` section, which is where the real overhead is. – Mapsy Feb 09 '15 at 13:50
1

IMHO it's too complicated. Drop the LinkedList as this is a terrible thing anyway. Don't bother with collecting the indexes for removal, instead copy every rows to be preserved to another array. Then use arraycopy to overwrite the original.

You're copying whole rows, but you don't have to. Just rearrange them, so the the preserved rows falls down and move the full ones to the top and clean them. There's no memory allocation needed.

As all copying operation work with one dimension only, there's not much to optimize since the most time-consuming operations are probably determining if there's any zero in a row and (now and then) cleaning some rows.

I wonder what machine does it run on as I guess it must be damn fast on even the slowest phones. Btw. CR would be better suited. Think about better names, e.g., tempCheck -> noZeroFound.

Community
  • 1
  • 1
maaartinus
  • 44,714
  • 32
  • 161
  • 320
  • Thank you for the answer! I'm creating a bot for playing tetris, and right now it can put down about 700 pieces per second. Considering that it tries every way of putting a new piece down before making a decision, the `checkRows()` is executed a lot of times for every block. At this stage I'm trying to remove all bottlenecks. And thank you for telling me about Code Review! – maxb Feb 09 '15 at 12:29
  • Your answer actually helped me to optimize quite a bit. Not by removing the LinkedList (yet), but I figured that I can put a bound on where the filled rows will be, and then I only have to check a few (<5) rows instead of all – maxb Feb 09 '15 at 13:27
  • @maxb I see, writing a bot explains the optimization need. As you don't care of how a slot gets filled, you could switch to using bits and pack a whole row into an `int` (or a `long` in case of up to 64 columns). This should make everything much faster. Rotating a piece gets tricky, but you can simply precompute it. See you on CR. – maaartinus Feb 10 '15 at 04:39
  • I was going to go to CR, but your suggestion just smashed my best solution to pieces, making the entire program 3.5 times faster. – maxb Feb 10 '15 at 14:53