Mathematica 的模式匹配优化不佳? [英] Mathematica's pattern matching poorly optimized?

问题描述

我最近询问了为什么 PatternTest 会导致大量不必要的评估:PatternTest 没有优化? Leonid 回答说，在我看来，这是一种相当有问题的方法，这是必要的.我可以接受这一点，但我更喜欢更有效的替代方案.

I recently inquired about why PatternTest was causing a multitude of needless evaluations: PatternTest not optimized? Leonid replied that it is necessary for what seems to me as a rather questionable method. I can accept that, though I would prefer a more efficient alternative.

我现在意识到，我相信 Leonid 已经说过一段时间了，这个问题在 Mathematica 中存在的更深，我很困扰.我不明白为什么这不是或不能更好地优化.

I now realize, which I believe Leonid has been saying for some time, that this problem runs much deeper in Mathematica, and I am troubled. I cannot understand why this is not or cannot be better optimized.

考虑这个例子:

list = RandomReal[9, 20000];
Head /@ list; // Timing
MatchQ[list, {x__Integer, y__}] // Timing

{0., Null}

{1.014, False}

检查列表的头部本质上是即时的，但检查模式需要一秒钟的时间.当然 Mathematica 可以识别出由于列表的第一个元素不是整数，因此模式无法匹配，并且与 PatternTest 的情况不同，我看不出有任何可变性在图案中.对此有何解释?

Checking the heads of the list is essentially instantaneous, yet checking the pattern takes over a second. Surely Mathematica could recognize that since the first element of the list is not an Integer, the pattern cannot match, and unlike the case with PatternTest I cannot see how there is any mutability in the pattern. What is the explanation for this?

推荐答案

MatchQ 为这些类型的测试解包.原因是没有为此实施任何特殊情况.原则上它可以包含任何东西.

MatchQ unpacks for these kinds of tests. The reason is that no special case for this has been implemented. In principle it could contain anything.

On["Packing"]
MatchQ[list, {x_Integer, y__}] // Timing

MatchQ[list, {x__Integer, y__}] // Timing

改进这一点非常棘手 - 如果您破坏了模式匹配器，您就会遇到严重的问题.

Improving this is very tricky - if you break the pattern matcher you have a serious problem.

编辑 1:确实，拆包不是 O(n^2) 复杂度的原因.但是，它确实表明对于 MatchQ[list, {x__Integer, y__}] 部分，代码转到算法的另一部分(需要解包列表).其他一些需要注意的事情:只有当两种模式都是 __ 时才会出现这种复杂性，如果其中之一是 _ 算法具有更好的复杂性.

Edit 1: It is true that the unpacking is not the cause for the O(n^2) complexity. It does, however, show that for the MatchQ[list, {x__Integer, y__}] part the code goes to another part of the algorithm (which needs the lists to be unpacked). Some other things to note: This complexity arises only if both patterns are __ if either one of them is _ the algorithm has a better complexity.

该算法然后遍历所有 n*n 个潜在匹配项，并且似乎没有提前救助.大概是因为可以构建需要这种复杂性的其他模式 - 问题是上述模式迫使匹配器采用非常通用的算法.

The algorithm then goes through all n*n potential matches and there seems no early bailout. Presumably because other patters could be constructed that would need this complexity - The issue is that the above pattern forces the matcher to a very general algorithm.

然后我希望 MatchQ[list, {Shortest[x__Integer], __}] 和朋友，但无济于事.

I then was hoping for MatchQ[list, {Shortest[x__Integer], __}] and friends but to no avail.

所以，我的两分钱:要么使用不同的模式(并使用 On["Packing"] 来查看它是否进入通用匹配器)或进行预检查 DeveloperPackedArrayQ[expr] &&Head[expr[[1]]]===Integer 之类的.

So, my two cents: either use a different pattern (and have On["Packing"] to see if it goes to the general matcher) or do a pre-check DeveloperPackedArrayQ[expr] && Head[expr[[1]]]===Integer or some such.

这篇关于Mathematica 的模式匹配优化不佳?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！