🐈

競技プログラミング用の高速な入力マクロ(Rust)

2021/04/20に公開

Rust

高速とか言ってごめんなさい遅いです
2021/03/27 追記早くなりました

モチベーション

Rust では C++ の様に簡素な標準入力を受け取る仕組みが提供されていません。そのため AtCoder では配慮されたのか標準入力を簡潔に記載する crate が使用できるようになっています。
私の観測範囲では特に理由がなければ proconio が使用されているイメージです。

そこで「AtCoder で Rust を使用し競技プログラミングを始めたが、codeforces 等の他コンテストに出場する際に標準入力がハードルで参加していない。」というユーザが出現するようになりました。(私です)
※codeforces では外部 crate は使用できない

方針

ということで決まった方針は以下

インターフェースはproconio 踏襲
非標準crate不使用
できるだけ高速
~~行数は少なく(重要)~~

実装

io_pro

#[macro_export]
macro_rules! input{
    (sc=$sc:expr,$($r:tt)*)=>{
        input_inner!{$sc,$($r)*}
    };
    ($($r:tt)*)=>{
        let mut sc=fast_input::Scanner::new(std::io::stdin().lock(),4096);
        input_inner!{sc,$($r)*}
    };
}

#[macro_export]
macro_rules! input_inner{
    ($sc:expr)=>{};
    ($sc:expr,)=>{};
    ($sc:expr,$var:ident:$t:tt$($r:tt)*)=>{
        let $var=read_value!($sc,$t);
        input_inner!{$sc $($r)*}
    };
}

#[macro_export]
macro_rules! read_value{
    ($sc:expr,($($t:tt),*))=>{
        ($(read_value!($sc,$t)),*)
    };
    ($sc:expr,[$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($sc,$t)).collect::<Vec<_>>()
    };
    ($sc:expr,Chars)=>{read_value!($sc,String).chars().collect::<Vec<char>>()};
    ($sc:expr,Usize1)=>{read_value!($sc,usize)-1};
    ($sc:expr,$t:ty)=>{$sc.next::<$t>()};
}
pub struct Scanner {
    buf: Vec<u8>,
    pos: usize,
}
impl Scanner {
    pub fn new<R: std::io::Read>(mut reader: R, estimated: usize) -> Self {
        let mut buf = Vec::with_capacity(estimated);
        let _ = std::io::copy(&mut reader, &mut buf).unwrap();
        if buf.last() != Some(&b'\n') {
            panic!("{}", 0);
        }
        Scanner { buf, pos: 0 }
    }
    #[inline]
    pub fn next<T: std::str::FromStr>(&mut self) -> T
    where
        T::Err: std::fmt::Debug,
    {
        let mut start = None;
        loop {
            match (self.buf[self.pos], start.is_some()) {
                (b' ', true) | (b'\n', true) => break,
                (_, true) | (b' ', false) | (b'\n', false) | (b'\r', false) => self.pos += 1,
                (_, false) => start = Some(self.pos),
            }
        }
        let target = &self.buf[start.unwrap()..self.pos];
        unsafe { std::str::from_utf8_unchecked(target) }
            .parse()
            .unwrap()
    }
}

前半のマクロ部分の~~パクリ~~元

proconio の元となった(?) @tanakh さんのマクロのインターフェース部分を使わせていただいています。
変更点

source を削除
入力の受け取り方法を変更

後半部分の構造体の~~パクリ~~元

この記事に @qryxip さんがコメントで書かれていた InputScanOnce を流用させていただいております。

変更点

codeforces に合わせて改行区切りに "\r" を追加

中身について

String::split_whitespace で分割する方式ではなく、一文字づつ処理する方式を選択しました。理由としては codeforces でよくあるマルチテストケースに対応し辛かったことが挙げられます。

マルチテストケースの例

3           // テストケース数
2           // n
1 0         // 長さ n の配列
3
3 2 1
5
10 9 8 7 6

proconio

input!(t: usize);
for _ in 0..t {
    input!(n: usize, a: [i64; n]);
    // 処理
}

io_pro

let mut sc = io_pro::Scanner::new(std::io::stdin().lock(), 4096);

