Есть ли эффективный простой способ сравнить два списка одинаковой длины с Mathematica?

Question

Учитывая два списка A={a1,a2,a3,...an} и B={b1,b2,b3,...bn}, я бы сказал A>=B тогда и только тогда, когда все ai>=bi.

Существует встроенное логическое сравнение двух списков, A==B, но не A>B. Нужно ли сравнивать каждый элемент следующим образом

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

Есть ли лучшие приемы, чтобы сделать это?

EDIT: Большое спасибо всем вам.

Вот еще один вопрос:

Как найти максимальный список (если существует) среди N списков?

Любой эффективный и простой способ найти максимальный список из N списков одинаковой длины с помощью Mathematica?

Answer 1

Метод 1 : я предпочитаю этот метод.

NonNegative[Min[a - b]]

Метод 2 : Это просто для удовольствия.Как отметил Леонид, это дает немного несправедливого преимущества для данных, которые я использовал.Если кто-то делает парные сравнения и возвращает False и Break, когда это уместно, тогда цикл может быть более эффективным (хотя я обычно избегаю циклов в mma):

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

---

Некоторые временные сравнения насписки из 10 ^ 6 чисел:

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

---

Редактировать: я убрал время для моего метода № 2, поскольку они могут вводить в заблуждение.И метод № 1 больше подходит в качестве общего подхода.

Answer 2

Например,

And @@ Thread[A >= B]

должен выполнять работу.

РЕДАКТИРОВАТЬ: С другой стороны, это

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"
  ]

в 20 раз быстрее.Хотя и в 20 раз страшнее.

РЕДАКТИРОВАТЬ 2: Поскольку у Дэвида нет компилятора C, здесь приведены все временные результаты с двумя отличиями.Во-первых, его второй метод был исправлен для сравнения всех элементов.Во-вторых, я сравниваю a с самим собой, что является худшим случаем (в противном случае мой второй метод, приведенный выше, должен будет сравнивать только элементы до первого, чтобы нарушить условие).

(*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

Таким образом, скомпилированный метод намного быстрее (обратите внимание, что второй метод Дэвида и скомпилированный метод здесь - это один и тот же алгоритм, и единственная разница - накладные расходы).

Все они работают от батареи, поэтомумогут быть некоторые случайные колебания, но я думаю, что они являются репрезентативными.

РЕДАКТИРОВАТЬ 3: Если, как предложил ruebenko в комментарии, я заменяю Part на Compile`GetElement, как это

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"]

тогда cmp2 в два раза быстрее cmp.

Answer 3

Поскольку вы упомянули эффективность в качестве фактора в своем вопросе, вы можете найти эти функции полезными:

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

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

Эти функции будут достаточно эффективными.Решение @David по-прежнему в два-четыре раза быстрее, и если вам нужна предельная скорость и ваши списки являются числовыми (составленными из целых или действительных чисел), вам, вероятно, следует использовать компиляцию в C (решение @acl и аналогично для другихоператоры).

Вы можете использовать те же методы (используя Unitize вместо UnitStep для реализации equal и unequal), чтобы реализовать другие операторы сравнения (>, <,==, !=).Имейте в виду, что UnitStep[0]==1.

Answer 4

Функции сравнения, такие как Greater, GreaterEqual, Equal, Less, LessEqual, могут быть применены к спискам несколькими способами (все они являются вариациями подхода в вашем вопросе).

С двумя списками:

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

и два экземпляра с числовыми записями

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

, которые вы можете использовать

And@@NonNegative[na-nb]

Со списками с символьными записями

And@@NonNegative[na-nb]

дает

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

Для общих сравнений можно создать общую функцию сравнения, такую ​​как

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

Использование as

listCompare[GreaterEqual,na,nb]

дает True.С символическими записями

listCompare[GreaterEqual,a,b]

дает логически эквивалентное выражение a1 <= b1 && a2 <= b2 && a3 <= b3.

Answer 5

При работе с упакованными массивами и числовым компаратором, таким как >=, было бы трудно обойти метод Дэвида №1.

Однако для более сложных тестов, которые нельзя преобразовать в простую арифметику, требуется другой метод.

Хороший общий метод, особенно для распакованных списков, заключается в использовании Inner:

Inner[test, a, b, And]

Это не делает все сравнения раньше времени и поэтому может быть гораздо болееэффективнее в некоторых случаях, чем, например, And @@ MapThread[test, {a, b}].Это иллюстрирует разницу:

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

Если массивы упакованы и особенно если вероятность того, что возврат равен False высокий, тогда цикл, такой как метод Дэвида №2, является хорошим вариантом.Это может быть лучше написано:

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

1 >= 1
2 >= 3

False