Crates 2019
rust-jpのメンバーがAtCoderの2019年言語アップデート以降で利用したいと考えているクレートの一覧です。
このページは誰でも編集できます。
クレートを追加/削除したり、バージョンを更新したりする人はja-all-enableブランチにもPRをお願いします。
クレートの導入方法については対応するガイドブックのページもご参照ください。
導入の際はatcoder-rust-baseのja-all-enabledブランチ内に用意した以下2つのファイルを利用します。これらのファイルにはこのページにかかれているクレートが書かれているバージョンで指定されています。ただしマージされていないPRが残っている場合はatcoder-rust-base内の記述は最新でない場合があります。
Rust PlaygroundというRust公式のオンラインコード実行環境があります。ここでは以下の3つの条件を満たしたクレートを使用できます。 (Playgroundのヘルプ)
- crates.io上での"Downloads all time"のトップ100
-
Rust Cookbookで使われているクレート
- Rust Cookbookは、一般的なタスクをRustのスタンスに則って実現するにはどうすべきかを集めたExample集です。
- 1., 2.のすべてのdependency (dependencyのdependencyを含む)
-
tokio(トップ100)のdependencyであるtokio-fsが入ってないなどいくつか漏れがあるように見えますが手作業ではないようので謎。 - ビルドされるときにdependencyをDLするのでだいたいDL数上位300のような品揃えになっていると思われます。
-
2019-11-12+09:00現在、バージョン違いやwinapi, wasm_bindgenのような実質使えないものを含んで325個のクレートが利用可能です。
$ date +%Y-%m-%d%:z
2019-11-12+09:00
$ curl -s https://raw.githubusercontent.com/integer32llc/rust-playground/master/compiler/base/crate-information.json | jq length
325
$ # バージョン違いのみ除く
$ curl -s https://raw.githubusercontent.com/integer32llc/rust-playground/master/compiler/base/crate-information.json | jq 'map(.name) | unique | length'
295Rust Playgroundで利用されるクレートは知名度が保証されていると言ってもいいでしょう。以下で紹介するクレートのいくつかはこれに含まれています。
また今回提案するクレートリストをPlaygroundのものにしようという案もありました (スプレッドシートの"Rust (Playground)", Slackのコメント) が、以下の問題点があるため見送っています。
- 325個のクレートのうち、競技プログラミングにおいて僅かでも使えそうなものがせいぜい二割程度しかない。
- 全分野のRustユーザーでのダウンロード数に基くので、Web系やファイルIO、特殊なビルドでしか使わないものなどを含めて多数ある。
- コンテストに役立つようなアルゴリズムを提供するものや高速化を可能にするものは以外と多く含まれているが、肝心のコーディングをやりやすくするもの(categoryが
rust-patternsのようなもの)があまり無い。
- それらにも既にdeprecatedなものがある。
- きちんとメンテナンスされている後継クレートがあっても旧のクレートが含まれている場合がある (e.g.
bit-set→fixedbitset。後者は現在使用不可2019-11-08 +09:00をもってfixedbitsetが追加されたが、依然として古いものも含まれている) 。
- きちんとメンテナンスされている後継クレートがあっても旧のクレートが含まれている場合がある (e.g.
※ 最終的な提案はCargo.tomlとCargo.lockです。
-
標準ライブラリを補完するもの / Rust的な普段通りのコーディングで利用するもの
-
num num-derivendarraynalgebraalgalibm-
rand rand-distrpetgrapheuclid-
primal indexmapregexnomaho-corasickstrsimlazy_staticapproxordered-floatasciipermutohedronsupersliceitertoolsitertools-numtake_mutdefmacmacif_chainmaplitderive_morederive-neweitherim-rcfixedbitsetbitset-fixed
-
- 標準入力を扱うもの
- 主に競技プログラミング用を想定したもの
- 高速化するもの
このカテゴリに該当するクレートは次のいずれかにあたるものです。
- 他のいくつかの言語では標準の機能となっている。
- 普段のコーディングで利用されており、Rustらしいコードを書くのに利用している。
- boost や numpy など既に認められたライブラリ内に同等のものが存在する。
このカテゴリのクレートは基本的に全て導入されることを希望します。 (ただしbitset-fixedとfixedbitsetについてはいずれか片方が導入されることを希望します。)
このカテゴリのクレートの説明には、しばしば「かつてstd (標準ライブラリ) の一部だった」「かつてRust本体にバンドルされていた」のような表現が現れます。これは現在でも標準ライブラリに準じる存在だということを意味します。これらがユーザークレートになった理由は不評や利用者の少なさなどによるものではありません。cargoやcrates.ioのような強力なパッケージ管理システムを前提に、言語とライブラリの成長を分離する目的で意図的に標準ライブラリを小さくしているからです。
num v0.2.0 (docs) (anchor)
数値型に対するサポートを充実させるものの詰め合わせ。
-
pre 1.0時代には
libnumとしてRust本体にバンドルされていた (Slackのコメント) 。 - 2019-11-12+09:00現在Rust Playgroundで使用可能。
具体的には以下の6つのクレートの詰め合わせ。
-
num-bigint ^0.2.0 -
num-complex ^0.2.0 -
num-integer ^0.1.39 -
num-iter ^0.1.37 -
num-rational ^0.2.1 -
num-traits ^0.2.5
num-bigintは多倍長整数のサポート。BigInt, BigUintと、それらの型の乱数を生成するのに利用するRandomBitsを提供する。
num-complexは複素数型のサポート。Complex<_>, ComplexDistribution<_, _>を提供する。
num-integerは整数関連のサポートの強化。整数を拡張するトレイトInteger, Rootsの他、これらを使った関数 (gcd, sqrt, binomial等) を提供する。
num-iterは上のAdd<Output = Self> + PartialOrd + Clone + ToPrimitiveを実装するようなカスタム整数型やgenericな整数型へのイテレータのサポート。Range, RangeInclusive, Step, StepInclusiveとこれらを使った関数range, range_inclusive, step, step_inclusiveを提供する。
std::iter::Stepがunstableなのでa: T, b: T where T: PrimIntのようなa, bに対してa..b(: std::ops::Range<T>)のように書いてもIteratorにはならないが、これらの関数なら代用になる。
num-rationalは有理数型のサポート。Ratioを提供する。
num-traitsはNum, Float, PrimIntをはじめとした多数のトレイトを提供する。
Rustの整数型, 浮動点小数型には多くの同名のメソッド(e.g. {min, max}_value, count_{zeros, ones}, pow)があるがそれらはトレイトで抽象化されていない。
num-traitsはこれらをトレイトで統一して扱えるようにする。
またトレイトを『まとめる』トレイトを提供する。
(e.g. +-*/%に対応するトレイトを『まとめる』NumOps)
競技中の利用というよりは自前の競プロ用ライブラリを整備する際の利用が想定される。
特にAtCoderでのみRustを利用し、かつ本格的にライブラリを整えるような人が対象となる。
自作ライブラリの他コンテストサイトへの可搬性を気にする人は利用しないので多くの人が利用するかどうかには疑問も残るが、通常num-*を2個以上使うbinクレートであればnumとして利用するし、他のnum-*系クレートを含むこのUncyclo上のいくつかのクレートの依存にもなっているので、あえて外す意味もないクレートでもある。
またnum-traitsに依存しても後でポータブル化できる(多分)のでRust入門者(≠ 競プロ初心者)がとりあえずで競プロライブラリを移植しやすくなる..かもしれない。
やっていることはトレイトで抽象化するだけなので必要なものに絞れば『num-traitsっぽいもの』がそこそこ短く書ける。
実際上記のNumOpsの定義はこれである。
ボイラープレートを書かなくてはならないならmacro_rulesがある。
Procedural macros to derive numeric traits in Rust.
- 2019-11-13+09:00現在Rust Playgroundで使用可能
num-traitsをre-exportしているわけではなく"num_traits"というextern crate nameでアクセスできることを期待している。
rust-num/num-derive#34, rust-num/num-derive#35
基本的なNum系トレイトを自動実装できるようになる。Rustでは実質的に同じ型の値を持つ型であっても型システム上で区別するために新しい構造体を作る、いわゆるNewTypeパターンが広く利用されている (例:グラフ構造の頂点番号と重みに専用のIndex型や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)"
}numには含まれていない。
多次元配列のサポート。
- 2019-11-12+09:00現在Rust Playgroundで使用可能
Pythonにおけるnumpy.ndarrayに相当するもの。通常Rustで二次元以上の配列を扱うときはVec<Vec<...>>の形で扱うが、ただのJAG配列なので各種の不便がある。例えば、全要素に対する変更などを扱いにくい。ndarrayを利用すれば、多次元配列の形状変更やスライス、多次元配列同士の演算などの様々な機能を持つArray構造体が定義される。
線形代数
- 2019-11-12+09:00現在Rust Playgroundで使用可能
(競プロにおいては)ndarrayほどの手軽さは無いがndarrayが提供していないような関数が多数ある。
alga v0.9.2 (docs) (anchor)
- 2019-11-13+09:00現在Rust Playgroundで使用可能
num-traitsやnum-complexを拡張するトレイトを多数提供する。
nalgebraの一部ではあるが完全にはre-exportされてない。
examplesを見る限り共にuseすることを想定されているようにも見える。
libm v0.2.1 (docs) (anchor)
libmのRust実装
- 2019-11-13+09:00現在Rust Playgroundで使用可能
- リポジトリが@rust-lang下にある
- コンパイラに使われている
core (⊂ std)の数値型の関数はLLVMの実装によるものが多いが、このクレートは基本的にplatform independentな結果を返すので特に浮動点小数を扱うライブラリによく使われている。
なのでWindows使いやmacOS使いが浮動点小数を扱う際に手元とジャッジの環境で挙動が異なる、という可能性を潰せるといったメリットがあるかもしれない。
実際にそのような例は聞いたことが無いが。
またAPIがmath.h (⊊ cmath)のままなのでRust入門者にとっては使いやすいかもしれない。
rand v0.7.2 (docs) (anchor)
RNG疑似乱数
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- pre 1.0時代に
stdの一部だった歴史を持つ - rust-lang/rustで使われている
- CodinGameで使用可能
-
rand_distrv0.2.2 -
rand_chachav0.2.1 -
rand_pcgv0.2.1 -
small_rngfeatureが必要（Slackでのコメント）
以下の乱数を提供する。
-
OsRng(fromrand_core) -
SamllRng(fromrand_pcg) (feature-gated) -
StdRng(fromrand_chacha) ThreadRng-
StepRng(1から順番に吐くテスト用のもの)
このうち競技プログラミング向きなのはSmallRngだがこれは0.7になってdefault featuresから外れた。
使うにはsmall_rng featureを付け加える必要がある。
ありとあらゆる所に使われているクレートであり、2019-11-06+09:00現在総DL数1位に輝いている。
グラフ
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
Graph, StableGraph, GraphMap, CsrのほかUnionFindを提供する。
Boostのグラフ関連や今回Pythonへの導入が確定したNetworkXのようなもの。
節点と辺がindex(デフォルトはu32)のnewtypeで管理されているのは良いのだが、各操作は割と冗長。
グラフをgraphviz形式で表示する機能もあり、グラフの形がわからなくなったときにさっと図示できる。
TODO: BoostやNetworkXとの比較
euclid v0.20.5 (docs) (anchor)
幾何
- リポジトリが@servo下にある
TODO
primal v0.2.3 (docs) (anchor)
素数
以下の3つのクレートの詰め合わせ。
-
primal-check ^0.2 -
primal-estimate ^0.2 -
primal-sieve ^0.2
primal-checkはmiller_rabin, as_prime_power, as_perfect_powerを提供する。
primal-estimateはnth_prime, prime_piを提供する。
primal-sieveはPrimes, Sieve, SievePrimes, StreamingSieveを提供する。
TODO: Boostに素数を扱うものがあったような?
挿入順を保持するhash table
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
- rust-lang/rustで使われている
IndexMap, IndexSetとそれらのmaplit風のコンストラクタ用マクロindexmap!, indexset!を提供する。
C++のboost::multi_index::multi_index_container (を使ったもの)やJavaのjava.util.LinkedHashMap、C#のSystem.Collections.Specialized.OrderedDictionary、Pythonのcollections.OrderedDictのようなもの。
特徴は"Feature Highlight"より
- 挿入順を保持する
-
.sort()や.pop()ができる -
Equivalentというtraitでgetがやりやすくなる -
MutableKeysというtraitでkeyとvalueの&mutが取れる。ただしkeyのhashやequivalentの結果を変えるような変更をした場合動作は保証されない (unsoundではないが)
前はordermapという名前のクレートだった。こちらも2019-11-11+09:00現在、Playgroundで利用可能である。
regex v1.3.1 (docs) (anchor)
正規表現
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- pre 1.0時代に
libregexとしてRust本体にバンドルされていた - リポジトリが@rust-langにある
- clippy(公式のlinter)にこのクレート用のルールがある
- CodinGameで使用可能
str用のregex::Regexと[u8]用のregex::bytes::Regexを提供する。
通常のコーディングでは下記のlazy_static(あるいはonce_cell)を用いるのが一般的。
別にそのままコンストラクトしてもClippyに怒られたりはしないが。
nom v5.0.1 (docs) (anchor)
パーサーコンビネータ
- 2019-11-13+09:00現在Rust Playgroundで使用可能
TODO
Aho–Corasick
- 2019-11-13+09:00現在Rust Playgroundで使用可能
- @BurntSushi氏が管理している
AhoCorasick, AhoCorasickBuilderを提供する。
regexのdependency。
strsim v0.9.2 (docs) (anchor)
Implementations of string similarity metrics.
- 2019-11-13+09:00現在Rust Playgroundで使用可能
hammingやjaro等2つのstrの"similarity"を計算する関数を多数提供する。
staticアイテムの遅延初期化
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- @rust-lang-nursery下で管理されている
- rust-lang/rustで使われている
- rust-lang/cargoで使われている
lazy_static!を提供する。
Rustではthread safetyとmutabilityの制限が厳しいので他の言語のような感覚で使えるグローバル変数というのは無い。
Rust入門者にとってはstatic mutがそれのように見えるかもしれないが2018 editionで『デフォルトでエラー』を越えて構文ごと削除しようと提案された程度には危険かつ嬉しくないものと見做されている。
では入門者ではない人はどうなのかというとプログラミングコンテストでもそれ以外でも基本的にはグローバルな状態を避け、明示的に引数で引き回す傾向にある。
なのでグローバル変数のようなものは他の言語と比べれば見る機会はそう多くはない。
実際AtCoderのいくつかのコンテストでのRustのコードを見た限りstatic mutもthread_local!も使っている人は極僅かだった(TODO: Codeforces等はどうなのか)。
とはいえ普段のコンテストのときのような小さいコードを短時間で書くときはグローバル変数が欲しくなるような人はそれなりにいるだろう。
特にRust入門者にとっては。
グローバルな状態を持ちたくなったときstatic mutの他には上での記事の分類のうち2つ、その状態に触れるスレッドが一つなら4つの選択肢がある。
- 静的変数 (
static)- 非スコープ借用される静的変数
- 組み込み
static lazy_static!
- 組み込み
- スコープ借用される静的変数
thread_local!scoped_thread_local!
- 非スコープ借用される静的変数
※ 上の記事での分類
組み込みstaticはstd::sync::atomic::Atomic*くらいしか使えない。
thread_local!は良さそうだがLocalKey<RefCell<_>>は中身を1つ呼ぶごとにネストを一段深くする必要がある。
なぜならthread localなオブジェクトはスレッドの終了時にデストラクトされるかもしれず、&'static _の形で持ち出せると困るからである。
ネストを生じない方法でやる方法はあるにはあり、RefCellのようなインターフェイスを提供するref_thread_localというクレートがあるが以下の理由により提案に入れていない。
-
v0.0.0である。補足するとcargo newで作られるパッケージのデフォルトのバージョンは0.1.0でありわざわざ下げている。インパクトが強く使う側の不安を誘いそう - デザイン自体は安全そうに見えるが実装が本当に完全にsoundかどうか判断がつかない
- 総DL数が24Kでreverse dependenciesは2。低くはないものの上2つを考えると微妙
逆に(lazy_static!と比較しての)メリットとしてはパフォーマンスの向上とデッドロック (TLE)がパニック (RE)になることである。
scoped_thread_local!.は(TODO: 不要な気はする)
そして最後にlazy_static!.だが他の3つのようなデメリットが無く、また(競プロ以外で)Rustを使っている人にとってはより馴染み深い方ではある。
lazy_staticクレートを導入することでユーザに選択肢を与えることができる。
ちなみにregexではlazy_static!の上でRegexのコンパイルを行なうことを推奨している。
人によってはこれをスニペットにしているかもしれない。
(TODO: rustup component化以前のclippyのperfあたりにこれ関連のルールがあったような.. 記憶違い? regex!のと混同してる?)
同様な機能を提供するクレートとしてonce_cellというのもある。
参考:
https://github.com/rust-lang/rust/issues/53639#issuecomment-543305790
競技プログラミングにてミュータブルなグローバル変数を使ってみたら書くスピードが上がりそう
↓
static mutの危険性 ※ Rust 1.39でconst_vec_newは安定化された
Before:
use std::cell::RefCell;
thread_local! {
static VALUES: RefCell<Vec<i32>> = RefCell::new(vec![1, 2, 3]);
}
VALUES.with(|values| {
let mut values = values.borrow_mut();
values.push(4);
assert_eq!(&*values, &[1, 2, 3, 4]);
});After:
use lazy_static::lazy_static;
use std::sync::Mutex;
// thread local storageがmutexになるので当たり前だが少しだけ遅い
lazy_static! {
static ref VALUES: Mutex<Vec<i32>> = Mutex::default();
}
let mut values = VALUES.lock().unwrap();
values.push(1);
assert_eq!(&*values, &[1]);
approx v0.3.2 (docs) (anchor)
浮動点小数の比較
- 2019-11-13+09:00現在Rust Playgroundで使用可能
AbsDiffEq, RelativeEq, UlpsEq及び{, assert_}{abs_diff, relative, ulps}_{eq, ne}!マクロを提供する。
TODO: 必要となるとき
Ord/Eqを実装するNotNan<f64>, OrderedFloat<f64>
- 2019-11-12+09:00現在Rust Playgroundで使用可能
Rustの比較演算子用のインターフェイスにはEq, Ordの他にPartialEq, PartialEqがある。
具体的な要請はリンク先参照。
比較演算子にはPartialEqとPartialOrdが使われる。
何故このような区分があるのかというと浮動点小数のためである。
f32, f64はPartialEq, PartialOrdであるがEq, Ordではない。
というのもIEEE 754においては==の反射律すら期待してはならないからである。
他の言語においても配列のソートや順序を使うデータ構造の構築にNaNを混ぜるとその結果は保証されない。
C++に至っては鼻から悪魔が出てくる。
Rustではこのような関数やデータ構造に要素がtotal orderであることを要求することで『浮動点小数をソートしたら何か変』という事態を防いでいる。
で、我々Rustユーザーがソート等にどうやって浮動点小数を使うのかというと..ソートに関しては以下のようにすればいい。
この場合、NaNが混じっていると.unwrap()の部分でpanicする。
let mut xs = vec![2.0, 1.0, 0.0];
xs.sort_by(|a, b| a.partial_cmp(b).unwrap());これがBTreeMapやBinaryHeap等のデータ構造になるとこうはいかない。
f64に対するnewtypeが必要になる。
ordered-floatはNotNanとOrderedFloatを提供する。
これらは普通に四則演算したりprintできる。
自分でやるとただラップするだけでも結構しんどい。
そして本提案リストにあるnum-deriveやderive_moreは実装自体のカスタマイズができないのであまり助けにならない。
NotNanは中身としてNaNを拒否する。
四則演算の結果NaNになったのなら整数型と同様にpanicする。
ただしこちらはrelease buildでもチェックされる。
OrderedFloatはNaNを許容するがそれを『最大の値であり、自身と等しい』としている。
Before:
use itertools::Itertools as _;
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 set = BTreeSet::new();
set.insert(DirtyOrd(10.0 + 1.1));
set.insert(DirtyOrd(30.0 + 3.3));
set.insert(DirtyOrd(20.0 + 2.2));
assert_eq!(set.iter().map(|DirtyOrd(x)| x).join(" "), "11.1 22.2 33.3");After:
use itertools::Itertools as _;
use ordered_float::NotNan;
use std::collections::BTreeSet;
let mut set = BTreeSet::new();
set.insert("10.0".parse::<NotNan<_>>().unwrap() + 1.1);
set.insert("30.0".parse::<NotNan<_>>().unwrap() + 3.3);
set.insert("20.0".parse::<NotNan<_>>().unwrap() + 2.2);
assert_eq!(set.iter().join(" "), "11.1 22.2 33.3");
ascii v1.0.0 (docs) (anchor)
ASCII文字列
AsciiChar, AsciiStr, AsciiStringを提供する。
それぞれの表現はu8, [u8], Vec<u8>であり、チェック以外のオーバーヘッドは生じない。
[u8]のようにインデックスでアクセスしたり、strのようにsubstringを作ったり空白文字をtrimしたりできる。
Permutation生成
- @bluss氏が管理している
[T] (T: Ord)に対して拡張メソッド{prev, next}_permutationを提供する。
TODO: heap_recursive
スライスの強化
[T] (T: Ord)に対して{lower, upper}_boundをはじめとした拡張メソッドを提供する。
これには{prev, next}_permutationが含まれている。
イテレータの強化
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
- rust-lang/rustで使われている
- CodinGameで使用可能
Iteratorを拡張するItertoolsとその他の便利な関数やマクロを提供する。
Pythonのmore-itertoolsのようなもの。
ただ(当然ではあるが)itertoolsの名に因んでいるとはいえ単純に対応するものではなく、互いに存在しないものや対応していても名前が違う場合がある。
(e.g. Itertools::interleave ←→ more_itertools.interleave_longest, Itertools::interleave_shortest ←→ more_itertools.interleave)
- @bluss氏が管理している
ItertoolsNum::cumsum, linspaceの2つを提供する。
これだけ。
それぞれPythonのitertools.accumulate or numpy.cumsum, numpy.linspaceのようなもの。
itertoolsクレートと同じ作者だが分離されている理由はよくわからない。
linspaceのほうはitertools v0.5で削除され、このクレートに移動した。
Pythonのitertoolsにも入っているcumsumの方がこちらに分離されている理由として考えられるのはnum_traits::Zeroを使うためだと思われる。
パフォーマンスの為には『初期値』があった方がいいし、AddとDefaultのドキュメントには「Add<Self, Output = Self>であるならdefaultはその単位元でなくてはならない」とは書かれてない。
実際にはそうではない例を見つける方が難しいが。
実はstdのみでzero + a == a (∀ a)を満たすzeroは表現できることはできる。
Iterator::sumのドキュメントには
An empty iterator returns the zero value of the type.
と書かれておりこれはそのようなzeroだと解釈できる。
つまりstd::iter::empty().sum()で得ることができる。
まあそうは言ってもstd::iter::Sumよりはnum_traits::Zeroを使うほうが自然だろう。
ただnum_traitsは極めて軽量だしitertoolsの方で依存しても良さそうだが『事実上公式』なクレート同士で依存しあうのは良くないと考えたのかもしれない。
+use itertools_num::ItertoolsNum as _;
+
static XS: &[u32] = &[1, 2, 3, 4, 5];
-let cumsum = XS
- .iter()
- .copied()
- .scan(0, |sum, x| {
- *sum += x;
- Some(*sum)
- })
- .collect::<Vec<_>>();
+let cumsum = XS.iter().copied().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]);
&mut TからTを『借りる』
takeとtake_or_recoverを提供する。
takeは&mut TからTを『借りて』T -> Tの関数に適応する。
返せないとき、すなわちpanicした場合プログラムをabortさせる。
参考: Rustのパニック機構
defmac v0.2.1 (docs) (anchor)
1行で書けるmacro_rules
- @bluss氏が管理している
マクロを生み出すマクロdefmac!を提供する。
このマクロによりrustfmt下で最低5行を要するmacro_rulesを1行で記述し、視認性を高めることが可能になる。
またパターンで引数を与えることもできる。
(match (..) { (..) => .. }と展開するマクロになる)
Rustでは&mut _を巻き込むクロージャはその対象を専有できる必要があるがmacro_rulesを使った場合はそうではないため、競技プログラミングに限らずともclosureの代用としてよく使われる。
+use defmac::defmac;
+
let mut st = 0;
-macro_rules! incr {
- () => {
- st += 1;
- };
-}
+defmac!(incr => st += 1);
incr!();
assert_eq!(st, 1);
mac v0.1.1 (docs) (anchor)
シンプルなマクロの詰め合せ
- 2019-11-13+09:00現在Rust Playgroundで使用可能
matches!, inspect!, do_while!等シンプルで便利なマクロを多数提供する。
matches!についてはmatchesというクレートが全く同じ名前と定義のマクロを提供している。
ifとif letを『まとめる』マクロif_chain!
if_chain!を提供する。
100行に満たないシンプルなmacro_rulesだが以外と使いどころが多く、長い間使われ続けている。
else節が必要無くともインデントを2段までに抑える効果がある。
難点としてはRustの構文としては不正なため、現在のrustfmtだとフォーマットの対象にならないことである。
Before:
// docsの例
if let Some(y) = x {
if let Some(z) = y {
do_stuff_with(z)
} else {
do_something_else()
}
} else {
do_something_else()
}After:
// 〃
if_chain! {
if let Some(y) = x;
if let Some(z) = y;
then {
do_stuff_with(z)
} else {
do_something_else()
}
}
maplit v1.0.2 (docs) (anchor)
BTreeMap, BTreeSet, HashMap, HashSet用のマクロ
- @bluss氏が管理している
Vec<_>にはvec![a, b, c]のように構成できるがstdは現在上記の4つに対してそのようなコンストラクタを提供していない。
このクレートはvec!に似たbtreemap!, btreeset!, hashmap!, hashset!を提供する。
かなりポピュラーなクレートであり、コレクションっぽいデータ構造を提供するクレートは大抵これに似た形式のmacroを用意している。 またRFCsにこんな提案がある。 pre 1.0時代からあって現在もcloseされていない。もしかしたら標準ライブラリに似たようなのが入るかもしれない。
各key, valueを指定の関数に通すconvert_args!も地味に便利。
Before:
use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("foo", 10);
map.insert("bar", 20);
map.insert("baz", 30);After:
use maplit::hashmap;
let map = hashmap!(
"foo" => 10,
"bar" => 20,
"baz" => 30,
);
stdのトレイトに対応するderive macro
structやenumにFrom, Into, Index, Deref等stdのトレイトをderiveする数多くのderive macroを提供する。
Add-like等の四則演算を実装するものもある。
バージョンが0.15から0.99に飛んでいるがこれはAPIにbreaking changeを入れる予定はもう無いがdependencyに0未満のものが含まれているからだと思われる。 (TODO: この慣習どこ由来?)
メソッドnewを生やすderive macro
#[derive(derive_new::new)]でメソッドnewが生える。#[derive(Default)]とは違いカスタマイズできる。
either v1.5.3 (docs) (anchor)
即席enum Either<L, R>
- 2019-11-13+09:00現在Rust Playgroundで使用可能
即席structとしてのtuple (A, B)のように即席enumとしての Either<A, B>として扱える。
定義が極めてシンプルで小さいため様々なところで使われ、re-exportされている。
というよりitertoolsがre-exportしているのでこのクレートの名前を隠す必要が無い。
こういうものを専用構文付きで入れようという議論はpre 1.0時代からある。
im-rc v14.0.0 (docs) (anchor)
永続データ構造
- rust-lang/cargoで使われている
im_rc::{HashMap, HashSet, OrdMap, OrdSet, Vector}を提供する。
それぞれstd::{collections::{HashMap, HashSet, BTreeMap, BTreeSet}, vec::Vec}の永続データ構造版。
imとim-rcに分けられているがその違いはデータ構造に使われる参照カウンタが前者はArc、後者はRcであることである。
これはim-rcのデータ型はSyncでもSendでもなく複数のスレッドから参照するのはもちろん、他スレッドにmoveすることもできないことを意味している。
AtCoderにおいてはこれは問題にならないと考えられるため、imの方は提案から外してある。
Rcにすることで得られる恩恵は"20-25% increase in general performance"だそう。
可変長bit set
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
FixedBitSetを提供する。
C++のstd::bitsetというよりはboost::dynamic_bitset。
だいぶ昔std::collections::BitSetというのが提案、実装されていたが却下されていたらしい。
その後(TODO: 後?)bit-setというクレートが登場し、fixedbitsetはこれの後継。
(forkではない)
bit-setは今はdeprecatedだがPlayroundで使用できる。
さらに同様なクレートとしてbit-vec, bitvecがあり、bit-vecもPlaygroundで利用できる。
TODO: bit-vec, bitvecとの違い
Before:
// 😧
let mut ps = vec![false; 10000];After:
use fixedbitset::FixedBitSet;
// 😃
let mut ps = FixedBitSet::with_capacity(10000);
可変長bit set
- 今回の2019年言語アップデートを聞いて作られたクレート。
TODO
このカテゴリに該当するクレートは標準入出力を改善するものです。このカテゴリのクレートはいずれか一つが導入されることを希望しますが、上にあるものの方が希望順位が高くなるように並べてあります。
std::cinやjava.util.Scannerのような、空白文字区切りの文字列として渡される値を先頭から読むためのもの。
プログラミングコンテストでの必要性は言うに及ばず、それ以外でもこのようなものが必要になることが多々ある。
このようなクレートは複数あるがどれも十分な"知名度"があるとは言えない。 それでもこのようなクレートを提案する理由はRust入門者(競プロ初心者とは限らない)にとって標準入力の読み取りは結構な負担になっているという現状があるからである。
https://twitter.com/search?q=rust%20標準入力&src=typed_query&f=live
"DPまとめコンテスト"の"R - Wark"の入力を読むことを考える。 『素朴な』やりかただとこのようになる。
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_whitespace();
let n = input.next().unwrap().parse::<usize>().unwrap();
let k = input.next().unwrap().parse::<u64>().unwrap();
let a = (0..n)
.map(|_| {
(0..n)
.map(|_| input.next().unwrap().parse().unwrap())
.collect()
})
.collect::<Vec<Vec<u64>>>();
solve(n, k, &a);
}この煩わしさから解放されるには簡潔に入力を読む関数を自分で書かなくてはならない。 これはちょっとRustに触れてみようと考えた人にとってはつらい。 もちろん複数人が各々の入力ヘルパーを公開しているが(後で言及するtanakh氏のを含め) なまじ冗長でも躓かずに書けてしまうのでこれらを使ってみようと思う人はあまり多くはない。 しかしAtCoderで何も用意せずに使えるならばその限りではないだろう。
このセクションではproconio, text_io, whitereadの3つのクレートを提案する。
(空白文字区切りの値を読むにあたっては)proconioが最も利便性, ドキュメントの充実度共に優れていると我々は考えているが知名度で言えばtext_io, whitereadの方が上である。
他の候補としては次の3つがあった。
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 |
| qryxip-input |
筆者(@qryxip)のinput! (main3bをベース) |
1.920 |
| 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 |
以下"R - Wark"の用サンプルをそれぞれの末尾に載せる。
input!マクロを提供。
- 今回の2019年言語アップデートを聞いて作られたクレート。
tanakh氏の競プロの入力をスッキリ記述するマクロを参考に作られている。
なお氏のinput!マクロは現在Mit Licenseで公開されている。
オリジナルのinput!に加え以下の特長を持つ。
-
読む入力を
strやFileに替えることができる。人によっては
ojのようなツールを使っていてこの機能の出番は無いかもしれない。 ただLLDB等のデバッガは使いやすくなる。use proconio::input; use proconio::source::once::OnceSource; input! { from OnceSource::from("42"), k: u32, } assert_eq!(k, 42);
-
変数に
mutを付けられる。use proconio::input; use proconio::source::once::OnceSource; input! { from OnceSource::from("42"), mut k: u32, } assert_eq!(k, 42); k -= 1; assert_eq!(k, 41);
-
Readableというトレイトでマーカーと読む対象が対応付けられている。FromStrである型は自身が対象のReadableである。 そうではないReadableとして文字列をVec<u8>として受けとるBytes,Vec<char>として受けとるChars, 整数値を1-based indexと解釈して値を-1するUsize1,Isize1が用意されている。use proconio::input; use proconio::marker::Usize1; use proconio::source::once::OnceSource; input! { from OnceSource::from("3\n2 1 2"), n: usize, g: [Usize1; n], } assert_eq!(g, &[1, 0, 1]);
use proconio::input;
fn main() {
input! {
n: usize,
k: u64,
a: [[u64; n]; n],
}
solve(n, k, &a);
}
text_io v0.1.7 (docs) (anchor)
read!マクロを提供。
現在"The MIT non-military non-spy License"なるライセンスで配布されている。
read!() (引数無し)でFromStrな値を1つずつ読める。
scanfっぽいことができるが空白文字区切りならread!()しか使わないだろう。
Rust 1.38 (2018 edition)で使って即座にわかる問題点として
-
#[macro_use] extern crate text_io;とするかglob importするか下のようにtry_read, try_scanごとuseする必要がある -
Clippyのwarningを踏む。黙らせるには下のように
#allow(clippy::try_err)とする必要がある
というのがあり、筆者(@qryxip)がこれらを解決するPull Requestを出してマージされたがおそらくこれに反応があるまでversion bumpは行なわれないだろう。
use text_io::{read, try_read, try_scan};
#[allow(clippy::try_err)]
fn main() {
let n: usize = read!();
let k: u64 = read!();
let a = (0..n)
.map(|_| (0..n).map(|_| read!()).collect())
.collect::<Vec<Vec<u64>>>();
solve(n, k, &a);
}
std::cinの使い勝手を再現したらしい。
MSRV (Minimal supported Rust version)が1.15 1.20 (v0.5.0で)であり、whiteread自身を単体のファイルに展開するCLIツールwhiteread-templateが付属している。
というよりむしろクレートとしての提供がおまけでdocs.rsが目当てだろう。
競技プログラミングに特化したインターフェイスでありながらbattle-provenな貴重なクレートであるとも言える。
use whiteread::Reader;
use std::io;
fn main() {
let stdin = io::stdin();
let mut rdr = Reader::new(stdin.lock());
let n = rdr.p::<usize>();
let k = rdr.p::<u64>();
let a = (0..n)
.map(|_| rdr.line().unwrap())
.collect::<Vec<Vec<u64>>>();
solve(n, k, &a);
}このカテゴリに該当するクレートは、上の二つと後述する高速化に当てはまらないものです。利用範囲が主には競技プログラミングに限られるものの、競技プログラミングの面白さを損なわない範囲（ズルにならない範囲）で便利になるものになります。このカテゴリのクレートは利便性の面から導入を希望しますが、強く希望するものではありません。
modtype v0.7.0 (docs) (anchor)
modint
- 今回の2019年言語アップデートを聞いて作られたクレート。
普通の整数型などと同じ感覚で扱うだけで自動的にmodを取ってくれる (参考: C++での使用例)
このカテゴリに該当するクレートは、Rustに標準で同等の機能をもつものが存在してもセキュリティなどの理由から高速性が犠牲になっている機能を置き換えるものです。利用シーンとしては主にマラソン形式のコンテストが想定されます。このカテゴリのクレートは今回のアップデートの趣旨に沿わない可能性が高いと認識しています。マラソンに対する扱いに変化があったときに再考していただけるよう、残してあります。
高速なハッシュ関数
- リポジトリが@rust-lang-nursery下にある
- (名前からして当然だが) rust-lang/rustで使われている
名の通りrustc(とFirefox)で使われているハッシュ関数。
fnvより速いらしい（hatooさんのツイート）
なおnightly-2019-11-05でベンチしたら以下の通りになった。
$ cargo +nightly bench 2>/dev/null
running 12 tests
test bench_default_hasher ... bench: 1,236,716 ns/iter (+/- 25,412)
test bench_default_hasher_80bytes ... bench: 5,129,332 ns/iter (+/- 89,715)
test bench_default_hasher_hashset ... bench: 5,001,261 ns/iter (+/- 87,264)
test bench_fnv ... bench: 916,566 ns/iter (+/- 1,850)
test bench_fnv_80bytes ... bench: 9,169,264 ns/iter (+/- 40,484)
test bench_fnv_hashset ... bench: 3,925,380 ns/iter (+/- 84,645)
test bench_metrohash ... bench: 741,043 ns/iter (+/- 42,943)
test bench_metrohash_80bytes ... bench: 4,102,943 ns/iter (+/- 207,716)
test bench_metrohash_hashset ... bench: 3,858,755 ns/iter (+/- 71,850)
test bench_rustc_hash ... bench: 8,555 ns/iter (+/- 44)
test bench_rustc_hash_80bytes ... bench: 1,375,034 ns/iter (+/- 1,796)
test bench_rustc_hash_hashset ... bench: 2,547,330 ns/iter (+/- 34,076)
test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out
ある長さまで要素を『直に』持ち、残りをヒープアロケートする可変長配列
- 2019-11-12+09:00現在Rust Playgroundで使用可能
- リポジトリが@servo下にある
- rust-lang/rustで使われている
C++のboost::container::small_vectorのようなもの。
可変長が必要だが大半は要素数1か2、という場合に便利。
boost::container::static_vectorのようなものを提供するarrayvecというクレートがあり、こちらもPlaygroundで使用可能であるがsmallvecで代用できると判断したため提案からは外してある。
代替ヒープアロケータ
pc-windows-msvcではビルドできないためcfg(not(windows))で指定。
pc-windows-gnu向けにはAppVeyorが走っているがずっと真っ赤。(下のほうは緑に見えるがallow_failuresしただけで中身は赤)
いくつもの問題によりRust 1.32.0からシステムアロケータに置きかえられたが、システムアロケータより速くなるケースは依然として存在する。 (TODO: 具体例)
A safe wrapper over
jemalloc'smallctl*()control and introspection APIs.
jemallocatorと同様。
TODO