关于如何读取一个本地文件的重复行？

Question

手里有一个400M的txt文件，里面的数据格式如下："aaa","bbb","222"
"aaa","bbb","222"
"ccc","bbb","222"
"aaa","bbb","222"
"aaa","4444","222"
"aaa","bbb","222"
"tttt","bbb","222"
"aaa","bbb","222"
....
....我想写程序返回重复行的内容和行号。最开始的思路就是很简单的从上到下逐个比较，即，第一行和后面所有行比较，第二行和下面所有行比较，等等，但实际上这是根本不可能的，400M的文件这么比较下去，计算机都哭了；
第二种思路是先对文件的内容进行排序，然后按照第一个单词对这个400M的文件进行拆分，然后再逐个比较，但问题又来了，我找了好长时间，但仍然不知道好的重复行比较方法有什么，最后还是逐行比较，只不过现在是在单个小文件内比较。所以我想在这里问问大家，对于上面形式的文件，得到重复行行号和内容的算法有什么呢，给个思路就成。
非常感谢。

Answer 1

这是一个非常好的问题。
由于你的每行的数据的类型比较特别，所以你的第二种方法始终非常有效地办法。
分级是一个行之有效的办法。由于数据总共有3列，分别作出比较，所以呢，我给出一个比较粗鄙的方法吧
第一步是对整个文件处理，在每一行的末尾都添加行号。
第二步是对文件进行处理，我们为第一列的每种数据新建一个文件。比如第一列的就把aaa全部放在第一个文件呢。
第三部是对第二部形成的文件列表，征对第二列数据重复第二部的操作。
第四部是对第三部形成的文件列表，征对第三列数据重复第二部的操作。第四步最终得到的就是你要的结果。在同一个文件内的都是重复的，并且拥有其最初行号。这个方法的时间复杂度为O（N），空间复杂度也是O(N)。
如果你觉得硬盘空间上有问题，你可以再完成后删除文件。比如第三部完成后，删除第二步的生成的文件，然后第四步完成后删除第三步生成的文件。
之所以用文件而不用分层hash的考虑就是在于文件比较大。

Answer 2

谢谢 nihuajie05 提供的思路，今天太晚了，明天试试。
不过细节上还是有些问题，不过有个思路总是好的。

Answer 3

感觉没说清楚，以你的例子为例吧：
"aaa","bbb","222" 
"aaa","bbb","222" 
"ccc","bbb","222" 
"aaa","bbb","222" 
"aaa","4444","222" 
"aaa","bbb","222" 
"tttt","bbb","222" 
"aaa","bbb","222" 
现在我想得到"aaa","bbb","222"的重复行和行号
"aaa","bbb","222"作为正则表达式的公式，然后进行全文匹配，因为你是按行进行匹配的所以你在循环的时候变量i就是你的行号，当前行如果和你的正则公式成立，返回行号，并执行当前行的删除操作，这样就得到这样的结果。"aaa","bbb","222" 0，1，3，5，7
下面是你匹配完 "aaa","bbb","222" 后的文本内容，这样主要是为了匹配其他公式时可以减少匹配量
"ccc","bbb","222" 
"aaa","4444","222" 
"tttt","bbb","222" 

Answer 4

400M = 400*1024*1024 bytes,每行十个字符左右.那么约等于40000000.这个问题就是千万级的数据虑重操作.
为什么要知道每行大约多少行?如果每行为100字符,大约400万行,每行1000字符,大约40万行.
这就是一个散列级数和桶的级数问题.对于4000万行,如果极端情况下数据没有重复.如果是文件外排序,可能会建立多少文件?有些无知的人
根本就没有真正处理大规模数据的经验在那里瞎叫唤.对于规模靠的是方案而不是算法.如果楼主给的是4G文件(这一点不过份,假如400M是天数据,那么按月统计已经是12G了).或全年的数据,什么算法能处理?4000万行的数据,建议还是入库处理,比某些SB生民成4000万左右的文件然后再打开4000万个文件查看是一条还是多条要快1000倍.另外如果列的内容散列没有聚集的话,也就是每列内容分布平均,不要第一列都是"aaa",然后变化主要体现在后面的列.如果产生极端冲突,那么散列就没有意义了.如果大概是平均分布.第一列的长度是多少?
比如第一列长度是3,那么最多可以得到一级散列999个,而如果是6,则是99999.所以列的长度也非常有关系.如果按你给出的数据来分析,可以在内存中做两级hashMap.400M的数据,2G内存分配1.5G给JVM可以胜任,这种处理可以在几分钟内处理完成.

