边读边捋【july的】海量数据处理面试题

本文主要是介绍边读边捋【july的】海量数据处理面试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、寻找 TOP IP

海量日志数据，提取出某日访问百度次数最多的那个 IP。

个人捋之：海量，直接处理往往不中。

1）设计一个hash函数，其功能为将任意IP地址映射为一个数，再将该数对某个不太大的数取余，使得任意IP -> 一个不太大的数（比如1000）。这样就保证能实时地将现有日志中所有的IP分布到1000个桶里，我们每次只将一个桶提到内存里然后处理；

2）逐个将桶提到内存里，按value（次数）sort，取最大<key（IP）, value（次数）>对，存下；

3）对这1000个键值对按次数排序，再取最大次数，得到对应键值即为所求。

2、搜索引擎会通过日志文件把用户每次检索所使用的所有查询串都记录下来，每个查询串的长度为
1-255 字节。假设目前有 1000 万个查询记录（但因为这些查询串的重复度比较高，所以虽然总数是 1000
万，但如果除去重复后，不超过 300 万个查询字符串），请统计其中最热门的 10 个查询串，要求使用的
内存不能超过 1G。

个人捋之：

1）1000万 * 255 byte = 2.5G > 1G，so 全部读入内存处理不成。但是题目里提到很多重复，去重后大概需要800M，自然而然想到使用STL中的map或者hash_map或者trie树起一个过滤作用，从文件中逐条读入记录，加入到map中。

2）排序，不过既然是top k 的题，自然想到用堆排。

这题数据量比较坑爹，不大不小。如july所说，如果是1亿个查询记录呢？

个人捋之：

1）25G >> 1G。考虑将这个大文件拆分成若干个能处理的小文件，比如说100个。拆分的方式不妨采用hash映射的方式：从原文件读一行，fgets(oneline, input.txt)；再用hash函数算个hash值，long long hashValue = hashFunc(oneline)；再将该值对100取余，hashValue %= 100；将其写入hashValue对应的那个桶对应的那个小文件中；

之后两种方法：

1>对这100个小文件，各自map去重，然后取top10；再对所有的top10 取 top10；

2>对这100个小文件，使用外排序，得top10；

这篇关于边读边捋【july的】海量数据处理面试题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---