这是一个创建于 2296 天前的主题，其中的信息可能已经有所发展或是发生改变。
简介
地址 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 代替了指针，目前测试来看控制合理，两者内存的使用率差不多。
 |
1
swulling 2018-07-28 23:03:11 +08:00 via iPad
awk 的 hash 表内存占用有点高，支持。
|
 |
2
easylee 2018-07-28 23:12:00 +08:00
牛，赞一个。
|
 |
3
lihongjie0209 2018-07-30 08:53:18 +08:00
发一个测试文件出来看看
|
 |
4
firebroo OP @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 生成一个随机文件测试。 |
 |
5
engineer9 2018-07-30 10:15:43 +08:00
用了多长时间呀？ 9000 万行
|
|
7
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 我是很佩服了. |
|
8
firebroo OP @lihongjie0209 我说了时间在一个量级意义不大，主要还是内存使用上面。
|
 |
9
s1ma 2018-07-30 17:42:10 +08:00
有点溜
|
 |
10
Sfan 2018-07-30 17:57:11 +08:00
确实有点溜
|
Select Language