快速求和算法的比较

• 下载演示C++代码 - 3.3 KB

布局

• 引言
• 编程语言中数学序列的表示
• 树能否提供高效的序列？
• 层链接完美二叉树
• 排名算法
• 带数据压缩的数组表示
• 求和算法
• 应用
• 注释

引言

标准的顺序求和具有线性运行时间。本文讨论的算法可以在对数时间内计算连续元素的和。它们是通用的，并且可以在简单的单处理器系统上运行。替代的并行计算需要超级计算机才能达到相同的运行时间。然而，即使在拥有无限处理器的理想机器中，并行求和在总操作数方面也具有很高的线性计算成本。

有几种数据结构支持具有对数运行时间的快速求和算法。在本文中，我们考虑一个完美二叉树，它可以表示为节点的链式结构和数组。比较不同的表示方法有助于更好地解释快速求和算法的各个方面。

第一个有趣的现象是，我们得到了与Fenwick最初为二项树的数组表示提出的相同的求和算法[1]。该算法的吸引人之处在于代码量小，易于编写实现。然而，这种优势是以表面上的简单性为代价的。实现隐藏了快速求和算法背后的思想。它并不明显它是如何工作的，数组表示的局限性是什么。这个事实不应该令人惊讶，因为该算法是为数据压缩而设计的。其实现可以被视为“压缩”的。

另一个有趣的现象是，相同的数组表示不仅可以支持最优的，还可以支持“解压缩”的更长形式的快速求和算法，这些算法与链式节点树中的算法类似[2]。“解压缩”实现可用于说明快速求和算法的基本原理。仅使用链式树描述这些算法将需要更多的代码和解释空间。

编程语言中数学序列的表示

求和算法应用于序列，序列可以存储有序和无序的数据集。序列的基本属性是为了识别目的而对元素进行计数。根据定义，在数学序列中，每个元素都由其秩标识，即该元素之前的元素数量。根据这个定义，序列中给定元素的秩是相同整数值1的特殊和。这个事实表明，计算部分和和元素秩的快速算法应该彼此密切相关。向前跳跃，我们可以说前者算法可以被认为是后者的扩展。

序列最广泛使用的表示基于数组和链表。数组是一种主要的底层数据结构，可以在用户算法中表示序列。基于数组的容器由于可以通过下标或索引运算符快速随机访问元素而成为许多应用程序的不错选择：value=array[index]。在算法的设计和分析中，该运算符的运行时间被认为是恒定的。另一种可以表示序列的众所周知的数据结构是链表。链式节点结构在列表中有效地支持快速顺序处理。访问远距离元素很慢：具有线性运行时间。

树能否提供高效的序列？

乍一看，基于链式树的序列似乎不是一个好主意。大多数实际应用使用平衡搜索树，它们存储有序数据集以保证各种操作的高效率。此类树中的元素按其键排序。元素的秩不影响顺序，因为它是元素固有的属性。它是用户算法分配给元素的外部标签。它还指定了元素在容器中的位置。秩值取决于键的顺序。有序树中随机访问的效率与链表基本相同。这就是为什么，与数组类似，并且与链表相似，典型的搜索树不支持下标运算符。

序列的高效表示使用一种特殊的链式树。通过应用增强[3]的方法，可以提高这些树中随机访问的性能。这种方法允许我们通过向现有数据结构节点插入新数据来设计和微调算法。增强树可以存储不同算法的多种数据集。表示无序序列的树仅支持快速秩算法，这是数组中下标运算符的替代方案。对于有序序列，增强树提供两种通过秩和键的快速搜索算法。在本文中，我们仅讨论无序序列。增强树中元素的随机访问不如数组快。它具有对数时间，比恒定时间差。然而，对数时间比基本搜索树和链表提供的线性时间要好得多。

数组和链式树序列变体之间的区别可以总结如下。数组直接由编程语言支持下标运算符。链式树必须提供一种快速搜索方法来通过秩访问元素。树不仅存储给定序列的元素，还存储表示特定的数据。在空间和时间效率方面，数组通常优于树。

层链接完美二叉树

在本文中，我们考虑了一种层链接的二叉树变体，如图1所示。主数据结构由黑色链接连接的正方形节点组成。在结构方面，它类似于跳表。附加的父子关系树，以绿色显示，通常称为完美二叉树。该树也是一个完全和完整的二叉树。

图1：层链接完美二叉树。父子关系用绿色绘制。

对于本文讨论的算法，这种树提供了重要的优势。从任何节点到其父节点、子节点和兄弟节点的链接集支持高效的树遍历。该树支持几何解释，这简化了求和算法的说明和解释。

