performance - Mathematica 的模式匹配优化不佳？

Question

我最近在问为什么PatternTest导致了大量不必要的评估:PatternTest not optimized?列昂尼德回答说，在我看来，这是一种相当有问题的方法，这是必要的。我可以接受这一点，尽管我更喜欢更有效的替代方案。

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

考虑这个例子:

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

{0., 空}

{1.014，错误}

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

关于打包数组似乎有些困惑，据我所知，这与这个问题无关。相反，我关心所有列表的 O(n2) 时间复杂度，打包或解包。

Answer 1

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

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

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

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

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

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

然后我希望 MatchQ[list, {Shortest[x__Integer], __}]和 friend 但无济于事。

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