2

Mathematica 有一个内置函数ArgMax，用于基于标准数学定义的无限域上的函数。

有限域的类比是一种方便的效用函数。给定一个函数和一个列表（称其为函数的域），返回列表中使函数最大化的元素。下面是一个有限 argmax 的例子： Canonicalize NFL team names

这是我的实现（连同 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 怎么样，它不是返回最大元素，而是返回最大元素的位置？

4

2 回答 2

3

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

对于 0 到 100 之间的 100,000 个随机整数列表，这在一些基本测试中快了大约 30%。

对于一个posmax函数，这种有点不优雅的方法是我能想到的最快的方法：

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

当然，我们可以再次应用 memoization：

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]]]
于 2010-04-17T08:39:14.853 回答
0

对于 posmax，您可以首先将函数映射到列表上，然后只询问最大元素的位置。IE：

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

whereposmax[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

这些都没有解决如何找到所有最大元素（或它们的位置）的问题。在实践中，这通常不会出现在我身上，尽管我认为拥有它会很好。

于 2010-04-17T00:53:54.093 回答