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

ivor

上校

Rank: 6 Rank: 6

帖子: 979
积分: 3381
技术: 172
捐助: 40
注册时间: 2012-1-7

3楼

发表于 2019-1-29 20:25 | 只看该作者

这种问题有点偏

yhcfsr

中尉

Rank: 5 Rank: 5

帖子: 635
积分: 969
技术: 107
捐助: 0
注册时间: 2017-11-23

4楼

发表于 2019-1-29 21:38 | 只看该作者

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

QQ 33892006

Batcher

管理员

Rank: 12

帖子: 14935
积分: 46142
技术: 857
捐助: 745
注册时间: 2008-6-9

5楼

发表于 2019-1-30 15:06 | 只看该作者

一周才收6000真是良心价啊，我项目里的工程师收客户至少3000每人天

我帮忙写的代码不需要付钱。如果一定要给，请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家，加入VIP会员！】http://bbs.bathome.net/thread-67716-1-1.html

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

6楼

发表于 2019-3-19 18:10 | 只看该作者

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

用 Rust 简单试了下

use lazy_static::lazy_static;
use regex::Regex;
use std::collections::HashMap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, Write};

/// 从字符串中提取出"字符串"
fn get_keywords(text: &str) -> Vec<&str> {
    lazy_static! {
        static ref RE: Regex = Regex::new(r#"\d+|[a-zA-Z]+"#).unwrap();
    }
    RE.find_iter(text)
        .map(|m| &text[m.start()..m.end()])
        .collect()
}

fn main() {
    let path = "a.txt";
    let file = File::open(path).expect("无法打开文件");
    let file = BufReader::new(file);

    // 遍历全文, 确定每个"字符串"出现次数
    let mut keyword_map = HashMap::new();

    for line in file.lines() {
        let line = line.unwrap();
        for keyword in get_keywords(&line) {
            // TODO: 此处的 clone 可避免否?
            *keyword_map.entry(keyword.to_owned()).or_insert(0) += 1;
        }
    }

    // 再次遍历, 确定每行所包含的字符串的出现次数
    let file = BufReader::new(File::open(path).unwrap());
    let mut line_map = HashMap::new();

    for line in file.lines() {
        let line = line.unwrap();
        let keywords = get_keywords(&line);

        let mut occurs_cnt = keywords.iter().map(|&s| *keyword_map.get(s).unwrap()).collect::<Vec<_>>();
        occurs_cnt.sort_unstable_by(|a, b| b.cmp(a));

        line_map.entry(occurs_cnt).or_insert(vec![]).push(line);
    }

    // 排序
    let mut keys = line_map.keys().collect::<Vec<_>>();
    keys.sort_unstable_by(|a, b| b.cmp(a));

    // 输出
    let stdout = io::stdout();
    let mut handle = stdout.lock();
    for key in keys {
        let lines = line_map.get(key).unwrap();
        for line in lines {
            handle.write(line.as_bytes()).unwrap();
            handle.write(&[b'\n']).unwrap();
        }
    }
}
复制代码

没有测试文本, 就拿1L的文本复制粘贴了100MB测试了一下.
时间 7s
内存占用 176MB

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

1 评分人数

523066680: Rust技术 + 1

链接:第三方下载

523066680

版主

Rank: 7 Rank: 7 Rank: 7

帖子: 3151
积分: 6455
技术: 317
捐助: 70
注册时间: 2008-8-3

7楼

发表于 2019-3-19 18:38 | 只看该作者

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

回复 6# bailong360

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

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

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

FuniCode 编程论坛

老刘1号

论坛巡查

Rank: 8 Rank: 8

帖子: 997
积分: 1789
技术: 205
捐助: 50
注册时间: 2016-4-17

8楼

发表于 2019-3-19 19:12 | 只看该作者

mark一下，，

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

9楼

发表于 2019-3-19 23:29 | 只看该作者

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

回复 7# 523066680

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

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

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

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

主体代码如下, 完整代码传百度云了(论坛上传竟然要 Flash 支持?...
链接: https://pan.baidu.com/s/1lvI4UPwOclizsfp108j0EQ 提取码: s39j

use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
use extsort::*;
use std::collections::HashMap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, Read, Write};

/// 从字符串中提取出"字符串"
fn get_keywords(text: &str) -> Vec<&str> {
    #[inline]
    fn type_of(b: u8) -> u8 {
        if b.is_ascii_alphabetic() {
            return 1;
        } else if b.is_ascii_digit() {
            return 2;
        } else {
            return 3;
        }
    }

    let bytes = text.as_bytes();
    let mut ret = vec![];
    let mut pos = 0;
    for i in 0..bytes.len() - 1 {
        if bytes[i].is_ascii_alphanumeric() && type_of(bytes[i]) != type_of(bytes[i + 1]) {
            ret.push(&text[pos..=i]);
            pos = i + 1;
        } else if !bytes[i].is_ascii_alphanumeric() {
            pos = i + 1;
        }
    }
    if bytes[pos].is_ascii_alphanumeric() && type_of(bytes[pos]) == type_of(bytes[bytes.len() - 1])
    {
        ret.push(&text[pos..]);
    }
    ret
}

/// 读取文件, 确定每个"字符串"出现的次数
fn make_keyword_map(path: &str) -> HashMap<String, u32> {
    let file = BufReader::new(File::open(path).expect("无法打开文件"));
    let mut ret = HashMap::new();

    for line in file.lines() {
        let line = line.unwrap();
        for keyword in get_keywords(&line) {
            *ret.entry(keyword.to_owned()).or_insert(0) += 1;
        }
    }

    ret
}

/// 根据每行的字符串出现次数生成一个"特征值"
fn make_line_map(
    path: &str,
    keyword_map: &HashMap<String, u32>,
) -> (usize, HashMap<Vec<u32>, Vec<u32>>) {
    let file = BufReader::new(File::open(path).expect("无法打开文件"));
    let mut line_cnt = 0;
    let mut ret = HashMap::new();

    for (idx, line) in file.lines().enumerate() {
        let line = line.unwrap();
        let keywords = get_keywords(&line);

        let mut occurs_cnt = keywords
            .iter()
            .map(|&s| *keyword_map.get(s).unwrap())
            .collect::<Vec<_>>();
        occurs_cnt.sort_unstable_by(|a, b| b.cmp(a));

        ret.entry(occurs_cnt).or_insert(vec![]).push(idx as u32);
        line_cnt = idx;
    }

    (line_cnt, ret)
}

#[derive(Debug, Ord, PartialOrd, Eq, PartialEq)]
struct Line(u32, String);

impl Sortable<Line> for Line {
    fn encode(item: Line, write: &mut Write) {
        write.write_u32::<LittleEndian>(item.0).unwrap();
        write.write(item.1.as_bytes()).unwrap();
        write.write(&[b'\n']).unwrap();
    }

    fn decode(read: &mut Read) -> Option<Line> {
        let idx = read.read_u32::<LittleEndian>().ok()?;
        let mut bytes = read.bytes();
        let s = String::from_utf8(
            bytes
                .by_ref()
                .map(|b| b.unwrap())
                .take_while(|b| *b != b'\n')
                .collect(),
        )
        .unwrap();
        // eprintln!("{} {}", idx, s);
        Some(Line(idx, s))
    }
}

fn main() {
    let path = "a.txt";

    let keyword_map = make_keyword_map(path);
    let (line_cnt, line_map) = make_line_map(path, &keyword_map);

    // 排序
    let mut keys = line_map.keys().collect::<Vec<_>>();
    keys.sort_unstable_by(|a, b| b.cmp(a));

    // 确定每行的顺序
    let mut line_order = vec![0; line_cnt + 1]; // TODO: 我没记错的话当 line_cnt 很大时会出问题
    let mut order = 0 as u32;
    for key in keys {
        let idxs = line_map.get(key).unwrap();
        for &idx in idxs {
            line_order[idx as usize] = order;
            order += 1;
        }
    }

    // 进行外排序
    let file = BufReader::new(File::open(path).expect("无法打开文件"));
    let mut sorter = ExternalSorter::new();
    sorter.set_max_size(1 * 1024 * 1024 * 1024 / 128); // 按每行 128 字节算, 1G 内存每次最多载入多少行
    let sorted_iter = sorter
        .sort_by(
            file.lines()
                .enumerate()
                .map(|(idx, s)| Line(idx as u32, s.unwrap())),
            |a, b| line_order[a.0 as usize].cmp(&line_order[b.0 as usize]),
        )
        .unwrap();

    // 输出
    let stdout = io::stdout();
    let mut handle = stdout.lock();
    for line in sorted_iter {
        handle.write(line.1.as_bytes()).unwrap();
        handle.write(&[b'\n']).unwrap();
    }
}
复制代码

1 评分人数

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

链接:第三方下载

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

10楼

发表于 2019-3-20 11:23 | 只看该作者

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

链接:第三方下载

523066680

版主

Rank: 7 Rank: 7 Rank: 7

帖子: 3151
积分: 6455
技术: 317
捐助: 70
注册时间: 2008-8-3

11楼

发表于 2019-3-20 12:53 | 只看该作者

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

回复 10# bailong360

我用随机数据50M做测试，9楼 Rust 内存消耗峰值700M，耗时约 1 分38秒（程序输出重定向到 >nul ） CPU 频率 4GHz

12:52:01.14
    Finished dev [unoptimized + debuginfo] target(s) in 0.14s
     Running `target\debug\tmp.exe`
12:53:38.68
复制代码

用 tigerpower 工具生成的50M结果做测试，rust 出现错误提示：

thread 'main' panicked at 'attempt to subtract with overflow', src\main.rs:23:17

note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
error: process didn't exit successfully: `target\debug\tmp.exe` (exit code: 101)
复制代码

for i in 0..bytes.len()-1 {
复制代码

应该是空行会导致此问题，rust 不熟，在外面加了层 if bytes.len() > 1 {}
耗时 2分钟07 秒。

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

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

期待更多尝试

1 评分人数

bailong360: 感谢指正技术 + 1

FuniCode 编程论坛

tigerpower

四级士官

Rank: 3 Rank: 3

帖子: 95
积分: 269
技术: 27
捐助: 0
注册时间: 2015-2-26

12楼

发表于 2019-3-20 13:07 | 只看该作者

估计论坛里有不少人没有编译器，我上传一个编译好的，方便大家生成样本。
只要用的命令一样，大家在自己机器上能生成一样的样本，方便比较。
用法：gensample 字节数 [seed] [p] > 文件名.txt
seed为任意整数，缺省时为1
p为1时，打印空行，缺省时不打印空行
比如生成100M的样本：

gensample 104857600 > sample_100M.txt
复制代码

生成1000字节，seed为2019的样本：

gensample 1000 2019 > sample_1000_2019.txt
复制代码

生成3000字节保留空行的样本：

gensample 3000 1 1 > sample_3000_p.txt
复制代码

将100字节样本在屏幕上输出：

gensample 100 2>NUL
复制代码

大家生成的都一样，可用MD5校验：

49199e9274dd58d870227d12c1a20d3d *sample_100M.txt
b7cb800dd095a113091d21c438cee872 *sample_1000_2019.txt
b5192c110dad4f25ef1e4d0ad3d674a2 *sample_3000_p.txt
复制代码

100G的话是107374182400字节，请各位注意查看自己的硬盘剩余空间，谨慎使用

1 评分人数

523066680: 收到PB + 6

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

13楼

发表于 2019-3-20 17:59 | 只看该作者

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

回复 11# 523066680

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

追求更卓越性能的话应该这样

:: 使用针对本机 CPU 优化过的代码
set RUSTFLAGS="-C target_cpu=native"
cargo build --release
复制代码

有数据生成器就好办了, 我看再来优化一下

1 评分人数

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

链接:第三方下载

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

14楼

发表于 2019-3-20 18:20 | 只看该作者

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

链接:第三方下载

Rank: 5 Rank: 5

帖子: 578
积分: 1235
技术: 170
捐助: 60
注册时间: 2012-8-5

15楼

发表于 2019-3-20 23:17 | 只看该作者

本帖最后由 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 评分人数

523066680: 强大技术 + 1

链接:第三方下载