[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]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),语言不限,大家有兴趣吗?

回复 17# 523066680

当时随便找的图片 XD, 我有时间找张 SFW 的图片换上去

不要放弃啊, Rust 有官方文档的翻译: https://kaisery.github.io/trpl-zh-cn/

国内也出版了 Rust编程之道 和 深入浅出Rust, 资料其实也不算少了

我也试试找个嵌入式数据库, 看内存会下降多少(&耗时会上升多少
1

评分人数

TOP

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

回复 16# bailong360

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

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

TOP

本帖最后由 bailong360 于 2019-3-21 00:07 编辑

又优化了一下, 代码放到 GitHub 上了: https://github.com/Aloxaf/Rust-toys/tree/master/biglog_sort

主要改动如下:
1. 更换了 HashMap 的实现
2. 使用了多线程排序
3. 更换了内存分配器
4. 记录字符串出现次数的时候不保存字符串本身, 而是保存其 Hash

目前 100MB 耗时 11s+, 内存占用 614MB

(耐着性子测了一下 1GB, 耗时 3:12, 内存占用 4.2GB......看来中间数据也不能放在内存里, 这任务真的挺麻烦的= =

PS. 更新了签名图片

=== 深夜更新 ===
试着学 LZ 在 CU 的帖子里的方法, 只记录出现次数最高的项
100MB 耗时瞬间降到了 7s, 内存占用 282MB
1GB 耗时降到了 2:00, 内存占用 1GB

原来那么大的内存都用来存每行的每个字符串的出现次数了......
1

评分人数

TOP

用 @tigerpower 提供的生成器生成了 100MB 随机数据
目前耗时 27s, 内存占用 819MB
profile 了一下确实有 1/3 的时间花在了 HashMap 相关操作上

TOP

本帖最后由 bailong360 于 2019-3-20 18:07 编辑

回复 11# 523066680


    你这是 debug 模式, Rust 的 debug 模式巨慢(但编译很快). 要用 release 模式编译. 命令 cargo build --release

追求更卓越性能的话应该这样
  1. :: 使用针对本机 CPU 优化过的代码
  2. set RUSTFLAGS="-C target_cpu=native"
  3. cargo build --release
复制代码
有数据生成器就好办了, 我看再来优化一下
1

评分人数

    • 523066680: 学习了。PS:你的签名图片失效了技术 + 1

TOP

估计论坛里有不少人没有编译器,我上传一个编译好的,方便大家生成样本。
只要用的命令一样,大家在自己机器上能生成一样的样本,方便比较。
用法:gensample 字节数 [seed] [p] > 文件名.txt
seed为任意整数,缺省时为1
p为1时,打印空行,缺省时不打印空行
比如生成100M的样本:
  1. gensample 104857600 > sample_100M.txt
复制代码
生成1000字节,seed为2019的样本:
  1. gensample 1000 2019 > sample_1000_2019.txt
复制代码
生成3000字节保留空行的样本:
  1. gensample 3000 1 1 > sample_3000_p.txt
复制代码
将100字节样本在屏幕上输出:
  1. gensample 100 2>NUL
复制代码
大家生成的都一样,可用MD5校验:
  1. 49199e9274dd58d870227d12c1a20d3d *sample_100M.txt
  2. b7cb800dd095a113091d21c438cee872 *sample_1000_2019.txt
  3. b5192c110dad4f25ef1e4d0ad3d674a2 *sample_3000_p.txt
复制代码
100G的话是107374182400字节,请各位注意查看自己的硬盘剩余空间,谨慎使用
1

评分人数

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

想了想 100G 的话, 就算每行 80 个字符, 也有 10+ 亿行.
但 2G 内存就是连 10 亿个 int32 都放不下...
也就是说上面的代码还是应付不了数百GB的数据...这任务确实挺麻烦的= =

TOP

最近在学 Rust, 感觉非常好用~

回复 7# 523066680


    诶, 这位我有印象. 没想到竟然是 CU 的版主


我最终还是找了个 API 很难用的 crate 改了下, 先用起来再说

这次 100MB 用时 4.4s, 最高内存占用 200MB
看起来内存占用并没有减少, 嘛...因为文件大小太小了看不出来, 我也没耐心弄个几G的文件测试

加上多线程应该还能快一点, 不过试了下加上效果也不是很明显, 估计瓶颈应该在 IO 上 (也有可能是文件太小了...

主体代码如下, 完整代码传百度云了(论坛上传竟然要 Flash 支持?...
链接: https://pan.baidu.com/s/1lvI4UPwOclizsfp108j0EQ 提取码: s39j
  1. use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
  2. use extsort::*;
  3. use std::collections::HashMap;
  4. use std::fs::File;
  5. use std::io::{self, BufRead, BufReader, Read, Write};
  6. /// 从字符串中提取出"字符串"
  7. fn get_keywords(text: &str) -> Vec<&str> {
  8.     #[inline]
  9.     fn type_of(b: u8) -> u8 {
  10.         if b.is_ascii_alphabetic() {
  11.             return 1;
  12.         } else if b.is_ascii_digit() {
  13.             return 2;
  14.         } else {
  15.             return 3;
  16.         }
  17.     }
  18.     let bytes = text.as_bytes();
  19.     let mut ret = vec![];
  20.     let mut pos = 0;
  21.     for i in 0..bytes.len() - 1 {
  22.         if bytes[i].is_ascii_alphanumeric() && type_of(bytes[i]) != type_of(bytes[i + 1]) {
  23.             ret.push(&text[pos..=i]);
  24.             pos = i + 1;
  25.         } else if !bytes[i].is_ascii_alphanumeric() {
  26.             pos = i + 1;
  27.         }
  28.     }
  29.     if bytes[pos].is_ascii_alphanumeric() && type_of(bytes[pos]) == type_of(bytes[bytes.len() - 1])
  30.     {
  31.         ret.push(&text[pos..]);
  32.     }
  33.     ret
  34. }
  35. /// 读取文件, 确定每个"字符串"出现的次数
  36. fn make_keyword_map(path: &str) -> HashMap<String, u32> {
  37.     let file = BufReader::new(File::open(path).expect("无法打开文件"));
  38.     let mut ret = HashMap::new();
  39.     for line in file.lines() {
  40.         let line = line.unwrap();
  41.         for keyword in get_keywords(&line) {
  42.             *ret.entry(keyword.to_owned()).or_insert(0) += 1;
  43.         }
  44.     }
  45.     ret
  46. }
  47. /// 根据每行的字符串出现次数生成一个"特征值"
  48. fn make_line_map(
  49.     path: &str,
  50.     keyword_map: &HashMap<String, u32>,
  51. ) -> (usize, HashMap<Vec<u32>, Vec<u32>>) {
  52.     let file = BufReader::new(File::open(path).expect("无法打开文件"));
  53.     let mut line_cnt = 0;
  54.     let mut ret = HashMap::new();
  55.     for (idx, line) in file.lines().enumerate() {
  56.         let line = line.unwrap();
  57.         let keywords = get_keywords(&line);
  58.         let mut occurs_cnt = keywords
  59.             .iter()
  60.             .map(|&s| *keyword_map.get(s).unwrap())
  61.             .collect::<Vec<_>>();
  62.         occurs_cnt.sort_unstable_by(|a, b| b.cmp(a));
  63.         ret.entry(occurs_cnt).or_insert(vec![]).push(idx as u32);
  64.         line_cnt = idx;
  65.     }
  66.     (line_cnt, ret)
  67. }
  68. #[derive(Debug, Ord, PartialOrd, Eq, PartialEq)]
  69. struct Line(u32, String);
  70. impl Sortable<Line> for Line {
  71.     fn encode(item: Line, write: &mut Write) {
  72.         write.write_u32::<LittleEndian>(item.0).unwrap();
  73.         write.write(item.1.as_bytes()).unwrap();
  74.         write.write(&[b'\n']).unwrap();
  75.     }
  76.     fn decode(read: &mut Read) -> Option<Line> {
  77.         let idx = read.read_u32::<LittleEndian>().ok()?;
  78.         let mut bytes = read.bytes();
  79.         let s = String::from_utf8(
  80.             bytes
  81.                 .by_ref()
  82.                 .map(|b| b.unwrap())
  83.                 .take_while(|b| *b != b'\n')
  84.                 .collect(),
  85.         )
  86.         .unwrap();
  87.         // eprintln!("{} {}", idx, s);
  88.         Some(Line(idx, s))
  89.     }
  90. }
  91. fn main() {
  92.     let path = "a.txt";
  93.     let keyword_map = make_keyword_map(path);
  94.     let (line_cnt, line_map) = make_line_map(path, &keyword_map);
  95.     // 排序
  96.     let mut keys = line_map.keys().collect::<Vec<_>>();
  97.     keys.sort_unstable_by(|a, b| b.cmp(a));
  98.     // 确定每行的顺序
  99.     let mut line_order = vec![0; line_cnt + 1]; // TODO: 我没记错的话当 line_cnt 很大时会出问题
  100.     let mut order = 0 as u32;
  101.     for key in keys {
  102.         let idxs = line_map.get(key).unwrap();
  103.         for &idx in idxs {
  104.             line_order[idx as usize] = order;
  105.             order += 1;
  106.         }
  107.     }
  108.     // 进行外排序
  109.     let file = BufReader::new(File::open(path).expect("无法打开文件"));
  110.     let mut sorter = ExternalSorter::new();
  111.     sorter.set_max_size(1 * 1024 * 1024 * 1024 / 128); // 按每行 128 字节算, 1G 内存每次最多载入多少行
  112.     let sorted_iter = sorter
  113.         .sort_by(
  114.             file.lines()
  115.                 .enumerate()
  116.                 .map(|(idx, s)| Line(idx as u32, s.unwrap())),
  117.             |a, b| line_order[a.0 as usize].cmp(&line_order[b.0 as usize]),
  118.         )
  119.         .unwrap();
  120.     // 输出
  121.     let stdout = io::stdout();
  122.     let mut handle = stdout.lock();
  123.     for line in sorted_iter {
  124.         handle.write(line.1.as_bytes()).unwrap();
  125.         handle.write(&[b'\n']).unwrap();
  126.     }
  127. }
复制代码
1

评分人数

    • 523066680: Rust实战,我也顺带学一学技术 + 1

TOP

mark一下,,

TOP

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

回复 6# bailong360

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

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



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

TOP

嘛, 几千大洋是在 100G 数据, 2G 内存, C++ 编写 这几个条件下算出的价格
数据量减小一百倍(OR 内存增大一百倍[如果有钱的话]), 同时换简单点的语言的话, 价格应该就没那么高了
那位老哥显然没有理解"量变引起质变"这句话

用 Rust 简单试了下
  1. use lazy_static::lazy_static;
  2. use regex::Regex;
  3. use std::collections::HashMap;
  4. use std::fs::File;
  5. use std::io::{self, BufRead, BufReader, Write};
  6. /// 从字符串中提取出"字符串"
  7. fn get_keywords(text: &str) -> Vec<&str> {
  8.     lazy_static! {
  9.         static ref RE: Regex = Regex::new(r#"\d+|[a-zA-Z]+"#).unwrap();
  10.     }
  11.     RE.find_iter(text)
  12.         .map(|m| &text[m.start()..m.end()])
  13.         .collect()
  14. }
  15. fn main() {
  16.     let path = "a.txt";
  17.     let file = File::open(path).expect("无法打开文件");
  18.     let file = BufReader::new(file);
  19.     // 遍历全文, 确定每个"字符串"出现次数
  20.     let mut keyword_map = HashMap::new();
  21.     for line in file.lines() {
  22.         let line = line.unwrap();
  23.         for keyword in get_keywords(&line) {
  24.             // TODO: 此处的 clone 可避免否?
  25.             *keyword_map.entry(keyword.to_owned()).or_insert(0) += 1;
  26.         }
  27.     }
  28.     // 再次遍历, 确定每行所包含的字符串的出现次数
  29.     let file = BufReader::new(File::open(path).unwrap());
  30.     let mut line_map = HashMap::new();
  31.     for line in file.lines() {
  32.         let line = line.unwrap();
  33.         let keywords = get_keywords(&line);
  34.         let mut occurs_cnt = keywords.iter().map(|&s| *keyword_map.get(s).unwrap()).collect::<Vec<_>>();
  35.         occurs_cnt.sort_unstable_by(|a, b| b.cmp(a));
  36.         line_map.entry(occurs_cnt).or_insert(vec![]).push(line);
  37.     }
  38.     // 排序
  39.     let mut keys = line_map.keys().collect::<Vec<_>>();
  40.     keys.sort_unstable_by(|a, b| b.cmp(a));
  41.     // 输出
  42.     let stdout = io::stdout();
  43.     let mut handle = stdout.lock();
  44.     for key in keys {
  45.         let lines = line_map.get(key).unwrap();
  46.         for line in lines {
  47.             handle.write(line.as_bytes()).unwrap();
  48.             handle.write(&[b'\n']).unwrap();
  49.         }
  50.     }
  51. }
复制代码
没有测试文本, 就拿1L的文本复制粘贴了100MB测试了一下.
时间 7s
内存占用 176MB

内存占用大了点, 毕竟 Rust 好像没啥成熟的外排序库, 也不想手写 (
同时 profile 了一下发现 1/3 多的时间竟然花在了正则上面...这个倒是可以考虑手写一下
1

评分人数

TOP

一周才收6000真是良心价啊,我项目里的工程师收客户至少3000每人天
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

不管三七二十二,先mark收藏,随时关注.
我看到结果才明白,楼主说的"字符串"的划分,是纯数字[0-9]+,或纯字母[a-z]+.
QQ 33892006

TOP

返回列表