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

Question

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

总而言之，我想要一个用于编程比赛的快速I / O例程，在该例程中，一个文件即可解决问题，而无需外部包装。它应从BufRead（标准输入或文件）空白序列中读取标记。标记可以是整数，浮点数或ASCII词，用空格和换行符分隔，因此看来我应该FromStr一般支持类型。少数问题是交互式的，这意味着一开始并不是所有输入都可用，但是总会出现完整的问题。

对于上下文，这是导致我在此处发布的讨论。有人编写了非常快速的自定义代码，以直接从的&[u8]输出中解析整数BufRead::fill_buf()，但在中不是通用的FromStr。

到目前为止，这是我最好的解决方案（强调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()成String，做read_until(b'\n')成Vec<u8>，其次是str::from_utf8_unchecked()。

但是，我也想知道什么是最快的安全解决方案。有没有一种聪明的方法告诉Rust我的Scanner实现实际上是安全的，消除了mem::transmute？直观地，似乎我们应该将SplitWhitespace对象视为拥有缓冲区，直到它在返回之后有效地被删除为止None。

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

Answer 1

我很高兴你问这个问题，因为我在 LibCodeJam rust 实现中解决了这个问题。具体来说，从 a 读取原始标记BufRead是由TokensReader类型以及一些微小的相关帮助程序处理的。

\n\n

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

\n\n

#[derive(Debug)]\npub enum LoadError {\n    Io(io::Error),\n    Utf8Error(Utf8Error),\n    OutOfTokens,\n}\n\n/// TokenBuffer is a resuable buffer into which tokens are\n/// read into, one-by-one. It is cleared but not deallocated\n/// between each token.\n#[derive(Debug)]\nstruct TokenBuffer(Vec<u8>);\n\nimpl TokenBuffer {\n    /// Clear the buffer and start reading a new token\n    fn lock(&mut self) -> TokenBufferLock {\n        self.0.clear();\n        TokenBufferLock(&mut self.0)\n    }\n}\n\n/// TokenBufferLock is a helper type that helps manage the lifecycle\n/// of reading a new token, then interpreting it as UTF-8.\n#[derive(Debug, Default)]\nstruct TokenBufferLock<\'a>(&\'a mut Vec<u8>);\n\nimpl<\'a> TokenBufferLock<\'a> {\n    /// Add some bytes to a token\n    fn extend(&mut self, chunk: &[u8]) {\n        self.0.extend(chunk)\n    }\n\n    /// Complete the token and attempt to interpret it as UTF-8\n    fn complete(self) -> Result<&\'a str, LoadError> {\n        from_utf8(self.0).map_err(LoadError::Utf8Error)\n    }\n}\n\npub struct TokensReader<R: io::BufRead> {\n    reader: R,\n    token: TokenBuffer,\n}\n\nimpl<R: io::BufRead> Tokens for TokensReader<R> {\n    fn next_raw(&mut self) -> Result<&str, LoadError> {\n        use std::io::ErrorKind::Interrupted;\n\n        // Clear leading whitespace\n        loop {\n            match self.reader.fill_buf() {\n                Err(ref err) if err.kind() == Interrupted => continue,\n                Err(err) => return Err(LoadError::Io(err)),\n                Ok([]) => return Err(LoadError::OutOfTokens),\n                // Got some content; scan for the next non-whitespace character\n                Ok(buf) => match buf.iter().position(|byte| !byte.is_ascii_whitespace()) {\n                    Some(i) => {\n                        self.reader.consume(i);\n                        break;\n                    }\n                    None => self.reader.consume(buf.len()),\n                },\n            };\n        }\n\n        // If we reach this point, there is definitely a non-empty token ready to be read.\n        let mut token_buf = self.token.lock();\n\n        loop {\n            match self.reader.fill_buf() {\n                Err(ref err) if err.kind() == Interrupted => continue,\n                Err(err) => return Err(LoadError::Io(err)),\n                Ok([]) => return token_buf.complete(),\n                // Got some content; scan for the next whitespace character\n                Ok(buf) => match buf.iter().position(u8::is_ascii_whitespace) {\n                    Some(i) => {\n                        token_buf.extend(&buf[..i]);\n                        self.reader.consume(i + 1);\n                        return token_buf.complete();\n                    }\n                    None => {\n                        token_buf.extend(buf);\n                        self.reader.consume(buf.len());\n                    }\n                },\n            }\n        }\n    }\n}\n

\n\n

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

\n\n

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

\n\n

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

\n