在几何模型中，两个节点之间的水平链接的长度代表存储在连接节点之一中的值。对于求和算法，垂直链接没有长度。垂直链接仅负责不同层级节点之间的连接。求和运算和此类树的遍历遵循简单的规则。遍历水平链接等同于加或减一个值，而遍历垂直链接对累积和没有贡献。

图2说明了快速求和算法的主要思想。上面树层的一个段的长度等于最深层许多段的长度之和，最深层存储了给定序列的所有元素。虽然有很多方法可以获得最深层连续元素的和，但直观上很明显，快速方法应该使用该数据结构的较高层而不是较低层。最高效的算法应使用最少数量的段。

图2：层链接二叉树自顶向下遍历的说明。所示的红色路径比蓝色路径更有效。

在讨论的这个阶段，我们故意在图2中不显示数据。即使特定的数据集非常复杂，快速求和算法的效率主要取决于第一个节点和最后一个节点之间路径上的链接数量。结果值是通过对访问节点中的值的求和来计算的。

排名算法

所有可能的数据集中最简单的是序列元素计数的集合。图3使用一棵树说明了这样的数据集，该树在最深层的每个节点中存储整数值1。计数累积的值显示在水平链接的右侧节点中。这样的内部节点中的每个节点都是以该节点为根的子树的父节点。因此，内部节点中的计数提供了相应子树中给定序列的连续元素的数量，该数量等于序列范围内元素的数量。请注意完美二叉树的一个简单而重要的属性，即每个计数都是2的幂。计数在树的每个层级上具有相同的值。

图3：具有计数数据集的层链接完美二叉树。最底行的数字显示了序列元素秩的值，这些值存储在这种树的最深层的节点中。

快速秩算法表示自顶向下搜索最深层中包含由其秩指定的序列元素的节点。搜索涉及对存储在树内部节点中的计数的加法运算以及对累积值与给定秩的比较运算。除了加法运算的使用外，搜索与搜索树中按键搜索相似。红色路径说明了针对秩为5的节点的搜索和计数计算。

带数据压缩的数组表示

如前所述，二叉树的数组实现比链式节点数据结构具有更好的性能和空间效率。这种高效数组实现的一个经典例子是基于完全二叉树的堆。这种方法可以应用于层链接的完美二叉树，但在本文中，我们有兴趣考虑一种更节省空间的数组实现。

数据压缩方法基于每个父节点存储其子节点值之和的属性。在这种二叉树中，一个子节点的值允许我们找到另一个子节点的值。因此，即使树只存储一个子节点的值，快速求和算法也可以工作。此外，为了获得最佳性能，此类算法应避免使用第二个子节点水平链接。与通过合适父节点的路径相比，此遍历可能会使路径变长。

图4显示了一棵具有简化数据集的树，用于计算最深层节点秩。该树将所有重要数据存储在每组的第一个子节点中。第二个子节点中所有未使用的值都设置为零。相应的虚线链接不被最优求和算法使用。为了比较，图3中的树具有相同的结构，但存储了完整的数据集。

图4：具有最小重要数据集的完美二叉树。序列值的计数显示为二进制表示。红色路径说明了秩为5的最优计算。

计数的二进制表示有助于说明所讨论算法的以下方面。当快速自顶向下秩算法遍历树的所有层时，它会产生与指定秩值二进制表示中的位序列完全相同的位序列。每个访问的层都为结果贡献二进制表示中的1或0。图4中的示例提供了整数5：(0101) = 0x8 + 1x4 + 0x2 + 1x1 = 4 + 1。

图5说明了存储无序序列的常规数组如何转换为支持更快速求和的压缩数组。输入数组显示在底部。为了简化代码，该数组在第一个位置有一个额外的零值。所有数组值都传递到层链接完美二叉树的最深层节点。随着树构建算法向上移动，它为每个父节点计算其子节点值的总和，并将新层中的节点数量减少2的因子。写入结果压缩数组的重要值存储在垂直链的顶部节点中。所有其他预先计算的数据不被最优求和算法使用，但它们是构建树所必需的。在几何表示方面，压缩数组仅保存实心水平链接的长度。虚线链接不被最优求和算法遍历。它们在结果数组中不被保存。在代数形式中，给定序列{ a, b, c, d, e, f, g, h }，压缩数组存储以下总和：{ 0, a, a+b, c, a+b+c+d, e, e+f, g, a+b+c+d+e+f+g+h }。

图5：使用层链接完美二叉树构建压缩数组的自底向上图。此树中的每个节点都存储一个计数以及序列元素范围值的总和，这些元素来自底部数组。

