天天好味道

没钱没权没户口，靠走靠吼靠小狗
随笔 - 68, 文章 - 1, 评论 - 517, 引用 - 5

导航

<2006年5月>
日一二三四五六
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

留言簿(12)

随笔分类

随笔档案

文章档案

我的链接

搜索

最新评论

阅读排行榜

评论排行榜

文件处理-最优算法？

同学的问题：

一个文本文件，2000多万行，每行用空格格开了8列。

什么算法可以最快从这些行中选出每列都不相同的？
就是说，对于两行，8列中的每个对应的列都要比较，如果有一列相同就算相同。


这个问题目前有很多解法(都不是我想出来的)：
1.八个hash table比较
2.(外)排序，然后删除重复的
3.插入数据库，排序，删除


不过还没有看到有人实现了的，其中第三个实现更加麻烦，还需要数据库...


posted on 2006-05-17 13:17 jzhang 阅读(1484) 评论(8)  编辑 收藏

评论

# re: 文件处理-最优算法？

强烈关注！
2006-05-17 16:59 | zuilang

# re: 文件处理-最优算法？

用数据库，可能还是最简单方便的方法。
给每行一个编号，数据库里处理后，编号没有了的就是重复了。

别的方法，可能运算下来很慢！
2006-05-17 18:12 | 清风雨

# re: 文件处理-最优算法？

看不懂楼主的题意。
2006-05-17 19:41 | 一笑

# re: 文件处理-最优算法？

偶猜测的含义是：
由于分割多个列的空格可能是不定的，如：
one two three four five six seven eight
one   two three  four    five  six  seven eight
应该被判断成相同的。

算法：
step1除去多余空格，将每行按照一个String塞入Set(集合)中
step2按要求格式打印Set中的每个元素
2006-05-17 20:22 | 一笑

# re: 文件处理-最优算法？

这里有个“参照物”的问题，即和谁比较？

从比较逻辑的角度来看，可能会出现这样的情况：
1. A = B（只有第一列相同）; B = C（只有第二列相同）。似乎A = B = C。
2. 如果A和C直接比较，没有相同的列，就是A != C。

这就出现了相互矛盾的结果，感觉问题本身有问题。
2006-05-18 11:34 | OneZ

# 恩，我也糊涂了

我同学没有把问题说清楚....
2006-05-18 16:56 | jzhang

# re: 文件处理-最优算法？

问题没说清楚，要找最优解还是可行解？如果是最优解的话看着像是求最大独立集，NPC。可行解就太简单了，随便贪心一下就出来了，或者干脆只挑一个。
2006-05-19 00:38 | abcs

# re: 文件处理-最优算法？

hash 吧 必要的话 存一部分到硬盘上
2007-11-06 16:47 | babam
标题  
姓名  
主页
验证码 *
内容   
  登录  使用高级评论  Top
[使用Ctrl+Enter键可以直接提交]