Skip to content

2020 Update

Jump to bottom Edit New page
Ryo Yamashita edited this page Oct 22, 2020 · 25 revisions

AtCoder 2020年言語アップデート以降の環境

AtCoder の2020年言語アップデート以降で利用できるようになる Rust のバージョンとクレートの一覧です。

Rust

情報を割り出すのには各コンテストの「コードテスト」("Custom Test")を使うといいです。

ただ2KiB (一時期は1KiBだった)の出力の制限があります。 atcoder-rust-baseを用意するにあたってはこのようなツールを作ってファイルをcatしました。

bash-on-atcoder (Crates.ioには最近上げた)

See also:

https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/Since-1.15.1#以上の情報を割り出す方法

クレート

最終的には次のクレートが導入される予定です。

num

badge badge badge badge badge badge

数値型に対するサポートを充実させるクレートです。

Version

v0.2.1

Sub-crates
  • num-bigint v0.2.6 badge badge
  • num-complex v0.2.4 badge badge
  • num-integer v0.1.42 badge badge
  • num-iter v0.1.40 badge badge
  • num-rational v0.2.4 badge badge
  • num-traits v0.2.11 badge badge
Details

num それ自体は上にあげた6つのサブクレートをまとめて再公開しているクレートです。今現在 num 上で実装されている関数や構造体はありません。 例えば多倍長整数は実際には num_bigint クレート内で実装されていますが、直接このクレートを依存関係に追加しなくても num::bigint としてアクセスすることができるようになっています。さらによく使われる一部のアイテム、例えば num_bigint::BigInt などは num 直下でも再公開されており、 num::BigInt として使うことができます。

各サブクレートを簡単に紹介します。

  • num-traits

    組み込み数値型を統一的に扱えるトレイトを提供します。

    順番（アルファベット順）を前後してこちらから紹介します。 Rustの整数型や浮動小数点数型には多くの同名のメソッド（例えば {min, max}_value, {leading, trailing}_zeros, pow など）が用意されていますが、それらをトレイトにまとめる抽象化はなされていません。 また、数値型の間をキャストするのに使う演算子 as をオーバーライドすることもできません。 これらの抽象化を提供することで、多くの数値型に対してジェネリックに使える関数などを定義しやすくするのが num-traits です。

    num-traitsはPrimInt, Floatをはじめとした多数のトレイトを提供します。 また、個別に指定すると面倒になりがちな複数のトレイトをまとめたトレイト（例えば+-*/%をすべて実装していることを表すNumOps など）を提供します。

    また数値型の抽象化の他にもOneとMulでべき乗を計算するpowやFloat::integer_decodeといった関数が新たに定義, 実装されています。 これらも地味ながら有用です。

    num-traitsによる抽象化は良くできていて、競技プログラミングのライブラリ整備においても有用です。 現状AtCoderの他においては使えませんが、必要なものに絞れば各トレイトの模倣は簡単です。 例えば上記のNumOpsの定義はこれなのでこれを真似ればT: Add<Output = T> + Sub<Output = T> + Mul<Output = T> + ..とする必要はなくなります。 ボイラープレートが嵩むなら、Rustのプログラミング全般に言えますがmacro_rules!が有用です。 AtCoder以外のコンテストに参加する方もライブラリを整備するときに参考にしてみてはいかかでしょうか。

    あるいはまずはお試しでnum-traitsを活用してライブラリを組むという手もあります。 クレート依存を絶ちたくなった場合、例としてPrimIntはこのようにすれば簡易的なものが手に入ります。

    use std::ops::{Add, Div, Mul, Rem, Sub};

// 必要な分だけ
pub trait PrimInt:
    Copy
    + Ord
    + Add<Output = Self>
    + Sub<Output = Self>
    + Mul<Output = Self>
    + Div<Output = Self>
    + Rem<Output = Self>
{
    fn zero(self) -> Self;
    fn one(self) -> Self;
    fn trailing_zeros(self) -> u32;
    fn pow(self, exp: u32) -> Self;
}

macro_rules! impl_prim_int(($($ty:ty),*) => {
    $(
        impl PrimInt for $ty {
            fn zero(self) -> Self {
                0
            }

            fn one(self) -> Self {
                1
            }

            fn trailing_zeros(self) -> u32 {
                self.trailing_zeros()
            }

            fn pow(self, exp: u32) -> Self {
                self.pow(exp)
            }
        }
    )*
});

impl_prim_int!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);

  • num-iter

    ジェネリックな整数型やカスタム整数型へのイテレータのサポートを追加します。

    プリミティブの整数型にはstd::iter::Stepが実装されています。 これはインクリメント等の操作を定義したトレイトです。 これにより整数型の範囲（a..bやa..=b）はイテレータになり、for文で回せるようになります。 しかしリンク先を見ていただけるとわかりますがstd::iter::Stepはまだunstableです。 つまりカスタム整数型やジェネリック整数型に対してa..b等をイテレータにすることはできません。

    このクレートは代替としてstd::cmp::PartialOrd (大小比較)とstd::ops::Add (加法)と num_traits::One (乗法単位元 = 1)を使って範囲を示すイテレータを生成する関数を提供します。

    また、range_step, range_step_inclusiveという1以外のステップを設定できるものもあります。 ただRust 1.28でIterator::step_byが安定化されたので具体的な整数型に対して使うことは無いでしょう。

    TODO: パフォーマンスは?

  • num-bigint

    多倍長整数、すなわち巨大な整数のサポートです。

    通常のRustで利用できる型のうち最大の整数を扱える型はu128ですが、場合によってはそれよりも大きな数を扱いたいことがあります。 そういったニーズに答える BigInt, BigUint と、それらの型の乱数を生成するのに利用する RandomBits を提供しています。

  • num-complex

    複素数型のサポートです。

    Complex<_>, ComplexDistribution<_, _> を提供します。

  • num-integer

    整数関連のサポートを強化します。

    u16, i32などの組み込み整数型とBigIntなどのカスタム整数型を拡張するInteger, Rootsと、これらを使った関数 (gcd, sqrt, binomial など) を提供します。

  • num-rational

    有理数型、すなわち分数のサポートです。

    有理数を扱うときには通常浮動小数点数が用いられますが、大抵の場合誤差と戦う必要が出てます。

    このクレートはRatio<_>を提供します。 これは以下の場合に有用です。

    1. 64-bit/64-bit、または128-bit/128-bitの分数で表現できる（一応BigIntやBigUintも使えますが..）
    2. 浮動小数点数だと苦しい（苦しくないのならf64を使うべきです）
    3. 大小比較が必要（等値比較のみで良いのならいくつかのpに対してℤ/pℤ上で計算すれば良いです）

    See also: 誤差と戦う小手先のテク - みさわめも

Examples

num-derive