input!(sc = sc, t: usize);
for _ in 0..t {
    input!(sc = sc, n: usize, a: [i64; n]);
    // 処理
}

proconio が裏で持っている入力のロックを手動で持ち回っています。input! マクロを一度しか使用しない場合は、 Scanner 構造体はマクロ側で生成するので proconio と同じインターフェースで利用できます。

計測

計測手法は先程の記事を踏襲し、1e7行の入力を読み込み平均を取ります。
今回は競技プログラミングでよくある大きな入力ということで、1e5も計測しています。
ソースはこちら
環境
Windows WSL2
1.50.0-x86_64-unknown-linux-gnu
core i5 9400F
結果

	1e5	1e7
proconio	40ms	2315.6ms
io_pro	66ms	5492.4ms

遅いですね。完。

まとめ

なんとか似たインターフェースで動くものになったのですが、遅い部分であったり、構造体の使い回しの記述であったり、入力後ctrl + Dしないと動いてくれなかったりで気に入ってない部分があります。
記事を書いた理由の大きい部分として「有識者がなにか教えてくれるかもしれない。」というのがあるので、何かお気づきの方は教えて下さい。
お願いします。

追記 2021/03/27

パースする部分はネックなのでは？との指摘をさんにいただき書き換え。

io_pro

#[macro_export]
macro_rules! input{
    (sc=$sc:expr,$($r:tt)*)=>{
        input_inner!{$sc,$($r)*}
    };
    ($($r:tt)*)=>{
        let mut sc=io_pro::Scanner::new(std::io::stdin().lock());
        input_inner!{sc,$($r)*}
    };
}

#[macro_export]
macro_rules! input_inner{
    ($sc:expr)=>{};
    ($sc:expr,)=>{};
    ($sc:expr,$var:ident:$t:tt$($r:tt)*)=>{
        let $var=read_value!($sc,$t);
        input_inner!{$sc $($r)*}
    };
}

#[macro_export]
macro_rules! read_value{
    ($sc:expr,($($t:tt),*))=>{
        ($(read_value!($sc,$t)),*)
    };
    ($sc:expr,[$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($sc,$t)).collect::<Vec<_>>()
    };
    ($sc:expr,Chars)=>{read_value!($sc,String).chars().collect::<Vec<char>>()};
    ($sc:expr,Usize1)=>{read_value!($sc,usize)-1};
    ($sc:expr,$t:ty)=>{$sc.next::<$t>()};
}
pub struct Scanner {
    s: Box<str>,
    input: std::iter::Peekable<std::str::SplitAsciiWhitespace<'static>>,
}
impl Scanner {
    pub fn new<R: std::io::Read>(mut reader: R) -> Self {
        let s = {
            let mut s = String::new();
            reader.read_to_string(&mut s).unwrap();
            s.into_boxed_str()
        };
        let mut sc = Scanner {
            s,
            input: "".split_ascii_whitespace().peekable(),
        };
        use std::mem;
        let s: &'static str = unsafe { mem::transmute(&*sc.s) };
        sc.input = s.split_ascii_whitespace().peekable();
        sc
    }
    #[inline]
    pub fn next<T: std::str::FromStr>(&mut self) -> T
    where
        T::Err: std::fmt::Debug,
    {
        self.input
            .next()
            .unwrap()
            .parse::<T>()
            .expect("Parse error")
    }
}

初期化の際に標準入力を読み切り、読み取った値をパースせず Scanner に保持する方式です。
最終的にproconio に近くなりましたね。~~というか一緒では~~

もう一度計測

	1e5	1e7
proconio	40ms	2315.6ms
io_pro	66ms	5492.4ms
追記	35.2ms	1839.4ms
早くなっていますね。

元々一文字ずつ読み取る方式にした理由としてこの記事での速度比較を参考にしていました。私の現在の環境では記事とは異なった結果が出ていそうですが、環境、標準ライブラリの処理等のどの要因が影響しているかまでは計測調査中となります。

GitHubで編集を提案

モチベーション

方針

実装

中身について

計測

まとめ

追記 2021/03/27

Discussion