分治思想笔记

• 例：现有1T文件数据，其中只有两行内容相同，找出这两行需要怎么做？
  假设一台机器内存500MB

单机思想：

1. 分别读取每行数据，取哈希值
2. 每个哈希值对2000取余数，余数相同归为一组，得到2000组转存为2000个文件
3. 相同内容行的哈希值相同，对2000取余必相同，所以相同内容行必在一个文件内
4. 1T文件分为2000个小文件，每个文件大约500MB相当于内存大小
5. 取单个文件写入内存，便可找到是否有相同内容行

分治思想：

1. 1T文件，分为2000份，每份大约500MB
2. 分发到 2000个计算机
3. 在单机思想基础上，每台计算机并行计算哈希取余过程
4. 将每台计算机取余为0拷贝到第一台计算机，取余为1拷贝到第二台计算机，以此类推
5. 并行计算每台计算机是否有向同行。

总结：

1. 单机思想时，读取小文件并计算用时约30分钟，需要执行2000次，假设每次1秒，需要2000秒，约30分钟，需大约一个小时完成。
2. 分治思想时，将1T文件分发到2000台计算机需要耗费大量时间，约3个小时，在带宽为100MB的情况下，拷贝取余相同行，因每台计算机文件500MB，需5秒，计算机并行运算为1秒，可看出大量用在分发文件。
3. 假设每天都会有1T数据需要运算，一年则是365T数据，单机运行需要至少365小时，分治思想在最后一天也只是花3小时进行分发，运算时间远少于单机运算。