关于最小的k个数的讨论(top-k问题）

给定一个长度为 n 的序列，不妨设为 L1,L2,L3,….,Ln 。这个序列可以是任意一种排列，可能的排列有 n ！种，我们要找到最小的 k 个数，即找到这样的 k 个数 { Li(1) ， Li(2) ， Li(3)… ， Li(k)} ，并满足 Li(1)<=Li(2)<=Li(3)…<=Li(k) ；且对任意的 j ： k+1<=j<=n ，有 Li(k)<=Li(j) ，。

    例如：有这样一个长度为 8 的序列 {1 ， 4 ， 1 ， 5 ， 6 ， 7 ， 4* ， 6} ，找出最小的 3 个数，则结果为 {1 ， 1 ， 4} 或者 {1 ， 1 ， 4*} ，而不是最小的 k 个排序码 {1 ， 4 ， 5} 。

        我们只讨论 n 较大的情况，不妨设 n 至少百万数量级（ M ），下面对 k 进行逐一的分析：

    首先，回顾一下几大类排序

    冒泡排序

    选择排序： { 简单选择排序，锦标赛排序，堆排序 }

    快速排序，快速排序也可以看作一种选择排序。

    插入排序： { 直接插入排序，希尔排序 }

    归并排序：

    基数排序：

    计数排序：

    其中，适合 topk 问题的排序，只有冒泡排序，选择排序和快速排序，其余的排序都必须在排序最后一刻才能知道谁是最小的 k 个元素。

    如果 k = 1 ，此时很显然只能在简单选择排序和冒泡排序中考虑，因为锦标赛排序和堆排序初始化的成本太大。而冒泡排序在最坏情况下需要有 3 （ N-1 ）次移动，即如果初始排列正好是降序的情况。而简单选择排序，只需要扫描一遍，无需移动数据。但冒泡排序有一个其他排序都不具备的性质就是，如果初始排列恰好是有序的（升序），则一趟冒泡就可以知道这个信息。因此在 k > 1 时，可以考虑第一趟用冒泡的方法，既能判断出初始序列是否有序，也能够在 O （ n ）的时间内找到最小值，一举两得。

如果 1 < k < c1( 某个小常数 c1) ，则继续使用简单选择排序也是理想的，这个 c1 的临界点恰好是锦标赛排序和堆排序这种复杂排序初始化的时间开销引起的，当越过了 c1 的临界点后，锦标赛排序和堆排序的优势就发挥了出来。在这种情况下，简单选择排序，需要比较的次数为 n-1+n-2+…+n-c1 次。从内存的层次结构的角度看，复杂选择排序 ( 非线性 ) 和简单选择排序（线性）相比，缓存的命中率更低，换入换出的代价较大，且堆排序的初始化过程虽然复杂度也为 O （ N ），但在 n 很大的情况下，最坏情况下，系数接近 4 。

 

    如果 c1 <= k < c2 ，此时锦标赛排序会是更理想的选择，和堆排序相比，锦标赛排序树是一个完全二叉树（有些教材认为是满二叉树，这是不够好的），需要 n-1 个辅助空间，但锦标赛排序的初始化比较次数很少，只有 n-1 次(没有最好最坏之分)和堆排序的 4n（最坏情况下） 相比，在选出最小的元素后，选择后续的元素，堆排序和锦标赛排序都需要调整，锦标赛从底向上调整，堆排序从上向下调整，但锦标赛排序每上升一格只需要比较 1 次，堆排序需要比较 2 次（据称采用加速堆的方法，可以把这个系数降到 1 ，但需要付出 lglgn 的代价，同时付出代码的复杂性，本文不深入讨论这一点）。锦标赛排序总需要从叶子到根，而堆排序可能不需要，比如 n 个元素都相同的情况下，后者其他恰好符合堆性质而不需调整，或不需调整到叶子，总体情况看，锦标赛排序占据初始化的优势，在排序的早期应该能够胜出堆排序。当然锦标赛排序和堆排序都有优化提高的空间，就优化后的比较本文不作探讨。

 

    如果 c2 <= k < n/2 ，堆排序将会是更理想的选择，堆排序是一种原地排序，辅助空间为 O （ 1 ），因此空间局部性更好，特别是如果把堆看做一个数组，那么随着排序的进行，主要的计算都集中在数组的一段，而且局部性越来越好，因为数组的尾部已经是排好序的，没有访问的必要了。为了找出最小的 k 个数，堆排序将会使用小根堆，输出时从数组的尾部反序输出。

 

    如果 n/2 < k ，此时可以考虑用快速排序和堆排序结合的方法。前几趟用快速排序，快速压缩问题空间。使得问题转化为在 l 长度序列的排序 + m 个序列中找 top-k’ 个元素的问题或者在 L’ 长度序列中找 top-k 的问题。

    举个例子，例如 {4 ， 2 ， 1 ， 5 ， 6 ， 7 ， 4* ， 6 ， 8 ， 3} 中找前 5 个元素，则通过 4 的划分后得到 {3 ， 2 ， 1} 4 {5 ， 6 ， 7 ， 4* ， 6 ， 8} ，由于已知 4 是第 4 大的元素，则只需要将前一段全部排序输出，再输出 4 ，在输出后一段的第 5 – 4 = 1 个元素即可。如果是找前 2 个元素，问题就归结为在 {3,2,1} 中找最小的 2 个元素，则问题将大大化简。

 

    当 k 接近 n 的时候，毫无疑问使用快排序应该是最理想的了。

 

    最后，我们再讨论一下，当 n 足够大，以至于不能使用内排的情况。 由于这时问题的复杂性主要取决于读盘，因此我们希望的是找出最小的 k 个数的代价是只读一遍磁盘，同时考虑排序码还有其他卫星数据的情况。

   在这种情况下，直接选择排序，只有在 k = 1 时，才是最理想的。

   当 k > 1 时，选择堆排序时很理想的，因为锦标赛排序的辅组空间不能接受。可以设置一个大小为 k 的最大堆，该元素是整个堆最大的，如果在扫描磁盘的过程中，有排序码比这个更大则 pass ，如果更小，则把这个值淘汰掉，插入这个更小的值后，恢复成一个最大堆。扫描完毕后留在堆中的 k 个值，即为所求。 如果有其他卫星数据的情况下，堆的结点只需要增加相应的数据域或指针域即可。

 

    但问题是，假定实际的问题是需要在 100 亿网页 URL 中，找到 PV 最大的 top100 时（我们讨论的是最小，最大也可以用一样的方法）。我们使用了堆的方法，找到了结果，但是，领导突然需要看 top 1000 的 URL 时，还得做个大小为 1000 的堆再跑一遍，如果 topk 中的某些条件发生变化，比如 URL 长度在 512 以上的排除。。。可见，用堆的方法没有保存有价值的中间结果，这是很不理想的。

 

        什么才是理想的中间结果呢？我们考虑使用计数排序，例如这样一个整数序列 {4 ， 2 ， 1 ， 5 ， 6 ， 7 ， 4* ， 6 ， 8 ， 3} ，我们可以申请从 1 到 8 的 8 个计数器，组成一个数组，pennyliang_ counter[]={1,1,1,2,1,2,1,1} ，其中 pennyliang_counter [0] = 1 ，表示 1 出现了 1 次，penny_ counter[3] = 2 ，表示 4 出现了 2 次。输出时，按照计数器数组，输出即为有序序列，计数排序是线性的，而且计数器数组是理想的排序中间结果。

 

    对于 top-k PV 的问题，申请一个阈值以上的计数器，例如 1024 以上的 PV 数值才能有可能申请计数器，对 10k 以上的 PV 数值，才申请存储 URL 的空间，（后续的处理也有很多优化，本文不再展开）。扫描一趟磁盘，就可以生成这样的计数器数组，对于任意的处理要求，可以通过这个计数器数组直接得到，最坏情况也可以通过这个计数器数组加上再一次的磁盘扫描线性地得到。

        昨夜，我一夜难眠，就在想怎么把这个问题讲清楚，临到写的时候，还是感到很多内容无法展开，同时感到自己对这个问题的理解还不能定量的分析，因此甚是遗憾

 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/fatshaw/archive/2011/04/11/6315504.aspx