Is there any efficient easy way to compare two lists with the same length with Mathematica?

6.8k views Asked by At

Given two lists A={a1,a2,a3,...an} and B={b1,b2,b3,...bn}, I would say A>=B if and only if all ai>=bi.

There is a built-in logical comparison of two lists, A==B, but no A>B. Do we need to compare each element like this

And@@Table[A[[i]]>=B[[i]],{i,n}]

Any better tricks to do this?

EDIT: Great thanks for all of you.

Here's a further question:

How to find the Maximum list (if exist) among N lists?

Any efficient easy way to find the maximum list among N lists with the same length using Mathematica?

5

There are 5 answers

10
DavidC On BEST ANSWER

Method 1: I prefer this method.

NonNegative[Min[a - b]]

Method 2: This is just for fun. As Leonid noted, it is given a bit of an unfair advantage for the data I used. If one makes pairwise comparisons, and return False and Break when appropriate, then a loop may be more efficient (although I generally shun loops in mma):

result = True;
n = 1; While[n < 1001, If[a[[n]] < b[[n]], result = False; Break[]]; n++]; result

Some timing comparisons on lists of 10^6 numbers:

a = Table[RandomInteger[100], {10^6}];
b = Table[RandomInteger[100], {10^6}];

(* OP's method *)
And @@ Table[a[[i]] >= b[[i]], {i, 10^6}] // Timing

(* acl's uncompiled method *)
And @@ Thread[a >= b] // Timing

(* Leonid's method *)
lessEqual[a, b] // Timing

(* David's method #1 *)
NonNegative[Min[a - b]] // Timing

timings 2


Edit: I removed the timings for my Method #2, as they can be misleading. And Method #1 is more suitable as a general approach.

6
acl On

For instance,

And @@ Thread[A >= B]

should do the job.

EDIT: On the other hand, this

cmp = Compile[
  {
   {a, _Integer, 1},
   {b, _Integer, 1}
   },
  Module[
   {flag = True},
   Do[
    If[Not[a[[p]] >= b[[p]]], flag = False; Break[]],
    {p, 1, Length@a}];
   flag],
  CompilationTarget \[Rule] "C"
  ]

is 20 times faster. 20 times uglier, too, though.

EDIT 2: Since David does not have a C compiler available, here are all the timing results, with two differences. Firstly, his second method has been fixed to compare all elements. Secondly, I compare a to itself, which is the worst case (otherwise, my second method above will only have to compare elements up to the first to violate the condition).

(*OP's method*)
And @@ Table[a[[i]] >= b[[i]], {i, 10^6}] // Timing

(*acl's uncompiled method*)
And @@ Thread[a >= b] // Timing

(*Leonid's method*)
lessEqual[a, b] // Timing

(*David's method #1*)
NonNegative[Min[a - b]] // Timing

(*David's method #2*)
Timing[result = True;
 n = 1; While[n < Length[a], 
  If[a[[n]] < b[[n]], result = False; Break[]];
  n++]; result]

(*acl's compiled method*)
cmp[a, a] // Timing

enter image description here

So the compiled method is much faster (note that David's second method and the compiled method here are the same algorithm, and the only difference is overhead).

All these are on battery power so there may be some random fluctuations, but I think they are representative.

EDIT 3: If, as ruebenko suggested in a comment, I replace Part with Compile`GetElement, like this

cmp2 = Compile[{{a, _Integer, 1}, {b, _Integer, 1}}, 
  Module[{flag = True}, 
   Do[If[Not[Compile`GetElement[a, p] >= Compile`GetElement[b, p]], 
     flag = False; Break[]], {p, 1, Length@a}];
   flag], CompilationTarget -> "C"]

then cmp2 is a twice as fast as cmp.

4
Leonid Shifrin On

Since you mentioned efficiency as a factor in your question, you may find these functions useful:

ClearAll[lessEqual, greaterEqual];
lessEqual[lst1_, lst2_] :=
   SparseArray[1 - UnitStep[lst2 - lst1]]["NonzeroPositions"] === {};

greaterEqual[lst1_, lst2_] :=
   SparseArray[1 - UnitStep[lst1 - lst2]]["NonzeroPositions"] === {};

These functions will be reasonably efficient. The solution of @David is still two-four times faster, and if you want extreme speed and your lists are numerical (made of Integer or Real numbers), you should probably use compilation to C (the solution of @acl and similarly for other operators).

You can use the same techniques (using Unitize instead of UnitStep to implement equal and unequal), to implement other comparison operators (>, <, ==, !=). Keep in mind that UnitStep[0]==1.

0
kglr On

Comparison functions like Greater, GreaterEqual, Equal, Less, LessEqual can be made to apply to lists in a number of ways (they are all variations of the approach in your question).

With two lists:

 a={a1,a2,a3};
 b={b1,b2,b3};

and two instances with numeric entries

na={2,3,4}; nb={1,3,2}; 

you can use

And@@NonNegative[na-nb]

With lists with symoblic entries

And@@NonNegative[na-nb]

gives

NonNegative[a1 - b1] && NonNegative[a2 - b2] && NonNegative[a3 - b3]

For general comparisons, one can create a general comparison function like

listCompare[comp_ (_Greater | _GreaterEqual | _Equal | _Less | _LessEqual), 
         list1_List, list2_List] := And @@ MapThread[comp, {list1, list2}]

Using as

listCompare[GreaterEqual,na,nb]

gives True. With symbolic entries

listCompare[GreaterEqual,a,b]

gives the logially equivalent expression a1 <= b1 && a2 <= b2 && a3 <= b3.

4
Mr.Wizard On

When working with packed arrays and numeric comparator such as >= it would be hard to beat David's Method #1.

However, for more complicated tests that cannot be converted to simple arithmetic another method is required.

A good general method, especially for unpacked lists, is to use Inner:

Inner[test, a, b, And]

This does not make all of the comparisons ahead of time and can therefore be much more efficient in some cases than e.g. And @@ MapThread[test, {a, b}]. This illustrates the difference:

test = (Print[#, " >= ", #2]; # >= #2) &;

{a, b} = {{1, 2, 3, 4, 5}, {1, 3, 3, 4, 5}};

Inner[test, a, b, And]
1 >= 1
2 >= 3

False
And @@ MapThread[test, {a, b}]
1 >= 1
2 >= 3
3 >= 3
4 >= 4
5 >= 5

False

If the arrays are packed and especially if the likelihood that the return is False is high then a loop such as David's Method #2 is a good option. It may be better written:

Null === Do[If[a[[i]] ~test~ b[[i]], , Return@False], {i, Length@a}]
1 >= 1
2 >= 3

False