1
$\begingroup$

I have a matrix of logicals (TRUE, FALSE) and I need to count the number of rows that contain only TRUE values.

My current algorithm:

For every row:

  1. initialize counter
  2. reduce each col by + (take the sum of all the values in that row)
  3. if the result from 1. == the number of total columns, increment counter.

Is there a different (hopefully more efficient) routine I could apply?

$\endgroup$
7
  • 2
    $\begingroup$ Any way to do this must examine all entries in each row in the worst case, i.e. $n \cdot m$ entries for an $n \times m$ matrix. You can get a better algorithm by stopping as soon as you see a FALSE in a row, which makes the best case better (and presumably the average too) but has the same worst case. $\endgroup$ – vonbrand Sep 27 '15 at 17:29
  • $\begingroup$ @vonbrand thanks, I have tried this and in practice actually checking for a FALSE is much slower than just summing over the whole row then checking the sum :( $\endgroup$ – hannah heres Sep 27 '15 at 17:31
  • 1
    $\begingroup$ That very much depends on an optimized "reduce sum over row" implementation in your language (and if it is "reduce and", they might internally do short circuiting). $\endgroup$ – vonbrand Sep 27 '15 at 17:34
  • $\begingroup$ @vonbrand yea in c++ or c or R this seems to be the case, sorry if I didn't set it up clearly; thanks for the input though :) $\endgroup$ – hannah heres Sep 27 '15 at 17:42
  • $\begingroup$ If the matrix is stored as column bit vectors, you can reduce the column vectors with logical AND, stopping if you get all zeroes, then do a bit count. $\endgroup$ – Davislor Sep 28 '15 at 11:23

Your Answer

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

Browse other questions tagged or ask your own question.