3

I'm practicing problems and found this weird one. I can't figure out the best way to solve it.

You are given a 2D matrix size n*n with only 1's and 0's, you have to find the longest sequence of 1's either column-wise or row-wise.

I'm pretty stuck on this problem. I was trying to use a divide and conquer technique to split up the array into 4 n/2 * n/2 arrays, but the step where I merge together is still so slow because I have to check every adjacent row/column. Any advice on a fast solution would be great. I've spent way too much time staring at this.

  • You can find the maximum element in a sequence in O(n). No need for divide and conquer, just a simple linear search will be the fastest. – Lie Ryan Sep 11 '19 at 2:51
1

Let us set N=n*n. The worst case complexity of any algorithm for solving the problem is O(N), since for a "checker-board" like matrix with alternating ones and zeroes, or even for a matrix filled only with zeroes it should be clear that any cell has to be inspected at least once, otherwise the question for the length of the longest sequence cannot be answered.

Finding the longest sequence of "ones" in one row is a simple linear scan which requires O(n) iterations. Doing this for n rows results in O(N) operations in total for finding the sequence length for each of the n rows. Determining their maximum requires O(n) operations, so in total still O(N). And doing this 2 times (once for all rows, once for all columns) will still need 2*O(N) = O(N) operations.

Thus, there is no algorithm which can have a smaller complexity than the straightforward and simple iteration over all columns and rows described above.

Of course, you can try to optimize some real algorithm (maybe by some parallelism as suggested by @ErikEidt), but no "divide-and-conquer" strategy will bring the total complexity down any further.

| improve this answer | |
  • In your first paragraph, don't you mean the best case complexity? – Jacob Raihle Sep 11 '19 at 13:10
  • @JacobRaihle: why? The examples I mentioned are worst cases for any algorithm, other cases (like a matrix where the first row is filled with ones) can be solved with just n iterations. – Doc Brown Sep 11 '19 at 14:12
  • Ah. I misread you as saying "the worst possible algorithm you could build is O(N)", but you meant "the best possible algorithm still needs O(N) for the worst possible input". – Jacob Raihle Sep 11 '19 at 14:18
1

Algorithmically, you don't always have to examine all the elements. I'll explain how, but I'm not sure if it becomes sublinear time (growing slower than proportional to the number of array elements). In practical terms of elapsed run time, I'll focus on the dominant factor.

Starting with a straightforward program, you can use that to test that improved candidates still get the right result. In a non-learning situation, you could also decide if the initial program is fast enough for your purposes.

A straightforward program would scan each column once and each row once, count the longest sequence of 1's in each, and keep the highest count over all those.

Now to optimize, the question is what are we optimizing? Classic big-O algorithmic complexity would mainly count the number of probes into the array. Then given the longest run yet found of l elements, if l equals n, you're done; no need to examine the remaining rows and columns. Else when starting on the next span, jump forward l+1 elements. If that's a 0 or beyond the end of that row or column, then you don't need to probe any of the intermediate elements. Else if probing halfway to the previous probe finds 0, you don't need to probe the elements before that 0, etc. [So statistically, you can skip many array elements.]

But if you want to optimize elapsed time on modern hardware, the number of probes isn't what counts. I'll assume you're programming in a language that compiles (or JIT compiles) to native code so we're not dealing with interpreter overhead. (If you're writing this in Python, aim to do as much as possible in each call to Numpy.)

On modern hardware, the run time will be dominated by loading the data from RAM into the CPU cache. You can run many instructions in that amount of time. Those are the "probes" that matter, not testing the array elements. In that case what you want to optimize first is the data format so it's bit-packed into 8 elements per byte.

If the entire array is too large to fit into the CPU cache, then the next optimization step is to load it into the CPU only once or twice. For row-oriented data, scanning over the rows will be fine but scanning over the columns ought to reuse the data loaded per row, keeping partial results per column, or else make a second pass over columns but process a stripe that's 1 cache-line wide at a time (8 x 64 bit-packed columns? whatever the cache-line size is on your CPU) so it can load each cache line only once.

This assumes you don't have to consider the time it takes to get the array into physical RAM (not virtual memory) and it all fits into RAM at once. If those assumptions don't hold, then what dominates is getting the data into RAM as fast as possible and only once, similar to the cache loading discussion. Either way, it's using the lesson of a B-tree.

Now you can consider parallelization across CPU cores. Do the cores share cache memory? Getting the cores usefully working in parallel can be subtle. Each core can work on a separate array row but reusing the loaded data for column stripes gets tricky.

It might also be interesting to use GPU vectorization.

The l+1 skip probe can still help if applied at the level of cache-line loading or RAM loading, but it gets complicated esp. with the need to scan in 2 dimensions. Still, finding a run of length l means you needn't examine any more data.

| improve this answer | |
0

Ok, I'm looking forward to seeing some magic solution, but until then:

The only advantage I can see in splitting things up is in being able to applying parallelism.  If you're not using CPUs in parallel there doesn't seem to be any point in divide and conquer: any subdivision smaller than a row or smaller than a column requires reassembling solutions that cross artificial boundaries: seems to me, might as well just solve one whole row at a time and then one whole column at a time and take the best answer.

(To solve a row or a column just scan resetting the counter each time a zero is seen; increment the counter for each zero seen; capture the location (and maybe value and direction horizontal or vertical) of the highest counter value seen).

If you are applying parallelism, then split up rows into CPUCount groups and farm each group out to a different CPU, and split up columns into CPUCount groups and do similar, taking the best of the best.  As row and column answers are independent of each other, they are just separate problems to solve.

| improve this answer | |
0

Here's one approach that doesn't improve on the time complexity given by other answers O(n) but might have some performance benefits. The basic idea is to load the matrix rows (or columns) into a series of bytes. For example, if n is 24, you need three bytes. You can then use a lookup table to determine the sequences and continuations available in that 8 cell chunk. Here's what you would need in the table:

FF: (8,S,E)
FE: (7,S)
FD: (6,S);(1,E)
FC: (6,S)
...
A1: (1,S);(1);(1,E)
3F: (6,E)
...
0F: (4,E)
...

The first row is for the byte 0xFF or in binary: 11111111. The entry tells us there is one sequence of length 8 and that it is adjacent to the start and end of the 8 cell chunk. 0xFD: 11111101 has 2 sequences a 6 cell one at the start and a single cell one at the end. A1 has 3 sequences that are all one cell long, on at the start, one in the middle, and one at the end. NOTE: there's no reason to store more than the longest middle sequence for a byte.

Once you have the full table, you can hardcode it into your program. You could, for example build a switch statement that returns all 3 elements (start, longest internal, end), for example.

Then for the tricky part: you iterate over the 8-cell bytes for the row. You need to keep track of any continuations between chunks. For example, if the first cell is 0xFD, so far the longest complete sequence is 6 long. But you can't ignore the 1 cell at the end, you don't know how long that sequence is until you read the next chunk.

I'm not going to claim this is any faster than straight forward counting algorithm but I think it's worth mentioning from a conceptual level for alternate ways to solve problems like this.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.