Самая быстрая идиоматическая процедура ввода / вывода в Rust для соревнований по программированию? - PullRequest
Новая
       15

Самая быстрая идиоматическая процедура ввода / вывода в Rust для соревнований по программированию?

5 голосов
/ 04 июня 2019

На мой вопрос был дан частичный ответ, поэтому я пересмотрел его в ответ на то, что узнал из комментариев и дополнительных экспериментов.

Итак, я хочу быструю процедуру ввода-вывода для соревнований по программированию, в которой проблемы решаются с одним файлом и без внешних ящиков. Он должен читать последовательность символов, разделенных пробелами, из 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 другим, кто проводит конкурсы по программированию.

...