[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在海量数据中，此时普通的数组、链表、Hash、树等等结构有无效了，因为内存空间放不下了。而常规的递归、排序，回溯、贪心和动态规划等思想也无效了，因为执行都会超时，必须另外想办法。这类问题该如何下手呢？这里介绍三种非常典型的思路：

使用位存储，使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组，如果用整数存储需要16GB左右的空间，而如果使用位存储，就可以用2GB的空间，这样很多问题就能够解决了。

如果文件实在太大，无法在内存中放下，则需要考虑将大文件分成若干小块，先处理每个块，最后再逐步得到想要的结果，这种方式也叫做外部排序。这样需要遍历全部序列至少两次，是典型的用时间换空间的方法。

堆，如果在超大数据中找第K大、第K小，K个最大、K个最小，则特别适合使用堆来做。而且将超大数据换成流数据也可以，而且几乎是唯一的方式，口诀就是“查小用大堆，查大用小堆”。
常识补充：10亿 ≈ 1G、100万 ≈ 1M

题目：对20GB文件进行排序

解决思路：外部排序 + 两两合并

需要先考虑内存要求、时间要求等限制条件，然后根据要求确定需要划分为多少块进行处理。
比如内存限制为1GB，则将20GB文件分为20块文件。
对每块文件进行排序。
最后两两合并即可。（也可以使用堆排序策略合并）

题目：超大文本中搜索两个单词的最短距离

题目要求：有个超大文本文件，内部是很多单词组成的，现在给定两个单词，请你找出这两个单词在这个文件中的最小距离，也就是像个几个单词。你有办法在 O(n)时间 里完成搜索操作吗？方法的空间复杂度如何。
[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题,算法与数据结构,算法,排序算法,大数据

解决思路：双指针法

使用两个指针来记录两个单词的索引位置，通过遍历文本文件，不断更新这两个指针，以便计算最小距离。

声明两个指针，初始都默认指向-1；再声明一个变量length，用于接收两个单词的距离。
遍历这个文本文件，
- 遇道单词1，就让指针1指向单词1的索引，
- 遇道单词2，就让指针2指向单词2的索引，
- 如果指针1和指针2都>0时，算出两指针的距离，如果该距离比<length，就赋值给length。
遍历完了之后，此时length就是两个单词的最短距离。

复杂度：时间复杂度 $O (n)$ 、空间复杂度 $O (1)$

题目：从10亿数字中寻找最小的100万个数字

题目要求：设计一个算法，给定一个10亿个数字，找出最小的100万的数字。假定计算机内存足以容纳全部10亿个数字。

解决思路

方案1：对10亿数字做快速排序，返回前100万个。

对10亿数字做升序的快速排序后，前100万个就是最小的100万个数字了。

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (l o g n)$

所需内存大概4G左右，太高不推荐。

方案2：对10亿数字做选择排序，100万次

对10亿数字做选择排序，每次遍历找到当前最小的数字，遍历100万次就能找到最小的100万个数字了。

复杂度：时间复杂度 $O (nm)$ 、空间复杂度 $O (m)$

时间复杂度为：10亿*100万次，这个效率一般的服务器都达不到。

方案3【推荐】：维护长度为100万的最大堆

构建一个长度为100万的最大堆，
遍历10亿-100万中剩余的数字，依次和堆顶比较，如果 < 堆顶，就跟堆顶交换，然后最大堆化。
最后该最大堆就是最小的100万个数字。

补充说明：
如果数据量没有这么大，也可以直接使用这种方式。
如果将10亿数字换成流数据，也可以使用堆来找，而且对于流数据，几乎只能用堆来做。

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (m)$

所需内存为 100万*4B ≈ 4MB ，可以接受。文章来源地址https://www.toymoban.com/news/detail-693875.html

到了这里，关于[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题

题目：对20GB文件进行排序

解决思路：外部排序 + 两两合并

题目：超大文本中搜索两个单词的最短距离

解决思路：双指针法

复杂度：时间复杂度 $O (n)$ 、空间复杂度 $O (1)$

题目：从10亿数字中寻找最小的100万个数字

解决思路

方案1：对10亿数字做快速排序，返回前100万个。

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (l o g n)$

方案2：对10亿数字做选择排序，100万次

复杂度：时间复杂度 $O (nm)$ 、空间复杂度 $O (m)$

方案3【推荐】：维护长度为100万的最大堆

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (m)$

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

[Go版]算法通关村第十五关黄金——继续研究超大规模数据场景的问题

题目：对20GB文件进行排序

解决思路：外部排序 + 两两合并

题目：超大文本中搜索两个单词的最短距离

解决思路：双指针法

复杂度：时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)

题目：从10亿数字中寻找最小的100万个数字

解决思路

方案1：对10亿数字做 快速排序，返回前100万个。

复杂度：时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)、空间复杂度 O ( l o g n ) O(logn) O(logn)

方案2：对10亿数字做 选择排序，100万次

复杂度：时间复杂度 O ( n m ) O(nm) O(nm)、空间复杂度 O ( m ) O(m) O(m)

方案3【推荐】：维护长度为100万的最大堆

复杂度：时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)、空间复杂度 O ( m ) O(m) O(m)

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

复杂度：时间复杂度 $O (n)$ 、空间复杂度 $O (1)$

方案1：对10亿数字做快速排序，返回前100万个。

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (l o g n)$

方案2：对10亿数字做选择排序，100万次

复杂度：时间复杂度 $O (nm)$ 、空间复杂度 $O (m)$

复杂度：时间复杂度 $O (n l o g n)$ 、空间复杂度 $O (m)$