概要
Atcoderで最近Python -> Rustに移行している最中でライブラリを作成中． ライブラリーを作りつつ，Atcoderで使えるcrate一覧に記載があるcrateを眺めているのでそのメモ． 使えそうな問題があれば別途記事をまとめていく． https://img.atcoder.jp/file/language-update/language-list.html#:~:text=Rust
ac-library-rs@=0.1.1
acl (AtCoder Library)のRust実装版．
https://atcoder.github.io/ac-library/master/document_ja/atcoder.github.io
once_cell@=1.18.0
static_assertions@=1.1.0
varisat@=0.2.2
CDCLとSATに関連しているやつ．
使い方
Aalto University（スウェーデン）の講義資料（まだ読んでない）
SATソルバーを使って数独を解く． ipsj.ixsq.nii.ac.jp
如何せん全く知らない分野なので軽めに眺めてほへーという感じ．
memoise@=0.3.2
メモ化再帰を行うときに使えるattribute macro
例:
use memoise::memoise;
fn main() {
#[memoise(n <= 10)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
let ans = fib(10);
println!("{}",ans);
}
=> 55
use memoise::memoise;
fn main() {
#[memoise(n <= 10)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
let ans = fib(10);
println!("{}",ans);
}
thread 'main' panicked at src/bin/a.rs:4:5: index out of bounds: the len is 11 but the index is 11
定義した枠を超えるとpanicする． 一応，キャッシュする定義域を指定しない方法もあるが，動的にキャッシュを残す．おそらくパフォーマンスは落ちる．
use memoise::memoise;
fn main() {
#[memoise(n)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
let ans = fib(11);
println!("{}",ans);
}
memoise => Memoise function by using Vec memoise_map=> Memoise function by using BTreeMap
キャッシュは，Vec版とBtreeMapがあるらしい．キャッシュするもの値が連続値でない場合は，BtreeMapを使うといいだろう．
使えそうな問題 atcoder.jp
argio@=0.2.0
use argio::argio;
#[argio]
fn main(n: usize, a: [i64; n]) -> i64 {
a.into_iter().sum()
}
関数の引数と戻り値を標準入出力から取るように変更するマクロ．
[tex:N] [tex:A_1 A_2 ... A_N]
この標準入力を受け，Aの合計値を標準出力で出力．
少しコード量が減り楽ができそう．ただし，自分のAtcoderのテンプレートはproconioで作っているので使わないかな．．．
bitvec@=1.0.1
bitvec provides a foundational API for bitfields in Rust. It specializes standard-library data structures (slices, arrays, and vectors of bool) to use one-bit-per-bool storage, similar to std::bitset
and std::vector in C++. Additionally, it allows a memory region to be divided into arbitrary regions of integer storage, like binaries in Erlang.
If you need to view memory as bit-addressed instead of byte-addressed, then bitvec is the fastest, most complete, and Rust-idiomatic crate for you.
bitvec は、Rust におけるビットフィールドの基礎となる API を提供します。これは、C++のstd::bitset<N>やstd::vector<bool>と同様に、標準ライブラリのデータ構造（スライス、配列、boolのベクトル）を1ビット/ブールのストレージに特化したものです。 さらに、Erlangのバイナリのように、メモリ領域を整数ストレージの任意の領域に分割することができます。 もしメモリをバイトアドレスではなくビットアドレスで見る必要があるなら、bitvecは最も高速で、最も完全で、Rustらしいクレートです。
1bit(boolも1bit)の場合は，bitvecが高速らしい．このクレートのDocではErlangの名前が多々出てくるが詳しいことは知らないのでそこらへんは読み飛ばしています．（VMがあって，ElixirがそのVM上で動いていることことくらいの知識がない．．．Elixirも使ったことない，Rustを演る人はErlangくらい知っているよねレベルの話なんだろうか．）
counter@=0.5.7
Counter counts recurrent elements of iterables. It is based on the Python implementation.
Pythonのcollections.Counterをベースに作られている．
数学的にはこれが近いらしい． en.wikipedia.org
テストを眺めていて気になったものを抜粋 docs.rs
test_add_update_iterable
#[test]
fn test_add_update_iterable() {
let mut counter = Counter::init("abbccc".chars());
let expected = hashmap! {
'a' => 1,
'b' => 2,
'c' => 3,
};
assert!(counter.map == expected);
counter += "aeeeee".chars();
let expected = hashmap! {
'a' => 2,
'b' => 2,
'c' => 3,
'e' => 5,
};
assert!(counter.map == expected);
}
まさかの+=演算子(-=も実装されている)が定義されている．Counter同士ならわかるがこれは便利．
impl<I, T, N> AddAssign<I> for Counter<T, N>
where
I: IntoIterator<Item = T>,
most_common_ordered
countが多いかつkeyでソート．
let by_common = "eaddbbccc".chars().collect::<Counter<_>>().most_common_ordered();
let expected = vec![('c', 3), ('b', 2), ('d', 2), ('a', 1), ('e', 1)];
assert!(by_common == expected);
test_total
fn test_total() {
let counter = Counter::init("".chars());
let total: usize = counter.total();
assert_eq!(total, 0);
let counter = Counter::init("eaddbbccc".chars());
let total: usize = counter.total();
assert_eq!(total, 9);
}
hashbag@=0.1.11
pathfinding@=4.3.0
recur-fn@=2.2.0
indexing@=0.4.1
amplify@=3.14.2
amplify_derive@=2.11.3
amplify_num@=0.4.1
easy-ext@=1.0.1
multimap@=0.9.0
btreemultimap@=0.1.1
bstr@=1.6.0
az@=1.2.1
glidesort@=0.1.2
tap@=1.0.1**
omniswap@=0.1.0
multiversion@=0.7.2
num@=0.4.1
num-bigint@=0.4.3
num-complex@=0.4.3
num-integer@=0.1.45
num-iter@=0.1.43
num-rational@=0.4.1
num-traits@=0.2.15
num-derive@=0.4.0
ndarray@=0.15.6
nalgebra@=0.32.3
alga@=0.9.3
libm@=0.2.7
rand@=0.8.5
getrandom@=0.2.10
rand_chacha@=0.3.1
rand_core@=0.6.4
rand_hc@=0.3.2
rand_pcg@=0.3.1
rand_distr@=0.4.3
petgraph@=0.6.3
indexmap@=2.0.0
regex@=1.9.1
lazy_static@=1.4.0
ordered-float@=3.7.0
ascii@=1.1.0
permutohedron@=0.2.4
superslice@=1.0.0
itertools@=0.11.0
itertools-num@=0.1.3
maplit@=1.0.2
either@=1.8.1
im-rc@=15.1.0
fixedbitset@=0.4.2
bitset-fixed@=0.1.0
proconio@=0.4.5
text_io@=0.1.12
docs.rs read!()マクロは、常に次のアスキー空白文字( \n, ˶r, ˶t, またはスペース)まで読みます．
rustc-hash@=1.1.0
Fast, non-cryptographic hash used by rustc and Firefox.
なんでFirefoxって思ったけど，どちらもmozillaか．
A speedy hash algorithm for use within rustc. The hashmap in liballoc by default uses SipHash which isn't quite as speedy as we want. In the compiler we're not really worried about DOS attempts, so we use a fast non-cryptographic hash.
HashのDOS攻撃 => hashテーブルで衝突を狙い計算機リソースを無駄に消費させる攻撃． Pythonのsetで起こるので気をつけよう的なことがAtcoderの解説でもされていた． atcoder.jp
smallvec@=1.11.0
一定数の要素をインライン（つまり、スタック上）に格納し、それを超える場合にはヒープに割当します。以下の利点があります．
キャッシュ局所性の向上
インラインに要素を格納することで、データが連続したメモリブロックに配置され、CPUキャッシュの効率が向上します。これは、データアクセス時のレイテンシを減らし、全体的なパフォーマンスを向上させることができます。
アロケータトラフィックの削減
小さなデータセットの場合、smallvecはヒープ割り当てを避けることができます。これは、メモリ割り当てと解放に関連するオーバーヘッドを減らし、特に割り当てが頻繁に行われるシナリオではパフォーマンスの向上につながります。
なんのこっちゃ．LLVMに同じ名前のデータ構造があるので，本気で最適化をする際にはよく使われるっぽい．背景知識がなさすぎて絶望． どういう理由でatcoderで使えるLibに追加されたのだろうか．．．
よく調べてみるとRust製のhtmlのレンダーの配下のプロジェクトっぽい．使い所がいまいちわからないのでここを見てみようと思う． github.com
以下GPT４
smallvecの特性は、競技プログラミングのようなパフォーマンスが重要な状況で非常に有用です。競技プログラミングでは、実行時間やメモリ使用量を最小限に抑えることが求められます。smallvecは、以下のような場面で特に役立ちます。小さなグラフの操作
競技プログラミングの問題には、グラフに基づくものがよくあります。ノード数が比較的少ない場合や、各ノードが少数のエッジしか持たない場合、ノードの隣接リストを
smallvecで保持することで、メモリの割り当て回数を減らし、キャッシュの効率を向上させることができます。効率的なスタックとキュー
アルゴリズムでスタックやキューが必要な場合、そのサイズが予測可能であれば、
smallvecを用いることで実行効率を向上させることができます。たとえば、深さ優先探索(DFS)や幅優先探索(BFS)で探索するノードの数があらかじめわかっている場合、スタックやキューにsmallvecを使用することで、メモリ割り当てのオーバーヘッドを減らすことができます。ダイナミックプログラミング
ダイナミックプログラミング(DP)の解法を実装する際、特に状態の数が限られているケースでは、DPテーブルを
smallvecの配列で表現することができます。状態遷移に必要なデータが少ない場合、smallvecを使用することでメモリアクセスの効率を上げることができます。小さな集合の管理
競技プログラミングの問題で、小さな要素の集合を頻繁に作成・操作する必要がある場合（例えば、ある条件を満たす要素の集合）、
smallvecを使用すると、集合の作成や操作時のメモリ割り当てコストを削減できます。パフォーマンスチューニング
特定の問題において、アルゴリズムの実行時間がぎりぎりの場合、
smallvecを使って微調整を行うことが解決策になることがあります。ヒープ割り当てを避けることで、わずかながらもパフォーマンスを改善できる場合があります。これらの利用例からもわかるように、
smallvecは競技プログラミングにおいて、特定の条件下でパフォーマンスの最適化を図るための強力なツールとなり得ます。ただし、その効果は使用する状況やデータのサイズに依存するため、適切な場面での利用が重要です。
如何せん，allocにコストが掛かることは知識として知っているが，どのくらいパフォーマンスに影響出るかは，低レイヤー言語での実装経験がなさすぎるのでどこかで試してみよう．
todo
- allocのパフォーマンスへの影響
