从Mathematica中的列表末尾搜索

Question

许多算法(如用于按字典顺序查找列表的下一个排列的算法)涉及查找列表中最后一个元素的索引.但是,我还没有找到一种方法在Mathematica中做到这一点并不尴尬.最直接的方法使用LengthWhile,但它意味着反转整个列表,如果您知道所需的元素接近列表的末尾并颠倒谓词的意义,则可能效率低下:

findLastLengthWhile[list_, predicate_] :=
 (Length@list - LengthWhile[Reverse@list, ! predicate@# &]) /. (0 -> $Failed)

我们可以做一个明确的,强制性的循环Do,但结果也有点笨拙.如果Return实际上从函数而不是Do块返回它会有所帮助,但它没有,所以你不妨使用Break:

findLastDo[list_, pred_] :=
 Module[{k, result = $Failed},
  Do[
   If[pred@list[[k]], result = k; Break[]],
   {k, Length@list, 1, -1}];
  result]

最终,我决定使用尾递归进行迭代,这意味着提前终止更容易一些.使用#0允许匿名函数调用自身的奇怪但有用的符号,这变为:

findLastRecursive[list_, pred_] :=
 With[{
   step =
    Which[
      #1 == 0, $Failed,
      pred@list[[#1]], #1,
      True, #0[#1 - 1]] &},
  step[Length@list]]

但这一切看起来都太难了.有没有人看到更好的方法？

编辑添加:当然,我的首选解决方案有一个错误,这意味着它在长列表中被打破,因为$IterationLimit.

In[107]:= findLastRecursive[Range[10000], # > 10000 &]
$IterationLimit::itlim: Iteration limit of 4096 exceeded. 
Out[107]= (* gack omitted *)

你可以解决这个问题Block:

findLastRecursive[list_, pred_] :=
 Block[{$IterationLimit = Infinity},
  With[{
    step =
     Which[
       #1 == 0, $Failed,
       pred@list[[#1]], #1,
       True, #0[#1 - 1]] &},
   step[Length@list]]]

$IterationLimit 不是我最喜欢的Mathematica功能.

Answer 1

不是一个答案,只是findLastDo上的几个变种.

(1)实际上,Return可以采用无证的第二个参数来告诉返回什么.

In[74]:= findLastDo2[list_, pred_] := 
 Module[{k, result = $Failed}, 
  Do[If[pred@list[[k]], Return[k, Module]], {k, Length@list, 1, -1}];
  result]

In[75]:= findLastDo2[Range[25], # <= 22 &]
Out[75]= 22

(2)更好的是使用Catch [... Throw ...]

In[76]:= findLastDo3[list_, pred_] := 
 Catch[Module[{k, result = $Failed}, 
   Do[If[pred@list[[k]], Throw[k]], {k, Length@list, 1, -1}];
   result]]

In[77]:= findLastDo3[Range[25], # <= 22 &]
Out[77]= 22

Daniel Lichtblau

Answer 2

喜欢冒险...

以下定义定义了一个reversed[...]伪装成列表对象的包装表达式,该列表对象的内容看起来是包装列表的反转版本:

reversed[list_][[i_]] ^:= list[[-i]]
Take[reversed[list_], i_] ^:= Take[list, -i]
Length[reversed[list_]] ^:= Length[list]
Head[reversed[list_]] ^:= List

样品用途:

$list = Range[1000000];
Timing[LengthWhile[reversed[$list], # > 499500 &]]
(* {1.248, 500500} *)

请注意,此方法比实际反转列表慢 ...

Timing[LengthWhile[Reverse[$list], # > 499500 &]]
(* 0.468, 500500 *)

...但当然它使用的内存要少得多.

我不推荐这种技术用于一般用途,因为假面舞会中的缺陷可以表现为微妙的错误.考虑一下:为了使模拟更加完美,需要实施哪些其他功能？展示的包装器定义显然足以愚弄LengthWhile和TakeWhile简单的情况,但其他功能(特别是内置内置)可能不会那么容易被愚弄.压倒一切Head似乎充满了危险.

尽管存在这些缺点,但这种模仿技术有时在受控环境中是有用的.

Answer 3

就个人而言,我没有看到任何LengthWhile基于解决方案的错误.此外,如果我们想要重用mma内置的列表遍历函数(而不是显式循环或递归),我没有看到避免恢复列表的方法.这是一个版本,但不会反转谓词:

Clear[findLastLengthWhile];
findLastLengthWhile[{}, _] = 0;
findLastLengthWhile[list_, predicate_] /; predicate[Last[list]] := Length[list];
findLastLengthWhile[list_, predicate_] :=
   Module[{l = Length[list]}, 
     Scan[If[predicate[#], Return[], l--] &, Reverse[list]]; l];

是否更简单我不知道.它肯定比基于它的效率低LengthWhile,特别是对于打包阵列.另外,0当没有找到满足条件的元素时,我使用返回的约定,而不是$Failed,但这只是个人偏好.

编辑

这是一个基于链表的递归版本,效率更高:

ClearAll[linkedList, toLinkedList];
SetAttributes[linkedList, HoldAllComplete];
toLinkedList[data_List] := Fold[linkedList, linkedList[], data];

Clear[findLastRec];
findLastRec[list_, pred_] :=
  Block[{$IterationLimit = Infinity},
     Module[{ll = toLinkedList[list], findLR},
       findLR[linkedList[]] := 0;
       findLR[linkedList[_, el_?pred], n_] := n;
       findLR[linkedList[ll_, _], n_] := findLR[ll, n - 1];
       findLR[ll, Length[list]]]]

一些基准:

In[48]:= findLastRecursive[Range[300000],#<9000&]//Timing
Out[48]= {0.734,8999}

In[49]:= findLastRec[Range[300000],#<9000&]//Timing
Out[49]= {0.547,8999}

编辑2

如果您的列表可以是一个打包的数组(无论什么尺寸),那么您可以利用C语言编译基于循环的解决方案.为了避免编译开销,您可以记住已编译的函数,如下所示:

Clear[findLastLW];
findLastLW[predicate_, signature_] := findLastLW[predicate, Verbatim[signature]] = 
   Block[{list},
       With[{sig = List@Prepend[signature, list]},
      Compile @@ Hold[
        sig,
        Module[{k, result = 0},
          Do[
            If[predicate@list[[k]], result = k; Break[]], 
            {k, Length@list, 1, -1}
          ];
          result], 
        CompilationTarget -> "C"]]]

该Verbatim部分是必要的,因为在典型的签名中{_Integer,1},_Integer否则将被解释为模式并且存储的定义将不匹配.这是一个例子:

In[60]:= 
fn = findLastLW[#<9000&,{_Integer,1}];
fn[Range[300000]]//Timing

Out[61]= {0.016,8999}

编辑3

这是一个基于链表的更紧凑,更快速的递归解决方案:

Clear[findLastRecAlt];
findLastRecAlt[{}, _] = 0;
findLastRecAlt[list_, pred_] :=
  Module[{lls, tag},
    Block[{$IterationLimit = Infinity, linkedList},
       SetAttributes[linkedList, HoldAllComplete];
       lls = Fold[linkedList, linkedList[], list];
       ll : linkedList[_, el_?pred] := Throw[Depth[Unevaluated[ll]] - 2, tag];
       linkedList[ll_, _] := ll;
       Catch[lls, tag]/. linkedList[] :> 0]]

它与基于Do- 循环的版本一样快,并且比原始版本快两倍findLastRecursive(即将添加的相关基准测试 - 我目前无法在不同的机器上执行一致的(以前的)基准测试).我认为这很好地说明了mma中的尾递归解决方案与程序(未编译)解决方案一样有效.