代码之家 › 专栏 › 技术社区 › dreeves

posmax:类似argmax,但给出元素x的位置,f[x]是最大的。

utilities wolfram-mathematica functional-programming function math

dreeves · 技术社区 · 14 年前

Mathematica有一个内置函数 ArgMax 对于无限域上的函数,基于 standard mathematical definition .

有限域模拟是一种方便的实用函数。给定一个函数和一个列表(称之为函数的域),返回列表中使函数最大化的元素。下面是有限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如何,它不是返回最大元素,而是返回最大元素的位置?

2 回复 | 直到 14 年前

Michael Pilat 14 年前

@德雷夫斯,你说得对 Ordering 是有限域上最快实现argmax的关键:

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

原始实现使用的部分问题 Fold 你最后会评估吗? f 是必要的两倍,这是效率低下的,尤其是在计算时 f 是慢的。这里我们只评估 f 域的每个成员一次。当域中有许多重复的元素时,我们可以通过 memoizing 价值观 f :

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

对于10万个0到100之间的随机整数的列表,这在一些基本测试中大约快了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]]]

dreeves 14 年前

对于posmax,您可以首先在列表上映射函数,然后请求最大元素的位置。Ie:

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

这些都不能解决如何找到 全部的 最大元素(或元素的位置)。在实践中,这通常不会出现在我身上,尽管我认为这样做很好。