performance - 为什么 Cases[] 在这里这么慢？有什么技巧可以加快速度吗？

在尝试粘贴图像时，我注意到 Cases[] 非常慢。

要复制，首先将大图像复制到剪贴板(只需按 Print Screen)，然后评估以下内容:

In[33]:= SetSystemOptions["PackedArrayOptions" -> "UnpackMessage" -> True];

In[34]:= AbsoluteTiming[nb = NotebookGet@ClipboardNotebook[];]
Out[34]= {0.4687500, Null}

In[35]:= AbsoluteTiming[d1 = nb[[1, 1, 1, 1, 1, 1, 1]];]
Out[35]= {0., Null}

In[36]:= AbsoluteTiming[d2 = First@Cases[nb, r_RasterBox :> First[r], Infinity, 1];]

During evaluation of In[36]:= Developer`FromPackedArray::unpack: Unpacking array in call to Notebook. >>

Out[36]= {0.9375000, Null}

(我是在 Windows 上这样做的，不确定粘贴代码在其他系统上是否相同。)

请注意，与直接使用 Cases 相比，使用 Part 提取数据非常慢，即使我明确告诉 Cases 我只需要一个匹配项。

我确实发现(如上所示)Cases 由于某种原因触发了解包，即使搜索应该在它到达内部的打包数组之前停止。使用比 Infinity 更浅的级别规范可能会避免解包。

问题: 在这里使用 Cases 比 Part 更容易也更可靠(如果子表达式可以出现在不同的位置怎么办？使用 a25 或 13 的不同位置，使用 13 或 13 的不同方式，可能是 13 或 13 的不同位置？

可能相关的问题:Mathematica's pattern matching poorly optimized?
(这就是我将 Cases 规则从 Cases 更改为 RasterBox[data_, ___] -> data 的原因。)

最佳答案

我现在无法访问 Mathematica，因此以下内容未经测试。我的猜测是 Cases 在这里解包，因为它搜索深度优先，因此首先看到打包的数组。如果这是正确的，那么您可以改用规则( ReplaceAll ，而不是 Replace )，并在第一次匹配时抛出异常:

Module[{tag},
   Catch[
     nb /. r_RasterBox :> Block[{}, Throw[First[r], tag] /; True];
     $Failed,
     tag]
]

正如我所说，这只是一个未经检验的猜测。

编辑 2:一种基于从模式匹配器中屏蔽部分表达的方法

前言

在第一次编辑(下面)中，提出了一种相当繁重的方法。在许多情况下，人们可以采取另一种方式。在这个特定问题(以及许多其他类似问题)中，主要问题是以某种方式将某些子表达式从模式匹配器中屏蔽掉。这也可以通过使用规则来实现，用一些虚拟符号临时替换感兴趣的部分。

代码

这是对 Cases 的修改，它就是这样做的:

Clear[casesShielded];
casesShielded[expr_,pt_,shieldPattern_,levspec_,n_,opts:OptionsPattern[]]:=
   Module[{dummy,inverseShieldingRules, shielded, i=0},
      inverseShieldingRules =
        If[#==={},#,Dispatch@First@#]&@
           Reap[shielded= expr/.(p:shieldPattern):>
             With[{eval = With[{ind = ++i},Sow[dummy[ind]:>p];dummy[ind]]},
                eval/;True];
           ][[2]];
      Cases[shielded,pt,levspec,n,opts]/.inverseShieldingRules];

这个版本的 Cases 有一个额外的参数 shieldPattern(第三个)，它指示哪些子表达式必须被模式匹配器屏蔽。

优点和适用性

上面的代码非常轻量级(与下面的 edit1 的建议相比)，它允许完全重用和利用现有的 Cases 功能。这适用于主要模式(或规则)对相关部分的屏蔽不敏感的情况，这是一种相当常见的情况(特别是涵盖 _h 类型的模式，包括手头的情况)。这也可能比应用 myCases(如下所述)更快。

手头的案子

在这里，我们需要这个调用:

In[55]:=
(d4=First@casesShielded[nb,x_RasterBox:>First@x,
    p_List/;Developer`PackedArrayQ[p],Infinity,1]);//Timing

Out[55]= {0.,Null}

结果当然和以前一样:

In[61]:= d2===d4
Out[61]= True

编辑:另一种类似 Cases 的功能

动机和代码

