有两个文件,A文件和B文件,每个文件在2G左右大小,文件存储的内容是用户信息格式如下
1|张三|23|南京市
2|...........以下略
以每一行一条记录的格式,每个字段用 | 进行分隔,记录数在100万至500万之间,不会超过500万条.
A和B的文件的格式都是一样,现在要比较两个文件之间不同的记录数,要求把结果输出到新的文件,以A文件为基础,如果A文件里有的记录而B文件里没有,则把此记录记到新文件中,并在最后增加标志位设为3(表示删除);如果A文件里有的记录而B文件里也有,但记录的内容不一样,则也把B文件中的此记录内容记录到新文件中,并在最后增加标志位设为2(表示修改);如果A文件里没有的记录而B文件里有,则把B文件中的此记录内容记录到新文件中,并在最后增加标志位设为1(表示新增)(注:同样的记录在两个文件中可能位置不一样,并且记录的顺序也可能不一样.不过两个文件的差异性不会超过10%)
最后生成的新文件则是A和B两个文件的差异.
问,用什么样的思路解决此问题?方法不限,要求速度越快越好,内存占用越少越好.
1|张三|23|南京市
2|...........以下略
以每一行一条记录的格式,每个字段用 | 进行分隔,记录数在100万至500万之间,不会超过500万条.
A和B的文件的格式都是一样,现在要比较两个文件之间不同的记录数,要求把结果输出到新的文件,以A文件为基础,如果A文件里有的记录而B文件里没有,则把此记录记到新文件中,并在最后增加标志位设为3(表示删除);如果A文件里有的记录而B文件里也有,但记录的内容不一样,则也把B文件中的此记录内容记录到新文件中,并在最后增加标志位设为2(表示修改);如果A文件里没有的记录而B文件里有,则把B文件中的此记录内容记录到新文件中,并在最后增加标志位设为1(表示新增)(注:同样的记录在两个文件中可能位置不一样,并且记录的顺序也可能不一样.不过两个文件的差异性不会超过10%)
最后生成的新文件则是A和B两个文件的差异.
问,用什么样的思路解决此问题?方法不限,要求速度越快越好,内存占用越少越好.
解决方案 »
- 关于true 和false
- Solaris系统启动某程序的命令是什么?
- 怎么样执行字符串??
- java.awt.Button对象上显示的文字如何换行
- 初学者问题,请大家指教!
- 请高手给我指条明路吧(迷茫中)
- 一个简单的多线程,但是不能运行,大家帮我
- String.valueOf(Object obj)返回一个String,这个String的内容代表了obj的什么?
- 包调用的问题,困惑中......
- EJB3.0+JBOSS7.1,客户端局域网内调用EJB出错
- java中怎样改变键盘输入?
- 请问:java -jar app.jar 可以运行,双击却不能(could not find the main class。。。),为啥?
a记录在A文件的头,却在B文件的尾,B文件却有2G内容,呵呵,这个时间差我们就不用比了吧!
只有先把文件读到库中,再比较,然后回写文件!
个人观点!
我只做为25M文件的比较2G的话,太大了。是否有主键或者什么的,如果前面的那个数字是主键的话,那后面的那个名字必须是唯
一的,否则没有办法进行比较,如果有两个人是同名的话,怎么比?比如:A 文件中有
两个同名的a和b,B文件中也有这两个人,并且都是修改过的,这样就没有办法比了!
public class ReadBigFile { static int length = 0x8FFFFFF; // 128 Mb public static void main(String[] args) throws Exception {
MappedByteBuffer out = new RandomAccessFile("test.txt", "rw")
.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, length);
for (int i = 0; i < length; i++) {
out.put((byte) 'a');
}
System.out.println("Finished writing");
for (int i = length / 2; i < length / 2 + 6; i++)
System.out.print((char) out.get(i)); // read file
}}
引用(
是否有主键或者什么的,如果前面的那个数字是主键的话,那后面的那个名字必须是唯
一的,否则没有办法进行比较,如果有两个人是同名的话,怎么比?比如:A 文件中有
两个同名的a和b,B文件中也有这两个人,并且都是修改过的,这样就没有办法比了!)第一列是主键,同一文件中没有相同的全部读出来没问题,但内存中存不下,会报什么outmeney错误,程序就中止退出了chenggm朋友的方法我先试试,不知道有没有其他方法了?另外问一下,如果先全部读入到数据库中,再进行比较,是不是会好一点?karlpan01 说的对,读一行比较一行肯定是没问题的,但是正如他所说的a记录在A文件的头,却在B文件的尾,效率上不可想像
http://www.10zhizui.cn
就好象为什么一个ORACLE做了这么多年才做成现在的样子,要是你想把这2G的文件管理好,还有查什么的
就自己写个ORACLE一般的数据库吧.反正我自己学个一二百年也编不出来,还是先转到数据库里吧,不然
这次解决了以后要是再有什么需求不更麻烦
不过我觉得你就是想写着玩....写着玩的话.写得半天...我先工作之后再写出来...语言先限定C++
A文件打开,一行一行的解析,B文件打开,把第一列(主健)全部映射到HashSet中,
记录最多500万,那长度也就在七八个字节,全部读进来的话占用的内存应该不到50M,
读文件A时,提取第一列,与HashSet的contains方法比较(hash算法速度很快的),
当为false时,将这一行写入记录文件,并标记为“3”,直到A文件读完。新增的话与删除相反,把A文件的主键全部读入到HashSet中,B文件一行一行地读,并
将主键与HashSet比较,为false时,写入记录文件,并标记为“2”,直到B文件读完。但是修改的话就讨厌了,我目前的想法是:读取刚才生成的才个记录文件,里面有标记
为“2”和“3”的记录,将这个记录文件的主键全部读入到HashSet中,关闭该文件。打开A文件,一行一行地读,分隔所有列,用主键匹配那个HashSet,只要不在其中的,就分隔
键和值,存到HashMap中,key存键,值的话估计很长(2G,500万行,一行平均425个字节)这样
的话肯定是不能直接存进去的,可以采用SHA-1生成该行的散列值,散列字符串的话是40个字节,
这样可以以十分之一的大小存到HashMap的值当中,这样500万行,除掉一些增加删除的,内存
占用估计在200~300MB左右,读完好关掉A文件;
打开B文件,一行一行地读,跳过HashSet中有的记录,分隔键和值,计算SHA-1散列,通过键在
HashMap中查找,若比较相同的,则读取下一行,若不同的,将这一行记录到文件中,并标记为
“3”,直至B文件全中读完。以上的方法仅仅是理论上的,由于需要采用SHA-1进行散列计算,速度可能会比较慢一些,但是
这样比较节省内存,SHA-1产生碰撞的概率是1/2^50以下。对于500万行数据不同的SHA-1散列相
同的概率是微忽其微的,况且HashMap的键是主键,值是包括主键和所有列的散列值,这样产生
碰撞的概率,可以视为0。以上仅是个人的建议,可以参考一下。
1 首先两个文件分割,分割时可以按一定的范围分割,比如1-1000的进第一个文件,1001-2000的进第二个文件,等等,同时把这些文件内容排序。2 把分割好的A和B的小文件循环load到两个map中,然后通过集合的交,差运算,分别得出更新集合(集合A交集合B),删除集合(集合A差集合B)和添加集合(集合B差集合A)。因为1已经按顺序分割好了,所以只需要A的文件1跟B的文件1比,A的文件2跟B的文件2比,等等就可以了。其中只有更新集合需要判断是否被更新,所以循环更新集合,判断是否更新后输出到文件即可,其他两个集合可以直接输出到文件。这样,所有分割的小文件循环完,处理也就结束。
到200M,都不够用,根本就不能用内置的集合类。虽然采用1万个StringBuilder数组(50万/50),根据hashcode存到不同的下标中,这样虽
然解决了增加和删除的功能,但是修改的还无法做到,因为要使用Map。但是你的行数是500万,是10倍左右了,这个比较关键不在于文件的大小,而在于文件的行
数!
qybao 朋友的想法和我有点像,不过记录没有排序过,是不是要先排个序先?此问题的难点在于内存不够,如果是两个小文件的话,装到两个map中进行比较是非常容易的所以,目前我想的方案有两种,一种是把大文件分成几块,如10万条为一块,装到map中,另一个文件也这样处理,然后进行循环比较.(这样做的效率还没有计算)
另一种是对A文件先进行排序,生成新的文件,再把B文件的记录与排序后的文件进行比较,这样会快一点.不过先对A文件排序的工作量就比较大,因为不可能全部读入内存排序,只能分段排序,用所谓的外排序了下周就要定方案,有没有朋友有好的想法啦?不一定做过或试过的,只要你觉得可行都可以提出来探讨一下
其实我上面虽然提到了排序,实际上也不一定需要排序的,比如说你按10万条分一个文件,那么你把它按id为1-99999,100000-199999,200000-299999等分别分割,也算是一种排序了。比如有500万条数据,那么就被分割为50个小文件,比如A文件被分割在A文件夹里,分别为1.txt, 2.txt...50.txt,B文件被分割在B文件夹,分别为1.txt, 2.txt...50.txt,分割文件时还可以用两个线程同时对A,B分割。
分割完以后,如果你最后的输出文件对id的顺序没有特别的要求,那你就可以采用多线程分别从A和B文件夹中取文件进行比较,如果对id顺序有要求,采用单线程也没关系,因为是按id分好的文件,所以只需要A的1.txt和B的1.txt比,A的2.txt和B的2.txt比...A的50.txt和B的50.txt比就可以了。这里面需要注意的是A文件夹有的文件B不一定有,这说明B已经把A中该记录删除了,反过来B文件夹有的A也不一定有,这说明B中追加了新的记录。两个文件夹都有的,则把文件读入到map中,然后通过集合的交并差运算去比较。
这个问题说难也不难,关键是性能。哪天有空再写个sample试试看吧。
两个线程同时读取文件的一行
然后把内容放到hashtable中
最后把hashtable中的数据打印出来不知道有没有帮助
改进了一下存储结构,采用int数组,可以大大地节省内存。测试数据为随机两个随机生成的100万行文件,key为(0~120万)的随机值,记录为4个常量值,
根据系统的纳秒数随机选择,文件大小253MB,采用这个算法的话,文件不在于多,而是在于行数
的多少,因为已经将记录映射为一个int类型的数据。在使用
[code=BatchFile]java -Xmx20m Test[/code]
设最高heap堆内存为20MB,完成比较,耗时150秒左右,如果你有500万行的话,可以提高堆内存占
用,比如说增加5倍到100MB(-Xmx100m),这样不过是存在三个文件当中的,为了加快执行速度,
源代码都放在了一个文件当中,比较大,将分多次贴出,可以参考一下:FileComparison.java(第一部分)import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;public class FileComparison {
// 文件中最大的行数,不会超过500万的话,就设为500万
private final int LINE = 1000000;
// 字段分隔符
private final String FIELD_SEPARATOR = "|";
// 行结束符
private final String LINE_SEPARATOR = System.getProperty("line.separator");
// 新增加条目所加的后缀
private final String ADD = FIELD_SEPARATOR + "1" + LINE_SEPARATOR;
// 被删除条目所加的后缀
private final String MODIFY = FIELD_SEPARATOR + "2" + LINE_SEPARATOR;
// 被修改过条目所加的后缀
private final String DELETE = FIELD_SEPARATOR + "3" + LINE_SEPARATOR;
// 旧文件
private File oldFile;
// 新文件
private File newFile;
// 记录增加的文件
private File addedFile;
// 记录删除的文件
private File deletedFile;
// 记录被修改的文件
private File modifyFile;
// 增加记录的数量
private int addedNumber = 0;
// 删除记录的数量
private int deletedNumber = 0;
public FileComparison(File oldFile, File newFile, File addedFile, File deletedFile, File modifyFile) {
this.oldFile = oldFile;
this.newFile = newFile;
this.addedFile = addedFile;
this.deletedFile = deletedFile;
this.modifyFile = modifyFile;
} /**
* 比较被修改的条目,以新文件为依据,若有不同则存入新文件的条目,
* 并在最后标记为“2”
*/
public void recordModified() {
long t0, t1;
System.out.println("开始比较修改的记录...");
t0 = System.currentTimeMillis();
int[][] oldFileMap = readFile(oldFile, LINE, deletedFile, deletedNumber);
BufferedReader br = null;
BufferedWriter bw = null;
int[] addedKeys = readKey(addedFile, addedNumber);
int count = 0;
try {
br = new BufferedReader(new FileReader(newFile));
bw = new BufferedWriter(new FileWriter(modifyFile));
String newFileLine = "";
int key;
int value;
while((newFileLine = br.readLine()) != null) {
key = getKey(newFileLine);
if(Arrays.binarySearch(addedKeys, key) < 0) {
int index = Arrays.binarySearch(oldFileMap[0], key);
if(index >= 0) {
value = getValue(newFileLine);
if(oldFileMap[1][index] != value) {
bw.write(newFileLine + MODIFY);
count++;
}
}
}
}
bw.close();
br.close();
}catch(IOException e) {
e.printStackTrace();
}
t1 = System.currentTimeMillis();
System.out.printf("被修改的记录比较完成,有 %d 条被修,耗时 %.1f 秒,存放于:%s%n", count, (t1-t0)/1000F, modifyFile.getName());
}
/**
* 比较新文件中,新增的条目(新文件中有的,旧文件中没有的),
* 记录到文件中,并在最后标记为“1”
*/
public void recordAdded() {
long t0, t1;
System.out.println("开始比较新增加的记录...");
t0 = System.currentTimeMillis();
int[] oldFileKey = readKey(oldFile, LINE);
BufferedReader br = null;
BufferedWriter bw = null;
try {
br = new BufferedReader(new FileReader(newFile));
bw = new BufferedWriter(new FileWriter(addedFile));
String newFileLine = "";
while((newFileLine = br.readLine()) != null) {
int key = getKey(newFileLine);
if(Arrays.binarySearch(oldFileKey, key) < 0){
addedNumber++;
bw.write(newFileLine + ADD);
}
}
br.close();
bw.close();
}catch(IOException e) {
e.printStackTrace();
}
oldFileKey = null;
br = null;
bw = null;
t1 = System.currentTimeMillis();
System.out.printf("新增加的记录比较完成,有 %d 条新增,耗时 %.1f 秒,存放于:%s%n", addedNumber, (t1-t0)/1000F, addedFile.getName());
System.gc();
}
/**
* 比较新文件中,删除的条目(旧文件中有的,新文件中没有的),
* 记录到文件中,并在最后标记为“3”
*/
public void recordDeleted() {
long t0, t1;
System.out.println("开始比较删除的记录...");
t0 = System.currentTimeMillis();
int[] newFileKey = readKey(newFile, LINE);
BufferedReader br = null;
BufferedWriter bw = null;
try {
br = new BufferedReader(new FileReader(oldFile));
bw = new BufferedWriter(new FileWriter(deletedFile));
String newFileLine = "";
int key;
while((newFileLine = br.readLine()) != null) {
key = getKey(newFileLine);
if(Arrays.binarySearch(newFileKey, key) < 0) {
deletedNumber++;
bw.write(newFileLine + DELETE);
}
}
br.close();
bw.close();
}catch(IOException e) {
e.printStackTrace();
}
newFileKey = null;
bw = null;
br = null;
t1 = System.currentTimeMillis();
System.out.printf("被删除的记录比较完成,有 %d 条删除,耗时 %.1f 秒,存放于:%s%n", deletedNumber, (t1-t0)/1000F, deletedFile.getName());
System.gc();
}
/****************
* 未完,接下帖 *
****************/
}
* 续,承上帖 *
**************/
/**
* 从文件中读取 key
* @param file 文件
* @param size 文件的最大行数
* @return int[] 已排序的 key 数组
*/
private int[] readKey(File file, int size) {
int[] keys = new int[size];
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(file));
String str = "";
int i = 0;
while ((str = br.readLine()) != null) {
keys[i++] = getKey(str);
}
br.close();
} catch (IOException e) {
e.printStackTrace();
}
Arrays.sort(keys);
br = null;
System.out.printf(" %s 的键读取完成,大小 %d%n", file.getName(), size);
System.gc();
return keys;
}
/**
* 映射源文件
* @param file 源文件
* @param fileLine 源文件的行数
* @param excludeFile 可以被排除的文件(删除/新增的记录集)
* @param excludeSize 被排除文件的行数
* @return int[][] int[0][] 源文件的 key 数组,按照 int[0][] 值的大小排序
* int[1][] 源文件的记录数组(已映射成为int数据)
*/
private int[][] readFile(File file, int fileLine, File excludeFile, int excludeSize) {
int[][] map = new int[2][fileLine - excludeSize];
BufferedReader br = null;
int[] excludeKeys = readKey(excludeFile, excludeSize);
int i = 0;
try {
br = new BufferedReader(new FileReader(oldFile));
String oldFileLine = "";
int key;
while((oldFileLine = br.readLine()) != null) {
key = getKey(oldFileLine);
if(Arrays.binarySearch(excludeKeys, key) < 0) {
map[0][i] = key;
map[1][i] = getValue(oldFileLine);
i++;
}
}
br.close();
}catch(IOException e) {
e.printStackTrace();
}
sort(map, 0, map[0].length);
excludeKeys = null;
System.out.printf(" %s 文件映射完成,记录数 %d%n", file.getName(), i);
System.gc();
return map;
}
/******************************************************
* 这个方法是核心,比较的成败取决于这个方法,当前采用的
* 是 hashcode,但有待于改进
*
* 为了节省存储空间,需要将字符串转换成一个int类型的值
* 期望能做到:
* 两个字符串相同时,其int值也相同;
* 两个字符串不同时,其int值也不同。
*
* @param str 需要转换的字符串
* @return 字符串的“int值”
******************************************************/
private int getValue(String str) {
return str.hashCode();
}
/**
* 从一行字符串中获得键
* @param str
* @return
*/
private int getKey(String str) {
char[] chars = str.toCharArray();
int i = 0;
int num = 0;
while(chars[i] != '|') {
num = num * 10 + (chars[i++] - '0');
}
return num;
}
/**
* 从JDK源代码中抄的Arrays.sort()排序算法,
* 改进一下,以x[0]排序,同时交换a[1]的值,即同步交换
* 排序前:
* [0] [1]
* 63 9
* 51 12
* 7 33
* 48 15
* 45 82
* 55 76
* 排序后([0]作为键,[1]作为值,交换键的同时交换值):
* 7 33
* 45 82
* 48 15
* 51 12
* 55 76
* 63 9
*/
private void sort(int x[][], int off, int len) {
if (len < 7) {
for (int i = off; i < len + off; i++)
for (int j = i; j > off && x[0][j - 1] > x[0][j]; j--)
swap(x, j, j - 1);
return;
}
// Choose a partition element, v
int m = off + (len >> 1); // Small arrays, middle element
if (len > 7) {
int l = off;
int n = off + len - 1;
if (len > 40) { // Big arrays, pseudomedian of 9
int s = len / 8;
l = med3(x, l, l + s, l + 2 * s);
m = med3(x, m - s, m, m + s);
n = med3(x, n - 2 * s, n - s, n);
}
m = med3(x, l, m, n); // Mid-size, med of 3
}
int v = x[0][m]; int a = off, b = a, c = off + len - 1, d = c;
while (true) {
while (b <= c && x[0][b] <= v) {
if (x[0][b] == v)
swap(x, a++, b);
b++;
}
while (c >= b && x[0][c] >= v) {
if (x[0][c] == v)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);
} int s, n = off + len;
s = Math.min(a - off, b - a);
vecswap(x, off, b - s, s);
s = Math.min(d - c, n - d - 1);
vecswap(x, b, n - s, s); if ((s = b - a) > 1)
sort(x, off, s);
if ((s = d - c) > 1)
sort(x, n - s, s);
}
private void swap(int x[][], int a, int b) {
int t = x[0][a];
x[0][a] = x[0][b];
x[0][b] = t;
t = x[1][a];
x[1][a] = x[1][b];
x[1][b] = t;
}
private void vecswap(int x[][], int a, int b, int n) {
for (int i = 0; i < n; i++, a++, b++)
swap(x, a, b);
}
private int med3(int x[][], int a, int b, int c) {
return (x[0][a] < x[0][b] ? (x[0][b] < x[0][c] ? b : x[0][a] < x[0][c] ? c : a)
: (x[0][b] > x[0][c] ? b : x[0][a] > x[0][c] ? c : a));
}Test.java(测试类)import java.io.File;public class Test { public static void main(String[] args) {
File oldFile = new File("f:/diff3.txt");
File newFile = new File("f:/diff4.txt");
File addFile = new File("f:/diff_add.txt");
File deleteFile = new File("f:/diff_delete.txt");
File modifyFile = new File("f:/diff_modify.txt");
FileComparison fc = new FileComparison(oldFile, newFile, addFile, deleteFile, modifyFile);
// 这两个需要在recordModified前执行
fc.recordAdded();
fc.recordDeleted();
fc.recordModified();
}
}
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;public class FileGenerator { private static MessageDigest md;
public final static String FIELD_SEPARATOR = "|";
public final static String LINE_SEPARATOR = System.getProperty("line.separator");
public final static int FILE_LINE = 10;
public static void main(String[] args) {
generateFile("f:/diff1.txt");
System.out.println("ok");
generateFile("f:/diff2.txt");
System.out.println("ok");
}
static {
try {
md = MessageDigest.getInstance("sha-1");
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
}
private static void init(String algorithm) {
try {
md = MessageDigest.getInstance(algorithm);
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
}
public static String encrypte(String plainText) {
md.update(plainText.getBytes());
byte[] b = md.digest();
StringBuffer output = new StringBuffer(32);
for (int i = 0; i < b.length; i++) {
String temp = Integer.toHexString(b[i] & 0xff);
if (temp.length() < 2) {
output.append("0");
}
output.append(temp);
}
return output.toString();
}
public static void generateFile(String filename) {
Set<Integer> set = new HashSet<Integer>();
File file = new File(filename);
Random ran = new Random();
BufferedWriter bw = null;
String[] content = new String[4];
init("sha-512");
for(int i = 0; i < 4; i++) {
content[i] = encrypte((i + System.nanoTime()) + "") + FIELD_SEPARATOR + encrypte(i+"");
}
try {
bw = new BufferedWriter(new FileWriter(file));
int key = -1;
set.add(key);
int ranNum = FILE_LINE + (FILE_LINE * 2) / 10;
for(int i = 0; i < FILE_LINE; i++) {
while(set.contains(key)) {
key = ran.nextInt(ranNum);
}
set.add(key);
String str = key + FIELD_SEPARATOR + content[(int)(System.nanoTime()%4)] + LINE_SEPARATOR;
bw.write(str);
}
set.clear();
bw.close();
}catch(IOException e) {
e.printStackTrace();
}
}
}
1、把A、B文件转换成定长记录文件,即每个字段、每条记录定长,再到内存中索引文件。
2、逐条读入A文件记录,利用B文件的索引做比较。再反着做。
中间有些技巧,比如比较过的做上记号,不再重复比较。
虚拟机运行时要设置 -Xmx1000000000 参数,不然会出现out of memory错误。package csdn;import java.util.*;
import java.io.*;class Index implements Comparable{
public int no;
public int begin;
public int end;
public boolean process;
public int hashCode(){
return no;
}
public boolean equals(Object o){
if (!(o instanceof Index))
return false;
return ((Index)o).no==no;
}
public int compareTo(Object o){
return no-((Index)o).no;
}
}public class TwoGbFile {
static final Random random=new Random();
/**
* 本方法产生模拟文件,5%删除,5%新增,10%修改
* 本机共耗时222秒,产生A文件1,694,863,131字节,产生B文件1,694,595,802字节
*/
static final int MAXRECORDCOUNT=5000000;
public static void createSimulativeFile(String afile,String bfile){
long tb=System.currentTimeMillis();
BufferedWriter fa=null;
BufferedWriter fb=null;
try{
fa=new BufferedWriter(new FileWriter(afile));
fb=new BufferedWriter(new FileWriter(bfile));
for (int i=1;i<MAXRECORDCOUNT;i++){
int rand=random.nextInt(100);
if (rand<5){ //删除
fa.write(createRandomString(i));
} else if (rand<10){ //新增
fb.write(createRandomString(i));
} else if (rand<20) {
fa.write(createRandomString(i));
fb.write(createRandomString(i));
} else {
String temp=createRandomString(i);
fa.write(temp);
fb.write(temp);
}
//if (i%10000==0){
// System.out.println(i);
//}
}
}catch (Exception ex){
ex.printStackTrace();
}finally{
try{
fa.close();
fb.close();
}catch(Exception ex){
ex.printStackTrace();
}
}
System.out.println("产生模拟数据共耗时:"+(System.currentTimeMillis()-tb)/1000+"秒");
}
/**
* 本方法产生随机字符串,字符串长度在300-400字节,格式:xxxx|...................
* @return
*/
static final int RANDSTR_LENVAR=95;
static final int RANDSTR_MINLEN=300;
static final String NEWLINEDELIMITER="\r\n";
static final int NEWLINEDELIMITERLEN=NEWLINEDELIMITER.length();
public static String createRandomString(int no){
StringBuffer str=new StringBuffer();
str.append(no);
str.append('|');
int len=random.nextInt(RANDSTR_LENVAR)+RANDSTR_MINLEN;
for (int i=0;i<len;i++){
str.append((char)('A'+random.nextInt(26)));
}
str.append(NEWLINEDELIMITER);
return str.toString();
}
/**
* 本方法建立索引
* 耗时约127秒
* @param filename
* @return
*/
public static List<Index> createIndex(String filename){
long tb=System.currentTimeMillis();
List<Index> list=new ArrayList<Index>();
BufferedReader f=null;
try{
f=new BufferedReader(new FileReader(filename));
String temp=null;
int pointer=0;
int cnt=0;
while ((temp=f.readLine())!=null){
cnt++;
int pos=temp.indexOf("|");
Index index=new Index();
index.begin=pointer;
pointer+=temp.length()+NEWLINEDELIMITER.length();
index.end=pointer;
int no=Integer.parseInt(temp.substring(0,pos));
index.no=no;
list.add(index);
//if (cnt%10000==0){
// System.out.println(cnt+","+no);
//}
}
}catch(Exception ex){
ex.printStackTrace();
}finally{
try{
f.close();
}catch(Exception ex){
ex.printStackTrace();
}
}
System.out.println("创建"+filename+"的索引共耗时:"+(System.currentTimeMillis()-tb)/1000+"秒");
tb=System.currentTimeMillis();
Collections.sort(list);
System.out.println("排序"+filename+"的索引共耗时:"+(System.currentTimeMillis()-tb)/1000+"秒");
return list;
}
/**
* 本方法从文件中读出指定的记录
* @param f
* @param x
* @return
*/
public static String getRecordFromFile(RandomAccessFile f,Index x){
String temp=null;
try{
f.seek(x.begin);
byte[] b=new byte[x.end-x.begin-NEWLINEDELIMITERLEN];
f.read(b);
temp=new String(b);
}catch(Exception ex){
ex.printStackTrace();
}
return temp;
}
/**
* 本方法完成主要功能:文件对比
* @param la
* @param lb
* @param afile
* @param bfile
* @param resultfile
*/
public static void compare(List<Index> la,List<Index> lb,String afile,String bfile,String resultfile){
long tb=System.currentTimeMillis();
BufferedWriter fr=null;
RandomAccessFile fa=null;
RandomAccessFile fb=null;
try{
fa=new RandomAccessFile(afile,"r");
fb=new RandomAccessFile(bfile,"r");
fr=new BufferedWriter(new FileWriter(resultfile));
for (Index xa:la){
int find=Collections.binarySearch(lb, xa);
if (find<0){//a的记录b中没找到,说明被删除
String s=getRecordFromFile(fa,xa);
fr.write(s+"|3"+NEWLINEDELIMITER);
} else {
Index xb=lb.get(find);
xb.process=true;
String s1=getRecordFromFile(fa,xa);
String s2=getRecordFromFile(fb,xb);
if (!s1.equals(s2)){
fr.write(s2+"|2"+NEWLINEDELIMITER);
}
}
}
System.out.println("完成"+afile+"对比"+bfile+"共耗时:"+(System.currentTimeMillis()-tb)/1000+"秒");
tb=System.currentTimeMillis();
for (Index xb:lb){
if (xb.process==true)
continue;
int find=Collections.binarySearch(la, xb);
if (find<0){//b的记录a中没找到,说明新增
String s=getRecordFromFile(fb,xb);
fr.write(s+"|1"+NEWLINEDELIMITER);
} else {//如果找到了,说明出问题了!
System.out.println("ERROR!!!!!!!!!!");
}
}
System.out.println("完成"+bfile+"对比"+afile+"共耗时:"+(System.currentTimeMillis()-tb)/1000+"秒");
}catch (Exception ex){
ex.printStackTrace();
}finally{
try{
fr.close();
fa.close();
fb.close();
}catch(Exception ex){
ex.printStackTrace();
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
createSimulativeFile("f:\\temp\\a.txt","f:\\temp\\b.txt");
List<Index> l1=createIndex("f:\\temp\\a.txt");
List<Index> l2=createIndex("f:\\temp\\b.txt");
compare(l1,l2,"f:\\temp\\a.txt","f:\\temp\\b.txt","f:\\temp\\c.txt");
}}
把:
pointer+=temp.length()+NEWLINEDELIMITER.length();
改为:
pointer+=temp.getBytes().length+NEWLINEDELIMITER.length();
1、做索引时不要用行号。看看我的代码,直接用记录的起止位置做索引,这样找起文件记录更快。毫无疑问,随机访问比顺序访问更快。
2、没必要用特征码!MD5,SHA-1算法都比较费时间,每个字符串都算一遍耗费不少时间,直接比较字符串虽然多读了次硬盘,但也慢不了多少。
3、这种程序用多线程纯属画蛇添足!
不过不记录行号而记录起止位置是个好方法,可以一用。
但如果不把记录转换成特征码,而是每次比较都要读取文件,是不是太慢了?
而转换字符串的时间和读取文件的时间肯定不在一个数量组上的。
另外想问一下,为什么用多线程是画蛇添足呢?还请点明一下,谢谢了
过使用字符串数组来存储数据的话500万行需要占用的内存超过300M,
如果再使用Java的集合类来存储的话,那内存占用还需要增加。由于我的机器配置不是很高(P4:2.8G;480M内存)我在41~43楼的代码
中已经全部舍弃了使用对象类型来存储数据了,直接采用基本的int类
型来存储,没有任何浪费,一行仅占用8个字节左右的内存。对于排序和查找都使用了Arrays.sort()、Arrays.binarySearch()方法,
这是个高度优化过的快速排序算法和拆半查找,对于大容量的排序特别
有效率。对于500万行的数据,执行的时间跟你的时间差不多,但是内存
占用量仅需要100M左右。
不过,采用多线程,提高的时间很有限(由于只有一个IO通道),而且程序出错的可能性大大提高,所以去掉多线程的操作.
而火龙果的方案的确不错,和我的最终方案非常一致,关键点都是要把很大的字符串的内容转化成特征码,不过你这里用的是hasCode,不安全,需要调整.因为存在重码的可能.所以,最终方案,先建立索引文件,再用索引文件对关键字进行比较,把不同的地方保存到新的集合中,按行号进行排序,再读取原文件的记录,具体的实现可参考火龙果的代码(稍微优化一下就可用了).对于大文件的比较,困难点在于不能够一次读入内存中(如果能够全部在内存中排序,就不会有问题了,java自带的排序就能工作的很好),而整个程序的瓶颈在于IO性能,读取磁盘的次数和读取量的多少决定了程序的性能.谢谢大家这么多天的讨论.希望大家都从中学到了东西(至少我学了不少东西,呵呵).