前言
之前在网上看过一个很有意思的问题？
在单机且内存不能放下全部足量的数据的情况下，如何在1T的文件中，找到重复的两行？
看完这个问题，不妨我们来思考一下如何实现...
一.解决方案
首先实现这个问题我们的第一想到的最笨的解决方案就是对每一行都与文件中后面所有的行进行比较，这种方式的时间复杂度很高为O(n^2)...
那么有没有更好的解决方案呢...
这个时候我们还有一种思路就是将数据放到HashSet中，运用Hash表不能加入重复的Key的特征来实现需求，可是我们题目的条件是内存不能放下全部足量的数据..因此这个方案不可行。
但是我们可以借鉴哈希表的思想，哈希表是将数据根据HashCode经过算法算出对应的Hash值，然后根据Hash值找到数组下标，然后将数据存放到对应下标的位置，然后如果有哈希冲突，一般采用拉链法来解决..看到这里我们是否也能运用哈希表的原理来实现上述需求呢？下面我们来推演一下..
首先我们可以读取文件的每一行，然后根据每一行来模仿哈希表算出它的HashCode。拿到了HashCode，我们应该干啥呢？
哈希表中的数组，它主要是用来存储相同HashCode值的地方，那我们可以类似的将相同HashCode的行存储到相同的一个文件中，于是我们可以根据HashCode对1000取模，也就是将文件根据HashCode值分为1000份，那么每份的大小大约就是1GB的大小，这下内存可以放的下了吧，然后我们就可以利用我们之前想到的HashSet，来判断是不是重复行了。
上述的这种思想其实就是一种分治的思想，将文件根据某个规则切分成多分，对每一份进行处理，最终完成需求。
二.思考
1.这个过程的实现复杂度是多少呢？
首先对每一行进行遍历，时间复杂度为O(n)，然后根据每个拆分后的小文件，运用HashSet来判断重复行，1000个小文件，每个小文件处理的最坏情况，复杂度为O(n)，所有总的时间复杂度为O(n+1000*n)=O(n)，这种方式比上述的最笨的方式O(n^2)来说，是不是快的多呢...
2.磁盘IO会耗费多少时间
然后我们可以算一下这个过程会磁盘IO会耗费多少时间，首先I/O操作从文件中读取1TB的数据按照1分钟1GB的传输速度，差不多要100分钟，然后对每个小文件进行查重，最坏情况下差不多要100分钟。因此这个过程对应于单价来说，耗时3个小时20分钟。
后续如果有更好的解决方案，我会随时更新这篇文章，欢迎大家关注！
网友评论