【无敌】PowerBI 终极算法性能优化 最强版
- 2019 年 10 月 6 日
- 筆記
仅以此文送给PowerBI，祝4岁生日快乐。
本文副标题：PowerBI 最大连续元素数终极算法性能优化详解
本文不是为了让您看懂的，是为了让您感叹的。只有感叹了魅力才会热爱才会学会。
前情回顾：
最近，有网友发来信息，称实现了超过我们此前公布的算法。牛了，都优化了10万倍性能了还能被超越。晕~~
有伙伴提问老师是否可以给出更加优化的算法，并介绍如何进行性能的优化，答案是：肯定的。由于本案例有非常重要的代表性意义，故在这里记录之。
本文给出优化的通用思路和调试技巧，总体思路是：
- 在特性思路下，使用调试技巧进行优化。
- 要想超越固有模式，必须变换思路实现，再使用调试技巧进行优化。
由于此前已经充分说明了上下文，这里不再赘述，直接对各种算法做出比对。请看前情回顾。
通用数据结构
为了清晰地对比，先给出通用的结构：
只不过，该序列可能是1W行，也可能是1000W行。
现在来看看各种算法对此的性能表现。
累计元素算法
该算法的想法最初见于黄海剑老师提出的思路，后经网友实现，BI佐罗改良，得到终极状态如下：
AMethodPlus = // 累计求和算法增强版 VAR vT1 = ADDCOLUMNS( SampleData , "累计" , VAR vX = [Item] RETURN SUMX( SampleData , ( [Item] <= vX ) * ( 1 - [Flag] ) ) ) VAR vT2 = ADDCOLUMNS( SUMMARIZE( vT1 , [累计] ) , "出现次数" , VAR vX = [累计] RETURN COUNTROWS( FILTER( vT1 , [累计] = vX ) ) ) RETURN MAXX( vT2 , [出现次数] ) - 1
我们称该算法为：AMethodPlus版，是为AMethod的增强版。
其效果如下：
这是10000元素的运行结果，由BI佐罗优化过的算法，性能大致提升30%。进一步分析如下：
以下为该算法处理10000行数据的性能表现：
可以看出，这已经到达了该算法的可用性能边界。
备注：
从性能分析来看，该算法全部由PowerBI中DAX公式引擎FE完成，其中需要两次查询底层存储引擎SE，且都命中了缓存，故在该算法思路下，该算法已经达到极限状态。如需突破，必须换思路。
该算法的算法复杂度约为：O(n²)。
由于该算法时间复杂度为非线性增长的，故可以采用分治策略来缓解压力，而恰巧本案例在DAX中是可以用分治策略实现的。很巧的是，本案例确实可以在DAX中实现分治策略。
分治策略是算法的通用模式，对于通用编程语言，都可以通过分治策略来解决经典难题，由于DAX并不是严格意义的编程语言，而本案例启发我们在DAX中一样是可以发挥精妙的算法设计的。
分治法+累计元素法
要想突破算法思路上的极限，也就是突破O(n²)，的通用思维模型是分治策略，由于篇幅所限，不再赘述，直接给出参考实现：
DAMethod = VAR vStep = 53 VAR vT = FILTER( SampleData , [Flag] = 0 ) VAR vX = ADDCOLUMNS( vT , "SourceIndex" , [Item] ) VAR vY = SUBSTITUTEWITHINDEX( vX , "Index" , vT, [Item] , ASC ) VAR vCount = COUNTROWS( vY ) VAR vGroupValue = vCount / vStep VAR vGroupCount = IF( vGroupValue = INT( vGroupValue ) , vGroupValue - 1 , INT( vGroupValue ) ) VAR vGroup = SELECTCOLUMNS( GENERATESERIES( 0 , vGroupCount ) , "GroupIndex" , [Value] ) VAR vGroup_WithBegin = ADDCOLUMNS( vGroup , "BeginIndex" , SELECTCOLUMNS( FILTER( vY , [Index] = ( [GroupIndex] * vStep ) ) , "value" , [SourceIndex] ) ) VAR vGroup_WithBegin_End = ADDCOLUMNS( vGroup_WithBegin , "EndIndex" , IF( [GroupIndex] = vGroupCount , 1/0 , SELECTCOLUMNS( FILTER( vGroup_WithBegin , [GroupIndex] = ( EARLIER( [GroupIndex] ) + 1 ) ) , "value" , [BeginIndex] - 1 ) ) ) VAR vDivide = ADDCOLUMNS( vGroup_WithBegin_End , "Max" , VAR vDataPart = FILTER( SampleData , [Item] >= [BeginIndex] && [Item] <= [EndIndex] ) VAR vT1 = ADDCOLUMNS( vDataPart , "累计" , VAR vX = [Item] RETURN SUMX( vDataPart , ( [Item] <= vX ) * ( 1 - [Flag] ) ) ) VAR vT2 = ADDCOLUMNS( SUMMARIZE( vT1 , [累计] ) , "出现次数" , VAR vX = [累计] RETURN COUNTROWS( FILTER( vT1 , [累计] = vX ) ) ) RETURN MAXX( vT2 , [出现次数] ) - 1 ) RETURN MAXX( vDivide , [Max] )
由于是对AMethod实施的分治策略，故命名为：DAMethod算法。
其性能表现如下：
该算法经过分治策略，可以在0.5秒内完成1W数据的计算，10秒完成10W数据的计算。
但需要注意的是，分治策略本身并没有改变子算法的特点本质，因此只能得到优先的性能提升。
但更需要注意的是，分治策略是在PowerBI DAX领域首先由我们提出并设计实现的，这是一套通用的策略，也就是说，理论上，在某些问题中，只要嫌慢，都可以通过分治策略优化10到100倍的性能改进。
交错元素法
由我们的订阅课程学员给出了一种算法，采用了交错元素的技巧，实现了质的突破，这里利用了一个比较有意思的技巧，如下：
其思路是将原有元素交错起来排布，然后计算开始与结束的标识来进行计算。这里不禁感叹这位战友学员天才的思维，将纵向比较改为了横向比较，这样可以大幅降低迭代的次数。由于使用了交错元素的方法，我们不放称之为：JMethod。因此，该算法获得了显著的性能提升，如下：
计算10W元素，仅需0.6秒，比分治-累计元素法提升了约20倍。当然，外行看热闹，内行看门道，我们在这里揭示其性能真正得以提升的原因，在于：
该算法的时间复杂度为：O(n)。也就是线性的，这几乎是在算法设计界最高性能的算法理论状态，其原因很简单，解释如下：
由于实现元素交错，仅仅需要移动1位，而比较也是计算1次，因此，它是线性的，随着元素N的增长，应该呈线性时间的增长。但这位天才的学员，却没有解释这个原理，希望这个揭秘不要介意。
既然，我们理论预测了其线性时间复杂度，我们需要来验证：
可以观察到，随着元素的增多，时间的耗费成比例的放大，这是非常合理的。由于并为得到天才学员的授权，就不放其公式了，但大家也不用灰心，继续看。
深度思考
有其他战友学员发来提问，主要提出了两点：
- 老师，有没有办法想出来更快的方法？
- 老师，你的分治策略是否可以和交错算法结合后实现更快？
这两个都是很好的问题。
很显然，如果第二个可行，也就必然证明第一个可以做到，那我们只需要实现交错算法的分治策略版本即可。
分治策略是大道，它是通用思维模式。技巧，是不一定可以想到的，除非像这位天才一样想到。
这里匆匆回复了提问的学员：
分治策略无法继续加速这个算法。
你知道为什么吗？
可以在这里看懂的伙伴，恭喜您进入专家级别。我们一起来说明这个问题：
若，一个问题难度 = （正比于）元素个数N，把它分成 X 份，则该问题难度 = （正比于）X × ( N / X )。
若，一个问题难度 = （正比于）元素个数N²，把它分成 X 份，则该问题难度 = （正比于）X × ( N / X )²。
注意：
N = X × ( N / X )
而：
N² > X × ( N / X )² = N² / X
因此，分治策略可以加速一个算法复杂度是O(n)²的问题，但却无法加速一个算法复杂度本身就是O(n)的问题。
学员又问：那么这个算法就是最好的了吧。
老师回答：差不多吧，有空的话，还应该可以优化吧。
继续优化
了解PowerBI战友联盟的学院伙伴都清楚，我们是追求完美和极致的，对于天才的交错算法，已经达到了算法复杂度O(n)，这几乎真的不可能优化了。
但是，我们早就说过，优化是永无止境的。
更何况一个小姐姐说，如果你能写出比这个快的算法，就XXXXX。
哈哈，好吧，那正好有空来分析下如何继续优化一个看上去不可能优化的算法。
首先，我们在DAX引擎修车工具下来看下天才的交错算法实现：
天才的交错算法果然很牛，全部命中缓存，并且全部由FE引擎完成计算。
因此，我们只需要考虑如何来优化FE的计算即可。
这当然并非易事，但我们可以看到系统需要多次使用SE，虽然命中缓存，但仍然效率没有达到极致。由于这块内容太过专业，就此略过，给出优化后结果：
我们将整个查询优化成只需要读一次数据即可，而且全部使用FE最强技巧，使得理论上读取一次立即计算出结果，要算数据，必须得读一次吧。
因此，此时做到了真正的无懈可击，绝对完美。
请您仔细对比上下两图，您可以清晰地看到DAX引擎扫描了10W行记录直接得到结果，连缓存都不用去碰。
我们将天才学员的交错算法从原有的几十行优化为10行，如下：
VAR MyData = SELECTCOLUMNS( '10W' , "OrginIndex" , [Item] , "Value" , [Flag] ) VAR Add1 = ADDCOLUMNS( MyData , "Value2" , SELECTCOLUMNS( FILTER( MyData , [OrginIndex] = EARLIER( [OrginIndex] ) - 1 ) , "Value" , [Value] ) ) VAR Add1Filterd = FILTER( Add1 , [Value] + [Value2] = 1 ) VAR CreateBegin = ADDCOLUMNS( Add1Filterd , "BeginIndex" , IF( [Value] = 1 , [OrginIndex] ) ) VAR CreateEnd = ADDCOLUMNS( CreateBegin , "EndIndex" , IF( [Value2] = 1 , [OrginIndex] ) ) VAR CreateIndex = SUBSTITUTEWITHINDEX( CreateEnd , "Index" , SELECTCOLUMNS( CreateEnd , "OrginIndex" , [OrginIndex] ) , [OrginIndex] , ASC ) VAR AddAdd = ADDCOLUMNS( CreateIndex , "NewEndIndex" , SELECTCOLUMNS( FILTER( CreateIndex , [Index] = EARLIER( [Index] ) + 1 ) , "NewEndIndex" , [EndIndex] ) ) VAR AddAddFilterd = FILTER( AddAdd , ISBLANK( [EndIndex] ) ) RETURN MAXX( AddAddFilterd , [NewEndIndex] - [BeginIndex] )
性能大比拼
那到底运行的快了吗？上图来看吧。
我们采用了极致的优化技巧，将性能再度提升约40%。
也就是说：我们通过对FE引擎的特别优化，尽量采用最佳的DAX写法，只需要扫描一篇数据就可以得到最终结果。
分治策略的理论验证
但关于分治策略的描述属于理论的分析，那么事实是怎样的呢？
我们称分治策略+交错算法的实现，为：DJMethod。
准确地讲，我们将分治策略与我们极度优化的交错算法混合，来看看会是怎样的情况。
果然和我们预测的一样，虽说分治策略是一个很牛的策略，但在极致的优化面前，分治由于在分治时需要一点额外的时间，因此总的时间反而高于了单纯的极致优化法。
更深入的思考
如果您以为这就结束，就错了。
因为小姐姐又发难了，说这个优化不算，还是参考得人家的，属于微创新，有本事就来个全新的，彻底超越的方法才算。我的个天呢~
吃顿饭真难。
我们深入引擎去看看分治法为什么赢不了单纯极致法，我们打开引擎可以看到：
如果非常仔细的分析，可以得到：
- 分治，用到了对SE的访问
- 分治下的计算，用到了对SE的访问
因此，在这个案例中分治是干不过单纯的。
为什么分治会多出来一次呢？
可以看到第一次访问就是：
而第二次访问是：
这两次的目的是不同的，因此必须有两次访问，导致不如单纯的极致交错元素法。
超越极限
不来到这里，您看着一定不过瘾，这里也决定了PowerBI战友联盟的专业度在什么Level。要想完全原创超越错位元素法，我们先来看看超越上述一切的算法需要什么条件：
- 超越经BI佐罗深度优化的极致交错法必须只能读一次元素。
- 算法复杂度必须是 O(n)的。
这两条挡在这里，让你根本不可能超越。但我们就真的这么神奇，我们让你看看这个算法，它满足：
- 读取了少于N的元素，只读一次。
- 算法复杂度是O(n/a)的。其中，a是一个常数。
先来看看长啥样吧。
超越极限，不是说能0.001秒处理一个亿，而是在合理合乎科学的前提下做到了极致，甚至是极致中的极致。
我们来看看PowerBI引擎是如何看待这个算法的：
对于10W元素规模的计算，只需要扫描一半的元素，而并非是整个10W个元素。
震惊吧，这个问题的计算，居然可以不看所有元素就可以得到答案。
没错！当前的算法复杂度是O(n/a)。
其中，a = ( n / 0的个数 )。
好了：除了这个算法，其他的都很慢，不服来比吧。
要想战胜这个算法的苛刻条件：
- 扫描的元素个数必须少于总数；
- 只能扫描一次，由公式引擎计算完成。
从理论上讲，这是一个绝对不可超越的最强算法。我们非常拭目以待再次出现天才来超越。
总结
本文通过真实案例以及前序的几篇文章，从最初的应用挖掘到计算的极致，并用科学的理论和方法研究如何一步步逼近性能的绝对极限。
从本文主题来说，性能的排序如下：
最强算法>BI佐罗版交错算法>>交错算法>>>分治+累计元素法>>>>BI佐罗版累计元素法>累计元素法>>直观计算法
也就是说，本问题的算法经过了 7 次大型优化，最终得到了不可超越的极限。
从算法复杂度的角度来看：
- 直观计算法：O(n²)
- 累计元素法：O(n²)
- BI佐罗版累计元素法：O(n²)
- 分治+BI佐罗版累计元素法：O(n²/x)，x为分治的组数
- 交错算法：O(n)
- BI佐罗版交错算法：O(n)
- 最强算法：O(n/a)，n/a 为0元素的个数
本文从基础直通到顶级性能优化，不仅给出了说明，更加从理论和实践给出了解释和思考过程。主要是当有人说请你吃饭啊，打赌啊之类的时候可以激发人的潜能。主要是很有意思，精通了DAX，PowerBI就是你的玩具。
感谢联盟中的战友们，你们的智慧是无穷的。
本文文件模板专享给PowerBI战友联盟订阅战友，私信获取，您可以完全看到所有实现细节。同时以此文献给PowerBI四周年生日，PowerBI四岁了，已经逐渐成为该领域的最强者，我们将继续探索更多的乐趣，欢迎您赶快订阅会员，我们将帮助您超越99%的用户，成为专家。
另 线下VIP级培训进行中，我们让小白学会高手才能懂的大招思维模式。
BI佐罗 2019.07.25
帮您成为高手