badge badge badge badge badge badge

自分で新しく作った newtype に、 num で定義されるトレイトを自動実装する機能を追加するクレートです。

Version

v0.3.0

Details

先に挙げられた Float や Num といったトレイトを、新しく定義した newtype に #[derive(Num)] などを利用して自動実装できるようになります。

Rust では、実質的に同じ型の値を持つ型であっても型システム上で区別するために新しい構造体を作る、いわゆる newtype パターンが広く利用されています。例えば、グラフ構造の頂点番号と重みに専用の Index 型や Weight 型を用意するなどが考えられます。こうすることで、たとえどちらも実質的には i32 であったとしても、頂点番号と重みを間違えるとコンパイルエラーとなるようにでき、バグを埋め込む確率を下げることができます。しかし、区別する弊害として Weight 型同士の四則演算を個別に実装する必要が生まれます。この型への四則演算の実装をただひたすら中身の整数同士の演算として定義するのは面倒な作業なのですが、このクレートを使うと次のように自動実装させることができます。

use num_derive::{FromPrimitive, Num, NumCast, NumOps, One, ToPrimitive, Zero};

#[derive(
    Debug,
    Eq,
    PartialEq,
    PartialOrd,
    Ord,
    FromPrimitive,
    ToPrimitive,
    One,
    Zero,
    Num,
    NumCast,
    NumOps,
)]
struct Weight(i32);

fn main() {
    let w1 = Weight(3);
    let w2 = Weight(4);
    println!("{:?}", w1 + w2); // => "Weight(7)"
}

すべての四則演算を定義するのは都合が悪い場合でも、例えば Zero だけ実装したり FromPrimitive だけ実装したりということも可能です。

また、値を取らない普通の enum に対して FromPrimitiveとToPrimitive を実装することもできます。数値を enum に変換することは Rust では少し難しいのですが、 FromPrimitive を実装すれば簡単になります。

use num::{FromPrimitive as _, ToPrimitive as _};
use num_derive::{FromPrimitive, ToPrimitive};

#[derive(Debug, PartialEq, FromPrimitive, ToPrimitive)]
enum Color {
    Red,
    Blue,
    Green,
}

assert_eq!(Color::from_u32(0), Some(Color::Red));
assert_eq!(Color::from_u32(1), Some(Color::Blue));
assert_eq!(Color::from_u32(2), Some(Color::Green));
assert_eq!(Color::from_u32(3), None);

assert_eq!(Color::Red.to_u32(), Some(0));
assert_eq!(Color::Blue.to_u32(), Some(1));
assert_eq!(Color::Green.to_u32(), Some(2));
Examples

ndarray

badge badge badge badge badge badge

多次元配列のサポートです。

Version

v0.13.0

Details

Python の numpy.ndarray のような多次元配列を提供します。

通常 Rust で二次元以上の配列を扱うときは Vec<Vec<...>> の形で扱いますが、これはその型の通り Vec<...> の Vec でしかないので、全要素に対する変更などのユーティリティは用意されていません。

ndarray では NumPy のものと同じように形状変更やスライス、多次元配列同士の演算などの様々な機能を提供します。また行列の演算にも用いることができます。

使い方について、 NumPy ユーザー向けのドキュメントが ndarray::doc::ndarray_for_numpy_users に用意されています。ここでは ndarray の使い方が NumPy で同等のことをするコードと対比する形で解説されています。

Examples

nalgebra

badge badge badge badge badge badge

線形代数に特化したクレートです。

Version

v0.20.0

Sub-crates
  • alga v0.9.3 badge badge
Details

線形代数、特に行列に対する演算 (例えば、通常の和・積、アフィン変換、あるいはLU分解など) を扱うクレートです。一部では ndarray と似た部分もありますが、より行列に特化しています。また、少し使い勝手の異なる部分もあります。(例えば * と dot() が行なう演算が ndarray（や NumPy）とは逆になっています。)

ndarray ほどの手軽さはないかもしれませんが、 NumPy が提供しているもので ndarray には無いような関数もいくつかあります。

algaは抽象化のためのトレイトを提供します。 代数構造を扱うalga::generalと線形代数を扱うalga::linearからなります。

See also: データ構造と代数構造 - koba-e964の日記

Examples

libm

badge badge badge badge badge badge

C言語で馴染み深い数学ライブラリ、 libm の pure Rust による実装です。

Version

v0.2.1

Details

core (⊂ std)の浮動小数点数の関数はLLVMの実装によるものが多いですが、このクレートは基本的にplatform independentな結果を返すので特に浮動小数点数を扱うライブラリによく使われています。

しかしAtCoderにおいては他に気にするべき点が無数にありますし、実装の違いはさほど重要ではないのでstdの関数をそのまま使うのが良いでしょう。

ただstdでカバーされていない関数もいくつか存在します。 また関数名や呼び出し方が math.h (⊊ cmath) とほぼ一致するので、特に Rust に慣れていないだけの経験者には使いやすいかもしれません。

Examples
-let val = 10f64.powf(-9.0); // 実はプラットフォーム毎に微妙に挙動が違う
+let val = libm::pow(10.0, -9.0);
 assert_eq!(error.to_string(), "0.000000001");

rand

badge badge badge badge badge badge

擬似乱数ライブラリです。

Version

v0.7.3

Sub-crates
  • getrandom v0.1.14 badge badge
  • rand_chacha v0.2.2 badge badge
  • rand_core v0.5.1 badge badge
  • rand_hc v0.2.0 badge badge
  • rand_pcg v0.2.1 badge badge
Details

Rust には標準で疑似乱数を生成する機能がないため、乱数を利用するにはこのクレートを使う必要があります。このクレートは、例えば次のような擬似乱数生成器を提供します。

  • OsRng : プラットフォームごとに提供される方法で乱数を得る生成器。
  • SmallRng : より高速性を重視した乱数生成器。
  • StdRng : より安全性を重視した乱数生成器。
  • ThreadRng

それぞれに特徴がありますが、暗号理論的に安全である必要はなくより高速なほうが望ましい競技プログラミングには SmallRng が向いています。

rand_distr

badge badge badge badge badge badge

より多くの種類の乱数の分布を提供します。

Version

v0.2.2

Details

rand::distributionを拡張するものです。さらにいくつかの分布が追加されます。

petgraph

badge badge badge badge badge badge

グラフアルゴリズムを提供します。

Version

v0.5.0

Details
  • Graph : 隣接リスト形式のグラフです。
  • StableGraph : Graph と同様ですが、頂点削除時の挙動が異なります。
  • GraphMap : HashMap を使った隣接リスト形式のグラフです。
  • MatrixGraph : 隣接行列形式のグラフです。
  • Csr : 隣接行列が疎行列であるようなグラフです。
  • UnionFind : 素集合データ構造です。集合の「グループ分け」が効率的にできます。

