从10亿个浮点数中找出最大的1万个–很不错的一个问题（转）

- 日理万妓 2022-04-01 19:10 136阅读 0赞

主要参考：

http://www.cnblogs.com/yaozhongxiao/archive/2009/09/23/1572955.html

http://hi.baidu.com/sadawn/blog/item/4fdaee2433b7ed154d088d49.html

**解此问题的思想：**

首先，发掘一个事实：如果这个大数组本身已经按从大到小有序，那么数组的前1万个元素就是结果；然后，可以假设这个大数组已经从大到小有序，并将前1万个元素放到结果数组；再次，事实上这结果数组里放的未必是最大的一万个，因此需要将前1万个数字的**后续元素跟数组的最小元素比较**，**如果所有后续的元素**都比结**果数组的最小元素还小**，那结果数组就是想要的结果；如果某一**后续的元素比结果数组的最小元素大**，那就用它**替换**结果数组里最小的数字；最后，遍历完大数组，得到的结果数组就是想要的结果了。

所以最初想到的代码：

template <  class  T  >   
  
 void  solution\_3( T BigArr\[\], T ResArr\[\] )  
  
\{  
  
 // 取最前面的一万个   
   
memcpy( ResArr, BigArr,  sizeof (T)  \*  RES\_ARR\_SIZE );  
  
 // 标记是否发生过交换   
   
 bool  bExchanged  =  true ;  
  
 // 遍历后续的元素   
   
 for (  int  i  =  RES\_ARR\_SIZE; i  <  BIG\_ARR\_SIZE;  \++ i )  
  
\{  
  
 int  idx;  
  
 // 如果上一轮发生过交换   
   
 if ( bExchanged )  
  
\{  
  
 // 找出ResArr中最小的元素   
   
 int  j;  
  
 for ( idx  =  0 , j  =  1 ; j  <  RES\_ARR\_SIZE;  \++ j )  
  
\{  
  
 if ( ResArr\[idx\]  >  ResArr\[j\] )  
  
idx  =  j;  
  
\}  
  
\}  
  
 // 这个后续元素比ResArr中最小的元素大，则替换。   
   
 if ( BigArr\[i\]  >  ResArr\[idx\] )  
  
\{  
  
bExchanged  =  true ;  
  
ResArr\[idx\]  =  BigArr\[i\];  
  
\}  
  
 else   
  
bExchanged  =  false ;  
  
\}  
  
\}

上面的代码使用了一个布尔变量bExchanged标记是否发生过交换，这是一个前文没有谈到的优化手段——用以标记元素交换的状态，可以大大减少查找ResArr中最小元素的次数。也对solution\_3进行测试一下，结果用时2.0秒左右（不使用bExchanged则高达32分钟），远小于solution\_2的用时。

**一个比较好的解决方案：**

保持这一万个数为有序状态，然后与其中最小的比较。引伸出来的问题，一万个数排序会很麻烦，**维持有序的状态要更多的代价**

热点在哪里？**首先，遍历这10亿个数是肯定需要的**，但是这1万个数中，我们需要找出最小的。

**更好的解决方案：**

这1万个数必须排序好吗？**当然不需要**，**我们要的只是这个数组中最小的数字**，以用来比较，所以，**最小堆**在这里更加合适。

template <  class  T  >   
  
 void  solution\_3( T BigArr\[\], T ResArr\[\] )  
  
\{  
  
 // 取最前面的一万个   
   
memcpy( ResArr, BigArr,  sizeof (T)  \*  RES\_ARR\_SIZE );  
  
构建一小顶堆；  // 此处构建堆的代价为:theta(n)  
  
 // 标记是否发生过交换   
   
 bool  bExchanged  =  true ;  
  
 // 遍历后续的元素   
   
 for (  int  i  =  RES\_ARR\_SIZE; i  <  BIG\_ARR\_SIZE;  \++ i )  
  
\{  
  
 if ( BigArr\[i\]  >  ResArr\[ 1 \] )  // ResArr\[1\]是小顶堆第一个元素，即10000个数中最小的数   
   
\{  
  
ResArr\[idx\]  =  BigArr\[i\];  
  
Sift\_down(ResArr, 1 );  // 如果与小顶堆最小的数交换了，则要Sift\_down调整建堆；而Sift\_down最多只要比较  
  
 // 14次， 因为10000个数构成的完全二叉树只有14层   
   
\}  
  
\}  
  
\}

至此，这个算法的复杂度已经有了很大改进！

OK，到了这里是不是就完美了?我不会满足，如果算法上没有更好的方案，我会做多线程、平台优化、代码优化。

真的不能再优化了吗，堆只是一种常规的方案，斐波那契堆、multi-level buckets、HOT队列都是二叉堆的替代方案。