《从10亿个浮点数中找出最大的1万个》由会员分享，可在线阅读，更多相关《从10亿个浮点数中找出最大的1万个（8页珍藏版）》请在金锄头文库上搜索。
1、从从 10 亿个浮点数中找出最大的亿个浮点数中找出最大的 1 万个万个这是一道似易实难的题目，一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨，在常见计算机平台（如Win32）上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法，比如每次处理100万个数，然后再综合起来。不过这不是本文要讨论的主旨，所以本文把上题的10亿改为1亿，把浮点数改为整数，这样可以直接地完成这个问题，有利于清晰地讨论相关算法的优化（注2） 。 不假思索不假思索 拿到这道题，马上就会想到的方法是建立一个数组把1亿个数装起来，然后用for循环遍历
2、这个数组，找出最大的1万个数来。原因很简单，因为如果要找出最大的那个数，就是这样解决的；而找最大的1万个数，只是重复1万遍而已。templatevoid solution_1(T BigArr, T ResArr) for (int i = 0; i BigArridx)idx = j;ResArri = BigArridx;std:swap(BigArridx, BigArri);设BIG_ARR_SIZE 1亿，RES_ARR_SIZE = 1万，运行以上算法已经超过40分钟（注3） ，远远超过我们的可接受范围。 稍作思考稍作思考 从上面的代码可以看出跟SelectSort算法的核心代码是
3、一样的。因为SelectSort是一个O(n2)的算法（solution_1的时间复杂度为O(n*m)，因为solution_1没有将整个大数组全部排序） ，而我们又知道排序算法可以优化到O(nlogn)，那们是否可以从这方面入手使用更快的排序算法如MergeSor、QuickSort呢？但这些算法都不具备从大至小选择最大的N个数的功能，因此只有将1亿个数按从大到小用QuickSort排序，然后提取最前面的1万个。 templatevoid solution_2(T BigArr, T ResArr) std:sort(BigArr, BigArr + BIG_ARR_SIZE, std:gr
4、eater_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 里所有的元素都排
5、序了！而事实上只需找出最大的 1 万个即可，我们不是做了很多无用功吗？应该怎么样来消除这些无用功？ 如果你一时没有头绪，那就让我慢慢引导你。首先，发掘一个事实：如果这个大数组本身已经按从大到小有序，那么数组的前 1 万个元素就是结果；然后，可以假设这个大数组已经从大到小有序，并将前 1 万个元素放到结果数组；再次，事实上这结果数组里放的未必是最大的一万个，因此需要将前 1 万个数字后续的元素跟结果数组的最小的元素比较，如果所有后续的元素都比结果数组的最小元素还小，那结果数组就是想要的结果，如果某一后续的元素比结果数组的最小元素大，那就用它替换结果数组里最小的数字；最后，遍历完大数组，得到的结果
6、数组就是想要的结果了。templatevoid solution_3(T BigArr, T ResArr) /取最前面的一万个 memcpy(ResArr, BigArr, sizeof(T) * RES_ARR_SIZE);/标记是否发生过交换 bool bExchanged = true;/遍历后续的元素 for (int i = RES_ARR_SIZE; i ResArrj)idx = j;/这个后续元素比ResArr中最小的元素大，则替换。 if (BigArri ResArridx) bExchanged = true;ResArridx = BigArri; elsebExch
7、anged = false;上面的代码使用了一个布尔变量 bExchanged 标记是否发生过交换，这是一个前文没有谈到的优化手段用以标记元素交换的状态，可以大大减少查找 ResArr 中最小元素的次数。也对 solution_3 进行测试一下，结果用时 2.0 秒左右（不使用 bExchanged 则高达 32 分钟） ，远小于 solution_2 的用时。 深思熟虑深思熟虑 在进入下一步优化之前，分析一下 solution_3 的成功之处。第一、solution_3 的算法只遍历大数组一次，即它是一个 O(n)的算法，而 solution_1 是 O(n*m)的算法，solution_2
8、 是 O(nlogn)的算法，可见它在本质上有着天然的优越性；第二、在 solution_3 中引入了 bExchanged 这一标志变量，从测试数据可见引入 bExchanged 减少了约 99.99%的时间，这是一个非常大的成功。 上面这段话绝非仅仅说明了 solution_3 的优点，更重要的是把 solution_3 的主要矛盾摆上了桌面为什么一个O(n)的算法效率会跟 O(n*m)的算法差不多（不使用 bExchanged）？为什么使用了 bExchanged 能够减少 99.99%的时间？带着这两个问题再次审视 solution_3 的代码，发现 bExchanged 的引入实际上
9、减少了如下代码段的执行次数： for (idx = 0, j = 1; j ResArrj)idx = j;上面的代码段即是查找 ResArr 中最小元素的算法，分析它可知这是一个 O(n)的算法，到此时就水落石出了！原来虽然 solution_3 是一个 O(n)的算法，但因为内部使用的查找最小元素的算法也是 O(n)的算法，所以就退化为 O(n*m)的算法了。难怪不使用 bExchanged 使用的时间跟 solution_1 差不多；这也从反面证明了 solution_3 被上面的这一代码段导致性能退化。使用了 bExchanged 之后因为减少了很多查找最小元素的代码段执行，所以能够节
10、省 99.99%的时间！ Comment lxg1: 注意：ResArr中 的元素是按照从大到小排列的。至此可知元凶就是查找最小元素的代码段，但查找最小元素是必不可少的操作，在这个两难的情况下该怎么去优化呢？答案就是保持结果数组（即 ResArr）有序，那样的话最小的元素总是最后一个，从而省去查找最小元素的时间，解决上面的问题。但这也引入了一个新的问题：保持数组有序的插入算法的时间复杂度是 O(n)的，虽然在这个问题里插入的数次比例较小，但因为基数太大（1 亿） ，这一开销仍然会令本方案得不偿失。 难道就没有办法了吗？记得小学解应用题时老师教导过我们如果解题没有思路，那就多读几遍题目。再次审题
11、，注意到题目并没有要求找到的最大的 1 万个数要有序（注 4） ，这意味着可以通过如下算法来解决：1) 将BigArr的前1万个元素复制到ResArr并用QuickSort使ResArr有序，并定义变量MinElemIdx保存最小元素的索引，并定义变量ZoneBeginIdx保存可能发生交换的区域的最小索引； 2) 遍历BigArr其它的元素，如果某一元素比ResArr最小元素大，则将ResArr中MinElemIdx指向的元素替换，如果ZoneBeginIdx = MinElemIdx则扩展ZoneBeginIdx； 3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中寻找
12、最小元素，并用MinElemIdx保存其它索引； 4) 重复2)直至遍历完所有BigArr的元素。 依上算法，写代码如下： templatevoid 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;/可能产生交换的区域的最小索引 unsi
13、gned int ZoneBeginIdx = MinElemIdx;/遍历后续的元素 for (unsigned int i = RES_ARR_SIZE; i ResArrMinElemIdx) ResArrMinElemIdx = BigArri;if (MinElemIdx = ZoneBeginIdx)-ZoneBeginIdx;/查找最小元素 unsigned int idx = ZoneBeginIdx;unsigned int j = idx + 1;for (; j ResArrj)idx = j;MinElemIdx = idx;经过测试，同样情况下solution_4用时
14、约1.8秒，较solution_3效率略高，总算不负一番努力。 苦想冥思苦想冥思 这次优化从solution_4产生的输出来入手。把solution_4的输出写到文件，查看后发现数组基本无序了。这说明在程序运行一定时间后，频繁的替换几乎将原本有序的结果数组全部换血。结果数组被替换的元素越多，查找最小元素要遍历的范围就越大，当被替换的元素个数接近结果数组的大小时，solution_4就退化成solution_3。因为solution_4很快退化也就直接导致它的效率没有本质上的提高。 找出了原因，就应该找出一个解决的办法。通过上面的分析，知道solution_3和solution_4最消耗时间的是
15、查找最小元素这一操作，将它减少（或去除）才有可能从本质上提高效率。这样思路又回到保持结果数组有序这一条老路上来。在上一节我们谈到保持数组有序的插入算法将带来大量的元素移动，频繁的插入操作将使这一方法在效率上得不偿失。有没有办法让元素移动去掉呢？答案也是有的那就是使用链表。这时新的问题又来了，链表因为是非随机存取数据结构，插入前寻找位置的算法又是O(n)的。解决新的问题的答案是使用AVL树，但AVL树虽然插入和查找都是O(logn)，可是需要在插入后进行调整保持平衡，这又是一个耗费大量时间的操作。分析到现在，发现我们像进了迷宫，左冲右突都找不到突破口。 现在请静下来想一想，如果思考结果没有跳出上
16、面这个怪圈，那我不幸地告诉你：你被我误导了。这个故意的误导是要告诫大家：进行算法优化必须时刻保持自己头脑清醒，否则时刻都有可能陷入这样的迷宫当中。现在跳出这个怪圈重新思考，根据前文的分析，可知目标是减少（或去除）查找最小元素的操作次数（或查找时间） ，途径是让ResArr保持有序，难点在于给ResArr排序太费时。反过来想一想，是否需要时刻保持ResArr有序？答案为否，因为当查找最小元素需要遍历的范围较小时，速度还是很快的，这样就犯不着在每替换一个元素的时候都排序一次，而仅需要在无序元素较多的时候适时地排序即可（即保持查找最小元素要遍历的范围较小） 。这个思想有用吗？写代码来测试一下：templatevoid solution_5(T BigArr, T ResArr) /同solution_4，略/这个
