string - Rust 编程竞赛中最快的惯用 I/O 例程?
问题描述
我的问题已得到部分回答,因此我根据从评论和其他实验中学到的东西对其进行了修改。
总之,我想要一个用于编程竞赛的快速 I/O 例程,其中问题通过单个文件解决,无需外部 crate。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
是相当快的。如果我们不关心不安全性,它可以更快,而不是 do read_line()
into a String
,doing read_until(b'\n')
into a Vec<u8>
,然后是str::from_utf8_unchecked()
。
但是,我也想知道什么是最快的安全解决方案。有没有一种聪明的方法可以告诉 Rust 我的Scanner
实现实际上是安全的,消除了mem::transmute
? 直观地说,似乎我们应该将SplitWhitespace
对象视为拥有缓冲区,直到它在返回后被有效删除None
。
在其他条件相同的情况下,我想要一个“不错的”惯用标准库解决方案,因为我正试图向其他参加编程竞赛的人展示 Rust。
解决方案
我很高兴你问到,因为我在我的 LibCodeJam rust 实现中解决了这个确切的问题。具体来说,从 a 读取原始标记BufRead
由TokensReader
类型以及一些相关的小助手处理。
这是相关的摘录。这里的基本思想是扫描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());
}
},
}
}
}
}
这个实现不处理将字符串解析为FromStr
类型——这是单独处理的——但它确实处理正确的累积字节,将它们分成空格分隔的标记,并将这些标记解释为 UTF-8。它确实假设只有 ASCII 空白将用于分隔标记。
值得注意的是,FromStr
不能直接在fill_buf
缓冲区上使用,因为不能保证令牌不会跨越两次调用之间的边界,并且在现有缓冲区完全消耗之前fill_buf
无法强制 a读取更多字节。BufRead
我假设很明显,一旦你有了一个Ok(&str)
,你就可以FromStr
在闲暇时执行它。
此实现不是 0 复制,而是(摊销的)0 分配,它最大限度地减少了不必要的复制或缓冲。它使用单个持久缓冲区,仅当它对于单个令牌来说太小时才会调整大小,并且它会在令牌之间重用此缓冲区。字节直接从输入缓冲区复制到此缓冲区BufRead
,无需额外的中间复制。
推荐阅读
- excel - 在Excel中使用连接函数将两个单元格合并为一个
- java - 如何在个人 linux 裸机上管理微服务?
- php - 消息:未定义索引:图像更新图像 PHP
- python - 从python中的矩阵向量化所有组合的角度计算
- java - 现在以 16 位十六进制(16 个字符)获取时间和日期
- visual-studio-code - VS Code 的扩展图标消失了,为什么?
- javascript - 如果不匹配,数组中的 Javascript 对象仍然会被删除
- c# - 如何在 HttpRequestMessage 中传递图像文件?
- kotlin - 有没有办法实现`Comparable
` 与代表团? - c# - 将证书导入 Azure 密钥库:操作返回了无效的状态代码“冲突”