Rust 编程竞赛中最快的惯用 I/O 例程？

我的问题已部分得到解答，因此我根据从评论和其他实验中学到的知识对其进行了修改。

总之，我想要一个用于编程竞赛的快速 I/O 例程，其中使用单个文件解决问题，无需外部包。它应该从一个以空格分隔的标记序列中读取BufRead（标准输入或文件）。标记可以是整数、浮点数或 ASCII 单词，用空格和换行符分隔，所以看来我应该支持FromStr一般类型。一小部分问题是交互式的，这意味着最初并非所有输入都可用，但它总是完整的行。

对于上下文，这里是导致我在这里发帖的讨论 https://codeforces.com/blog/entry/67391?#comment-515711。有人编写了非常快速的自定义代码来直接从&[u8]的输出BufRead::fill_buf()，但它不是通用的FromStr.

这是我的迄今为止最好的解决方案 https://codeforces.com/contest/1151/submission/55185471（强调Scanner结构）：

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

fn solve<B: BufRead, W: Write>(mut scan: Scanner<B>, mut w: W) {
    let n = scan.token();
    let mut a = Vec::with_capacity(n);
    let mut b = Vec::with_capacity(n);
    for _ in 0..n {
        a.push(scan.token::<i64>());
        b.push(scan.token::<i64>());
    }
    let mut order: Vec<_> = (0..n).collect();
    order.sort_by_key(|&i| b[i] - a[i]);
    let ans: i64 = order
        .into_iter()
        .enumerate()
        .map(|(i, x)| a[x] * i as i64 + b[x] * (n - 1 - i) as i64)
        .sum();
    writeln!(w, "{}", ans);
}

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    let reader = Scanner::new(stdin.lock());
    let writer = io::BufWriter::new(stdout.lock());
    solve(reader, writer);
}

pub struct Scanner<B> {
    reader: B,
    buf_str: String,
    buf_iter: std::str::SplitWhitespace<'static>,
}
impl<B: BufRead> Scanner<B> {
    pub fn new(reader: B) -> Self {
        Self {
            reader,
            buf_str: String::new(),
            buf_iter: "".split_whitespace(),
        }
    }
    pub fn token<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buf_iter.next() {
                return token.parse().ok().expect("Failed parse");
            }
            self.buf_str.clear();
            self.reader
                .read_line(&mut self.buf_str)
                .expect("Failed read");
            self.buf_iter = unsafe { std::mem::transmute(self.buf_str.split_whitespace()) };
        }
    }
}

通过避免不必要的分配，这Scanner是相当快的。如果我们不关心不安全性，则可以通过以下方式加快速度，而不是这样做read_line() into a String, doing read_until(b'\n') into a Vec<u8>， 其次是str::from_utf8_unchecked().

不过我也想知道最快的是什么safe解决方案。有没有一种聪明的方法来告诉 Rust 我的Scanner实施确实是安全的，消除了mem::transmute？直觉上，我们似乎应该想到SplitWhitespace对象为owning缓冲区直到它返回后被有效删除None.

在其他条件相同的情况下，我想要一个“不错的”惯用标准库解决方案，因为我试图向其他参加编程竞赛的人展示 Rust。

我很高兴你问这个问题，因为我在 LibCodeJam rust 实现中解决了这个问题。具体来说，从 a 中读取原始令牌BufRead是由处理TokensReader type https://github.com/Lucretiel/LibCodeJam/blob/fcd6201e693082d3db334ad53116d2cc00ae1a17/rust/src/tokens.rs#L185-L227以及一些相关的小帮手。

这是相关摘录。这里的基本思想是扫描BufRead::fill_buf缓冲区的空白，并将非空白字符复制到本地缓冲区，该缓冲区在令牌调用之间重用。一旦找到空白字符，或者流结束，本地缓冲区将被解释为 UTF-8 并作为&str.

#[derive(Debug)]
pub enum LoadError {
    Io(io::Error),
    Utf8Error(Utf8Error),
    OutOfTokens,
}

/// TokenBuffer is a resuable buffer into which tokens are
/// read into, one-by-one. It is cleared but not deallocated
/// between each token.
#[derive(Debug)]
struct TokenBuffer(Vec<u8>);

impl TokenBuffer {
    /// Clear the buffer and start reading a new token
    fn lock(&mut self) -> TokenBufferLock {
        self.0.clear();
        TokenBufferLock(&mut self.0)
    }
}

/// TokenBufferLock is a helper type that helps manage the lifecycle
/// of reading a new token, then interpreting it as UTF-8.
#[derive(Debug, Default)]
struct TokenBufferLock<'a>(&'a mut Vec<u8>);

impl<'a> TokenBufferLock<'a> {
    /// Add some bytes to a token
    fn extend(&mut self, chunk: &[u8]) {
        self.0.extend(chunk)
    }

    /// Complete the token and attempt to interpret it as UTF-8
    fn complete(self) -> Result<&'a str, LoadError> {
        from_utf8(self.0).map_err(LoadError::Utf8Error)
    }
}

pub struct TokensReader<R: io::BufRead> {
    reader: R,
    token: TokenBuffer,
}

impl<R: io::BufRead> Tokens for TokensReader<R> {
    fn next_raw(&mut self) -> Result<&str, LoadError> {
        use std::io::ErrorKind::Interrupted;

        // Clear leading whitespace
        loop {
            match self.reader.fill_buf() {
                Err(ref err) if err.kind() == Interrupted => continue,
                Err(err) => return Err(LoadError::Io(err)),
                Ok([]) => return Err(LoadError::OutOfTokens),
                // Got some content; scan for the next non-whitespace character
                Ok(buf) => match buf.iter().position(|byte| !byte.is_ascii_whitespace()) {
                    Some(i) => {
                        self.reader.consume(i);
                        break;
                    }
                    None => self.reader.consume(buf.len()),
                },
            };
        }

        // If we reach this point, there is definitely a non-empty token ready to be read.
        let mut token_buf = self.token.lock();

        loop {
            match self.reader.fill_buf() {
                Err(ref err) if err.kind() == Interrupted => continue,
                Err(err) => return Err(LoadError::Io(err)),
                Ok([]) => return token_buf.complete(),
                // Got some content; scan for the next whitespace character
                Ok(buf) => match buf.iter().position(u8::is_ascii_whitespace) {
                    Some(i) => {
                        token_buf.extend(&buf[..i]);
                        self.reader.consume(i + 1);
                        return token_buf.complete();
                    }
                    None => {
                        token_buf.extend(buf);
                        self.reader.consume(buf.len());
                    }
                },
            }
        }
    }
}

本次实施doesn't处理将字符串解析为FromStr类型（单独处理），但它确实正确处理累积字节，将它们分隔成空格分隔的标记，并将这些标记解释为 UTF-8。它确实假设仅使用 ASCII 空格来分隔令牌。

值得注意的是FromStr不能直接用于fill_buf缓冲区，因为不能保证令牌不会跨越两个之间的边界fill_buf调用，并且没有办法强制BufRead读取更多字节，直到现有缓冲区被完全消耗。我假设很明显，一旦你有了Ok(&str)，你可以执行FromStr闲暇时就可以使用它。

此实现不是 0 复制，而是（摊销）0 分配，并且它最大限度地减少了不必要的复制或缓冲。它使用单个持久缓冲区，仅当它对于单个令牌来说太小时才调整大小，并且它在令牌之间重用该缓冲区。字节直接从输入复制到该缓冲区中BufRead缓冲区，无需额外的中间复制。