2
$\begingroup$

I need a quick test to check if a large matrix contains any non-zeros. The Contains functions work on Lists not matrices.

d1 = ConstantArray[0, 100];
d2 = ConstantArray[0, {100, 100}];
ContainsOnly[d1, {0}]
ContainsOnly[d2, {0}]
ContainsAny[d1, {0}]
ContainsAny[d2, {0}]

(* True False True False *)

I know that I could use Flatten[], but Flatten appears to create another entire list in memory, which takes time and (worse) consumes memory:

n = 20000;
d2 = ConstantArray[0, {n, n}];
Print[Timing[ContainsOnly[Flatten@d2, {0}]]];
Print[Timing[d3 = Flatten[d2]][[1]]];
Print[Timing[ContainsOnly[d3, {0}]]];

(* {2.46, True} 1.375 {0.75, True} *)

Is there a way to just search the matrix instead of copying it into a Flatten[]'d list to search?

I ultimately just need to know if the matrix contains any non-zeros. Hopefully, there's a method that will stop search once it finds a non-zero.

$\endgroup$
  • $\begingroup$ Directly from the docs: "ContainsOnly[e1,e2] yields True if e1 contains only elements that appear in e2". Your d2 - this is the e1 - is a list of lists of zeros - this list (the outer one) doesn't contain a 0 - e2 == {0} here - i.e. {0, ...., 0} is not 0. You can simply ContainsOnly[Flatten@d2, {0}] - yields True. $\endgroup$ – corey979 Jan 17 '17 at 23:48
  • 2
    $\begingroup$ Count[d2, 0, Infinity] if all you want is whether the array contains 0. If you also are interest in 0., use Count[d2, (0 | 0.), Infinity]. $\endgroup$ – bbgodfrey Jan 18 '17 at 0:19
  • 1
    $\begingroup$ If you know that you have only numbers, Total[Abs[d2], Infinity] gives a similar performance of 2.5 s. If you have only positive numbers then you can gain performance by using Total[d2, Infinity] (0.5 s) $\endgroup$ – Felix Jan 18 '17 at 0:24
  • 1
    $\begingroup$ Then Total[d2, Infinity]==0 gives even better performance. $\endgroup$ – Felix Jan 18 '17 at 0:32
  • 1
    $\begingroup$ Max@d2==0 s/b pretty quick for "... know I'll only have positive integers" case you state. $\endgroup$ – ciao Jan 18 '17 at 1:56
2
$\begingroup$

The function FirstCase[matrix,0,"No zero",2] should do the trick quickly. It gives 0 if there is at least one 0 in the matrix and "No zero" otherwise. The good thing is (a) you don't have to flatten your matrix first and (b) it stops as soon as the first zero is found, so as long as the only zero is not hidden at the very last position, it doesn't even go through the whole matrix to answer your question.

matrix=Table[RandomReal[],{2000},{2000}];

Here Timing[ContainsAny[Flatten[matrix],{0}]] gives on my laptop 4.4 seconds, while

Timing[FirstCase[matrix,0,"Non zero",2]]

gives 0.3 seconds i.e. about 10 times faster. If you have a zero early on in the matrix 'ContainsAny' is as slow as before, but FirstCase speeds up:

matrix[[223,445]]==0
Timing[FirstCase[matrix,0,"Non zero",2]

gives now 0.01 seconds.

$\endgroup$
  • 1
    $\begingroup$ Normally I'd use RepeatedTiming[] or at least AbsoluteTiming[]. Note also that AbsoluteTiming[FirstCase[matrix, 0, "Non zero", 2];] is faster than without the ;. $\endgroup$ – Feyre Jan 18 '17 at 12:56
0
$\begingroup$

Given your statement:

I know I'll only have positive integers.

the answer I gave for How do I check if any element in a list is positive? applies:

Positive @ Max @ d2                     (* negate with Not as needed *)

Early exit behaviors are also discussed in that answer. In the case of a matrix a block-based approach naturally presents itself: test each row separately and exit if a positive value is found:

AllTrue[d2, Not @* Positive @* Max]

In the case of an all-zero array this will be significantly slower than the first form but it can exit after only one row.

$\endgroup$

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.