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

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 ответа

Решение

@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]]]
Источник

Для 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

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

Источник
Другие вопросы по тегам