Answer 5

如果内存够大，可以使用Google-Collections http://code.google.com/p/google-collections/提供的Multimap

Answer 6

建一个HashMap<String,ArrayList<行号>>
读文件的时候，每读一行做如下处理：
判断本行在map中是不是存在，如不存在，新建一个list，往里添加一个行号，并把list存入map
如存在，则取出list，往里添加行号。
读完文件后，再循环map，如list大于1，则为重复行，并取出行内容和行号。

Answer 7

不会，反正个人觉得纯粹靠JVM来处理的话的确比较吃力了，数据太多。 不要说什么建立map 然后比较什么的，400M的文本类型文件，光是打开都要半天了……

Answer 8

我觉得自己实现一个Map更合理。把每一行作为一个object直接put进去，存在则对它的value增1。否则new。
即使这样的话，400M的文件+map占用的内存机器估计也吃不消了。
用数据库的话，工作量又有点大了。
所以建议用map+写文件的方式。这样内存压力就小多了。

Answer 9

散列不需要比较
调用get直接可以判断是否存在相同内容的行。

Answer 10

LZ的问题我不会，但是抛开LZ的问题，像12、23楼那哥们说的那样，假如出现极端情况，没有重复行，按照每行1000个字符算，那不是要写40万个文件？光是文件数量这一点，我相信windows应该是处理不了这么多文件的，到时候估计连磁盘分区都打不开。 而且这只不过是400M的文件，如果真有2G的文件，估计写出来的小文件应该算是磁盘碎片了。

Answer 11

恩，我弱智，这个问题真不会。
但是2G的文件的话，要写多少个文件？windows的一个分区，或者一个文件夹下能放多少个文件，我也不知道。
现在假设要分析的是2G的文件，每行1000字符，假设极端情况没有重复数据，如果你有空的话，你跟我讲讲要写多少个文件？让我也学学大量数据的处理吧

Answer 12

我也没别的意思，也不是想推翻你的想法。这个问题除了扔数据库里处理，别的处理方法我也不会了。
我还一个疑问，对文件的操作的时候，的确是可以随时保存的磁盘中，像前面说的那样“存在则对它的value增1”，如果这么处理，你选择什么时候把文件保存的磁盘上？假设400M文件只有第一条和最后一条是相同的，是不是要把整个文件遍历一次之后，把相同的挑出来？  没记错的话JVM处理10万级数据的时候，效率会明显降低。
像12楼说的那样“每行1000字符,大约40万行”，假设每条数据只有一条与之匹配数据，你觉得要写多少个文件？这些文件之间是否存在数据整合问题？如果你觉得我问的不靠谱的话，就别回答了，我现在也很乱 = =

Answer 13

建议：
新建个类，用来表示每行数据，重写hashcode方法，
读取文件内容，将行转化为一个对象，作为hashmap的key  put到map中去。
遍历读取文件一遍，map中存储的就是单一的行的对象了新建的对象类可以参照下面的
public class TargetBean {
private String content1;
private String content2;
private String content3; public TargetBean() {
} public TargetBean(String content1, String content2, String content3) {
this.content1 = content1;
this.content2 = content2;
this.content3 = content3;
} @Override
public boolean equals(Object obj) {
if (obj instanceof TargetBean) {
TargetBean new_obj = (TargetBean) obj;
return content1.equals(new_obj.content1)
&& content2.equals(new_obj.content2)
&& content3.equals(new_obj.content3);
} else {
return false;
}
} @Override
public int hashCode() {
return content1.hashCode() + content2.hashCode() + content3.hashCode();
} public String getContent1() {
return content1;
} public void setContent1(String content1) {
this.content1 = content1;
} public String getContent2() {
return content2;
} public void setContent2(String content2) {
this.content2 = content2;
} public String getContent3() {
return content3;
} public void setContent3(String content3) {
this.content3 = content3;
}
}

Answer 14