またグラフをgraphviz形式で表示する機能もあり、グラフの形を図示することも簡単にできます。日頃の勉強やデバッグ時に役立つかもしれません。

TODO: Boost や NetworkX との比較

Examples

indexmap

badge badge badge badge badge badge

挿入順を保つ HashMap を提供します。

Version

v1.3.2

Details

IndexMap, IndexSet と、それらの maplit 風のコンストラクタ用マクロ indexmap!, indexset! を提供します。基本的には機能・インターフェース共に HashMap, HashSet と同様ですが、 iter() や keys() などで得られるイテレータが要素を挿入した順に返すことを保証しています。

regex

badge badge badge badge badge badge

正規表現を提供します。

Version

v1.3.6

Details

Rust には標準で正規表現を扱う機能がないため、このクレートを利用する必要があります。 str 用の regex::Regex と [u8] 用の regex::bytes::Regex が提供されます。

正規表現を使う前にはコンパイル処理が行われるため、繰り返し同じ正規表現を利用する場合は初回に一度だけコンパイルしたものを使い回すほうが高速です。したがって、正規表現を繰り返し呼ばれる関数で使ったり複数の関数で使い回したりするときは、コンパイル済みの正規表現をグローバル変数においておくほうが効率的です。これは遅延初期化グローバル変数を定義する lazy_static と組み合わせることで実現できます。

lazy_static! {
    static ref REGEX: Regex = Regex::new(r#"[Rr]egex"#).unwrap();
}

なお、正規表現にはバックスラッシュ (\) など通常の文字列では特別な意味を持つ文字が出現する機会も多いので、こういった場合は生文字列リテラルと言われる r#"..."# を使うことも手です。 r#" と "# で囲まれた部分は、ダブルクオート (") やバックスラッシュ (\) であっても通常の文字とみなされます。

Examples

lazy_static

badge badge badge badge badge badge

遅延初期化されるグローバル変数を提供します。

Version

v1.4.0

Details

グローバル変数が存在するとスレッド安全性と可変参照の排他性を保つことが非常に困難となるため、 Rust ではグローバル変数、特にミュータブルなものはできるだけ使わせないよう設計されています。 (言語からの削除すら検討されています。) 例えば、ミュータブルなグローバル変数へのすべてのアクセスは unsafe です。また、必ずコンパイル時に値が定まるものしか置くことができません。Rust のグローバル変数 (static 変数) については Rustのstaticいろいろ - 簡潔なQ といったページも参考になります。

なお、競技プログラミングでミュータブルなグローバル変数を利用することについては、 競技プログラミングにてミュータブルなグローバル変数を使ってみたら書くスピードが上がりそう - Qiita という話題もありました。これについては static mutの危険性 - Qiita が参考になります。是非ではなく、簡単に速く書けるメリットもあり、そのトレードオフもあるというご紹介です。

一方、こうした制約はあまりにも不便でもあります。特に必ずコンパイル時に値が定まっていなければいけないため、要素をもつ Vec や HashMap 、あるいはコンパイル済み正規表現を持たせることもできません。そこで、最初のアクセスまで値の初期化を遅延するグローバル変数が考えられました。 lazy_static は、それを簡単に定義するためのマクロ lazy_static! を提供しています。また、ミュータブルなグローバル変数が必要な場合も、これと Mutex などの適切なロックを組み合わせることで安全に定義することができます。

Examples

Before:

static mut VALUES: Vec<i32> = Vec::new();

unsafe {
    VALUES.extend_from_slice(&[1, 2, 3, 4]);
    assert_eq!(&*VALUES, &[1, 2, 3, 4]);
}

After:

use lazy_static::lazy_static;
use std::sync::Mutex;

lazy_static! {
    static ref VALUES: Mutex<Vec<i32>> = Mutex::default();
}

let mut values = VALUES.lock().unwrap();
values.extend_from_slice(&[1, 2, 3, 4]);
assert_eq!(&*values, &[1, 2, 3, 4]);

ordered-float

badge badge badge badge badge badge

浮動小数点数に Ord/Eq を実装するためのラッパー NotNan<f64>, OrderedFloat<f64> を提供します。

Version

v1.0.2

Details

Rust では、等値比較のために Eq と PartialEq が、順序比較のために Ord と PartialOrd が用意されています。それぞれ2つずつあるのは前者と後者で満たすべき制約が異なるからです。詳しくはリンク先を参照していただけれると分かりますが、 Eq のほうが PartialEq よりも制約が強く、 Ord のほうが PartialOrd よりも制約が強くなっています。比較演算子は PartialEq と PartialOrd が実装されている型で利用できます。

Eq と PartialEq の区別がある理由は、 a == a (反射律と呼ばれます) が常には成り立たない型があるからです。例えば浮動小数点数においては NaN != NaN となります。しかし、それをもって浮動小数点数には == や != 演算子を定義できないとするのはいささか極端です。したがって、比較演算子は反射律を要求しない PartialEq を利用します。

Ord と PartialOrd の区別がある理由も同様です。 a < b, a == b, a > b のいずれも成り立たないような a, b が存在する型があるからです。例えば浮動小数点数においては NaN < NaN, NaN == NaN, NaN > NaN はいずれも false となります。しかし、それをもって浮動小数点数には < や > 演算子を定義できないとするのはいささか極端です。したがって、比較演算子は反射律を要求しない PartialOrd を利用します。

一方で、厳密に順序が定まってほしい状況もあります。例えばジェネリックなソート関数においてNaNのような値が混じっていると非常に困ります。他の言語だと対象の型には全順序であることを期待し、そうではない場合結果は保証されません。C++に至っては鼻から悪魔が出てきます。 Rustでは対象が全順序でないと困る関数やデータ構造でEqやOrdを要求することで意図しない変な結果になるのを防止しています。(ただしその実装で嘘をつくと当然変な結果になります)

非常に Rust らしく厳格な仕組みですが、実際にEqまたはOrdが要求される場所では浮動小数点数をそのままで利用することができないという問題があります。

このうち関数については.foo()に対して大抵.foo_by(impl FnMut(..) -> std::cmp::Ordering)のようなものが共に用意されているのでこれを使えばどうにかすることができます。例えばソートについては以下のように雑にできます。この場合NaNが混じっていると.unwrap()の部分でpanicします。

let mut xs = vec![2.0, 1.0, 0.0];
xs.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());

maxやminも同様にIterator::max_byを使うかあるいはf64::maxでfoldすれば良いです。

use std::f64;

static XS: &[f64] = &[0.0, 1.0, 2.0];

let max = XS.iter().copied().fold(f64::NEG_INFINITY, f64::max);

しかしBTreeMap<_> (B木のマップ)やBinaryHeap<_> (優先度付きキュー)等のデータ構造になるとこうはいきません。 Ordを実装するf64/f32のラッパーが必要になります。

