认识达内从这里开始

认真做教育专心促就业

如何高效的处理亿万级数据？（9）

发布：青岛达内
来源：青岛达内
时间：2019-03-20 14:08

青岛达内的小编总结，10. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
方案1:这题用trie树比较合适，hash_map也行。
方案2:from xjbzju:,1000w的数据规模插入操作完全不现实，以前试过在stl下100w元素插入set中已经慢得不能忍受，觉得基于hash的实现不会比红黑树好太多，使用vector+sort+unique都要可行许多，建议还是先hash成小文件分开处理再综合。
一个文本文件，找出前10个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解
方案1:首先根据用hash并求模，将文件分解为多个小文件，对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理，找出最终的10个最常出现的词。
100w个数中找出最大的100个数
方案1:局部淘汰法
取前100个元素，并排序，记为序列L

然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O（100w*100）。

青岛达内

方案2
快速排序的思想，每次分割之后只考虑比轴大的部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O（100w*100）
方案3
在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O（100w*lg100）。
接下来看第二种方法，双层桶划分
秘技二：双层桶划分
一种算法设计思想。面对大量的数据我们无法处理时，可以将其分成一个个小任务，然后根据一定的策略来处理这些小任务，从而达到目的。
适用场景
第k大，中位数，不重复或重复的数字
基本原理及要点
因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）。
【扩展】当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其中的逆过程。
【问题实例】 1）。2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为232,也就是，我们可以将这232个数，划分为2^8个区域（比如用单个文件代表一个区域），然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内

< 上一篇：如何高效的处理亿万级数据？（8）

下一篇：如何高效的处理亿万级数据？（10） >