Mathematica的模式匹配效果不佳？

Question

我最近询问为什么PatternTest导致大量不必要的评估:PatternTest没有优化？ 列昂尼德回答说,对我来说这是一个相当可疑的方法是必要的.我可以接受,尽管我更喜欢更有效的选择.

我现在意识到,我相信列昂尼德已经说了一段时间,这个问题在Mathematica中运行得更深,我感到很困扰.我无法理解为什么这不是或不能更好地优化.

考虑这个例子:

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

{0., Null}

{1.014, False}

检查列表的头部基本上是即时的,但检查模式需要一秒钟.当然,Mathematica可以认识到,由于列表的第一个元素不是整数,因此模式不能匹配,与PatternTest我的情况不同,我看不出模式中是否存在任何可变性.对此有何解释？

---

关于打包数组似乎有些混乱,据我所知,这与这个问题无关.相反,我担心所有列表上的O(n ²)时间复杂度,打包或解包.

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], __}]和朋友一起但无济于事.

所以,我的两分钱:或者使用不同的模式(并且使用On ["Packing"]来查看它是否转到一般匹配器)或进行预检DeveloperPackedArrayQ[expr] && Head[expr[[1]]]===Integer或其他一些.