| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 795 人关注过本帖
标题:[求助]如何加速大容量文本文件自我比较,高手请进
只看楼主 加入收藏
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
 问题点数:0 回复次数:9 
[求助]如何加速大容量文本文件自我比较,高手请进

已知一个100万行文本文件,每行固定有m个字符,文本文件中任意两个文本行内容都不重复,现要找出符合如下条件的结果:

1、m>n,n不为0,如果某文本行与另一文本行有且只有n个字符不同,则称此两文本行n互异。

2、若某文本行在文件中有且只有i个n互异文本行,则保留此文本行。

3、找出所有存在i个n互异文本行的文本行。


我的做法是:

1、把100万行文本文件复制一份,设为B,源文件为A;

2、读入A的第k行,与B中逐行比较,比较100万次后看是否n互异文本行数为i,是则保留。

3、k从1到100万循环。

这样要作100万*100万次计算,时间耗费很久,我2.8G的机子要30分钟左右,可是我看网络上有的人实现同样的功能只要1分钟,甚至10几秒。

请高手指点下如何能实现10几秒的速度,是要多线程吗?

懂得话给个算法思路,要不给个相关链接,多谢了!!!!

搜索更多相关主题的帖子: 文本文件 容量 
2005-10-29 23:16
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
得分:0 
顶上去

2005-10-30 11:35
yk87458410
Rank: 1
等 级:新手上路
帖 子:65
专家分:0
注 册:2005-9-26
收藏
得分:0 
好难啊.我不会,不过那位高手做出来了.我会过来学习学习的.

2005-10-30 11:54
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
得分:0 
怎么都没人懂?

2005-10-31 19:59
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
你的算法是比较100万*100万次,其实可以更少比一半。(100万+1)*50万次。

文件的前一行与其后的所有行比较,并作计数。

如:查找条件是有8个字符相同的

1。用行1去比行2,行3,行4,行5。符合条件的计数各加1

2。用行2去比行3,行4,行5。符合条件的计数各加1

3。类推....


1。 1234567890 2 5 计为 2
2。 1234567800 1 5 计为 2
3。 3456789012 计为 0
4。 3456789456 计为 0
5。 1234567877 1 2 计为 2

[此贴子已经被作者于2005-10-31 20:56:52编辑过]


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-10-31 20:55
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
采用上述算法,非常适合使用多线程,你完全可起足够多的线程从不同的起点开起对比。十几秒不说,按你的算法单线程只要30分钟,我的算法对比量又少了一半,也就是15分钟,如果起几个线程,1,2分钟应足够了吧?

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-10-31 21:05
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
得分:0 
你这个算法我还是不大明白,

1。 1234567890 2 5 计为 2
2。 1234567800 1 5 计为 2
3。 3456789012 计为 0
4。 3456789456 计为 0
5。 1234567877 1 2 计为 2

如果1。为1234567891的话,那么2。就有2个8个字符相同的,它们是1234567890和1234567877。可是1234567890没计算进去。只比较后面的话,前面有互异的不就漏掉了吗?还有红色部分的5、5、2是什么意思?

忘了说明一下,比较是按位进行的,1234567891和1234567800是2互异,3456789012和1234567890是10互异。

[此贴子已经被作者于2005-11-1 0:18:07编辑过]


2005-11-01 00:06
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
得分:0 

对于第n行来说只比较n+1.......100万行,那么前面1....n-1行怎么办,关键是我不理解如何把前面比较过的结果记在n行上。难道是构造一个含100万个元素的数组来记录?有点明白了,我要仔细再想一想。

[此贴子已经被作者于2005-11-1 0:33:45编辑过]


2005-11-01 00:28
tiger92061
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-10-29
收藏
得分:0 
还是没想明白如何把前面比较过的结果记在n行上,斑竹再指点下

2005-11-02 21:42
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
这个i很大么?你的程序很占内存么?用数组来记录也行,数值达到i的大小就不必累计了。

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-11-02 23:42
快速回复:[求助]如何加速大容量文本文件自我比较,高手请进
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030678 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved