wolfram-mathematica - 在 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

就个人而言，我认为 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 中的尾递归解决方案可以与程序(未编译)解决方案一样有效。