你能有多快？大家来比一下！

一个windows下的c,处理一个1.5G的txt文件，删除其中重复的行，每行不超过300字节，内容随机。我用的是哈希表，小弟不才跑了半个小时，期待高手出现！

18 个解决方案

#1

没有内存是有限制，我可直接往内存里装了 =w=b

#2

和硬件有关，这个竞赛开展不起来

#3

用哈希表如何处理冲撞的？

#4

可惜我的内存只有1G 估计光IO就是瓶颈
直接每行md5算了 

#5

要用哈希表处理这个问题，不考虑冲撞根本就不能保证结果的准确性。md5还不一样是哈希，只不过冲撞几率小点。

#6

可以专门建一个哈希表的文件
比如 每行都这样的格式
开始位置 结束位置 md5值
然后排下序，把相同部分读原文件直接比较

#7

引用 6 楼 flyrack 的回复:

可以专门建一个哈希表的文件
比如 每行都这样的格式
开始位置 结束位置 md5值
然后排下序，把相同部分读原文件直接比较

......冲撞处理呢？

#8

hash处理的话，俺怎么认为可以忽略hash的时间，只认为: 处理时间 = 读文件的时间N + N * 0.01
过滤完，再写入到另一文件，就要费点时间了。

#9

hash冲突的话你得回头，当然如果都装内存里这个问题就不大了。可另一方面如果内存够大，trie没什么特殊情况会比hash快不少。

#10

有没有人可以提供一个效率高点的代码啊，也让大家学习一下。除了哈希表还有什么好的办法吗》如果内存有限制的话，又该怎么办呢

#11

不是说不能用哈希表，而是使用哈希表就必须考虑冲撞处理。不考虑冲撞处理得出的结果是不可信的。此外，你没有具体描述文件的情况，也就不可能选择适合的哈希函数来完成这个任务。所以我认为你那半小时的计算做的只是无用功。

仅仅简单的说句：“内容随机”是不够的。文件中包含哪些字符？英文的还是中文的？仅仅常用字符还是带有其它字符？词汇量多还是少？重复行出现频繁吗？大致会占据多少比例？

想要得到优化的结果，没这些信息是无法做到的。软件开发并不是简单的学会语言和算法，需要了解的知识还有很多很多。

#12

我做的思路是读一行字符串，然后通过哈希函数计算出关键值，这样遍历一遍，没有考虑冲突，全部计算。然后是根据关键值进行排序，最后遍历一遍把关键值相等的用strcmp比较一样的则删除。这样效率确实很低，但不知道怎么用哈希表快速删除重复的行。

#13

文本内容有汉字，字母，数字，标点

#14

哈西表正好不适合干这事......哈希值不等那倒是没问题，一相等了哈希算法的毛病就钻出来了。

#15

那要删除一个文件中重复的行，应该怎么办呢。总不能第一句和之后的句子比较，然后再第二句和之后的比较吧。大神有什么好的方法吗

#16

要快很简单，别局限于比较，比较只是一部分，其他比如文本加载，信息记录等都有速度提升的空间

#17

英文的话还好想办法，汉字就比较麻烦了。汉字信息量太大了。

#18

如果重复行非常少的话也可以用哈希表来加速，选择冲撞率尽量小的哈希函数就好了。冲撞低了处理起来也就快。

如果词汇量很小的话选择trie就会很快，但要是词汇量太大内存就装不下了。