use std::collections::BinaryHeap;

let mut queue = BinaryHeap::<f64>::new();

// error[E0599]: no function or associated item named `new` found for type `std::collections::BinaryHeap<f64>` in the current scope
//  --> src/lib.rs:6:36
//   |
// 5 | let mut queue = BinaryHeap::<f64>::new();
//   |                                    ^^^ function or associated item not found in `std::collections::BinaryHeap<f64>`
//   |
//   = note: the method `new` exists but the following trait bounds were not satisfied:
//           `f64 : std::cmp::Ord`

ordered-floatはそのようなラッパーを2種類提供します。

  • NotNan<_>

    中身として NaN が含まれないことを保証します。 NotNan::newの返り値はResultでNaNを渡すとErrになります。 また計算過程で NaN となってしまった場合も整数型のように panic します。 ただしこちらはrelease build時でもチェックされます。 浮動小数点数は NaN を除けば Ord と Eq の要件を満たすため、 NotNan は Ord と Eq を実装することができます。

    実際に使う際ですが、f64からNotNan<f64>に変換するにはNotNan::new(x).unwrap()とする必要があります。 これは少々冗長です。 ただNotNan<f64>はFromStrを実装しているので標準入力からそのまま得ることができ、また四則演算の右辺には中身の型が許されているので1.0等のリテラルをどうするかについても困ることはそう無いはずです。

    use ordered_float::NotNan;

let x = "42.0".parse::<NotNan<_>>().unwrap(); // `proconio`等で読む。
let half: NotNan<_> = x / 2.0;
let plus_one: NotNan<_> = x + 1.0;

    それでもNotNanのリテラルが必要になる場合にはマクロを一行用意すると良いでしょう。

    macro_rules! notnan(($lit:literal) => (NotNan::new($lit).unwrap()));

let y = if p(x) { x } else { notnan!(1.0) };

  • OrderedFloat<_>

    NaN を「その浮動小数点数型の中で最大の値で NaN == NaN となる値」と定義する方法です。

    こちらはf64からの変換は容易ですがNotNanと違い四則演算自体ができません。std::cmp::Reverseのようなものだと思いましょう。

    use ordered_float::OrderedFloat;

let x = "42.0".parse::<OrderedFloat<f64>>().unwrap();

// Error
//let half: OrderedFloat<f64> = x / 2.0;
//let half: OrderedFloat<f64> = x / OrderedFloat(2.0);
let half: f64 = *x / 2.0;
let half: OrderedFloat<f64> = OrderedFloat(half);

// Error
//let plus_one: OrderedFloat<f64> = x + 1.0;
//let plus_one: OrderedFloat<f64> = x + OrderedFloat(1.0);
let plus_one: f64 = *x + 1.0;
let plus_one: OrderedFloat<f64> = OrderedFloat(plus_one);
Examples
 use itertools::Itertools as _;
+use ordered_float::OrderedFloat;

-use std::cmp;
 use std::collections::BTreeSet;

-#[derive(PartialEq, PartialOrd, Debug)]
-struct DirtyOrd(f64);
-
-// The inner value cannot be `NaN`... probably!
-impl Eq for DirtyOrd {}
-
-impl Ord for DirtyOrd {
-    fn cmp(&self, rhs: &Self) -> cmp::Ordering {
-        self.partial_cmp(rhs).unwrap()
-    }
-}
-
 let mut input = "10.0 30.0 20.0".split_whitespace();
 macro_rules! read(($ty:ty) => (input.next().unwrap().parse::<$ty>().unwrap()));

 let mut set = BTreeSet::new();
-set.insert(DirtyOrd(read!(f64) + 1.1));
-set.insert(DirtyOrd(read!(f64) + 3.3));
-set.insert(DirtyOrd(read!(f64) + 2.2));
+set.insert(OrderedFloat(read!(f64) + 1.1));
+set.insert(OrderedFloat(read!(f64) + 3.3));
+set.insert(OrderedFloat(read!(f64) + 2.2));

-assert_eq!(set.iter().map(|DirtyOrd(x)| x).join(" "), "11.1 22.2 33.3");
+assert_eq!(set.iter().join(" "), "11.1 22.2 33.3");
 use itertools::Itertools as _;
+use ordered_float::NotNan;

-use std::cmp;
 use std::collections::BTreeSet;

-#[derive(PartialEq, PartialOrd, Debug)]
-struct DirtyOrd(f64);
-
-// The inner value cannot be `NaN`... probably!
-impl Eq for DirtyOrd {}
-
-impl Ord for DirtyOrd {
-    fn cmp(&self, rhs: &Self) -> cmp::Ordering {
-        self.partial_cmp(rhs).unwrap()
-    }
-}
-
 let mut input = "10.0 30.0 20.0".split_whitespace();
 macro_rules! read(($ty:ty) => (input.next().unwrap().parse::<$ty>().unwrap()));

 let mut set = BTreeSet::new();
-set.insert(DirtyOrd(read!(f64) + 1.1));
-set.insert(DirtyOrd(read!(f64) + 3.3));
-set.insert(DirtyOrd(read!(f64) + 2.2));
+set.insert(read!(NotNan<_>) + 1.1);
+set.insert(read!(NotNan<_>) + 3.3);
+set.insert(read!(NotNan<_>) + 2.2);

-assert_eq!(set.iter().map(|DirtyOrd(x)| x).join(" "), "11.1 22.2 33.3");
+assert_eq!(set.iter().join(" "), "11.1 22.2 33.3");

TODO: 浮動小数点数をpriority queueとかに突っ込まなければならない問題がAtCoder上にないか

ascii

badge badge badge badge badge badge

ASCII 文字列をより扱いやすくするクレートです。

Version

v1.0.0

Details

Rust の組み込みの文字列型 &str は UTF-8 文字列であり、1 文字が 1 バイトで表されるとは限らないため、文字列に対するインデックスアクセスができないようになっています。したがって、文字単位のランダムアクセスをするためには毎回 .as_bytes()[i] とするか、一度 Vec<u8> や Vec<char> に変換してから扱うこととなります。ランダムアクセスをできるようにする代わりに str にある (replace などの) 便利なメソッド類を諦めることになります。

しかし、競技プログラミングの世界で扱う文字列は基本的にはアルファベットのみなのでインデックスアクセスに何の問題もありません。 ascii はこういった需要に答え、 ASCII 文字のみを含むような文字列をもう少し扱いやすくするクレートです。 AsciiChar, AsciiStr, AsciiString を提供します。それぞれの内部表現はu8, [u8], Vec<u8>であり、インデックスアクセスにオーバーヘッドは生じません。

Examples
use ascii::{AsciiChar, AsciiStr};

