// Generate Random Text
// 2019-03-20

#include <iostream>
#include <fstream>
#include <string>
#include <random>
#include <chrono>
using namespace std;
using namespace std::chrono;

void init_table( string &table );
void write_random_data( string &table, ofstream &fh );
void time_used(system_clock::time_point& time_a);

const long long FILE_SIZE = 1024*1024*100;

int main(int argc, char *argv[] ) 
{
    string table;
    init_table(table);
    string file = "F:/Cu_Topics/data.txt";
    ofstream fh(file, ios::binary);
    if ( fh.fail() ) {
        cout << "Can't open file" << endl;
        return 1;
    }

    system_clock::time_point timestamp = chrono::system_clock::now();
    write_random_data( table, fh );
    time_used( timestamp );
    return 0;
}

void write_random_data( string &table, ofstream &fh )
{
    char *buff = new char[FILE_SIZE+1];
    default_random_engine engine(12345);
    uniform_int_distribution<int> get_rand(0, table.size()-1);
    register long long iter = 0LL;
    while ( iter < FILE_SIZE ) {
        buff[iter++] = table[ get_rand(engine) ];
    }
    fh.write( buff, FILE_SIZE );
}

void init_table( string &table )
{
    table =
    "abcdefghijklmnopqrstuvwxyz"
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "1234567890" "1234567890"
    "   " "!(),-.:;?[]_{}" "\n\n"
    ;
}

void time_used(system_clock::time_point& time_a) {
    duration<double> diff;
    diff = chrono::system_clock::now() - time_a;
    cout << "Time used: " << diff.count() << endl;
    time_a = chrono::system_clock::now();
}
复制代码

@echo off
set /a MB=1^<^<20, SIZE=MB*100, SEED=2019
gensample %SIZE% %SEED%>F:/CU_Topics/a.txt
pause
复制代码

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();
        }
    }
}
复制代码

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();
    }
}
复制代码

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

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 {
复制代码

gensample 104857600 > sample_100M.txt
复制代码

gensample 1000 2019 > sample_1000_2019.txt
复制代码

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

gensample 100 2>NUL
复制代码

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

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