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を含む)
-
x86_64-unknown-linux-gnu上のものに限ります。 (2020-01-03Zから) - ビルドされるときにdependencyをDLするのでだいたいDL数上位250のような品揃えになっていると思われます。
-
2020-01-07+09:00現在、バージョン違いやwinapiのような実質使えないもの (大半は除外されるようになりました)を含んで271個のクレートが利用可能です。
$ date +%Y-%m-%d%:z
2020-01-07+09:00
$ curl -s https://raw.githubusercontent.com/integer32llc/rust-playground/master/compiler/base/crate-information.json | jq length
271
$ # バージョン違いのみ除く
$ curl -s https://raw.githubusercontent.com/integer32llc/rust-playground/master/compiler/base/crate-information.json | jq 'map(.name) | unique | length'
251Rust Playgroundで利用されるクレートは知名度が保証されていると言ってもいいでしょう。以下で紹介するクレートのいくつかはこれに含まれています。
また今回提案するクレートリストをPlaygroundのものにしようという案もありました (スプレッドシートの"Rust (Playground)", Slackのコメント) が、以下の問題点があるため見送っています。
- 271個のクレートのうち、競技プログラミングにおいて僅かでも使えそうなものがせいぜい二割程度しかない。
- 全分野の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-bigint
- num-complex
- num-integer
- num-iter
- num-rational
- num-traits
- num-derive
- ndarray
-
nalgebra
- alga
- libm
-
rand
- getrandom
- rand_chacha
- rand_core
- rand_hc
- rand_pcg
- rand_distr
- petgraph
- euclid
-
primal
- primal-check
- primal-estimate
- primal-sieve
- indexmap
- regex
- nom
- aho-corasick
- strsim
- lazy_static
- approx
- ordered-float
- ascii
- permutohedron
- superslice
- itertools
- itertools-num
- take_mut
- defmac
- matches
- if_chain
- maplit
- derive_more
- derive-new
- either
- im-rc
- fixedbitset
- bitset-fixed
- union-find
-
num
- 標準入力を扱うもの
- 主に競技プログラミング用を想定したもの
- 高速化するもの
このカテゴリに該当するクレートは次のいずれかにあたるものです。
- 他のいくつかの言語では標準の機能となっている。
- 普段のコーディングで利用されており、Rustらしいコードを書くのに利用している。
- boost や numpy など既に認められたライブラリ内に同等のものが存在する。
このカテゴリのクレートは基本的に全て導入されることを希望します。 (ただしbitset-fixedとfixedbitsetについてはいずれか片方が導入されることを希望します。)
このカテゴリのクレートの説明には、しばしば「かつてstd (標準ライブラリ) の一部だった」「かつてRust本体にバンドルされていた」のような表現が現れます。これは現在でも標準ライブラリに準じる存在だということを意味します。これらがユーザークレートになった理由は不評や利用者の少なさなどによるものではありません。cargoやcrates.ioのような強力なパッケージ管理システムを前提に、言語とライブラリの成長を分離する目的で意図的に標準ライブラリを小さくしているからです。
数値型に対するサポートを充実させるものの詰め合わせ。
v0.2.1
- num-bigint v0.2.5
- num-complex v0.2.4
- num-integer v0.1.42
- num-iter v0.1.40
- num-rational v0.2.3
- num-traits v0.2.11
-
pre 1.0時代には
libnumとしてRust本体にバンドルされていた (Slackのコメント) 。 - 2020-01-07+09:00現在Rust Playgroundで使用可能。
上記のsub crate6つ（e.g. num_bigint → num::bigint）といくつかのアイテム（e.g. num_bigint::BigInt → num::BigInt）をre-exportしている。
このクレート上で実装されているものは無い。
以下sub crateについて説明する。
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)があるがそれらは現在のところ、トレイトによる抽象化はされていない。
また数値型を（雑に）キャストするのに使うasもトレイトで定義されていない。
num-traitsはこれらをトレイトで統一して扱えるようにする。
さらにトレイトを『まとめる』トレイト（e.g. +-*/%に対応するトレイトをまとめるNumOps）を提供する。
このうちnum-traitsとnum-iterはコンテスト中の利用というよりはAtCoderだけで使う競プロライブラリを整備する際の利用が想定される。
当然可搬性は無いのでCodeforces等に参加する人はまず利用しないと考えられる。
（CodinGameのようにクレートを導入しているところが増えればそうでもなくなるかもしれない。）
そのため多くの人が直接利用するかどうかには疑問も残る。
ただし他のnum-*系クレートを含むこのWiki上のいくつかのクレートの依存にもなっており、Cargo.tomlから削除してもdependency graph上に残るので名前をわざわざ隠す必要はあまり無いと考えている。
Procedural macros to derive numeric traits in Rust.
v0.3.0
- 2020-01-07+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には含まれていない。
多次元配列のサポート。
v0.13.0
- 2020-01-07+09:00現在Rust Playgroundで使用可能
Pythonのnumpy.ndarrayのような多次元配列を提供する。
通常Rustで二次元以上の配列を扱うときはVec<Vec<...>>の形で扱うが、ただのJAG配列なので全要素に対する変更などのユーティリティは用意されていない。
自分で用意しようとしてもRustの場合借用チェッカが牙を剥くことがある。
ndarrayが提供する多次元配列はNumPyのものと同じく形状変更やスライス、多次元配列同士の演算などの様々な機能を持つ。 もちろん行列の演算にも用いることができる。
線形代数
v0.19.0
- alga v0.9.2
- 2020-01-07+09:00現在Rust Playgroundで使用可能
(競プロにおいては)ndarrayほどの手軽さは無いがNumPyが提供しているものでndarrayには無いような関数がいくつかある。
libmのRust実装
v0.2.1
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- リポジトリが@rust-lang下にある
- コンパイラに使われている
core (⊂ std)の数値型の関数はLLVMの実装によるものが多いが、このクレートは基本的にplatform independentな結果を返すので特に浮動小数点数を扱うライブラリによく使われている。
またAPIがmath.h (⊊ cmath)のままなのでRust入門者にとっては使いやすいかもしれない。
このコメントによれば重要な役割を持ち始めたのは最近のよう。
RNG疑似乱数
v0.7.3
- getrandom v0.1.13
- rand_chacha v0.2.1
- rand_core v0.5.1
- rand_hc v0.2.0
- rand_pcg v0.2.1
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- pre 1.0時代に
stdの一部だった歴史を持つ - rust-lang/rustで使われている
- CodinGameで使用可能
small_rng featureが必要（Slackでのコメント）
以下の乱数を提供する。
-
OsRng(fromrand_core) -
SamllRng(fromrand_pcg) (feature-gated) -
StdRng(fromrand_chacha) ThreadRng-
StepRng(1から順番に吐くテスト用のもの)
このうち競技プログラミング向きなのはSmallRngだがこれは0.7になってdefault featuresから外れた。
使うにはsmall_rng featureを付け加える必要がある。
ありとあらゆる所に使われているクレートであり、2020-01-07+09:00現在総DL数1位に輝いている。
分布に従った乱数を生成
v0.2.2
- 2020-01-07+09:00現在Rust Playgroundで使用可能
rand::distributionを拡張したもの。色々な分布が用意されているらしい。
@rust-randomのクレートの中で唯一randに含まれていない。
グラフ
v0.5.0
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
Graph, StableGraph, GraphMap, Csrに加えUnionFindを提供する。
またv0.5.0でMatrixGraphが追加された。
Boostのグラフ関連や今回Pythonへの導入が確定（？）したNetworkXのようなもの。 グラフをgraphviz形式で表示する機能もあり、グラフの形がわからなくなったときにさっと図示できる。
TODO: BoostやNetworkXとの比較
幾何
v0.20.7
- リポジトリが@servo下にある
TODO
素数
v0.2.3
- primal-check v0.2.3
- primal-estimate v0.2.1
- primal-sieve v0.2.9
primal-checkはmiller_rabin, as_prime_power, as_perfect_powerを提供する。
primal-estimateはnth_prime, prime_piを提供する。
primal-sieveはPrimes, Sieve, StreamingSieveを提供する。
一応参考としてJuliaにはPrimesの導入が確定している。
またBoostにはMiller-Rabin testの機能があるし10000番目までの素数が格納されている。
use primal::Sieve;
let sieve = Sieve::new(100);
assert!(sieve.is_prime(97));
assert_eq!(sieve.nth_prime(25), 97);
assert_eq!(sieve.prime_pi(97), 25);
itertools::assert_equal(sieve.primes_from(10).take(3), vec![11, 13, 17]);
assert_eq!(sieve.factor(991 << 54), Ok(vec![(2, 54), (991, 1)]));
挿入順を保持するhash table
v1.3.0
- 2020-01-07+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-12-15+09:00現在、Playgroundで利用可能である。
正規表現
v1.3.3
- 2020-01-07+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)を用いるのが一般的。
パーサーコンビネータ
v5.0.1
-
2019-12-15+09:00現在Rust Playgroundで使用可能(外れました)
v5より前はマクロによるDSLで記述する形だったがv5から関数で構成する形になった。
対抗馬としてcombineというクレートがある。
nom v5はこのクレートに比べて
- 4倍以上の総DL数
- 型が簡略化されている。
combineはメソッドチェーン1つごとに型がラップされていくので型合わせが失敗するとエラーメッセージがわからなくなる - ↑によりコンパイルの負担が小さい
- 無理にパーサーをコンビネートしなくても途中から手続き型のように書ける
という利点がある。
Aho–Corasick
v0.7.6
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- @BurntSushi氏が管理している
AhoCorasick, AhoCorasickBuilderを提供する。
regexの依存。
外すこともできるがその場合マッチが数倍遅くなるらしい。
Implementations of string similarity metrics.
v0.9.3
- 2020-01-07+09:00現在Rust Playgroundで使用可能
hammingやjaro等2つのstrの"similarity"を計算する関数を多数提供する。
staticアイテムの遅延初期化
v1.4.0
- 2020-01-07+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数が
で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:
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]);
浮動小数点数の比較
v0.3.2
- 2020-01-07+09:00現在Rust Playgroundで使用可能
AbsDiffEq, RelativeEq, UlpsEq及び{, assert_}{abs_diff, relative, ulps}_{eq, ne}!マクロを提供する。
TODO: 必要となるとき
Ord/Eqを実装するNotNan<f64>, OrderedFloat<f64>
v1.0.2
- 2020-01-07+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
AsciiChar, AsciiStr, AsciiStringを提供する。
それぞれの表現はu8, [u8], Vec<u8>であり、チェック以外のオーバーヘッドは生じない。
stdの範囲でASCII文字列を持つ方法にはstr, Stringと[u8], Vec<u8>の2通りがある。
前者では.as_bytes()[i]とすればi番目の文字を読むことができるが書き換えるのは面倒。
後者では楽にランダムアクセスできるがstrが持つメソッドが使えない。
AsciiStr, AsciiStringはこの両方の長所を持つ。
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: 実際に嬉しい例が見つからない!
Permutation生成
v0.2.4
- @bluss氏が管理している
[T] where T: Ordの拡張メソッド{prev, next}_permutationと関数heap_recursiveを提供する。
heap_recursiveは名の通りHeapのアルゴリズムを使うものでnext_permutationを連打するより少しだけパフォーマンスが良い。
また値の順序を要求しないので浮動小数点数でもそのまま使える（ordered-floatの項を参照）。
Rustにはdo-while文自体はないものの、下の例のような書きかたができるので順序が重要でない場合もどちらを使うかは好みと言えるだろう。
この関数は下で紹介するsupersliceには無い。
use permutohedron::LexicalPermutation as _;
let mut values = [1, 2, 3];
while {
eprintln!("{:?}", values);
values.next_permutation()
} {}let mut values = [1, 2, 3];
permutohedron::heap_recursive(&mut values, |values| eprintln!("{:?}", values));
スライスの強化
v1.0.0
スライスに対して以下の拡張メソッドを提供する。
-
<[_] as Ext>::{lower, upper}_bound{, _by, _by_key}Rust 1.17から
BTreeSet::rangeが使えるのでC++のそれらよりは出番が無いかもしれない。 -
<[_] as Ext>::equal_range{, _by, _by_key}lower bound以上upper bound以下の範囲を返す。
-
<[_] as Ext>::{next, prev}_permutationpermutohedron::heap_resursiveのようなものは提供していない。 -
<[_] as Ext>::apply_permutation組み合わせ（
[isize]）を『適用』する。 -
<[_] as Ext>::apply_inverse_permutationinverse permutation（
[isize]）を『適用』する。 -
<[isize] as Ext2>::invert_permutationinverse permutationを返す。
ちなみに前身のordsliceのDL数は
イテレータの強化
v0.8.2
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- @bluss氏が管理している
- rust-lang/rustで使われている
- CodinGameで使用可能
Iteratorを拡張するItertoolsとその他の便利な関数やマクロを提供する。
Pythonのmore-itertoolsのようなもの。 itertoolsの名に因んでいるとはいえ単純に対応するものではなく、互いに存在しないものや対応していても名前が違う場合がある。
Pythonの標準ライブラリの方のitertoolsにもあるpermutations, combinations, zip_longestの他more_itertools.ichunkedのようなchunks,
more_itertools.intersperseのようなintersperse,
more_itertools.paddedのようなpad_using,
more_itertools.interleaveとmore_itertools.interleave_longestのようなinterleave_shortestとinterleave,
Rustならではのcoalesce, set_from,
単純な略式メソッドのcollect_vec等々多彩なメソッドが使えるようになる。
v0.1.3
- @bluss氏が管理している
ItertoolsNum::cumsum, linspaceの2つを提供する。
これだけ。
itertoolsクレートと同じ作者だが分離されている理由はよくわからない。
それぞれPythonのitertools.accumulate or numpy.cumsum, numpy.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]);
&mut TからTを『借りる』
v0.2.2
takeとtake_or_recoverを提供する。
takeは&mut TからTを『借りて』T -> Tの関数に適応する。
返せないとき、すなわちpanicした場合プログラムをabortさせる。
参考: Rustのパニック機構
1行で書けるmacro_rules
v0.2.1
- @bluss氏が管理している
マクロを生み出すマクロdefmac!を提供する。
このマクロによりrustfmt下で最低5行を要するmacro_rulesを1行で記述し、視認性を高めることが可能になる。
またパターンで引数を与えることもできる。
(match (..) { (..) => .. }と展開するマクロになる)
Rustでは&mut _を巻き込むクロージャはその対象を専有できる必要があるがmacro_rulesを使った場合はそうではないため、競技プログラミングに限らずともclosureの代用としてよく使われる。
+use defmac::defmac;
+
let mut st = 0;
-macro_rules! incr {
- ($n:expr) => {
- st += $n;
- };
-}
+defmac!(incr n => st += n);
incr!(1);
assert_eq!(st, 1);examples/abc129-f.rsexamples/abc142-d.rsexamples/abc144-d.rsexamples/abc151-d.rsexamples/atc002-b.rsexamples/sumitrust2019-c.rs
パターンをbool式に
v0.1.8
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- Rust 1.42から
std::matches!が使えるようになる予定
matches!, assert_matches!, debug_assert_matches!を提供する。
matches!によって
let p = match x {
$pat => true,
_ => false,
};のようなものを
let p = matches!(x, $pat);のようにできる。
(debug_)assert_matches!は(debug_)assert!(matches!(..))のショートカットのようなもの。
失敗時に対象の式の値を表示してくれる点が異なる。
実装は非常に簡素。 テストを抜けば29（= 9 + 9 + 11）行しかない。 多分本提案リストのなかで最小。
またcore::matches! (i.e. std::matches!)というのがRust 1.42から使える予定。現在のnightlyのRustで使うことができる。
こちらはif節ガートがサポートされている。
-let p = 'a' <= c && 'z' <= c || '0' <= c && c <= '9' || c == '-' || c == '_';
+let p = matches::matches!(c, 'a'..='z' | '0'..='9' | '-' | '_');
ifとif letを『まとめる』マクロif_chain!
v1.0.0
if_chain!を提供する。
100行に満たないシンプルなmacro_rulesだが以外と使いどころが多く、長い間使われ続けている。
else節が必要無くともインデントを2段までに抑える効果がある。
Before:
let x: Option<i32> = todo!();
if let Some(x) = x {
if p(x) {
f(x);
} else {
g();
}
} else {
g();
}After:
use if_chain::if_chain;
let x: Option<i32> = todo!();
if_chain! {
if let Some(x) = x;
if p(x);
then {
f(x);
} else {
g();
}
}
BTreeMap, BTreeSet, HashMap, HashSet用のマクロ
v1.0.2
- @bluss氏が管理している
Vec<_>にはvec![a, b, c]のように構成できるがstdは現在上記の4つに対してそのようなコンストラクタを提供していない。
このクレートはvec!に似たbtreemap!, btreeset!, hashmap!, hashset!を提供する。
また各key, valueを指定の関数に通すconvert_args!も提供する。
かなりポピュラーなクレートであり、コレクションっぽいデータ構造を提供するクレートは大抵これに似た形式のmacroを用意している。 またRFCsにこんな提案がある。 pre 1.0時代からあって現在もcloseされていない。もしかしたら標準ライブラリに似たようなのが入るかもしれない。
-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,
+);
stdのトレイトに対応するderive macro
v0.99.2
structやenumにFrom, Index, Deref, Add, IntoIterator等stdのトレイトの内derive macroが用意されていないものに対するderive macroを提供する。
バージョンが0.15から0.99に飛んでいるがこれはAPIにbreaking changeを入れる予定はもう無いがdependencyに0未満のものが含まれているからだと思われる。 (TODO: この慣習どこ由来?)
Display以外実装のカスタマイズはできないので条件付きのnewtypeには使えなさそうに見えるが、IntoやDeref, Index等カスタマイズの必要性の無いものは普通に使える。
-use std::fmt::Display;
-use std::iter::Sum;
-use std::ops::{Add, AddAssign, Sub, SubAssign};
+use derive_more::{Add, AddAssign, Display, Sub, SubAssign, Sum};
+#[derive(Display, Clone, Copy, Add, AddAssign, Sub, SubAssign, Sum)]
+#[display(fmt = "{} {}", _0, _1)]
struct Vector2(f64, f64);
-
-// 略-use std::fmt;
-use std::ops::Deref;
+use derive_more::{Deref, Display};
-#[derive(Clone, Copy)]
+#[derive(Display, Deref, Clone, Copy)]
struct Z {
repr: u64,
}
-impl fmt::Display for Z {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- fmt::Display::fmt(&**self, fmt)
- }
-}
-
-impl Deref for Z {
- type Target = u64;
-
- fn deref(&self) -> &u64 {
- &self.repr
- }
-}
-
impl Z {
fn new(val: u64) -> Self {
let repr = val % 1_000_000_007;
Self { repr }
}
}
let x = Z::new(1_000_000_008);
let _: u64 = *x;
println!("{}", x);
メソッドnewを生やすderive macro
v0.5.8
#[derive(derive_new::new)]でメソッドnewが生える。#[derive(Default)]とは違いカスタマイズできる。
-use derive_new::new;
+#[derive(new)]
struct Item {
param: u64,
}
-impl Item {
- fn new(param: u64) -> Self {
- Self { param }
- }
-}
-
let item = Item::new(42);
即席enum Either<L, R>
v1.5.3
- 2020-01-07+09:00現在Rust Playgroundで使用可能
即席structとしてのタプル (A, B)のように即席enumのEither<A, B>として扱える。
定義が極めてシンプルで小さいため様々なところで使われ、re-exportされている。
というよりitertoolsがre-exportしているのでこのクレートの名前を隠す必要が無い。
ちなみに即席直和型を専用構文付きで入れようという議論がpre 1.0時代からある。
-enum Either<L, R> {
- Left(L),
- Right(L),
-}
+use either::Either;
永続データ構造
v14.1.0
- 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"だそう。
-let mut map = maplit::hashmap!();
-map.insert("foo", 42);
+let map = im::hashmap!();
+let map = map.update("foo", 42);
可変長bit set
v0.2.0
- 2020-01-07+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
v0.1.0
- 今回の2019年言語アップデートを聞いて作られたクレート。
TODO
union-find (a.k.a. disjoint-set)
v0.3.2
union-findとしてQuickFindUfとQuickUnionUf、各unionの表現としてUnionByRankとUnionByRankSize, UnionBySize, UnionBySizeRankを提供する。
petgraphのUnionFindと違い実装を2×4通りから選べる上、各unionのサイズを取得できる（UnionByRank以外なら）。
このカテゴリに該当するクレートは標準入出力を改善するものです。
proconio, text_io, whitereadの3つのクレートを提案します。 これらのうち高々一つが導入されることを想定していますが、whitereadよりtext_io, text_ioよりproconioが導入されることを希望しています。
これらを使った例を載せておきます。
(-naiveは比較の為のクレートを使わない例です)
また他の候補としてはscan-rules, scanlex, scanner-rustがありました。
改良input!とprintln!を自動バッファリングにするattribute macro
v0.3.4
- 今回の2019年言語アップデートを聞いて作られたクレート。
input!と#[fastout]を提供。
tanakh氏の競プロの入力をスッキリ記述するマクロを参考に作られている。
なお氏のinput!マクロは現在Mit Licenseで公開されている。
proconio::input!はオリジナルのinput!に以下の機能を追加したもの。
-
読む入力を
strやFileに替えることができる。LLDB等のデバッガが使いやすくなるが、人によっては
ojのようなツールのみを使っていてこの機能の出番は無いかもしれない。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"), g: [Usize1], } assert_eq!(g, &[1, 0, 1]);
また#[fastout]はRustで高速な標準出力 - κeenのHappy Hacκing Blogで紹介されているようなBufWriterを使う方法を自動でやるようにできるマクロ。
関数内のprint!とprintln!を置き換える。
println!は遅いので10^5個程の要素を出力しようとすると150msくらい持っていかれる。
致命的ではないものの精神的に良くないので大抵はBufWriterを使う。
ただこれはほんの少しだけ面倒。
fn main() {
let ans: Vec<i64> = todo!();
let stdout = io::stdout();
let mut stdout = BufWriter::new(stdout.lock());
for ans in ans {
// 間違えて`println!`を使わないように注意
writeln!(stdout, "{}", ans).unwrap();
}
stdout.flush().unwrap();
}// あるいは
fn main() {
let ans: Vec<i64> = todo!();
let stdout = io::stdout();
let mut stdout = BufWriter::new(stdout.lock());
// `std::println!`を置き換える
// `main`の外には置けない
macro_rules! println {
($($tt:tt)*) => {
writeln!(stdout, $($tt)*).unwrap()
};
}
for ans in ans {
println!("{}", ans);
}
stdout.flush().unwrap();
}proconioならmain()に#[proconio::fastout]を付けるだけでいい。
#[proconio::fastout]
fn main() {
let ans: Vec<i64> = todo!();
for ans in ans {
println!("{}", ans);
}
}examples/abc057-b-proconio.rsexamples/abc118-b-proconio.rsexamples/abc121-b-proconio.rsexamples/abc141-c.rs
read!マクロを提供。
v0.1.7
現在"The MIT non-military non-spy License"なるライセンスで配布されている。
read!() (引数無し)でFromStrな値を1つずつ読める。
scanfっぽいことができるが空白文字区切りなら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 (コメント欄) InputScanOnce1.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)のiostream3.791 cstdio C++ (g++ 9.2.0 with -std=c++17 -O2)のcstdio3.223 また
read!()は実装上も単なるread!("{}")のエイリアスであり、パフォーマンスのための特殊化はされていない。 -
使うには
#[macro_use] extern crate text_io;とするかglob importするか下のようにtry_read, try_scanごとuseする必要がある -
Clippyのwarningを踏む。黙らせるには下のように
#allow(clippy::try_err)とする必要がある
というのがあり、下2つは筆者(@qryxip)がこれらを解決するPull Requestを出してマージされたがおそらくこれに反応があるまでversion bumpは行なわれないと思われる。
std::cinの使い勝手を再現したらしい。
v0.5.0
MSRV (Minimal supported Rust version)が1.15 1.20 (v0.5.0で)であり、whiteread自身を単体のファイルに展開するCLIツールwhiteread-templateが付属している。
というよりむしろクレートとして提供されているのはdocs.rsに載せるためだけだと思われる。
競技プログラミングに特化したインターフェイスでありながら『実戦証明』された貴重なクレートであるとも言える。
このカテゴリに該当するクレートは、上の二つと後述する高速化に当てはまらないものです。利用範囲が主には競技プログラミングに限られるものの、競技プログラミングの面白さを損なわない範囲（ズルにならない範囲）で便利になるものになります。このカテゴリのクレートは利便性の面から導入を希望しますが、強く希望するものではありません。
modint
v0.7.0
- 今回の2019年言語アップデートを聞いて作られたクレート。
普通の整数型などと同じ感覚で扱うだけで自動的にmodを取ってくれる (参考: C++での使用例)
このカテゴリに該当するクレートは、Rustに標準で同等の機能をもつものが存在してもセキュリティなどの理由から高速性が犠牲になっている機能を置き換えるものです。利用シーンとしては主にマラソン形式のコンテストが想定されます。このカテゴリのクレートは今回のアップデートの趣旨に沿わない可能性が高いと認識しています。マラソンに対する扱いに変化があったときに再考していただけるよう、残してあります。
高速なハッシュ関数
v1.0.1
- リポジトリが@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
ある長さまで要素を『直に』持ち、残りをヒープアロケートする可変長配列
v1.1.0
- 2020-01-07+09:00現在Rust Playgroundで使用可能
- リポジトリが@servo下にある
- rust-lang/rustで使われている
C++のboost::container::small_vectorのようなもの。
可変長が必要だが大半は要素数1か2、という場合に便利。
boost::container::static_vectorのようなものを提供するarrayvecというクレートがあり、こちらもPlaygroundで使用可能であるがsmallvecで代用できると判断したため提案からは外してある。
+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]>>>();
代替ヒープアロケータ
v0.3.2
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.
v0.3.3
jemallocatorと同様。
TODO