大文本超快去重工具

[firebroo]

简介

地址 https://github.com/firebroo/UnixTools/tree/master/uniq

可能有造轮子的嫌疑，去重思想就是借鉴的 awk '!a[$0]++{print}'，但是极端情况还是有用的，自己测试当文本超大的时候，速度上可以比 awk 高两倍左右，时间在一个量级内当然这不是特别有用的，但是内存差不多也可以节约二倍左右，个人感觉这还是非常有用的，毕竟内存还是毕竟宝贵的，各位顺便看看还有没有可以优化的余地？

优点

• 根据需求精简了 hashtable 里的 hash 节点的结构体，hash 节点里面只保存 key 和为了解决 hash 冲突的指针，节约内存；
• 根据文本行数调整 hashtable.h 的 HASH_TABLE_MAX_SIZE，减少 rehash 次数，有利于加快去重速度；

把 key 用指针的方式改为了可变长数组，内存比之前可节约文本行数*8 个字节。

目前 9 千万行 2.7G 完全不重复的数据，去重所需内存 5.2G 左右，而使用 awk 则需要 20G+的内存占用。

看了下 lua 的内核实现，又加了个 dev 分支，闭散列法解决 hash 碰撞，hashnode 里面使用 int 代替了指针，目前测试来看控制合理，两者内存的使用率差不多。

[swulling]

awk 的 hash 表内存占用有点高，支持。

[easylee]

牛，赞一个。

[lihongjie0209]

发一个测试文件出来看看

[firebroo]

@lihongjie0209

```python
import random

def random_str(len):
seed = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+=-"
ret = ""
for i in range(20):
ret += random.choice(seed)
return ret

with open("2.log", "w") as f:
for i in xrange(80000000):
line = random_str(30) + "\n"
f.write(line)
```

用 python 生成一个随机文件测试。

[engineer9]

用了多长时间呀？ 9000 万行

[firebroo]

@engineer9 按照 4#生成的 8 千万行随机数据，我的 Thinkpad i5 上面 1 分 50 秒。

[lihongjie0209]

```
from datetime import datetime

print("{} start".format(datetime.now()))

with open("3.log", "r") as f:
lines = f.readlines()

print("{} before: {} line".format(datetime.now(), len(lines)))

set_lines = set(lines)
print("{} after: {} line".format(datetime.now(), len(set_lines)))


```

输出:
```
2018-07-30 14:43:24.128476 start
2018-07-30 14:43:47.338141 before: 80000000 line
2018-07-30 14:44:04.591483 after: 80000000 line
```

机器配置: I7, 32G, 固态硬盘, 占用内存 8G



分析:


```
2018-07-30 14:43:24.128476 start
2018-07-30 14:43:47.338141 before: 80000000 line

读取文件耗时 23s

2018-07-30 14:43:47.338141 before: 80000000 line
2018-07-30 14:44:04.591483 after: 80000000 line

去重耗时 17s

```


去重这种事情文件越大, IO 的影响越重. 按照你的生成算法,生成的文件有 1.6G, 这么大的文件全部读取本身就很费时间, 在机械硬盘下这种现象更加明显, 文件大, 文件读取的所占的比重越大.

所以对于这种优化希望还是先 profile 再优化, 楼主能手写 hashtable 我是很佩服了.

[firebroo]

@lihongjie0209 我说了时间在一个量级意义不大，主要还是内存使用上面。

[s1ma]

有点溜

[Sfan]

确实有点溜