首页 文章

已知统计分布数据的排序算法?

提问于
浏览
60

我刚想到,如果你对要排序的数据的分布(在统计意义上)有所了解,那么如果考虑到这些信息,排序算法的性能可能会受益 .

所以我的问题是,是否有任何排序算法考虑到这种信息?他们有多好?

编辑:一个示例澄清:如果您知道数据的分布是高斯分布,则可以在处理数据时动态估计平均值和平均值 . 这将为您估算每个数字的最终位置,您可以使用它来将它们放置在最终位置附近 .

编辑#2:我很惊讶答案不是一个维基链接到一个讨论这个问题的页面 . 这不是一个非常常见的情况(例如高斯情况)?

编辑#3:我正在为这个问题增加一笔赏金,因为我正在寻找明确的答案来源,而不是猜测 . 类似于“在高斯分布式数据的情况下,XYZ算法平均速度最快,正如Smith等人[1]所证实的那样” . 但欢迎任何其他信息 .

Note :我会将赏金奖励给得票最高的答案 . 明智地投票!

7 回答

  • 6

    如果您正在排序的数据具有已知分布,我将使用 Bucket Sort 算法 . 您可以为它添加一些额外的逻辑,以便您根据分布的属性计算各种桶的大小和/或位置(例如:对于Gaussian,您可能每个(sigma / k)远离均值,其中sigma是分布的标准偏差) .

    通过以这种方式获得已知的分布并修改标准的Bucket Sort算法,您可能会获得 Histogram Sort 算法或与其接近的算法 . 当然,您的算法在计算上会比直方图排序算法快,因为您可能不需要进行第一次传递(在链接中描述),因为您已经知道了分布 .

    Edit: 给出了您的问题的新标准,(虽然我以前的答案有关直方图排序链接到可敬的NIST并包含性能信息),这是来自国际并行处理 Session 的同行评审期刊文章:

    Adaptive Data Partition for Sorting Using Probability Distribution

    作者声称这种算法比流行的快速排序算法具有更好的性能(高达30%) .

  • 4

    听起来你可能想要阅读Self-Improving Algorithms:它们实现了任意输入分布的最终预期运行时间 .

    我们为两个问题提供了这样的自我改进算法:(i)对数字序列进行排序,以及(ii)计算平面点集的Delaunay三角剖分 . 两种算法均实现最佳预期限制复杂性算法从训练阶段开始,在训练阶段期间,他们收集有关输入分布的信息,然后是静态状态,其中算法适应其优化的化身 .

    如果你已经知道你的输入分布大致是高斯分布,那么在空间复杂度方面可能另一种方法会更有效,但就预期的运行时间而言,这是一个相当奇妙的结果 .

  • 5

    知道了数据源分布,就可以构建一个好的哈希函数 . 很好地了解分布,散列函数可以证明是完美的散列函数,或者对于许多输入向量来说接近完美 .

    这样的函数将大小为n的输入分成n个区间,使得最小的项目将映射到第一个区域,并且最大的项目将映射到最后的区域 . 当哈希是完美的 - 我们将实现排序只是将所有项目插入到箱子中 .

    将所有项插入哈希表,然后按顺序提取它们将是哈希完美时的O(n)(假设哈希函数计算成本为O(1),并且下划线哈希数据结构操作为O(1) ) .

    我会使用一组斐波那契堆来实现哈希表 .

    对于哈希函数不完美(但仍然接近完美)的输入向量,它仍然比O(nlogn)好得多 . 当它是完美的 - 它将是O(n) . 我不确定如何计算平均复杂度,但如果被迫,我会打赌O(nloglogn) .

  • 6

    计算机排序算法可以分为两类,基于比较的排序和基于非比较的排序 . 对于基于比较的排序,其中的排序时间最佳情况是Ω(nlogn),而在最坏情况下,性能排序时间可以上升到O(n2) . 近年来,已经提出了一些改进的算法来加速基于比较的排序,例如根据数据分布特征的高级快速排序 . 但是,这些算法的平均排序时间仅为Ω(nlog2n),只有在最佳情况下才能达到O(n) . 与基于比较的排序不同,基于非比较的排序(例如计数排序,桶排序和基数排序)主要取决于密钥和地址计算 . 当密钥的值在1到m的范围内是有限的时,非基于比较的排序的计算复杂度是O(m n) . 特别是,当m = O(n)时,分选时间可以达到O(n) . 然而,当m = n2,n3,...时,不能获得线性分类时间的上限 . 在基于非比较的排序中,桶排序将具有相似密钥的一组记录分配到适当的“桶”中,然后将另一排序算法应用于每个桶中的记录 . 使用存储桶排序,将记录划分为m个桶的时间较少,而每个存储桶中只包含少量记录,因此可以非常快速地应用“清理排序”算法 . 因此,与Ω(nlogn)算法相比,桶分类有可能渐近地节省排序时间 . 显然,如何将所有记录均匀地分配到桶中在桶分类中起着关键作用 . 因此,您需要一种根据数据分布构造哈希函数的方法,该方法用于根据每条记录的密钥将n条记录均匀分布到n个桶中 . 因此,在任何情况下,所提出的桶分类算法的分类时间将达到O(n) .

    查看本文:http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

  • 18

    只要您可以在O(1)时间内计算每个点的CDF,Bucket sort就会为您提供线性时间排序算法 .

    您也可以在其他地方查找的算法如下:

    a = array(0, n - 1, [])          // create an empty list for each bucket
    for x in input:
      a[floor(n * cdf(x))].append(x) // O(1) time for each x
    input.clear()
    for i in {0,...,n - 1}:
      // this sorting step costs O(|a[i]|^2) time for each bucket
      // but most buckets are small and the cost is O(1) per bucket in expectation
      insertion_sort(a[i])
      input.concatenate(a[i])
    

    运行时间是期望的O(n)因为期望有O(n)对(x,y)使得x和y落在同一个桶中,并且插入排序的运行时间恰好是O(n#对)在同一桶) . 分析类似于FKS static perfect hashing .

    编辑:如果你不知道分布,但你知道它是什么样的家族,你可以通过计算均值和方差来估计O(n)中的分布,在高斯情况下,然后使用相同的算法(顺便说一下) ,在这种情况下计算cdf是非常重要的) .

  • 3

    您可以在快速排序中使用该信息来选择透视值 . 我认为这将提高算法远离O(N ** 2)最坏情况复杂度的概率 .

  • 33

    我认为cycle sort属于这一类 . 当您知道希望每个元素最终到达的确切位置时,可以使用它 .

    Cyclesort有一些很好的属性 - 对于某些受限制的数据类型,它可以在线性时间内进行稳定的就地排序,同时保证每个元素最多移动一次 .

相关问题