大文本超快去重工具

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 2631 天前的主题，其中的信息可能已经有所发展或是发生改变。

简介

地址 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 次数，有利于加快去重速度；

第 1 条附言 2018-07-28 23:33:22 +08:00

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

第 2 条附言 2018-07-29 13:51:00 +08:00

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

第 3 条附言 2018-07-30 19:40:03 +08:00

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

10 条回复 2018-07-30 17:57:11 +08:00

swulling

2018-07-28 23:03:11 +08:00 via iPad

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

easylee

2018-07-28 23:12:00 +08:00

牛，赞一个。

lihongjie0209

2018-07-30 08:53:18 +08:00

发一个测试文件出来看看

firebroo

2018-07-30 09:49:27 +08:00

@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

2018-07-30 10:15:43 +08:00

用了多长时间呀？ 9000 万行

firebroo

2018-07-30 10:36:03 +08:00

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

lihongjie0209

2018-07-30 15:17:00 +08:00

```
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

2018-07-30 17:38:44 +08:00 via Android

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

s1ma

2018-07-30 17:42:10 +08:00

有点溜

Sfan

2018-07-30 17:57:11 +08:00

确实有点溜