PowerBI 最大连续元素数终极算法性能优化详解

最近，有网友发来信息，称实现了超过我们此前公布的算法。有伙伴提问老师是否可以给出更加优化的算法，并介绍如何进行性能的优化，答案是：肯定的。由于本案例有非常重要的代表性意义，故在这里记录之。

本文给出优化的通用思路和调试技巧，总体思路是：

• 在特性思路下，使用调试技巧进行优化。
• 要想超越固有模式，必须变换思路实现，再使用调试技巧进行优化。

由于此前已经充分说明了上下文，这里不再赘述，直接对各种算法做出比对。

通用数据结构

为了清晰地对比，先给出通用的结构：

只不过，该序列可能是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元素的个数

本文从基础直通到顶级性能优化，不仅给出了说明，更加从理论和实践给出了解释和思考过程。主要是当有人说请你吃饭啊，打赌啊之类的时候可以激发人的潜能。

感谢联盟中的战友们，你们的智慧是无穷的。

本文文件专享给PowerBI战友联盟订阅战友，同时以此文献给PowerBI四周年生日，PowerBI四岁了，已经逐渐成为该领域的最强者，我们将继续探索更多的乐趣，欢迎您赶快订阅会员，我们将帮助您超越99%的用户，成为专家。