我花了一段时间来生成这个函数，我不能 100% 确定它总是正常工作，但这里有一个 Cases 的版本，它仍然以深度优先方式工作，在子表达式之前分析整个表达式:

ClearAll[myCases];
myCases[expr_, lhs_ :> rhs_, upToLevel_: 1, max : (_Integer | All) : All,
    opts : OptionsPattern[]] :=
 Module[{tag, result, f, found = 0, aux},
   With[{
    mopts = FilterRules[{opts}, {Heads -> False}],
    frule =
       Apply[
         RuleDelayed,
         Hold[lhs, With[{eval =  aux}, Null /; True]] /.
            {aux :> Sow[rhs, tag] /; max === All,
             aux :> (found++; Sow[rhs, tag])}
       ]
    },
    SetAttributes[f, HoldAllComplete];
    If[max =!= All,
       _f /; found >= max := Throw[Null, tag]
    ];
    f[x_, n_] /; n > upToLevel := Null;
    f[x_, n_] :=
      Replace[
       HoldComplete[x],
       {
          frule,
          ex : _[___] :>
            With[{ev =
              Replace[
                HoldComplete[ex],
                y_ :> With[{eval = f[y, n + 1]}, Null /; True],
                {2},
                Sequence @@ mopts
              ]},
              Null /; True
            ]
       },
       {1}
      ]
   ]; (* external With *)
   result =
     If[# === {}, #, First@#] &@
        Reap[Catch[f[expr, 0], tag], tag, #2 &][[2]];
   (* For proper garbage-collection of f *)
   ClearAll[f];
   result
 ]

这个怎么运作

这不是最简单的一段代码，所以这里有一些注释。这个版本的 Cases 基于我首先提出的相同想法——即，使用规则替换语义首先尝试对整个表达式进行模式匹配，只有当失败时，才转到子表达式。我强调这仍然是深度优先遍历，但与标准遍历不同(它用于大多数表达式遍历函数，如 Map 、 Scan 、 Cases 等)。我使用 Reap 和 Sow 来收集中间结果(匹配)。这里最棘手的部分是防止子表达式求值，我不得不将子表达式包装到 HoldComplete 中。因此，我不得不使用(嵌套版本的)Trott-Strzebonski 技术(也许有更简单的方法，但我无法看到它们)，以启用对持有的(子)表达式中规则的rhsides 的评估，并使用具有适当级别规范的 Replace，考虑额外添加的 HoldComplete 包装器。我在规则中返回 Null ，因为主要操作是到 Sow 部分，所以最后注入(inject)原始表达式的内容无关紧要。代码添加了一些额外的复杂性以支持级别规范(我只支持指示要搜索的最大级别的单个整数级别，而不是可能的 lev.specs 的全部范围)、找到的最大数量的结果，以及Heads 选项。 frule 的代码用于在我们想要找到所有元素的情况下不引入对找到的元素进行计数的开销。我使用相同的 Module 生成的标签既作为 Sow 的标签，又作为异常的标签(当找到足够的匹配时，我用它来停止进程，就像我最初的建议一样)。

测试和基准

为了对该功能进行非平凡的测试，我们可以例如找到 DownValues 的 myCases 中的所有符号，并与 Cases 进行比较:

In[185]:=
And@@Flatten[
    Outer[
       myCases[DownValues[myCases],s_Symbol:>Hold[s],#1,Heads->#2]  ===
       Cases[DownValues[myCases],s_Symbol:>Hold[s],#1,Heads->#2]&,
       Range[0,20],
       {True,False}
    ]]

Out[185]= True

myCases 函数比 Cases 慢大约 20-30 倍:

In[186]:=
Do[myCases[DownValues[myCases],s_Symbol:>Hold[s],20,Heads->True],{500}];//Timing
Out[186]= {3.188,Null}

In[187]:= Do[Cases[DownValues[myCases],s_Symbol:>Hold[s],20,Heads->True],{500}];//Timing
Out[187]= {0.125,Null}

手头的案子

很容易查到myCases解决了原来的解包问题:

In[188]:= AbsoluteTiming[d3=First@myCases[nb,r_RasterBox:>First[r],Infinity,1];]
Out[188]= {0.0009766,Null}

In[189]:= d3===d2
Out[189]= True

希望 myCases 通常对这种情况有用，尽管使用它代替 0x2518122231343141 的性能损失很大，必须加以考虑。

关于performance - 为什么 Cases[] 在这里这么慢？有什么技巧可以加快速度吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8700934/