Любой эффективный простой способ найти максимальный список из N списков с одинаковой длиной, используя Mathematica? - PullRequest
Новая
       30

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

2 голосов
/ 17 января 2012

Этот вопрос является продолжением предыдущей темы для сравнения двух списков одинаковой длины:

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

Учитывая два списка A={a1,a2,a3,...an} и B={b1,b2,b3,...bn}, я бы сказал A>=B тогда и только тогда, когда все ai>=bi. Теперь у нас есть k списки H={{a11,a12,a13,...a1n}, {a21,a22,a23,...a2n},...,{ak1,ak2,ak3,...akn}}, и мы хотим найти максимальный, если существует.

Вот мой код:

Do[If[NonNegative[Min[H[[i]] - h]], h = H[[i]], ## &[]], {i, h = H[[1]]; 1, Length[H]}];h

Есть ли лучший способ сделать это?

EDIT:

Я хочу определить это как функцию вроде:

maxList[H_]:=Do[If[NonNegative[Min[H[[i]] - h]], h = H[[i]], ## &[]], {i, h = H[[1]]; 1, Length[H]}];h

Но вопрос в том, что код выше пересекает две строки, какое-нибудь исправление для этого? Вот код, работающий, но не такой красивый

maxList[H_] := Module[{h = H[[1]]}, Do[If[NonNegative[Min[H[[i]] - h]], h = H[[i]], ## &[]], {i, Length[H]}]; h]

или

maxList[H_]:=Last[Table[If[NonNegative[Min[H[[i]] - h]], h = H[[i]], ## &[]], {i, h = H[[1]]; 1, Length[H]}]]

Ответы [ 3 ]

5 голосов
/ 17 января 2012

Мне кажется, что это должно работать: 

maxList = # \[Intersection] {Max /@ Transpose@#} &;

maxList[ {{4, 5, 6}, {1, 4, 3}, {4, 3, 5}, {5, 6, 7}} ]

{{5, 6, 7}}

Я не думал о стоимости использования Intersection, и Артес показывает, чтоMemberQ гораздо лучший выбор.(Пожалуйста, проголосуйте за его ответ, как и я).Я написал бы функцию, не используя Module сам: 

maxList[a_] := If[MemberQ[a, #], #, {}] &[Max /@ Transpose@a]

Почти эквивалентный, хотя и не вполне , поскольку быстрый метод таков: 

maxList = Cases[#, Max /@ Transpose@# , 1, 1] &;

Результатв форме {{a, b, c}} или {}, а не {a, b, c} или {}.

3 голосов
/ 17 января 2012

Модификация подхода Mr.Wizard работает в несколько раз быстрее. 

maxListFast[list_List] := Module[{l}, 
                                 l = Max /@ Transpose@list; 
                                 If[MemberQ[list, l], l, {}]]

Мы тестируем оба метода с 

test  = RandomInteger[100, {500000, 10}];
test1 = Insert[test, Table[100, {10}], RandomInteger[{1, 500000}]];

и мы получаем 

In[5]:= maxList[test] // Timing
        maxListFast[test] // Timing

        Out[5]= {2.761, {}}
        Out[6]= {0.265, {}}

и 

In[7]:= maxList[test1] // Timing
        maxListFast[test1] // Timing

Out[7]= {1.217, {{100, 100, 100, 100, 100, 100, 100, 100, 100, 100}}}
Out[8]= {0.14, {100, 100, 100, 100, 100, 100, 100, 100, 100, 100}}

EDIT

В общем, чтобы выбрать метод, мы должны сначала знать, с какими данными мы имеем дело. (длина списков, их количество, типы номеров). Пока у нас большое количество коротких списков целых чисел maxListFast работает даже в 10 раз лучше (в случае 500000 списков длиной 10), чем maxList. Однако для списков действительных чисел это только в 3-4 раза быстрее, и чем больше и длиннее список, тем больше он замедляется, например. : 

         A = RandomReal[1000, {3000, 3000}];
         First@AbsoluteTiming[maxListFast@A;]/ First@AbsoluteTiming[maxList@A;]

Out[19]= 2.040516

однако, если мы вставим «величайший элемент»: 

In[21]:= IA = Insert[A, Table[1000, {3000}], RandomInteger[{1, 3000}]];
In[22]:= First@AbsoluteTiming[maxListFast@IA;]/ First@AbsoluteTiming[maxList@IA;]

Out[22]= 0.9781931

время близко.

2 голосов
/ 17 января 2012

Некоторые данные: Кстати, на самом деле нет необходимости маркировать отдельные подсписки.Я сделал это для удобства. 

a = {4, 5, 6}; b = {1, 4, 3}; c = {4, 3, 5}; d = {5, 6, 7};

lists = {a, b, c, d};

maxList определяет, является ли подсписок наибольшим списком, т.е. является ли каждый из его элементов больше, чем соответствующие элементы во всех другихподсписки.Мы изначально предполагаем, что подсписок является максимальным списком.Если это предположение нарушается (обратите внимание на использование Negative вместо NonNegative), возвращается значение False.Кстати, список будет сравниваться с самим собой;это проще, чем удалить его из lists;и это не влияет на результат. 

maxList[list_] :=
   Module[{result = True, n = 1},
   While[n < Length[lists] + 1, 
   If[Negative[Min[list - lists[[n]]]], result = False; Break[]];  n++]; result]

Теперь давайте проверим, является ли один из перечисленных выше подсписков maxList: 

greatestList = {};
n = 1; While[n < Length[lists] + 1, 
If[maxList[lists[[n]]], greatestList = lists[[n]]; Break[]]; n++];
Print["The greatest list (if one exists): ", greatestList]

(* output *)
The greatest list (if one exists): {5,6,7}

Подсписок d является maxList.

Если бы не было maxList, результатом был бы пустой список.

...