最近遇到一个笔试题,求高手解决!
问题如下：
10亿个浮点数中，找出最大的10个浮点数，写出一个高性能算法。
求解。
[解决办法]
分段排序不知道行不行
A.读取M*10条记录 （M>1) 排序取出最大的10条(排序算法根据每次读取的数量选择) 依大到小放进List[M*10]
B.List放满就排序 10条最大在最前面
C.还有记录就 继续 A 不过List开始的10条保留(从List[10]开始插入)
D.List 开始 10条是最大的
以上是单线程
在List填充了开始10条后
开M-1个线程(每个线程执行A步骤填充List[(1...M-1)*10])
然后List排序一次
不知道会不会快点
[解决办法]
确切的说，排序算法是不错，最好的时间复杂度是n*Log（n），对于本问题，大概需要9*10^9次比较，不过牵扯的元素移动也比较多。
可以考虑设置1个10元素数组，用前10个值来初始化，然后挨个读取后续值，如果发现比其中的最小元素都大，那么把这个最小元素替换掉，者只需要浏览一边数据即可，时间复杂度10*10^9，这个的优点是不需要排序算法的元素移动量
[解决办法]
楼上那些说排序的，都应该拉出去打40大板！
一个O(n)的遍历问题非要搞成O(n*lg(n))的排序问题，晕！
[解决办法]
晕，干嘛要用排序，一次循环加个二分法插入（如果再加个多线程应该就会快很多）
public static void main(String[] args) { int length = 1000000000; int[] numbers = new int[length]; // 假设到此已经对10亿个的数字初始化完毕 // 当然，也有可能，这10亿个数字是从别人地方来的，比如文件之类的 int[] maxNumbers = new int[10]; // 给maxNumbers赋值 System.arraycopy(numbers, 0, maxNumbers, 0, 10); // 对10个数字进行其排序 Arrays.sort(maxNumbers); for (int i = 10; i < length; i++) { binaryInsert(maxNumbers, numbers[i]); } } private static void binaryInsert(int[] numbers, int number) { // 二分法插入 // 将number插入已经排序好的numbers中 // 具体略过 }
[解决办法]
另外，到现在为止
插入10亿表到数据我已经等不下去了
环境：2003 + sql server 2000
插入3236347，花了16分钟多
算我机器慢，大家比我快上10倍，也要花上
49
分钟
[解决办法]
void solution_2( T BigArr[], T ResArr[] )
{
std::sort( BigArr, BigArr + BIG_ARR_SIZE, std::greater_equal() );
memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );
}
因为STL里的sort算法使用的是QuickSort，在这里直接拿来用了，是因为不想写一个写一个众人皆知的QuickSort代码来占篇幅（而且STL的sort高度优化、速度快）。
对solution_2进行测试，运行时间是32秒，约为solution_1的1.5%的时间，已经取得了几何数量级的进展。
深入思考
压抑住兴奋回头再仔细看看solution_2，你将发现一个大问题，那就是在solution_2里所有的元素都排序了！而事实上只需找出最大的1万个即可，我们不是做了很多无用功吗？应该怎么样来消除这些无用功？
如果你一时没有头绪，那就让我慢慢引导你。首先，发掘一个事实：如果这个大数组本身已经按从大到小有序，那么数组的前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的用时。
深思熟虑
在进入下一步优化之前，分析一下solution_3的成功之处。第一、solution_3的算法只遍历大数组一次，即它是一个O(n)的算法，而solution_1是O(n*m)的算法，solution_2是O(nlogn)的算法，可见它在本质上有着天然的优越性；第二、在solution_3中引入了bExchanged这一标志变量，从测试数据可见引入bExchanged减少了约99.99%的时间，这是一个非常大的成功。
上面这段话绝非仅仅说明了solution_3的优点，更重要的是把solution_3的主要矛盾摆上了桌面——为什么一个O(n)的算法效率会跟O(n*m)的算法差不多（不使用bExchanged）？为什么使用了bExchanged能够减少99.99%的时间？带着这两个问题再次审视solution_3的代码，发现bExchanged的引入实际上减少了如下代码段的执行次数：
for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j )
{
if( ResArr[idx] > ResArr[j] )
idx = j;
}
上面的代码段即是查找ResArr中最小元素的算法，分析它可知这是一个O(n)的算法，到此时就水落石出了！原来虽然solution_3是一个O(n)的算法，但因为内部使用的查找最小元素的算法也是O(n)的算法，所以就退化为O(n*m)的算法了。难怪不使用bExchanged使用的时间跟solution_1差不多；这也从反面证明了solution_3被上面的这一代码段导致性能退化。使用了bExchanged之后因为减少了很多查找最小元素的代码段执行，所以能够节省99.99%的时间！
至此可知元凶就是查找最小元素的代码段，但查找最小元素是必不可少的操作，在这个两难的情况下该怎么去优化呢？答案就是保持结果数组（即ResArr）有序，那样的话最小的元素总是最后一个，从而省去查找最小元素的时间，解决上面的问题。但这也引入了一个新的问题：保持数组有序的插入算法的时间复杂度是O(n)的，虽然在这个问题里插入的数次比例较小，但因为基数太大（1亿），这一开销仍然会令本方案得不偿失。
难道就没有办法了吗？记得小学解应用题时老师教导过我们如果解题没有思路，那就多读几遍题目。再次审题，注意到题目并没有要求找到的最大的1万个数要有序（注4），这意味着可以通过如下算法来解决：
1) 将BigArr的前1万个元素复制到ResArr并用QuickSort使ResArr有序，并定义变量MinElemIdx保存最小元素的索引，并定义变量ZoneBeginIdx保存可能发生交换的区域的最小索引；
2) 遍历BigArr其它的元素，如果某一元素比ResArr最小元素小，则将ResArr中MinElemIdx指向的元素替换，如果ZoneBeginIdx == MinElemIdx则扩展ZoneBeginIdx；
3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中寻找最小元素，并用MinElemIdx保存其它索引；
4) 重复2)直至遍历完所有BigArr的元素。
依上算法，写代码如下：
template< class T, class I >
void solution_4( T BigArr[], T ResArr[] )
{
//取最前面的一万个
memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );
//排序
std::sort( ResArr, ResArr + RES_ARR_SIZE, std::greater_equal() );
//最小元素索引
unsigned int MinElemIdx = RES_ARR_SIZE - 1;
//可能产生交换的区域的最小索引
unsigned int ZoneBeginIdx = MinElemIdx;
//遍历后续的元素
for( unsigned int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )
{
//这个后续元素比ResArr中最小的元素大，则替换。
if( BigArr[i] > ResArr[MinElemIdx] )
{
ResArr[MinElemIdx] = BigArr[i];
if( MinElemIdx == ZoneBeginIdx )
--ZoneBeginIdx;
//查找最小元素
unsigned int idx = ZoneBeginIdx;
unsigned int j = idx + 1;
for( ; j < RES_ARR_SIZE; ++j )
{
if( ResArr[idx] > ResArr[j] )
idx = j;
}
MinElemIdx = idx;
}
}
}
经过测试，同样情况下solution_4用时约1.8秒，较solution_3效率略高，总算不负一番努力
[解决办法]
1.取前十个数组成长度为10的数组
2.对剩余的数做循环，依次插入，然后对十一个数做排序删除之最小的一个，然后坐下一次循环。
3.最后得到十个数。
（不考虑十亿个数的存放位置）
[解决办法]
既然是笔试，当然是概念题了，10亿个浮点数不知道JAVA占用多少字节，C/C++是3.7GB大小，既然存在3.7GB的数组，那么内存就不用管了，分成1千万一组，那就是100组，于是开100个线程，每线程100万的排序，不管用什么排序法，谁最快用用谁，100个线程排完了，就剩10000个元素的数组了，这10000个元素的数组你想怎么排就怎么排
[解决办法]
1、首先至少有一个循环，这个肯定不能少
2、因为只有10个数，因此用数组实现其实效率并不比链表慢，因为链表也同样存在指针复制的操作。
c++ 实现
#include "stdafx.h"#include "iostream"using namespace std;class CLoopArray{private: float _dat[10];public: CLoopArray() { for(int i=0;i<10;i++) _dat[i]=0; } //插入值，如果大于某个已有值，则插入，否则不插入 void InsertValue(float value) { if(value <= _dat[9])return; for(int i=0;i<9;i++) { if(_dat[i] < value) { for(int j=9;j>i;j--) { _dat[j] = _dat[j-1]; } _dat[i]= value; break; //跳出循环 } } } //取对应值 float& operator[](int index) { if( (index >=0) && (index <10)) { return _dat[index]; } }};int _tmain(int argc, _TCHAR* argv[]){ CLoopArray la; float v,v2; for(int i=0;i<10000000000;i++) { v2 = rand(); if(v2 == 0) v2 =1; //防止除零错误 v = rand()/ v2; la.InsertValue(v); } for(int i=0;i<10;i++) { cout << la[i] <<endl; } return 0;}