CODEWITHSUNDEEP
arraysalgorithm2dlogical-operators
chakshu
chakshu

Reputation: 33

Finding row with maximum no. of 1s if each row is sorted using logicalOR approach

Question similar to this may have been discussed before but I want to discuss a different approach to this. Given a boolen 2D array where each row is sorted, find the rows with maximum number of 1s.

Input Matrix :
0 1 1 1
0 0 1 1
1 1 1 1
0 0 0 0
Output : 2

How about doing this approach...Logical OR for column 0 of each row and if answer is 1, return that row index and stop. Like in this case if I do (0 | 0 | 1 | 0) answer would be one and thereby return that row index. if the input matrix is something like :

Input matrix:
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
Ouput : 0

When I do logicalOR of column 0 of each row, answer would be zero...so I would move to column 1 of each row, the procedure is followed till the LogicalOR is 1.?I know other approaches to solve this problem but I would like to have view on this approach.

Upvotes: 0

Views: 520

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58231

Your approach is likely to be orders of magnitude slower than the naive "go through the rows, and count the zeros, and remember the row with the fewest zeros." The reason is that, assuming your bits are stored one-row-at-a-time, with the bools packed tightly, then memory for the row will be in cache all at once, and bit-counting will cache beautifully.

Contrast this to your proposed approach, where for each row, the cache line will be loaded, and a single bit will be read from it. By the time you've cycled through all the rows in your array, the memory for the first row will (probably, if you've got any reasonable number of rows), be out of the cache, and the row will have to be loaded again.

Approximately, assuming a 64B cache line, the first approach is going to need (1/64*8) memory accesses per bit in the array, compared to 1 memory access per bit in the array compared to yours. Since counting the bits and remembering the max is just a few cycles, it's reasonable to think that the memory access are going to dominate the running cost, which means the first approach will run approximately 64 * 8 = 512 times faster. Of course, you'll get some of that time back because your approach can terminate early, but the 512 times speed hit is a large cost to overcome.

If your rows are super-long, you may find that a hybrid between these two approaches works excellently: count the number of bits in the first cache-line's worth of data in each row (being careful to cache-line-align each row of your data in memory), and if every row has no bits set in the first cache-line, go to the second and so forth. This combines the cache-efficiency of the first approach with the early termination of the second approach.

As with all optimisations, you should measure results, and be sure that it's important that the code is fast. The efficient solution is likely to impose annoying restrictions (like 64-byte memory alignment for rows), and the code will be harder to read than a straightforward solution.

Upvotes: 0

sebii
sebii

Reputation: 516

That would work since it's equivalent to finding the row for which the leftmost 1 is before (or at the same point as) any other row's leftmost 1. It would still be O(m * n) in the worst case:

Input Matrix :
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

Given that your rows are sorted, I would binary search for the position of the first one for each row, and return the row with the minimum position. This would be O(m * logn), although you might be able to do better.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55609

If it's:

0 ... 0 1
0 ... 0 0
0 ... 0 0
0 ... 0 0
0 ... 0 0

You'd have to search many columns.

The maximum amount of work involved would be linear in the number of cells (O(mn)), and the other approaches outperform this here.

Specifically the approach where:

  • You start at the top right and
  • Repeatedly:
    • Search left until you find a 0 and
    • Search down until you find a 1
  • And return the last row where you found a 1

Is linear in the number of rows plus columns (O(m + n)).

Upvotes: 3

Related Questions