所得的压缩数组也可以看作是扁平化的层链接完美二叉树。这是通过从树中移除0位节点（参见图4）的垂直链来实现的。在结果数组中，链式树的每个垂直链由顶层节点中的值表示，该顶层节点是图4中的1位节点。树中垂直链的数量由给定序列中的值数量决定。因此，所有重要树数据都可以保存在与原始序列基本相同长度的数组中。构建的数组仅在第一个位置有一个额外的零值。

求和算法

压缩数组表示支持许多快速求和算法，这些算法与二进制表示中的秩计算相呼应。算法的比较讨论基于这样一个事实：在完美二叉树中，具有最小计数数据集的层链接节点结构匹配秩的二进制表示中的位序列（参见图4）。我们从简单变体开始讨论，该变体等同于层链接完美二叉树中的自顶向下求和。该算法如图2所示。

int  sum_top_down ( const int  k ) const 
{
    int         sum   = 0 ; 
    int         count = 0 ;     
    for ( int   bit   = 1<<30 ; count < k ; bit >>= 1 )
    {
        if ( k & bit ) 
        {
            count += bit ;  
            sum   += m_tree [ count ] ; 
        }
    }

    return sum ; 
}

简而言之，该算法扫描输入秩k的二进制表示的位序列，并从压缩数组m_tree中提取数据以计算前k个值的总和。算法的详细工作方式如下。代码使用变量bit，该变量是2的幂，在算法执行期间只有一个1位。该测试位被初始化为32位整数的最显著位（1<<30），并通过操作bit >>= 1（除以2）进行移位。操作(k & bit)对于选择与秩k的二进制表示中的位相关的数据进行处理很重要。当k的当前位为1时，执行所有结果的计算。变量count累积已处理的第一个元素的数量。其值通过给定序列的当前范围大小count += bit来增加。同时，相同范围值的预计算子和被添加到此算法的结果sum += m_tree[count]。

与扁平压缩数组不同，层链接完美二叉树具有垂直维度。等效的求和算法表示自顶向下遍历与节点中存储的数据的计算操作相结合。链式树的顶层对应于压缩数组大小中最显著的位。对于链式树中秩的二进制表示中的0位，没有处理，这相当于通过0位节点（参见图4）的垂直遍历。秩中的1位k对应于链式树中水平链接的遍历。该算法使用相同的两次加法运算count和sum，不同之处在于当前序列元素范围的count和sum的值都存储在树的节点中（参见图5）。

在函数sum_top_down()中，for循环在比较操作( count < k )返回false时停止。这意味着给定范围内的所有元素都已处理完毕，并且可以在算法到达二叉树的最深层之前获得结果。这种提前退出有助于提高此求和算法的运行时间。如果我们用以下条件实现相同的自顶向下算法在for循环中

for ( int   bit = 1<<30 ; bit > 0 ; bit >>= 1 ) 

然后算法访问树的所有层，并在秩k引用的最深层节点处终止。在数组实现方面，算法测试秩k的每一位，并且计数的总和表示秩在二进制表示中的直接计算。

层链接完美二叉树中的快速自底向上求和算法仅在用户算法提供指向最深层节点的指针时才可能。由于节点由客户端识别，并且搜索上层第一个节点相对简单，因此该算法的主要任务是计算已处理元素的数量。它同时计算指定节点的秩和相应的局部和。其性能与自顶向下算法相同。 

与链式节点树不同，数组表示不施加类似的指向节点指针的限制，因为它可以利用恒定时间按秩访问其存储的任何元素。代码与前面的算法类似

    
int  sum_bottom_up ( const int  k ) const 
{
    int         sum   = 0 ; 
    int         count = 0 ; 
    int         i     = k ; 
    for ( int   bit   = 1 ; count < k ; bit <<= 1 ) 
    {
        if ( k & bit ) 
        {
            sum   += m_tree [ i ] ; 
            count += bit ;  
            i     -= bit ;  
        }
    }

    return sum ; 
}

主要区别在于，该算法以相反的顺序扫描树数据。最初，在最深层，数组m_tree的索引等于输入秩i=k。当算法向上移动一级时，索引会减去已处理范围的大小i -= bit（2的幂）。

基于计数已处理元素数量的数组算法相当快。尽管如此，它们并非最优，因为不必要的对秩k中的0位进行测试会增加迭代次数和运行时间。因此，我们可以提出以下问题：是否可以设计一种更有效的算法来解决这个问题？这个问题的肯定答案是Fenwick最初为二项树提出的算法[1]

int  sum_optimal ( int  k ) const 
{
    int     sum = 0 ; 
    while ( k > 0 ) 
    {
        sum += m_tree [ k ] ; 
        k = k & ( k - 1 ) ; 
    }

    return sum ; 
}

