[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[挑战]100G文本统计+排序

本帖最后由 523066680 于 2019-1-30 11:16 编辑

源自ChinaUnix一个用户提出的问题,当时帮题主理清基础的处理方式,但是上G的文件依然没有写出高效率的代码。

原帖1,先从较简短的示例描述
http://bbs.chinaunix.net/thread-4263348-1-1.html
Windows19 发表于 2017-06-20 10:54
有几百GB,LOG,乱出八粗的

找出在文本内重复字符串从多到少打印,

找出重复次数最多字符串,然后整行打印  (注: 按2种类型条件判断统计,重复字母串次数,重复数字串次数,然后由多到少整行打印出来). 剩余的行也需一并打印出来(出来结果应和原LOG行数一致)

找出两种类型字符串在文本中重复最多次数,从多到少排序

a.txt
  1. 65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
  2. 65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
  3. yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5
  4. efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
  5. efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
  6. 65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
  7. 65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com
复制代码
按条件统计后应该得到(人工审核不知道有没错)
  1. 65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
  2. 65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
  3. 65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
  4. efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
  5. efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
  6. 65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com
  7. yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5
复制代码


这个题主是个典型的令人头痛的类型,因为他不把问题描述完整,一开始还发过几个简化过的问题的帖子,等到有人回复,他又渐渐把完整的问题浮出水面(可能有些细节他自己都不确定)
我在另一个帖子对处理方案做了详细说明,题主认为符合需求,可供参考:
523066680 发表于 2017-06-22 23:12
以原贴的段落为例,
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com

处理结果:
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5

每行的关键字在全文中出现的次数统计(单行内多次计为一次)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)

处理后的顺序(按行排序,从最高的频率开始对比;如果最高的次数相同,则对比第二列,以此类推)
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)

纯数字,前后对比:
Before:
[0]6,5,5,5,5,5,5,4,1,1
[1]6,5,5,5,5,5,5,4,2,1
[2]3,2,2,1,1,1,1,1,1,1,1
[3]6,5,5,5,5,5,5,2,1,1
[4]6,5,5,5,5,5,5,3,2,2
[5]6,5,5,5,5,5,5,4,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1

After
[1]6,5,5,5,5,5,5,4,2,1
[0]6,5,5,5,5,5,5,4,1,1
[5]6,5,5,5,5,5,5,4,1
[4]6,5,5,5,5,5,5,3,2,2
[3]6,5,5,5,5,5,5,2,1,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1
[2]3,2,2,1,1,1,1,1,1,1,1


注意上面的结果是同一“单词”在单行中重复多次记为一次的。应考虑按多次计算的情况(或者做个开关允许按不同方式处理)
65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
一行内两次算是2次吗?我以为一行内多次也计为1次,还特地做了判断

Windows19 回复 53# 523066680
如果算2次影响效率
那在一行内出现相同的算1次也可以

当然这个细节不是主要问题,数据量大以后要考虑哈希表的内存占用,如果改用文件存储数据结构,则需要考虑效率、硬盘占用问题。
"分而治之"策略 和 归并排序 应该是少不了的,个人认为是很好的锻炼。

当时(17年)的代码虽然借用DB_File模块支持了大文件处理,但效率极低,正打算重写。
为了减少过度的测试时间和硬盘消耗,将此问题稍作修改,改为10G文件(或1G),语言不限,大家有兴趣吗?

补充 RE: [挑战]100G文本统计+排序

本帖最后由 523066680 于 2019-3-20 19:52 编辑

这个问题有一个分支剧情,就是当时我建议题主去C++板块提问,windoze版主给他提出了解答此题6000元的报价
windoze 回复 3# Windows19

nonono,问题不是支付方式,而是金额。
你要的这个东西显然已经超出论坛技术讨论的范围,我拍脑袋的估一下差不多要一周左右的工作量,假设你找了一个月薪20000的人帮你做这件事,至少就得掏5000块,而且一般零活的价钱会在月结工资的基础上再向上浮动10~20%。

不知道lz有没有做好掏6000块的心理准备。

想借windoze版主的话提醒各位一下,技术是有价值的,像lxh发的那些各种需求,十几二十元,三五人去给他轮番全方位解答,着实是在贬低技术的价值。
以及windoze为这个问题评估了一个价值,各位如果感兴趣可以自己试试,有话题,可以讨论,代码也未必要发出来(几千大洋 )。

-----------------  2019-03-19 补充 -----------------
生成随机文本的代码(初步),
文件大小通过 FILE_SIZE 指定,效率偏低,在我这里(CPU 4GHz) 生成100M需要 13秒,太慢。欢迎补充更好的生成工具。
g++ -std=c++11 -O3 -o gen gen.cpp

