有一个100GB的文件，里面内容是文本，要求：
- 找出第一个不重复的词
- 只允许扫一遍原文件
- 尽量少的IO
- 内存限制16G
本问题是一个out-of-core去重的问题，只不过还需要记录一下单词的位置。
去重问题主要有两种解决思路：一种是hash based，即将原数据进行hash，重复的数据会hash到一起；另一种思路是sort based，即先对原数据进行排序，然后从头到尾遍历一遍即可。
对于out-of-core的问题，可以借鉴external hash和external merge sort的思路，把原始的大文件分成多个小块，每一块单独处理，最终合并到一起得到最终结果。
sort based的方法IO开销太大，因此这里采用了hash based的解决思路，具体步骤如下：
- split阶段：读取原文件，根据
hash_func1将<word，index>分为P个partition。如果某个partition过大，则用hash_func2再将此partition继续划分成更多的sub-partition，依此类推。 - find阶段：读入每一个
partition，找到该partition中下标最小的不重复的单词。遍历完所有的partition即可找到原始文件中下标最小的不重复的单词。
设原文件大小为N，理想情况下只需要进行3N（2N + 1N）的IO。
在512M的数据上进行测试时（src/naive.cc）发现读入数据只需要7s，但找到第一个不重复单词需要88s。磁盘的IO没有跑满，而且大部分时间都在内存中做计算。可以考虑用多线程来优化。
- split阶段：通过
get_next_word_info_vec每次获取一个vector的<word, idx>，通过hash将vector的内容分发给不同的partition，多个partition同时进行去重，写文件操作。 - find阶段：多个
partition同时寻找下标最小的不重复的单词。
在512M的数据上测试结果如下：
- 单线程：
2min28s - 4线程：
1min45s
由于题目数据太大，这里按比例缩小了数据量，减小为原来的1/200，有512M数据，内存限制80M。
起初我尝试用真实的英文语料（resource/adv.txt）生成数据，但是英文中常用的单词不过几万，数据量大的情况下在split阶段已经全部去重了，因此这里使用的是长度为7的随机字符串。
整个测试过程如下：
生成512M的数据（resource/big.txt）：
tools/gen_large_data.py编译：
mkdir build && cd build
cmake ..
make -j测试：
make test运行，其中partitions表示原文件被分割成多少份，threads表示线程数：
# ./main <input> [partitions=16] [theads=1]
./main ../resource/big.txt 256 4利用memory_profiler监控运行时内存：
# pip3 install memory_profiler
mprof run ./main ../resource/big.txt 256 4
mprof plot -o 512M-80M-256-4 --backend Agg可以看到运行过程中总内存占用在500M左右，总用时1min45s。
- 内存占用：目前内存开销还是很大。在
split阶段可以通过控制写入磁盘的频率来控制内存占用。在find阶段可以考虑用其他的存储方法，比如不使用std::string而直接使用char[7]，不过需要提前知道单词的长度。 - IO效率：目前
split到磁盘上还是文本格式的<word, idx>。这里可以用二进制存储，并通过一定的压缩算法减少文件大小。还可以使用double buffering一边读取IO一边做计算。 - CPU效率：目前
find阶段可以每核可占用100%的CPU，但是split阶段每核只能占用50%的CPU。目前猜测是因为每次读入一个vector的<word, idx>后就要重新创建线程，未来可用线程池解决。