- 例：现有1T文件数据，其中只有两行内容相同，找出这两行需要怎么做？
假设一台机器内存500MB
单机思想：
- 分别读取每行数据，取哈希值
- 每个哈希值对2000取余数，余数相同归为一组，得到2000组转存为2000个文件
- 相同内容行的哈希值相同，对2000取余必相同，所以相同内容行必在一个文件内
- 1T文件分为2000个小文件，每个文件大约500MB相当于内存大小
- 取单个文件写入内存，便可找到是否有相同内容行
分治思想：
- 1T文件，分为2000份，每份大约500MB
- 分发到 2000个计算机
- 在单机思想基础上，每台计算机并行计算哈希取余过程
- 将每台计算机取余为0拷贝到第一台计算机，取余为1拷贝到第二台计算机，以此类推
- 并行计算每台计算机是否有向同行。
总结：
- 单机思想时，读取小文件并计算用时约30分钟，需要执行2000次，假设每次1秒，需要2000秒，约30分钟，需大约一个小时完成。
- 分治思想时，将1T文件分发到2000台计算机需要耗费大量时间，约3个小时，在带宽为100MB的情况下，拷贝取余相同行，因每台计算机文件500MB，需5秒，计算机并行运算为1秒，可看出大量用在分发文件。
- 假设每天都会有1T数据需要运算，一年则是365T数据，单机运行需要至少365小时，分治思想在最后一天也只是花3小时进行分发，运算时间远少于单机运算。
网友评论