-----------------  2019-03-20 更新 -----------------
g++ -std=c++11 -O3 -o gen gen.cpp
本机测试 100M 1.3秒
  1. // Generate Random Text
  2. // 2019-03-20
  3. #include <iostream>
  4. #include <fstream>
  5. #include <string>
  6. #include <random>
  7. #include <chrono>
  8. using namespace std;
  9. using namespace std::chrono;
  10. void init_table( string &table );
  11. void write_random_data( string &table, ofstream &fh );
  12. void time_used(system_clock::time_point& time_a);
  13. const long long FILE_SIZE = 1024*1024*100;
  14. int main(int argc, char *argv[] )
  15. {
  16.     string table;
  17.     init_table(table);
  18.     string file = "F:/Cu_Topics/data.txt";
  19.     ofstream fh(file, ios::binary);
  20.     if ( fh.fail() ) {
  21.         cout << "Can't open file" << endl;
  22.         return 1;
  23.     }
  24.     system_clock::time_point timestamp = chrono::system_clock::now();
  25.     write_random_data( table, fh );
  26.     time_used( timestamp );
  27.     return 0;
  28. }
  29. void write_random_data( string &table, ofstream &fh )
  30. {
  31.     char *buff = new char[FILE_SIZE+1];
  32.     default_random_engine engine(12345);
  33.     uniform_int_distribution<int> get_rand(0, table.size()-1);
  34.     register long long iter = 0LL;
  35.     while ( iter < FILE_SIZE ) {
  36.         buff[iter++] = table[ get_rand(engine) ];
  37.     }
  38.     fh.write( buff, FILE_SIZE );
  39. }
  40. void init_table( string &table )
  41. {
  42.     table =
  43.     "abcdefghijklmnopqrstuvwxyz"
  44.     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  45.     "1234567890" "1234567890"
  46.     "   " "!(),-.:;?[]_{}" "\n\n"
  47.     ;
  48. }
  49. void time_used(system_clock::time_point& time_a) {
  50.     duration<double> diff;
  51.     diff = chrono::system_clock::now() - time_a;
  52.     cout << "Time used: " << diff.count() << endl;
  53.     time_a = chrono::system_clock::now();
  54. }
复制代码
-----------------  2019-03-21 更新 -----------------
12楼提供了可执行的生成工具,我这里附一个小批处理,方便修改(但注意变量值范围限制)。
  1. @echo off
  2. set /a MB=1^<^<20, SIZE=MB*100, SEED=2019
  3. gensample %SIZE% %SEED%>F:/CU_Topics/a.txt
  4. pause
复制代码
1

评分人数

TOP

本帖最后由 523066680 于 2019-3-19 18:53 编辑

回复 6# bailong360

      在 bathome 看到 Rust 代码,很新鲜。
最近在知乎偶然看到 CU 的那位版主(徐晨),应该 Rust 他也熟的

https://zhuanlan.zhihu.com/p/38948830



我自己的重制版还没写出来,惭愧

TOP

本帖最后由 523066680 于 2019-3-20 17:06 编辑

回复 10# bailong360

    我用随机数据50M做测试,9楼 Rust 内存消耗峰值700M,耗时约 1 分38秒(程序输出重定向到 >nul ) CPU 频率 4GHz
  1. 12:52:01.14
  2.     Finished dev [unoptimized + debuginfo] target(s) in 0.14s
  3.      Running `target\debug\tmp.exe`
  4. 12:53:38.68
复制代码
用 tigerpower 工具生成的50M结果做测试,rust 出现错误提示:
  1. thread 'main' panicked at 'attempt to subtract with overflow', src\main.rs:23:17
  2. note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
  3. error: process didn't exit successfully: `target\debug\tmp.exe` (exit code: 101)
复制代码
  1. for i in 0..bytes.len()-1 {
复制代码
应该是空行会导致此问题,rust 不熟,在外面加了层 if bytes.len() > 1 {}
耗时 2分钟07 秒。

我认为这个问题的主要消耗在两个阶段:
1. 统计阶段,字符串/数字串的划分其实是线性处理的,真正的消耗在于超大的哈希表,大量的键值对会导致每一次查询都很慢。
2. 排序阶段,考虑归并排序(分而治之)。

随机内容的文件样本(这个版本没有空行):
https://pan.baidu.com/s/1F9KCxQKgIbbaS5PlKDNoBg
提取码:att3

期待更多尝试
1

评分人数

TOP

本帖最后由 523066680 于 2019-3-21 11:02 编辑

回复 16# bailong360

    强大,感觉 Rust 前景很明朗(我也想学,不过看英文PDF很吃力就放弃了)。
https://github.com/Aloxaf/MirageTankGo 上班时间点开这个雷姆吓一跳,已 follow

我当时的处理方案是用 Perl 的 DB_File 模块,把哈希表绑定到使用磁盘文件存储的数据结构(内部实现是 BTree?),模块简化了问题(所以我现在也还没学BTREE),暂时避免了爆内存。

TOP

返回列表