let mut s = AsciiStr::from_ascii("abcde\n").unwrap().to_owned();
s[2] = AsciiChar::C;
assert_eq!(s, "abCde\n");
assert_eq!(s.trim_end(), "abCde");

TODO: 実際に嬉しい例があるはずだが見つからない!

permutohedron

badge badge badge badge badge badge

順列を生成します。

Version

v0.2.4

Details

Ord を実装するような型 T のスライス [T] の拡張メソッドとして prev_permutation, next_permutation を提供します。また、順に順列を返していくイテレータ Heap や、少しだけ高速に順列を列挙できる関数 heap_recursive を提供します。

heap_recursive は Heap のアルゴリズムを使うもので、順に数列を生成していく場合は next_permutation を繰り返し利用するよりも少しだけパフォーマンスがよいようです。また、値の順序を要求しないため浮動小数点数でもそのまま使えます (順序について詳しくは ordered-float の項も参照ください) 。

Examples
use permutohedron::LexicalPermutation as _;

let mut values = [1, 2, 3];
loop {
    eprintln!("{:?}", values);
    if !values.next_permutation() {
        break;
    }
}

なお、 Rust には do-while 文はありませんが、 block expression { ... } を利用すれば次のように書くこともできてしまいます。ただし、誤解を招きやすい書き方になるため十分な注意が必要です。

use permutohedron::LexicalPermutation as _;

let mut values = [1, 2, 3];
while {
    eprintln!("{:?}", values);
    values.next_permutation()
} {}

heap_recursive() 関数を利用する場合は次のようになります。

let mut values = [1, 2, 3];
permutohedron::heap_recursive(&mut values, |values| eprintln!("{:?}", values));

superslice

badge badge badge badge badge badge

スライスの扱いを強化します。

Version

v1.0.0

Details

スライスに対して Ext トレイトとExt2トレイトにより以下の拡張メソッドを提供します。

  • lower_bound/upper_bound
    昇順にソートされた列に対し、指定された値以上の値になる (lower_bound) / 指定された値を超える (upper_bound) のような最初のインデックスを二分探索により求めます。 Rust 1.17 からは BTreeSet::range を使うこともできます。
  • lower_bound_by_key/upper_bound_by_key
    lower_bound/upper_bound と同様ですが、要素そのものではなくその各要素から定まる値を使います。
  • lower_bound_by/upper_bound_by
    lower_bound/upper_bound と同様ですが、比較関数を指定します。
  • equal_range/equal_range_by/equal_range_by_key 昇順にソートされた列に対し、値が指定された値と等しいようなインデックスの範囲を返します。
  • next_permutation/prev_permutation
    permutohedron と同様に、列を前後の順列に変更する関数です。
  • apply_permutation
    もともとの列を、指定された順列に従って並び替える関数です。つまり、元の列を before 、適用後の列を after 、指定された順列を perm とすれば、 after[i] == before[perm[i]] となります。数学で言えば置換に当たります。
  • apply_inverse_permutation
    apply_permutation と同様ですが、与えられた配列による置換の逆を適用します。つまり、元の列を before 、適用後の列を after 、指定された順列を perm とすれば、 after[perm[i]] == before[i] となります。
Examples

itertools

badge badge badge badge badge badge

イテレータをさらに強力にするクレートです。

Version

v0.9.0

Details

Iterator を拡張する Itertools とその他の便利な関数やマクロを提供します。 Python の more-itertools のような位置付けですが、単純に対応するものではなく、互いに存在しないものや対応していても名前が違う場合があります。

提供するものの例を挙げると、