这里我提供一个方法供参考，
主要是bloom filter算法的java实现
遍历文件一次就ＯＫ了
就是这个hash函数不太好弄
需要自己弄下怎么尽量小的避免碰撞
程序是用单hash加判断实现的，
细化还需要多加研究
查找资料去
package com.yaowei.algorithm;
import java.util.BitSet;
import java.io.*;
public class BloomFilter {
private BitSet bitSet;
private int tableSize;
public BloomFilter(){

}
public BloomFilter(int i){
tableSize = i;
bitSet = new BitSet(i);
}
public void add(String s){
int hashCode = Math.abs(GetHashCode.getHashCode(s))%tableSize;
bitSet.set(hashCode,true);
}
public boolean exists(String s){
int hashCode = Math.abs(GetHashCode.getHashCode(s))%tableSize;
return bitSet.get(hashCode);
} public static void main(String[]args){
BufferedReader br = null;
try{
    //long k = System.nanoTime();
    BloomFilter b = new BloomFilter(40000000);
    br = new BufferedReader(new FileReader("D://words.txt"));
    String s = "";
    int i = 0;
    while((s=br.readLine())!=null){
    i++;
    if(b.exists(s)){
    System.out.println(i+" "+s);
    }else{
       b.add(s);
    }
    }
    //long time = System.nanoTime() - k;
    //File f = new File("D://words.txt");
    //System.out.println(f.length());
    //System.out.println("用时："+time/1000000000+"秒");
}catch(Exception e){
e.printStackTrace();
}finally{
try{
if(br!=null){
br.close();
}
}catch(Exception e){

}
}
}
}
class GetHashCode{
/**
 * 这个方法里面的hashcode需要重写以避免碰撞程度加大
 * @param s
 * @return
 */
public static int getHashCode(String s){
return s.hashCode();
}
}

Answer 15

楼上有人说了新建文件可能存在的文件数目问题。
诚然这样的问题却是是用数据库解决最好了，我只是想要有一个不一样的方案出现。我在java版内曾经遇到个一个问题就是在导50W行数据时，java出现的内存泄露。而且还不是一次性处理的，分批处理的。但是由于垃圾处理的延迟性，最终还是导致了内存泄露。

Answer 16

是的，效率肯定是会降低的。
但也是一种解决问题的途径，比起全部放到内存里来说，起码这种方法可以实现功能了。
至于效率，可以通过划分成若干个文件，设计合理的hashCode算法来提高。
我说的若干个文件的意思是，比如第一个字段会以a,b,c,d,e五个字符开头，那么分成5个文件。
如果觉得还是太大，可以分的更细一些。

Answer 17

分文件是一个方法,但是，假设按照搂住的数据，400m差不多是2000w条记录，如果这2000w条记录全部不一样，那怎么办呢？
通过程序，我测试了下，我通过hashMap管理了数据，一共2000w条数据
HashMap在处理上一旦纪录过头，时间效率会大大降低，按照我公司机器的配置，如果是10000条不同的纪录，HashMap用了9秒不到，那么2000*9就是3。75个小时，如果是100条相同纪录，混合成2000w条，则差不多只要2分钟当然，极端的数据不会产生这样的业务，所以肯定介于我测试的之间。我的想法是按你所说的建立分文件是一个方式，我本来是决定用list维护map的，但是遇到的问题就是如何计数。因为并不知道正态数据的样本，所以如何划分文件或者map很难确定，这就不能做下去了。还是看业务决定，按照搂住的描述，我只能做到测试的效果

Answer 18

看看这个贴,可能里面还要注意些问题.
http://topic.csdn.net/u/20091215/10/82819869-6242-4886-954c-e55cad5525f3.html?37076

Answer 19

考虑了2天，我最后决定用多线程处理实验下
首先是分截文件，将2400w条记录的500m文件分成3个800w条记录的文件，然后3个线程同时去整理
并且维护在3个HashMap中，等处理结束后，开始遍历后2个Map去比较第一个Map，最后把结果维护进Map1
原来2分钟的2000w条记录，现在2400w条记录只用了1分多一点
目前准备测试bt数据，原本是有100条相同纪录，现在是1000条，统计数量是24000个，吃饭的时候测试主要是加入线程，以及根据HashMap的结构来决定这样的方式，对于Map，薄利多销往往起到很好的效果测试ing...

Answer 20

LZ什么环境，多个CPU吗，如果是单个的话，你这个IO操作这么频繁的程序，应该还是单线程数据快

Answer 21

怎么可能单线程快呢，我测试1000个不同的纪录在Map中，2400w条记录，也就是1条记录重复24000次，最后就用了13分钟，比原来快了很多很多