该算法看起来异常简单，但并非所有细节都可能清晰。它类似于sum_bottom_up()算法，因为两种算法都以相反的自底向上顺序处理数据。然而，它并不那么简单，因为它代表了第一个自底向上算法的“压缩”变体。

该算法的关键特征是位运算k&(k-1)，它会移除秩k的二进制表示中最不显著的位。该算法具有以下优点。代码不需要像count这样的特殊变量来处理已处理的序列元素。位移除操作会减去当前范围的大小并更新要处理的元素数量。作为数组的索引，k的更新值在压缩数组m_tree[k]中为下一次算法迭代提供了新的位置。这个新位置始终有效，这解释了为什么该算法不测试输入秩k的每一位。

此算法的迭代次数等于1位的数量。避免对0位进行测试可提高性能，与其他讨论的求和算法相比。在测试秩k的每一位并计算已处理元素数量的算法sum_bottom_up()中，迭代次数由输入秩k中最显著位的确切位置决定。在测试每一位的最差性能算法中，迭代次数是恒定的，等于算法使用的整数类型的总位数。

在链式树上算法的一般上下文中，这里讨论的快速求和变体基于最短路径算法。对于本文图中的层链接完美二叉树，这一点可能不明显。当序列中的元素数量很少时，无用0位节点的垂直遍历对总运行时间有可衡量的贡献。在具有大量子节点的树（例如层链接B+树[2]）中，使用最短路径进行计算的性能优势更为明显。

压缩数组表示具有通过计算其位置来访问所需元素的恒定时间的重要优势。这一优势使我们能够优化快速求和算法的迭代次数，并使其等于输入秩k的二进制表示中的1位的数量。对于层链接完美二叉树，这种最优性是不可能的。它需要找到一条最短路径，该路径仅使用最少数量的水平链接。然而，最短路径算法无法避免垂直链接的遍历和存储0位的节点的访问。层链接树的基本限制是它仅提供对给定节点邻居的快速访问。

应用

快速求和算法在许多实际应用中有用，特别是在大型数据库、大数据和数据科学中。它们能够非常有效地计算重要的统计参数：平均值和标准差。使用普通数组的求和算法的线性性能对于此类应用程序来说是不够的。可以通过预先计算的部分和数组来解决这个问题，该数组保证了计算任何连续元素和的恒定时间。然而，这个数组对于更新操作（修改现有元素的值）来说太慢了。在前缀和数组中，它具有线性运行时间，而在普通数组中，它是一个恒定时间操作。这些数组中的每一个都有一个效率低下的操作，可能导致整体性能下降。压缩数组表示同时提供了高效的求和和高效的更新操作。尽管有这个优势，压缩表示也有一些限制，可能使其在某些应用中的使用不是最优的。

插入和删除操作会改变数据集中的元素数量，需要对整个数组进行相当昂贵的重新计算，除了两个操作：在数组末尾追加一个元素和删除最后一个元素。压缩删除了原始数据集中的每第二个元素。因此，用户算法应存储原始数据集的副本，或通过差值sum(k) - sum(k-1)重新计算每个删除的元素。重新计算原始数据的需要可能导致非平凡的问题。这种重新计算的高效率需要一个逆运算，而逆运算在某些情况下可能不存在。特别是，在任何元素范围内计算最小值和最大值的运行时间比计算总和、平均值和标准差要差得多。

数组表示的局限性通常通过增强树来解决。在需要广泛高效插入和删除操作的应用中，首选B、B+或红黑树。关于C++中的半群的文章解释了如何使用一种数据结构以相同的对数运行时间来计算总和、最小值和最大值。

注释

互联网上有大量关于压缩数组表示不同深度描述的资源。这些以及相关数据结构在关于Fenwick树、二进制索引树、二项树和线段树的文章中进行了讨论。不幸的是，术语上的差异使理解这些有趣的数据结构及其支持的算法变得复杂。也许混淆的主要来源是“树”一词的使用。通常，这个术语表示一个存储数据集的容器。此外，树结构还用于说明算法的动态。在本文中，图中显示的树代表了数据集的容器。操作的动态用与链接并行的箭头说明。

压缩数组表示的另一个潜在问题与第一个位置的附加零值有关。这种方法使给定序列的表示成为1基的。0基数组实现不使用附加元素。组合0基和1基数组实现的 कोड是不安全的。它会导致用户算法中的错误。

参考文献

1. P.M. Fenwick。Cumulative frequency tables的新数据结构。Software-Practice and Experience, 24(3)，页码327-336，1994。

2. V. Stadnik。使用增强数据结构的快速顺序求和算法。arXiv:1404.1560，2014。（http://arxiv.org/abs/1404.1560）

3. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein。Introduction to Algorithms。第二版，MIT Press and McGraw-Hill，剑桥（MA），2001。