-if xs.iter().all(|x| x % 2 == 0) || xs.iter().all(|x| x % 2 == 1) {
+if xs.iter().map(|x| x % 2).all_equal() {
     todo!();
 }
-for i in 0..xs.len() {
-    for j in 1 + 1..xs.len() {
-        todo!();
-    }
+for (i, j) in (0..xs.len()).tuple_combinations() {
+    todo!();
 }
 let ans = (0..xs.len())
-    .flat_map(|i| (i + 1..xs.len()).map(move |j| (i, j)))
+    .tuple_combinations()
     .map(|(i, j)| f(&xs[i..=j]))
     .sum::<i32>();
-for i in 0..xs.len() {
-    for j in 0..ys.len() {
-        todo!();
-    }
+for (i, j) in iproduct!(0..xs.len(), 0..ys.len()) {
+    todo!();
 }
-let ans = (0..xs.len())
-    .flat_map(|i| (0..ys.len()).map(move |j| (i, j)))
+let ans = iproduct!(0..xs.len(), 0..ys.len())
     .map(|(i, j)| f(i, j))
     .sum::<i32>();
 let ans = xs
     .into_iter()
     .map(f)
-    .collect::<Vec<_>>()
-    .windows(2)
-    .map(|w| g(w[0], w[1]))
+    .tuple_windows()
+    .map(|(a, b)| g(a, b))
     .max()
     .unwrap();
 let ans = [1u32, 2, 3, 4, 5]
     .iter()
     .filter(|&x| x % 2 == 0)
-    .map(|x| (10 * x).to_string())
-    .collect::<Vec<_>>()
+    .map(|x| 10 * x)
     .join(" "); // `<[_]>::join` → `Itertools::join`

その他イテレータをソート済みにするsorted, 2つのイテレータをマージする merge, イテレータの要素から k 個取り出す順列をすべて生成する permutations の他、 combinations, zip_longest, intersperse, pad_using, interleave, coalesce, set_fromなど、挙げればキリがないような様々なメソッドが使えるようになります。

かなり多種多彩で便利なので、一度ドキュメントを読んでどのようなメソッドがあるのかを知っておくと役立つこともあると思います。 メソッドチェーン一本で解決できる問題が増えます。

See also:

Examples

itertools-num

badge badge badge badge badge badge

cumsumとlinspace

Version

v0.1.3

Details

一次元累積和のイテレータを生成するItertoolsNum::cumsumと等間隔な浮動小数点数のイテレータを生成する linspaceの2つを提供します。 提供するのはこの2つのみです。 そして累積和やlinspaceは用意に手で書くことができます。

+use itertools_num::ItertoolsNum as _;
+
 static XS: &[u32] = &[1, 2, 3, 4, 5];
-let cumsum = XS
-    .iter()
-    .scan(0, |sum, x| {
-        *sum += x;
-        Some(*sum)
-    })
-    .collect::<Vec<_>>();
+let cumsum = XS.iter().cumsum().collect::<Vec<u32>>();
 assert_eq!(cumsum, &[1, 3, 6, 10, 15]);

 const START: f64 = 2.0;
 const STOP: f64 = 3.0;
 const NUM: usize = 5;
-let linspace = (0..NUM)
-    .map(|i| START + (STOP - START) * (i as f64) / ((NUM - 1) as f64))
-    .collect::<Vec<_>>();
+let linspace = itertools_num::linspace(START, STOP, NUM).collect::<Vec<_>>();
 assert_eq!(linspace, &[2.0, 2.25, 2.5, 2.75, 3.0]);

ただしcumsumの使い道は結構多いです。 オーソドックスに先頭に0を入れた上でVecにして部分和を取るのに使っても良し、

use itertools_num::ItertoolsNum as _;

use std::iter;

static XS: &[u64] = &[0, 0, 1, 1, 2, 2, 2, 2, 4, 4, 5, 5, 6, 7, 8, 9];

let cumsum = iter::once(&0).chain(XS).cumsum().collect::<Vec<u64>>();
assert_eq!((5..=10).map(|i| XS[i]).sum::<u64>(), cumsum[11] - cumsum[5]);

そのままfor文に突っ込んでも良し、

-let mut sum = 0;
-for x in &xs {
-    sum += x;
+for sum in xs.iter().cumsum() {
     todo!();
 }

2次元累積和の構築や2次元いもす法の展開で使っても良しです。

// TODO: 何かの問題で使って`examples`に入れる

use itertools::Itertools as _;
use itertools_num::ItertoolsNum as _;

// https://imoz.jp/algorithms/imos_method.html

let mut imos = [[0; 7]; 7];

for &(i1, j1, i2, j2) in &[(0, 0, 3, 3), (2, 2, 5, 5), (3, 1, 4, 2)] {
    imos[i1][j1] += 1;
    imos[i1][j2 + 1] -= 1;
    imos[i2 + 1][j1] -= 1;
    imos[i2 + 1][j2 + 1] += 1;
}

let cumsum = imos
    .iter()
    .scan(vec![0; imos[0].len()], |prev, cur| {
        // ここで使う
        for (prev, sum) in prev.iter_mut().zip_eq(cur.iter().cumsum::<i32>()) {
            *prev += sum;
        }
        Some(prev.clone())
    })
    .collect::<Vec<_>>();

assert_eq!(
    cumsum,
    [
        [1, 1, 1, 1, 0, 0, 0],
        [1, 1, 1, 1, 0, 0, 0],
        [1, 1, 2, 2, 1, 1, 0],
        [1, 2, 3, 2, 1, 1, 0],
        [0, 1, 2, 1, 1, 1, 0],
        [0, 0, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ],
);
Examples

maplit

badge badge badge badge badge badge

BTreeMap, BTreeSet, HashMap, HashSet を生成するためのマクロを提供します。

Version

v1.0.2

Details

Vec には vec![a, b, c] のようなマクロが提供されていますが、標準ライブラリでは Vec 以外のコレクションに対してそのようなマクロを提供していません。このクレートは vec! と同様に、各コレクションを簡単に生成するマクロとして btreemap!, btreeset!, hashmap!, hashset! を提供します。また、マクロに渡したキーや値を追加する前に指定の関数に通すようにするマクロ convert_args! も提供されます。このマクロを使うと、例えば String を要素にもつコレクションを生成するときに &str で初期値を与えるといったことができます。

// キーの部分で一々 `"a".to_string()` などとするのは面倒だが、
// 次のようにして一括で `String::from` を適用するようにできる。
let map2 = convert_args!(keys=String::from, hashmap!(
    "a" => 1,
    "c" => 2,
));
Examples
-use std::collections::HashMap;
+use maplit::hashmap;

-let mut map = HashMap::new();
-map.insert("foo", 10);
-map.insert("bar", 20);
-map.insert("baz", 30);
+let map = hashmap!(
+    "foo" => 10,
+    "bar" => 20,
+    "baz" => 30,
+);

either

badge badge badge badge badge badge

汎用的に使える2バリアントの enum を提供します。

Version

v1.5.3

Details

Rust でさっと使える2バリアントの enum としては Result<T, E> がありますが、これはもともとエラー処理のための型なので、バリアントに Ok と Err という強い意味を持つ名前がつけられています。もちろん汎用的な enum として使えないことはありませんが、取りうる値に特に成功/失敗の関係がない場合、ミスリーディングにもなりえます。そういった事情もあり、特に意味のないバリアントとして Left, Right を持つような Either<L, R> を提供します。

Examples
-enum Either<L, R> {
-    Left(L),
-    Right(R),
-}
+use either::Either;

im-rc

badge badge badge badge badge badge

永続データ構造を提供します。

Version

v14.3.0

Details

永続データ構造とは、端的に言えば更新したときに更新前の状態を保存するデータ構造のことです。

標準ライブラリのHashMap, HashSet, BTreeMap, BTreeSet, Vec に対応する永続データ構造として、それぞれ HashMap, HashSet, OrdMap, OrdSet, Vectorを提供します。

ただし(&self, ..) -> Selfのシグネチャを持つメソッドは多くありません。 mutで宣言して(&mut self, ..) -> _の形で操作することになります。 これはREADMEにあるように(TODO)という方針だからです。

Examples
-let mut map = maplit::hashmap!();
-map.insert("foo", 42);
+let map = im::hashmap!();
+let map = map.update("foo", 42);

(TODO: Vector、すごい遅い気がする..)

fixedbitset

badge badge badge badge badge badge

可変長の bitset を提供します。 (その1)

Version

v0.2.0

Details

FixedBitSet を提供します。基本的な使い方などは HashSet<usize> と同様ですが、要素があるかないかをビットで管理する点が異なります。より省スペースで、高速な集合の演算が可能です。

TODO: bit-vec, bitvecとの違い

Examples

Before:

// 😧
let mut ps = vec![false; 10000];

After:

use fixedbitset::FixedBitSet;

// 😃
let mut ps = FixedBitSet::with_capacity(10000);

bitset-fixed

badge badge badge badge badge badge

可変長の bitset を提供します。 (その2)

Version

v0.1.0

Details

BitSetを提供します。

機能はfixedbitsetのものと比べて控え目ですがこちらはビットシフトが可能です。

Examples
use bitset_fixed::BitSet;

fn main() {
    let mut bitset = BitSet::new(64);

    bitset.set(0, true);
    bitset.set(1, true);
    bitset.set(2, true);
    assert_eq!(bitset.buffer(), &[0b111]);

    bitset <<= 1;
    assert_eq!(bitset.buffer(), &[0b1110]);

    bitset >>= 2;
    assert_eq!(bitset.buffer(), &[0b11]);

    bitset <<= 64;
    assert_eq!(bitset.buffer(), &[0b0]);
}

proconio

badge badge badge badge badge badge

標準入力ヘルパーその1です。また高速な標準出力を提供します。

Version

v0.3.6

Details

practice contestのA問題 (ログイン不要版)を解きたいとしましょう。 この問題においては(a, b, c, s): (u32, u32, u32, String)さえ得られればprintln!("{} {}", a + b + c, s);として正答できます。

さて、Rustの標準入力についてGoogle検索等で適当に調べると

  • Stdin::read_lineで一行読むことができる。
  • strはstr::split, str::split_whitespace, str::split_ascii_whtiespaceを使うことでスペースで分割できる。

ということがわかると思います。 これらを使って書いてみましょう。

use std::io;

fn main() {
    let line = getline();
    let mut split = line.split_ascii_whitespace();
    let a = split.next().unwrap().parse::<u32>().unwrap();

    let line = getline();
    let mut split = line.split_ascii_whitespace();
    let b = split.next().unwrap().parse::<u32>().unwrap();
    let c = split.next().unwrap().parse::<u32>().unwrap();

    let line = getline();
    let mut split = line.split_ascii_whitespace();
    let s = split.next().unwrap().parse::<String>().unwrap();

    println!("{} {}", a + b + c, s);
}

fn getline() -> String {
    let mut buf = "".to_owned();
    io::stdin().read_line(&mut buf).unwrap();
    buf
}

何だか冗長ですね。

ところでインタラクティブ問題でもない限り、一行一行ではなく一度に全体を読み込んでしまってもよいはずです。 Read::read_to_stringで書き直してみましょう。

use std::io::{self, Read as _};

fn main() {
    let mut input = "".to_owned();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace();

    let a = input.next().unwrap().parse::<u32>().unwrap();
    let b = input.next().unwrap().parse::<u32>().unwrap();
    let c = input.next().unwrap().parse::<u32>().unwrap();
    let s = input.next().unwrap().parse::<String>().unwrap();

    println!("{} {}", a + b + c, s);
}

まだ_.next().unwrap().parse::<_>().unwrap()という表現が何度も出て来てます。 これを切り出してみましょう。 inputをキャプチャしたクロージャを使ってみます。

// error[E0282]: type annotations needed for the closure `fn() -> _`
let mut read = || input.next().unwrap().parse().unwrap();

はい。残念ながら現在のRustでも多相なクロージャは書けません。

しかしRustにはマクロがあります。 マクロでは定義する場所から見える場合のみ外部のローカル変数を使うことができます。

macro_rules! read(($ty:ty) => (input.next().unwrap().parse::<$ty>().unwrap()));

このread!を使うとこのように最初のコードよりもずっとシンプルになりました。

use std::io::{self, Read as _};

fn main() {
    let mut input = "".to_owned();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace();
    macro_rules! read(($ty:ty) => (input.next().unwrap().parse::<$ty>().unwrap()));

    let a = read!(u32);
    let b = read!(u32);
    let c = read!(u32);
    let s = read!(String);

    println!("{} {}", a + b + c, s);
}

なお、インタラクティブ問題で一行ずつ読まなければならない場合でもRust 1.42ならこのようにすれば良いです。

use std::io;

fn main() {
    let mut input = "".split_ascii_whitespace();
    let mut read = || loop {
        if let Some(word) = input.next() {
            break word;
        }
        input = {
            let mut input = "".to_owned();
            io::stdin().read_line(&mut input).unwrap();
            if input.is_empty() {
                panic!("reached EOF");
            }
            Box::leak(input.into_boxed_str()).split_ascii_whitespace()
        };
    };
    macro_rules! read(($ty:ty) => (read().parse::<$ty>().unwrap()));

    let a = read!(u32);
    let b = read!(u32);
    let c = read!(u32);
    let s = read!(String);

    println!("{} {}", a + b + c, s);
}

しかしシンプルになったと言ってもC++やJava, Pythonと比べればどうでしょうか? C++にはstd::cin、Javaにはjava.util.Scanner、Pythonには__builtin__.inputがあります。 もっとコード量を減らしたくはならないでしょうか?

そこでrust-lang-jaとしては今回のアップデートにおいてproconio, text_io, whitereadの3つのクレートを提案しました。

これらを使った例を載せておきます。 (-naive は比較の為のクレートを使わない例です)

前置きが長くなりましたがproconioの解説に入ります。

proconio はtanakh さんのマクロを参考にして改良されたマクロ input! と、 println! を自動的に高速化するマクロ #[fastout] を提供します。

なお、元となった tanakh さんのマクロは現在Mit Licenseで公開されています。 AtCoderバイナリ提出専用になったようでinput!が消え、pub use proconio::inputになってました... 消える直前のライブラリ版はマーカーとしてbytesが追加されているだけなので以下Qiita版の方を「オリジナル」と呼びます。

proconio::input! はオリジナルの input! に以下の機能を追加したものです。

  • 入力を行ごとに読むのか EOF まで一度に読むのかを選べます。

    デフォルトでは、デバッグビルド時はデバッグに便利な行ごとのモード、リリースビルド時にはより高速な一気読みのモードを利用します。 また行ごとのモードでも記事にあるような重大なオーバーヘッドはありません。

  • 同じプログラムで2回以上使えます。

    proconio::input!のデフォルトのsourceはlazy_staticで宣言されていて、読み込んだ標準入力の内容をしっかりと保存しています。

    一回のinput!で読むことが難しい入力にも対処できます。

    use proconio::input;

input!(q: usize);
for _ in 0..q {
    input!(kind: u32);
    match kind {
        1 => {
            input!(xs: [i64]);
            todo!();
        }
        2 => {
            input!(i: usize);
            todo!();
        }
        _ => unreachable!(),
    }
}

  • 読む入力を str や File に替えることができます。

    テストを言語に組み込みの #[test] を使って行う場合、標準入力ではなくファイルや文字列リテラルから読み込みたい場合があるかもしれません。そのような場合に備え、読み込み元を変更することができます。

    use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from("42"),
    k: u32,
}
assert_eq!(k, 42);

  • 変数に mut を付けられます。また使わない値を_でスキップできます。

    $(mut)? $ttに該当するパターンで変数を取れます。

    use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from("57 42"),
    _: u32,
    mut k: u32,
}
assert_eq!(k, 42);
k -= 1;
assert_eq!(k, 41);

  • n: usize, xs: [T; n]をxs: [T]と書けます。

    入れ子にしたときに役立ちます。 例えばABC166-Bの入力はこのように取れます。

    use proconio::{input, marker::Usize1};

input! {
    n: usize,
    ass: [[Usize1]],
}

  • Readable というトレイトで読み込み方をカスタマイズできます。

    proconio では値の読み方を Readable というトレイトを通して制御します。これを用いると読み方を特別に定義するマーカーを作ることができます。たとえば文字列を Vec<u8> として受けとる Bytes, Vec<char> として受けとる Chars, 整数値を -1 して読み込む Usize1, Isize1 が用意されています。

    use proconio::{input, marker::Usize1, source::once::OnceSource};

input! {
    from OnceSource::from("3\n2 1 2"),
    g: [Usize1],
}
assert_eq!(g, &[1, 0, 1]);

また #[fastout] は、標準出力を Rustで高速な標準出力 - κeenのHappy Hacκing Blog で紹介されている方法で自動的に高速化します。

Rustではstd::println!で10^5個程度の要素を出力しようとすると150 msくらいかかることがあります。 これは致命的ではないものの気分が良いものではないのでこのようなときはprintln!を使わず、BufWriterとwriteln!を使ってまとめて書き込むということがなされます。

use std::io::{self, BufWriter, Write as _};

fn main() {
    let ans: Vec<i64> = unimplemented!();

    let stdout = io::stdout();
    let mut stdout = BufWriter::new(stdout.lock());

    for ans in ans {
        // 間違えて`println!`を使わないように注意
        writeln!(stdout, "{}", ans).unwrap();
    }
    stdout.flush().unwrap();
}
// あるいは
use std::io::{self, BufWriter, StdoutLock, Write as _};

fn main() {
    let ans: Vec<i64> = unimplemented!();

    buf_print(|stdout| {
        macro_rules! println(($($tt:tt)*) => (writeln!(stdout, $($tt)*).unwrap()));
        for ans in ans {
            println!("{}", ans);
        }
    });
}

fn buf_print(f: impl FnOnce(&mut BufWriter<StdoutLock>)) {
    let stdout = io::stdout();
    let mut stdout = BufWriter::new(stdout.lock());
    f(&mut stdout);
    stdout.flush().unwrap();
}

このような変更を自動的に行うのが #[fastout] です。 関数内のprint!とprintln!を発見して置き換えます。

#[proconio::fastout]
fn main() {
    let ans: Vec<i64> = unimplemented!();

    for ans in ans {
        println!("{}", ans);
    }
}
Known issues

statiolake/proconio-rs#8

現行のAtCoderでの#[proconio::fastout]はmatch armのprintln!を置き換えません。 これを踏んだ場合、標準出力の順番が変わります。

気づいたあとすぐに修正したのですが、アップデートにギリギリ間に合いませんでした。(2020-04-01)

最新のproconioでは、新たにprint!とprintln!をシャドーイングする形で定義して元のブロックをそのまま包み込みます。(fastout実装当時のstableのRustでは不可能でした)

Examples

text_io

badge badge badge badge badge badge

標準入力ヘルパーその2です。

Version

v0.1.8

Details

read!マクロを提供します。

read!() とするだけで空白区切りの値を1つずつ読むことができます。 FromStr を実装している型を読むことができます。競技プログラミングではあまり使う機会はないかもしれませんが、C言語の scanf のように、もう少し柔軟に使うこともできます。

1つずつしか読めないのでproconioやwhitereadのように複数の値をVec<_>で取るといったことは苦手です。

また、read!() (引数無し)はread!("{}")のエイリアスであり特殊化は行なわれておらずその仕組み上あまり高速ではありません。 Rustの競プロ向け入力関数やマクロを高速化できるかやってみたという記事と同様の方法で性能評価すると以下のようになります。

プログラム 内容 所要時間(秒)
main1a (記事本編) read() 関数 7.751
main1b (記事本編) 改良版 reads(), readl() メソッド 2.308
main1b 改 (記事本編) main1b で str::from_utf8_unchecked()を使用 1.953
main2a (記事本編) get!() マクロ 2.550
main2b (記事本編) 改良版 get!() マクロ 2.127
main3a (コメント欄) InputScanner<R: BufRead> 1.895
main3b (コメント欄) InputScanOnce 1.658
tanakh-input-once @tanakh氏のオリジナルの input! (EOFまで一度に) 2.021
tanakh-input-line @tanakh氏のオリジナルの input! (行ごと) 5.996
proconio proconio クレート 2.039
text-io text_io クレート 14.544
whiteread whiteread クレート 2.523
iostream C++ (g++ 9.2.0 with -std=c++17 -O2) の iostream 3.791
cstdio C++ (g++ 9.2.0 with -std=c++17 -O2) の cstdio 3.223
Examples

whiteread

badge badge badge badge badge badge

標準入力ヘルパーその3です。

Version

v0.5.0

Details

std::cin の使い勝手を再現したようです。

3つの標準入力ヘルパーのうち唯一' 'と'\n'を区別することができます。

Examples

rustc-hash

badge badge badge badge badge badge

高速なハッシュ関数を提供します。

Version

v1.1.0

Details

Rust コンパイラの rustc や Firefox でも使われているハッシュ関数です。かなり高速なようです。（hatooさんのツイート）

nightly-2020-02-17 でのベンチマーク結果は以下のようになりました。

$ cargo +nightly bench 2>/dev/null

running 12 tests
test bench_default_hasher         ... bench:   1,208,041 ns/iter (+/- 47,247)
test bench_default_hasher_80bytes ... bench:   5,107,028 ns/iter (+/- 68,891)
test bench_default_hasher_hashset ... bench:   5,037,694 ns/iter (+/- 62,134)
test bench_fnv                    ... bench:     916,753 ns/iter (+/- 2,426)
test bench_fnv_80bytes            ... bench:   9,170,034 ns/iter (+/- 37,260)
test bench_fnv_hashset            ... bench:   3,954,849 ns/iter (+/- 103,217)
test bench_metrohash              ... bench:     785,097 ns/iter (+/- 79,548)
test bench_metrohash_80bytes      ... bench:   4,094,272 ns/iter (+/- 84,689)
test bench_metrohash_hashset      ... bench:   3,898,019 ns/iter (+/- 141,702)
test bench_rustc_hash             ... bench:       8,556 ns/iter (+/- 35)
test bench_rustc_hash_80bytes     ... bench:   1,375,398 ns/iter (+/- 10,474)
test bench_rustc_hash_hashset     ... bench:   2,558,677 ns/iter (+/- 56,769)

test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out
Examples
-use std::collections::HashMap;
+use rustc_hash::FxHashMap;

-let mut map = HashMap::new();
+let mut map = FxHashMap::default();

smallvec

badge badge badge badge badge badge

ある長さになるまで要素を「直にinline」持ち、超えた場合ヒープアロケーションに切り替える可変長配列です。

Version

v1.2.0

Details

一般にヒープアロケーションは低速なので、可変長が必要でも大半は要素数 1 か 2 、という場合に Vec を使うよりも高速になることが期待できます。C++ の boost::container::small_vector に相当します。

Examples
+use smallvec::SmallVec;
+
 use std::iter;

 let probably_single_values = (0..100)
     .map(|i| generate_values(i).collect())
-    .collect::<Vec<Vec<_>>>();
+    .collect::<Vec<SmallVec<[_; 1]>>>();
Add a custom footer

目次

Clone this wiki locally