Rust 外部排序

ext-sort 是一个 Rust 外部排序算法实现。

外部排序是一类可以处理大量数据的排序算法。当待排序的数据不适合计算机的主内存（RAM）而必须存储在较慢的外部存储器（通常为硬盘驱动器）中时，就需要外部排序。排序过程分为两步。在第一步中，它对适合 RAM 的数据块进行排序，在第二步中，它将排序后的数据块合并在一起。更多信息请参阅 外部排序。

概述

ext-sort 支持以下功能

• 数据无关性：它默认支持所有实现 serde 序列化/反序列化的数据类型，否则您可以实现自己的序列化/反序列化机制。
• 序列化格式无关性：该库默认使用 MessagePack 序列化格式，但可以在不满足任务需求的情况下，轻松地替换为您自定义的格式。
• 多线程支持：支持多线程排序，这意味着数据将在多个线程中排序，充分利用 CPU 资源并减少排序时间。
• 内存限制支持：支持内存限制排序。这允许您限制排序内存消耗（需要 memory-limit 功能）。

基本示例

在 Cargo.toml 中激活 ext-sort crate 的 memory-limit 功能

[dependencies]
ext-sort = { version = "^0.1.4", features = ["memory-limit"] }

use std::fs;
use std::io::{self, prelude::*};
use std::path;

use bytesize::MB;
use env_logger;
use log;

use ext_sort::{buffer::mem::MemoryLimitedBufferBuilder, ExternalSorter, ExternalSorterBuilder};

fn main() {
    env_logger::Builder::new().filter_level(log::LevelFilter::Debug).init();

    let input_reader = io::BufReader::new(fs::File::open("input.txt").unwrap());
    let mut output_writer = io::BufWriter::new(fs::File::create("output.txt").unwrap());

    let sorter: ExternalSorter<String, io::Error, MemoryLimitedBufferBuilder> = ExternalSorterBuilder::new()
        .with_tmp_dir(path::Path::new("./"))
        .with_buffer(MemoryLimitedBufferBuilder::new(50 * MB))
        .build()
        .unwrap();

    let sorted = sorter.sort(input_reader.lines()).unwrap();

    for item in sorted.map(Result::unwrap) {
        output_writer.write_all(format!("{}\n", item).as_bytes()).unwrap();
    }
    output_writer.flush().unwrap();
}