Mathematica 的模式匹配优化不佳？

我最近询问了为什么PatternTest引起了大量不必要的评估：PatternTest 未优化？ https://stackoverflow.com/questions/8484299/patterntest-not-optimized列昂尼德回答说，对于我看来相当值得怀疑的方法来说，这是必要的。我可以接受这一点，尽管我更喜欢更有效的替代方案。

我现在意识到，我相信列昂尼德已经说过一段时间了，这个问题在更深层次上数学，我很烦恼。我不明白为什么这没有或不能更好地优化。

考虑这个例子：

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

{0., Null}  

{1.014, False}  

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

There appears to be some confusion regarding packed arrays, which as far as I can tell have no bearing on this question. Rather, I am concerned with the O(n²) time complexity on all lists, packed or unpacked.

MatchQ解压这些类型的测试。原因是没有实施这种特殊情况。原则上它could包含任何东西。

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

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

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

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

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

那时我希望MatchQ[list, {Shortest[x__Integer], __}]和朋友，但都无济于事。

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