Я реализовал простую программу для сортировки ввода уникальных чисел, заданных в виде десятичных знаков, в отдельной строке. Идея состоит в том, поскольку все числа уникальны, использовать (длинное) битовое поле, где 1 по индексу п означает, что число п находится в отсортированном списке. Таким образом, алгоритм состоит из следующих этапов (как описано в книге):

/* phase 1: initialize set to empty */
    for i = [0, n)
        bit[i] = 0
/* phase 2: insert present elements into the set */
    for each i in the input file
        bit[i] = 1
/* phase 3: write sorted output */
    for i = [0, n)
        if bit[i] == 1
            write i on the output file

Чтобы (заново) освежить мой Rust, я решил реализовать это в Rust, чтобы быть эффективной заменой sort (1) при задании -n вариант, предполагающий уникальный ввод. Таким образом, программа может называться:

$ bitfield # sorts stdin, writes to stdout
$ bitfield foo # sorts foo, writes to stdout
$ bitfield foo - bar # sorts foo, stdin, bar, writes to stdout

Как и в случае с упражнением, я предполагаю п (MAXNUM) быть 10 000 000:

use std::io::*;
use std::fs::File;
use std::env;

const MAXNUM: usize = 10_000_000;
const _MAXLINES: usize = 1_000_000;

fn fill(src: impl BufRead, bitfield: &mut[u8; MAXNUM >> 3]) -> Result<()> {
    for line in src.lines() {
        let num = line?.parse::<usize>().unwrap();
        if num > MAXNUM {
            return Err(Error::new(ErrorKind::Other, "number too large!"));
        }

        bitfield[num >> 3] |= 1 << (num & 0b111);
    }

    return Ok(());
}

fn print_sorted(bitfield: &[u8; MAXNUM >> 3], dest: impl Write) -> Result<()> {
    let mut dest = BufWriter::new(dest);

    for (i, byte) in bitfield.iter().enumerate() {
        for bit in 0..=0b111 {
            if byte & (1 << bit) != 0 {
                write!(&mut dest, "{}n", (i << 3) | bit)?;
            }
        }
    }

    return Ok(());
}

fn main() -> Result<()> {
    let mut bitfield: [u8; MAXNUM >> 3] = [0; MAXNUM >> 3];

    let args: Vec<_> = env::args().skip(1).collect();
    if args.is_empty() {
        fill(stdin().lock(), &mut bitfield)?;
    }

    for arg in args {
        if arg == "-" {
            fill(stdin().lock(), &mut bitfield)?;
        } else {
            let f = match File::open(&arg) {
                Err(e) => {
                    eprintln!("{}: {}", &arg, e);
                    continue;
                }
                Ok(f) => BufReader::new(f),
            };
            fill(f, &mut bitfield)?;
        }
    }
    print_sorted(&bitfield, stdout())?;

    return Ok(());
}

Для тестирования я использовал GNU / shuf (1), time (1) и cmp (1):

$ shuf -i 1-10000000 -n 1000000 > foo
$ time ./target/release/bitsort foo > bar
0.19s user 0.03s system 97% cpu 0.221 total
$ time sort -n foo > bar2
1.56s user 0.06s system 291% cpu 0.556 total
$ cmp bar bar2

Идеи?

use декларации

use std::env;
use std::fs::File;
use std::io::*;

Это хитрый способ импортировать io::{Error, Result}. Для удобства чтения может быть полезно указать io:: каждый раз. Также см. Раздел «Обработка ошибок» ниже.

use декларации могут быть сжатыми. Например:

use std::{env, fs::File, io};

Размещение

let args: Vec<_> = env::args().skip(1).collect();

Это ненужное выделение. В main функцию можно переписать в терминах итераторов, используя peekable:

fn main() -> Result<()> {
    // ...

    let mut args = env::args().skip(1).peekable();

    if args.peek().is_none() {
        // read from stdin
    }

    for arg in args {
        // handle arg
    }

    // ...
}

Обработка ошибок

Вместо того, чтобы разворачивать результат parse, вы можете распространить ошибку.

Для более крупной программы я бы предложил использовать anyhow ящик для обработки ошибок, что уменьшает количество шаблонов.

Разное

Не пиши return Ok(()); в конце функции — просто используйте
Ok(()).

Я думаю ты имел ввиду >= здесь: if num > MAXNUM.

В print_sorted, вы заверните писателя в BufWriter. Что, если писатель уже находится в буфере? Я бы оставил решение на усмотрение звонящего.

Вы можете использовать let mut bitfield = [0_u8; MAXNUM >> 3]; для меньшего дублирования.

Используя ящик вроде bit-set может быть полезно для удобочитаемости.