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

Question

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

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

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

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

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

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

Answer 1

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

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

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

使用概率分布进行排序的自适应数据分区

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

Answer 2

听起来您可能想要阅读自我改进算法:它们实现了任意输入分布的最终预期运行时间.

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

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

Answer 3

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

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

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

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

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

Answer 4

计算机排序算法可以分为两类,基于比较的排序和基于非比较的排序.对于基于比较的排序,其最佳情况下的排序时间为Ω(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？numumber = 5170434&tag = 1

Answer 5

只要您可以在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静态完美散列.

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