散列分治
- 寻找Top IP：海量日志数据，提取出某日访问百度次数最多的那个IP
- 1.分而治之：把该日访问百度的所有IP从日志中提取出来，逐个写入一个大文件中(这一步可以省略)。然后采取散列映射的方法(如hash(IP)%1024)，把海量IP日志分别存储到1024个小文件中，每个小文件最多包含4MB个IP地址
- 2.hash_map统计：对每个小文件，采用hash_map<ip, 出现次数>进行统计。找出每个小文件频率最高的IP，总共1024个IP
- 3.堆/快排：排序得到频率最高的IP
- 寻找热门查询：搜索引擎会通过日志文件把用户每次检索所使用的所有查询串都记录下来，每个查询串的长度为1~255字节。假设目前有1000万条查询记录(但是，因为这些查询串的重复度比较高，所以虽然总数是1000万，但如果除去重复后，查询串query不超过300万个)，请统计其中最热门的10个查询串，要求使用的内存不能超过1 GB
- 虽然有1000万个查询，但是因为重复度比较高，去除重复后，事实上只有300万个查询，每个查询为255字节，所以可以考虑把它们全部放进内存中去(假设300万个字符串没有重复，都是最大长度，那么最多占用内存300000 x 255 = 765MB = 0.765GB, 所以可以将所有字符串都存放在内存中进行处理)。
- 1.hash_ map统计。对这批海量数据进行预处理，用hash_map完成频率统计。在O(n)的时间复杂度内完成了所有query的频率统计
- 2.堆排序。借助堆找出Top k, 时间复杂度为0(nlogk)。维护k个元素的最小堆
- 也可用trie树
- 堆排找topK过程
- 维护k个元素的最小堆， 即用容量为k的最小堆存储最先遍历到的k个数，并假设它们就是最大的k个数， 建堆费时O(k)，有k1>k2>..> kmin (设kmin为最小堆中最小元素)。继续遍历整个数列剩下的n-k个元素，每次遍历一个元素x将其与堆项元素进行比较，若x > kmin 则更新堆，每次调整堆费时0(log k)，否则不更新堆。这样下来，总费时 O(k + (n- k) logk )= O(nlogk)。此方法得益于在堆中查找等各项操作的时间复杂度均为O(logk)
- 寻找Top 10：有海量数据分布在100台电脑中，请想个办法高效统计出这批数据出现次数最多的Top 10
- 如果同一个数据元素只出现在某一台机器中
- 1.堆排：每台电脑求Top10，然后扫描后面的元素，得到最终topK
- 2.组合归并：每台电脑求Top10，然后组合100台电脑上数据的1000个数据，再求topk
- 如果同一个数据元素出现在不同机器中
- 1.遍历所有数据，重新散列取模，回到上一个问题
- 2.暴力求解，直接统计所有元素，把同一元素再不同机器中出现次数相加，得到最终top10
- 查询串的重新排列：有10个文件，每个文件的大小是1 GB，每个文件的每一行存放的都是用户的查询串query，每个文件的query都可能重复。请按照query的频度排序
- 解法一
- 1.散列映射
- 2.hash_map统计
- 3.堆排、快排或归并，得到10个排好序的文件后，对这10个文件进行归并排序(内排和外排相结合)
- 解法二：query总量有限时，可一次性加入内存，采用Trie树和hash_map直接统计，按照出现次数做快排、堆排、归并排序即可
- 寻找共同的URL：给定a和b两个文件，各存放50亿个URL，每个URL占64字节，内存限制是4GB。请找出a和b文件中共同的URL
- 可以估计出每个文件的大小为5000000000x 64=320 GB
- 1.散列映射：对a，b文件，分别散列映射成1000对小文件。处理完后相同URL都在对应的小文件中。求出1000对小文件中相同的URL即可
- 2.hash_set统计：把一个小文件的URL存储到hash_set中，然后遍历另一个小文件的URL判断是否存在
多层划分
- 寻找不重复的数：在2.5亿个整数中找出不重复的整数的个数。注意，内存空间不足以容纳这2.5亿个整数
- 1.整数个数为2^{32}，将这2^{32}个数划分为 2^8个区域(用一个文件代表一个区域)
- 2.不同的区域再利用位图进行统计
- 寻找中位数：找出5亿个int型数的中位数
- 1.将这5亿个int型数划分为2^{16}个区域
- 2.读取数据统计落到各个区域里的数的个数，根据统计结果就可以判断中位数落到哪个区域，并知道这个区域中的第几大数刚好是中位数
- 3.第二次扫描只统计落在这个区域中的那些数即可
外排序
- 外排序介绍
- 采用「排序-归并」策略在排序。在排序阶段，先读入能放在内存中的数据，将其排序后输出到一个临时文件，依次进行，将待排序数据组织为多个有序的临时文件，而后在归并阶段将这些临时文件组合成一个大的有序文件
- 给10^7个数据的磁盘文件排序：给定一个文件，里面最多含有n个不重复的正整数( 也就是说可能含有少于n个不重复的正整数)，且其中每个数都小于等于n(n=10^7)。请输出一个按从小到大升序排列的包含所有输入整数的列表。假设最多有大约1 MB的内存空间可用，但磁盘空间足够。要求运行时间在5分钟以内，10 秒为最佳结果
- 1.位图
- 由于每个7位十进制整数表示一个小于1000万的整数，所以可以使用一个具有1000万个位的字符串来表示这个文件，当且仅当整数i在文件中存在时，字符串中的第i位置为1
- 能采用位图方案的原因
- 输入数据限制在相对较小的范围内
- 数据没有重复
- 其中的每条记录都是单一的整数，没有任何其他与之关联的数据
- 2.多路归并
- 先把整个大文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程
位图
- 电话号码统计：已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数
- 8位数字最多组成99 999 999个号码，大概需要99兆位，大概十几兆字节的内存即可
- 2.5亿个整数的去重：在2.5亿个整数中找出不重复的整数。注意，内存不足以容纳这2.5亿个整数
- 采用2位图(每个数分配2位，00表示不存在，01表示出现一次，10表示出现多次，11无意义)，共需内存2^32x2=1 GB内存，可以接受
- 扫描这2.5亿个整数，查看位图中相对应的位，如果是00就变为01,如果是01就变为10, 如果是10就保持不变。扫描完之后，查看位图，把对应位是01的整数输出即可
- 也可以先划分成小文件，然后在小文件中找出不重复的整数，并排序，最后归并， 归并的同时去除重复的数
- 整数的快速查询：给定40亿个不重复的没排过序的unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这40亿个整数当中?
- 可以用位图的方法，申请512 MB的内存，一个位代表一个unsigned int 型的值
- 读入40亿个数，设置相应的位
- 读入要查询的数，查看相应位是否为1, 如果为1表示存在，如果为0表示不存在
布隆过滤器(Bloom filter)
- 原理
- 相当于位图的扩展，其结构是长度为n的位数组，初始化为全0。当一个元素被加入集合中时，通过k个散列函数将这个元素映射成一个位数组中的k个点，并将这k个点全部置为1
- 在检索一个元素是否在一个集合中时，只需看这个元素被映射成位阵列的k个点是不是都是1。如果这k个点中有任何一个点为0，则被检索元素在集合中一定不存在；如果这k个点都是1，则被检索元素很可能在集合中
- 但会有误判的可能
simhash算法
- 设计一个比较两篇文档相似度的算法
- 一种方案是先将两篇文章分别进行分词，得到一系列特征向量，然后计算特征向量之间的距离(比如计算它们之间的欧氏距离、汉明距离或者夹角余弦等)，从而通过距离的大小来判断两篇文章的相似度。该方案的缺点是海量数据计算量极大
- simhash算法
参考
- 结构之法
- https://blog.csdn.net/v_JULY_v/article/details/6543438
