posmax: аналогично argmax, но задает положение (я) элемента x, для которого f [x] является максимальным - PullRequest
Новая
       27

posmax: аналогично argmax, но задает положение (я) элемента x, для которого f [x] является максимальным

2 голосов
/ 17 апреля 2010

Mathematica имеет встроенную функцию ArgMax для функций в бесконечных областях, основанную на стандартном математическом определении .

Аналогом для конечных областей является удобная функция полезности. Получив функцию и список (назовите его доменом функции), верните элемент (ы) списка, которые максимизируют функцию. Вот пример конечного argmax в действии: Canonicalize NFL названия команд

И вот моя реализация этого (наряду с argmin для хорошей меры): 

(* argmax[f, domain] returns the element of domain for which f of 
   that element is maximal -- breaks ties in favor of first occurrence. *)
SetAttributes[{argmax, argmin}, HoldFirst];
argmax[f_, dom_List] := Fold[If[f[#1]>=f[#2], #1, #2]&, First[dom], Rest[dom]]
argmin[f_, dom_List] := argmax[-f[#]&, dom]

Во-первых, это самый эффективный способ реализации argmax? Что если вам нужен список всех максимальных элементов, а не только первый?

Во-вторых, как насчет связанной функции posmax, которая вместо того, чтобы возвращать максимальные элементы, возвращает позицию (позиции) максимальных элементов?

Ответы [ 2 ]

3 голосов
/ 17 апреля 2010

@ dreeves, вы правы в том, что Ordering является ключом к самой быстрой реализации ArgMax в конечном домене: 

ArgMax[f_, dom_List] := dom[[Ordering[f /@ dom, -1]]]

Отчасти проблема с вашей первоначальной реализацией, использующей Fold, заключается в том, что в итоге вы оцениваете f в два раза больше, чем необходимо, что неэффективно, особенно когда вычисления f идут медленно. Здесь мы оцениваем f только один раз для каждого члена домена. Когда в домене много дублированных элементов, мы можем дополнительно оптимизировать, запоминая значения f: 

ArgMax[f_, dom_List] :=
  Module[{g},
    g[e___] := g[e] = f[e]; (* memoize *)
    dom[[Ordering[g /@ dom, -1]]]
  ]

Это было примерно на 30% быстрее в некоторых базовых тестах для списка из 100 000 случайных целых чисел от 0 до 100.

Для функции posmax этот несколько не элегантный подход - самая быстрая вещь, которую я могу придумать: 

PosMax[f_, dom_List] :=
  Module[{y = f/@dom},
    Flatten@Position[y, Max[y]]
  ]

Конечно, мы можем применить напоминание снова: 

PosMax[f_, dom_List] := 
  Module[{g, y},
    g[e___] := g[e] = f[e];
    y = g /@ dom;
    Flatten@Position[y, Max[y]]
  ]

Чтобы получить всех максимальных элементов, теперь вы можете просто реализовать ArgMax в терминах PosMax: 

ArgMax[f_, dom_List] := dom[[PosMax[f, dom]]]
0 голосов
/ 17 апреля 2010

Для posmax вы можете сначала отобразить функцию по списку, а затем просто запросить положение максимального элемента (ов).Т.е.: 

posmax[f_, dom_List] := posmax[f /@ dom]

, где posmax[list] полиморфно определяется, чтобы просто вернуть позицию максимального элемента (ов).Оказывается, есть встроенная функция Ordering , которая по сути делает это.Таким образом, мы можем определить версию posmax с одним аргументом следующим образом: 

posmax[dom_List] := Ordering[dom, -1][[1]]

Я только что проверил это на основе циклической версии и рекурсивной версии, и упорядочение во много раз быстрее.Рекурсивная версия хороша, поэтому я покажу ее здесь, но никогда не пытайтесь запускать ее на больших входах! 

(* posmax0 is a helper function for posmax that returns a pair with the position 
   and value of the max element. n is an accumulator variable, in lisp-speak. *)
posmax0[{h_}, n_:0] := {n+1, h}
posmax0[{h_, t___}, n_:0] := With[{best = posmax0[{t}, n+1]},
  If[h >= best[[2]], {n+1, h}, best]]

posmax[dom_List] := First@posmax0[dom, 0]
posmax[f_, dom_List] := First@posmax0[f /@ dom, 0]
posmax[_, {}] := 0

Ничто из этого не решает вопрос о том, как найти все максимальные элементы (или их позиции).Это обычно не подходит для меня на практике, хотя я думаю, что было бы хорошо иметь.

...