Nov 2024 Language Update ライブラリ案
このページは誰でも編集できます。
- 2024-2025年環境に要望するクレート
-
2023年環境のクレート
- ac-library-rs
- once_cell
- static_assertions
- varisat
- memoise
- argio
- bitvec
- counter
- hashbag
- pathfinding
- recur-fn
- indexing
-
amplify
- amplify_derive
- amplify_num
- easy-ext
- multimap
- btreemultimap
- bstr
- az
- glidesort
- tap
- omniswap
- multiversion
-
2020年環境のクレート
-
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
- indexmap
- regex
- lazy_static
- ordered-float
- ascii
- permutohedron
- superslice
- itertools
- itertools-num
- maplit
- either
- im-rc
- fixedbitset
- bitset-fixed
- proconio
- text_io
whiteread- rustc-hash
- smallvec
-
num
v0.17.1
- AHC推定ゲーのためにstatrsをください 分布を自分で実装するの大変・・・ (@toast-uz)
v0.3.0
- AHCで使いたいです (@NotLeonian)
v1.1.0
- 永続データ構造のライブラリです AHCで欲しくなったことが数回あります (@White-Green)
v0.1.1
-
ac-libraryのRust実装。 (@qryxip)
-
本家ACLへの追従、バグ修正、API改善、ドキュメント整備等色々やるべきだったが、全く手が回らずアップデートを迎えてしまった。 (@qryxip)
これを見ている方は是非手を貸して欲しい... issue作るだけだったりPRに横からapprove出すだけでも十分な助けになる。
-
2021年2月に#89をマージして以降も、破壊的変更も含めて色々変更がある。 (@qryxip)
例えば"crate name"が
ac_libraryになった。後でGitHub ReleasesなりCHANGELOGなりにちゃんと書く。
v1.17.1
-
lazy_staticと同じく、グローバル変数を定義できる。 (@qryxip)
use std::{collections::HashSet, sync::Mutex}; use once_cell::sync::Lazy; static SET: Lazy<Mutex<HashSet<i32>>> = Lazy::new(|| Mutex::new([0, 1, 2].into()));
-
2020年環境で導入されたlazy_staticよりも今はこちらの方が使われているはず。また今標準ライブラリに入りかけている。 (@qryxip)
-
とはいえ今は
Mutexがconst文脈で用意できたりするので、利用する機会は減ってるかもしれない。 (@qryxip)use std::{collections::BTreeSet, sync::Mutex}; // 中身を入れるのは非const文脈じゃないと無理 SET.lock().unwrap().extend([0, 1, 2]); static SET: Mutex<BTreeSet<i32>> = Mutex::new(BTreeSet::new());
v1.1.0
-
型の性質やconst文脈での真偽値を、コンパイル時にassertできる。 (@qryxip)
use static_assertions::{assert_impl_all, const_assert_eq}; // u16はusizeに変換可能である assert_impl_all!(u16: Into<usize>); // 1+1=2である const_assert_eq!(1 + 1, 2);
-
その性質上手元でさえ動けばいいので、AtCoder側に入れなくてもこうすればいいのでは?と思わなくもない。 (@qryxip)
// 手元のコードエディタではエラーがちゃんと出て、かつAtCoder側でcargo buildするときは無視される #[cfg(test)] const _: () = { use static_assertions::{assert_impl_all, const_assert_eq}; // u16はusizeに変換可能である assert_impl_all!(u16: Into<usize>); // 1+1=2である const_assert_eq!(1 + 1, 2); };
v0.2.2
- SATソルバー。 (@qryxip)
- まあ一応提案するだけした方がいいかもしれない? (@qryxip)
v0.3.2
- @tanakh氏製の、競プロ用途に特化したメモ化ライブラリ。 (@qryxip)
- cachedがよくメンテされているようだが、上記のブログの通りAtCoderには向かないかもしれない。 (@qryxip)
v0.2.0
- @tanakh氏製の、競プロ用標準入出力ライブラリ。 (@qryxip)
- 今のRust Analyzerならproconioの補完も十分にできるため、相対的な重要性は下がっている気はする。 (@qryxip)
v1.0.1
-
fixedbitsetやbitset-fixedと比べてGitHubのStarが多く、機能も充実している。(@falrnd)
-
fixedbitsetを置き換えるものではないと思う。bitvecは
Vec<bool>のように振る舞い、fixedbitsetはBTreeSet<usize>のように振る舞う。(@qryxip) -
[bool]/Vec<bool>のように振る舞う型を提供する。 (@qryxip)整数をビット列として挿入することもできる。
use bitvec::prelude::*; let mut bits = bitvec![u8, Msb0;]; bits.extend(0b00010101u8.view_bits::<Lsb0>()); bits.push(true); assert_eq!( bits.into_iter().map(u8::from).collect::<Vec<_>>(), [1, 0, 1, 0, 1, 0, 0, 0, 1], ); // ^^^^^^^^^^^^^^^^^^^^^^ ^ // 0b00010101 true
v0.5.7
-
Pythonの
collections.Counterのようなものを提供する。 (@qryxip)use counter::Counter; let mut counts = Counter::<_>::new(); counts += *b"abbccc"; counts[&b'd'] += 4; assert_eq!(counts[&b'a'], 1); assert_eq!(counts[&b'b'], 2); assert_eq!(counts[&b'c'], 3); assert_eq!(counts[&b'd'], 4); assert_eq!( counts.most_common_ordered(), [(b'd', 4), (b'c', 3), (b'b', 2), (b'a', 1)], );
use counter::Counter; let counts1 = (*b"abc").into_iter().collect::<Counter<_>>(); let counts2 = (*b"cde").into_iter().collect::<Counter<_>>(); assert_eq!( (counts1.clone() + counts2.clone()).into_map(), [(b'a', 1), (b'b', 1), (b'c', 2), (b'd', 1), (b'e', 1)].into(), ); assert_eq!( (counts1 - counts2).into_map(), [(b'a', 1), (b'b', 1)].into(), );
-
2020年の時は
__getitem__/__setitem__にあたる操作ができない、それほど有名ではないという2つの理由で提案から外したが、前者は私が実装し、後者についてはいつの間にかめちゃくちゃ使われるようになっていた。 (@qryxip)
v0.1.11
-
C++の
std::unordered_multisetにあたるものを提供する。 (@qryxip)use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert(b'a'); bag.insert(b'b'); bag.insert(b'b');
-
BTreeMap<T, usize>などで頑張ることもできるが、結構手間であるためコンテスト後によく悲鳴が聞こえた記憶がある。 (@qryxip) -
hashbagと下記のmultimapとbtreemultimapはすべて作者が別。
v4.2.1
-
グラフ関係のアルゴリズムを提供する。 (@qryxip)
#[rustfmt::skip] let maze = [ b"0111111", b"1#1###1", b"1#1#111", b"1#1#1##", b"1#91110", ]; let h = maze.len(); let w = maze[0].len(); let (path, cost) = pathfinding::directed::dijkstra::dijkstra::<(usize, usize), _, _, _, _>( &(0, 0), |&(i, j)| { [(0, -1), (0, 1), (-1, 0), (1, 0)] .into_iter() .map(move |(di, dj)| (i.wrapping_add_signed(di), j.wrapping_add_signed(dj))) .filter(|&(i, j)| i < h && j < w && maze[i][j] != b'#') .map(|(i, j)| ((i, j), usize::from(maze[i][j] - b'0'))) }, |&p| p == (h - 1, w - 1), ) .unwrap(); assert_eq!( path, [ (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6), (2, 5), (2, 4), (3, 4), (4, 4), (4, 5), (4, 6), ], ); assert_eq!(cost, 13);
-
petgraphと比べてAPIが簡略化されており、こちらであればアルゴリズムコンテストでの利用に耐えるのではないか。 (@qryxip)
v2.2.0
-
Rustでは自己再帰するクロージャを書くのに一手間要るが、その一手間をやってくれる。 (@qryxip)
use proconio::input; use recur_fn::RecurFn as _; input! { f0: u32, f1: u32, n: [u32], } let fib = recur_fn::recur_fn(|fib, n| match n { 0 => f0, 1 => f1, n => fib(n - 2) + fib(n - 1), }); let fib = |n| fib.call(n); for n in n { println!("{}", fib(n)); }
-
上記の例を書いているときに気付いたが、rust-analyzerがハングしてしまう。 (@qryxip)
v0.4.1
-
[T]への境界チェックを先に行うことで、「特定の[T]にチェック無しで何度でもアクセスできる添字型/範囲型」を作れる。 (@qryxip)[T]からは[0, n-1]の範囲のindexing::Rangeが取れ、そこから「より小さな」indexing::{Index, Range}が取れる。そこから境界チェック無しのアクセスが何度でもできる。let mut xs = vec![0, 1, 2, 3, 4]; indexing::scope(&mut xs, |xs| { let range = xs.range(); // 境界チェックをスキップしてアクセス for &x in &xs[range] { println!("{x}"); } // 空ではないことをチェック let range = range.nonempty().unwrap(); // そうすると「最初の要素」と「最後の要素」に境界チェック無しでアクセスできる println!("{}", xs[range.first()]); println!("{}", xs[range.last()]); });
// これはコンパイルエラーになる fn f(xs: &[i32], ys: &[i32]) { indexing::scope(xs, |xs| { indexing::scope(ys, |ys| { let index_of_xs = xs.vet(0).unwrap(); let _ = ys[index_of_xs]; }); }); }
-
上記のrecur-fnもそうだが、原理がわかってしまえば手作りできる類のものではある。 (@qryxip)
v3.14.2
- amplify_derive v2.11.3
- amplify_num v0.4.1
-
手書きで書くにはだるいが、ライブラリとして持つほどでも無いようなショートハンドを多数提供する。 (@qryxip)
maplit風のマクロや、
i1024型やu7型とかもある。use std::collections::BTreeMap; use amplify::{ bmap, num::{i1024, u7}, s, }; let _: String = s!("foo"); let _: BTreeMap<i32, i32> = bmap!(0 => 1); let _ = u7::try_from(42).unwrap(); let _ = i1024::from(1) << 1000;
v1.0.1
-
extension trait patternのショートハンドを提供する。 (@qryxip)
use easy_ext::ext; use proconio::input; input! { n: usize, } n.times(|| println!("Yes")); #[ext] impl usize { fn times(self, mut f: impl FnMut()) { for _ in 0..self { f(); } } }
v0.9.0
-
C++の
std::unordered_multimapにあたるものを提供する。 (@qryxip)use multimap::MultiMap; let mut map = MultiMap::new(); map.insert(b'a', 1); map.insert(b'b', 2); map.insert(b'b', 3);
v0.1.1
-
C++の
std::multimapにあたるものを提供する。 (@qryxip)use btreemultimap::BTreeMultiMap; let mut map = BTreeMultiMap::new(); map.insert(b'a', 1); map.insert(b'b', 2); map.insert(b'b', 3);
v1.4.0
-
[u8]/Vec<u8>に文字列操作っぽいメソッドを生やせる。 (@qryxip)use bstr::{ByteSlice as _, ByteVec as _}; let mut s = b"aaabbbccc"[..].to_owned(); assert!(s.contains_str("aaa")); assert!(!s.contains_str("aaaa")); assert_eq!(s.find(b"b"), Some(3)); assert_eq!(s.find_byte(b'b'), Some(3)); assert_eq!(s.find_byteset(b"bB"), Some(3)); assert_eq!(s.find_not_byteset(b"a"), Some(3)); assert_eq!(s.rfind(b"b"), Some(5)); assert_eq!(s.rfind_byte(b'b'), Some(5)); assert_eq!(s.rfind_byteset(b"bB"), Some(5)); assert_eq!(s.rfind_not_byteset(b"c"), Some(5)); assert_eq!(s.trim_end_with(|c| c == 'c'), b"aaabbb"); assert_eq!(s.split_str("bbb").collect::<Vec<_>>(), [b"aaa", b"ccc"]); assert_eq!(s.splitn_str(2, "bbb").collect::<Vec<_>>(), [b"aaa", b"ccc"]); assert_eq!(s.split_once_str("bbb"), Some((&b"aaa"[..], &b"ccc"[..]))); assert_eq!(s.replace("a", "A"), b"AAAbbbccc"); assert_eq!(s.replacen("a", "A", 2), b"AAabbbccc"); assert_eq!(s.to_str().unwrap(), "aaabbbccc"); s.replace_range(3..6, b"B"); assert_eq!(s, b"aaaBccc"); assert_eq!(s.drain_bytes(..3).collect::<Vec<_>>(), b"aaa"); assert_eq!(s, b"Bccc"); assert_eq!(s.into_string().unwrap(), "Bccc");
また
BStrとBStringという[u8]/Vec<u8>のラッパー型も提供している。残念ながらまだFromStrではないためproconioで直接取れたりはしないが、Displayではあるため直接println!できる。use bstr::BString; use proconio::{input, marker::Bytes}; input! { s: Bytes, } let mut s = BString::new(s); s.sort_unstable(); println!("{s}");
-
2020年環境に導入したasciiは使い勝手に難があったが、これなら使いやすいはず。 (@qryxip)
v1.2.1
-
プリミティブ整数型に以下の形の変換メソッドを生やせる。 (@qryxip)
use az::{CheckedAs as _, OverflowingAs as _, SaturatingAs as _, WrappingAs as _}; assert_eq!(1i32.checked_as::<usize>(), Some(1)); assert_eq!((-1i32).checked_as::<usize>(), None); assert_eq!(1i32.overflowing_as::<usize>(), (1, false)); assert_eq!((-1i32).overflowing_as::<usize>(), (usize::MAX, true)); assert_eq!(1i32.saturating_as::<usize>(), 1); assert_eq!((-1i32).saturating_as::<usize>(), 0); assert_eq!(1i32.wrapping_as::<usize>(), 1); assert_eq!((-1i32).wrapping_as::<usize>(), usize::MAX);
-
符号付き整数から
usizeに変換する際、役に立つことがあるはず。 (@qryxip)
v0.1.2
- Glidesort sorting algorithm
-
2023-02-04 の FOSDEM 2023 にて発表されたGlidesortは、マージソート(mergesort)・クイックソート(quicksort)・ブロック挿入ソート(block insertion sort)をハイブリッドした、任意の(全順序(total order)な) std::cmp::Ord 比較演算 をサポートする安定な比較ソート(stable
comparison sort)の実装。 (@mizar)
- Pattern-defeating quicksort (pdqsort) (2015年、pdqsortをもとにした実装は、 Rust 1.20.0 以降の sort_unstable、 Go 1.19 など) の作者による発表。
- 「ほぼソート済みな入力(pre-sorted data)（Timsort型マージソートが得意とする）」「ユニークな値が少ない入力（値の種類が要素数に比べて少ない）(many duplicates, low-cardinality inputs)（Pattern-defeating quicksortが得意とする）」の双方に良く適応する。また、パターンを持つデータに対する卓越した性能を発揮する一方で、ランダムなデータに対しても非常に高速。
-
$n$ 要素・$k$ 種類の入力に対する特性:- 最善ケース計算量:
$n$ - 平均ケース計算量:
$n \log k$ - 最悪ケース計算量:
$n \log n$ ($O(1)$ メモリのみが与えられた場合:$O(n (\log n)^2)$ ) - メモリ:
$n / 8$ 要素 ( 1MB以下の時:$n$ 要素、 1GB以下の時:$n / 2$ 要素 ) - 安定的:
Yes - 決定論的:
Yes
- 最善ケース計算量:
- 使用法:
a.sort()としていた部分をglidesort::sort(&mut a)のように置き換える。sort_byやsort_by_keyを使っていた部分も似たような具合に。 - Benchmark: 2021 Apple M1 にて
u64のさまざまな入力に対する[T]::sortや[T]::sort_unstableとの性能比較 - Visualization: (両ビジュアライゼーションともに、技術の動作を示すため、小さなソートのしきい値と補助的なメモリパラメータは異なる値を使っている)
-
glidesortの高度なマージ技術のデモ:
glidesort_merge_example.mp4
-
glidesortが既存のrun(昇順もしくは降順で連続して並んでいる・並べようとしている区間)と同様に、多くの重複した値に対しても適応的(adaptive)である事を示すデモ:
glidesort_adaptiveness_example.mp4
-
v1.0.1
-
すべてをメソッドチェーンで書きたい人向けのライブラリ。 (@qryxip)
大別して次の3種類の拡張メソッドを提供する。
-
{ let mut x = ..; modify(&mut x); x }のシンタックスシュガーとしてx.tap(modify)やx.tap_mut(modify)など -
f(x)のシンタックスシュガーとして、ML系言語の|>のようなx.pipe(f)など -
Into::<T>::into(x)のシンタックスシュガーとしてx.conv::<T>()など
use std::collections::VecDeque; use tap::prelude::*; let do_sort: bool = ..; let q = [1, 2, 3] .into_iter() .scan(0, |acc, x| Some(*acc.tap_mut(|acc| **acc += x))) // [1, 3, 6] .chain([3]) // [1, 3, 6, 3] .collect::<Vec<_>>() .tap_mut(|q| { if do_sort { q.sort_unstable(); // [1, 3, 3, 6] } }) .tap_dbg(|q| dbg!(q).pipe(drop)) .pipe(rlc) .conv::<VecDeque<_>>(); if do_sort { assert_eq!(q, [(1, 1), (3, 2), (6, 1)]); } else { assert_eq!(q, [(1, 1), (3, 1), (6, 1), (3, 1)]); } fn rlc<T: PartialEq, I: IntoIterator<Item = T>>(items: I) -> Vec<(T, usize)> { .. }
-
-
stdの
{Read, Write, Iterator}::by_refやitertoolsのItertools::batchingもあるし、Rustらしさから外れた発想ではないと思う。 (@qryxip)
v0.1.0
-
Rustの「うわ、swapできない」を解消するパッケージを作った (@qryxip)
Rustでは通称shared XOR mutableと呼ばれる原則があるため、重複しないことを保証できない場所の
&mutを同時に取ることができない。例えば次のコードはコンパイルできない。use std::mem; let mut a: Vec<i32> = ..; let i: usize = ..; let j: usize = ..; mem::swap(&mut a[i], &mut a[j]); // i ≠ j を示せない
error[E0499]: cannot borrow `a` as mutable more than once at a time --> src/main.rs:10:31 | 10 | mem::swap(&mut a[i], &mut a[j]); | --------- - ^ second mutable borrow occurs here | | | | | first mutable borrow occurs here | first borrow later used by call For more information about this error, try `rustc --explain E0499`.
大抵の場合型を提供する側に何とかするためのAPIが用意されていたりはする。この場合stdに
<[_]>::split_at_mutというメソッドが用意されている。assert!(i < j && j < a.len()); let (left, right) = a.split_at_mut(i + 1); mem::swap(&mut left[i], &mut right[j - i - 1]);
<[_]>::swapというメソッドもあるので、直接こう書くこともできる。a.swap(i, j);
しかしコレクションが入れ子になっていたりすると、そのようなAPIは無くなってくる。例えば2次元以上の配列になった時点で直接的にやることは無理になる。
let mut a: Vec<Vec<i32>> = ..; let i: usize = ..; let j: usize = ..; let k: usize = ..; let l: usize = ..; // ??? //mem::swap(&mut a[i][j], &mut a[k][l]);
このクレートが提供する
swap!およびrotate!は、次の条件と引き換えに任意の場所のスワップを行う。- 第一引数の式が2回評価される
- スワップ操作の間、次の値が番兵として第一引数の場所に入る
use std::collections::HashMap; use omniswap::swap; let mut map = HashMap::from([(0, vec![10, 20, 30]), (1, vec![40, 50, 60])]); swap!( &mut map.get_mut(&0).unwrap()[0], &mut map.get_mut(&1).unwrap()[0], ); assert_eq!( map, HashMap::from([(0, vec![40, 20, 30]), (1, vec![10, 50, 60])]), );
use omniswap::rotate; let mut a = [1, 0, 2, 0, 3]; rotate!(&mut a[0], &mut a[2], &mut a[4]); assert_eq!(a, [3, 0, 1, 0, 2]);
v0.7.1
- Function multiversioning attribute macros for Rust.
- AtCoder Jan 2023 環境では インストール時とそれ以外(提出時のコンパイル・実行)では同一マシンという保証ができない 件に対して、（インストール時にライブラリのコンパイルを行っているので）ジャッジ環境のビルドオプションから
-Ctarget-cpu=nativeを削除した代わりに導入。 (@mizar)
v0.2.1 → v0.4.0
- num-bigint v0.2.6 -> v0.4.3
- num-complex v0.2.4 -> v0.4.3
- num-integer v0.1.42 -> v0.1.45
- num-iter v0.1.40 -> v0.1.43
- num-rational v0.2.4 -> v0.4.1
- num-traits v0.2.11 -> v0.2.15
- なんだかんだでみんな使っていた印象。(@qryxip)
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.13.0 → v0.15.6
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.20.0 → v0.32.2
- alga v0.9.3 → v0.9.3
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.2.1 → v0.2.6
v0.7.3 → v0.8.5
- getrandom v0.1.14 → v0.2.9
- rand_chacha v0.2.2 → v0.3.1
- rand_core v0.5.1 → v0.6.4
- rand_hc v0.2.0 → v0.3.1
- rand_pcg v0.2.1 → v0.3.1
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.2.2 → 0.4.3
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.5.0 → v0.6.3
- 色々機能が追加されたと思うが未調査。(@qryxip)
v1.3.2 → v1.9.3
v1.3.6 → v1.7.3
v1.4.0 → v1.4.0
v1.0.2 → v3.6.0
- 色々機能が追加されたと思うが未調査。(@qryxip)
v1.0.0 → v1.1.0
- 個人的には使い道が見出せなかったが、そこそこ使われていた印象。(@qryxip)
v0.2.4 → v0.2.4
v1.0.0 → v1.0.0
v0.9.0 → v0.10.5
- 使い道は多分結構多い。使っていた人も多いのではないか。(@qryxip)
- 色々機能が追加されたと思うが未調査。(@qryxip)
v0.1.3 → v0.1.3
- 使っていた人はいるのか。(@qryxip)
v1.0.2 → v1.0.2
- 今のRustだと
HashSet::from([1, 2, 3])のように書けるとはいえ、maplitの書き方に慣れている人も多いのではないか。(@qryxip)
v1.5.3 → v1.8.1
- itertoolsがこれを返すことがあるので、それで使っていた人もいるのではないか。(@qryxip)
v14.3.0 → v15.1.0
- なんか遅いらしいし、実用していた人はいるのか。(@qryxip)
v0.2.0 → v0.4.2
- まあまあ手軽に使えたはずだし、使っていた人もいたかも。(@qryxip)
v0.1.0 → v0.1.0
v0.3.6 → v0.4.3
- RustでAtCoderに参加している人にとっては、言わずと知れたライブラリ。 (@qryxip)
- v0.3からの変更として致命的なバグの修正と、APIの追加がある(後で書く)。 (@qryxip)
v0.1.8 → v0.1.12
-
The MIT non-military non-spy Licenseというライセンスだったのが純粋な
MIT OR Apache-2.0に変わった。 (@qryxip) - その他の変更点は特に無いはず。
read!時にstdoutをflushするようになったことくらい?(text_ioでやるべきことか?という気もする) (@qryxip)
v0.5.0 → v0.5.0 削除
- つい最近気付いたが、ライセンスは
MITといいつつThe MIT non-military non-spy License。罠でしょこれは (@qryxip)
v1.1.0 → v1.1.0
v1.2.0 → v1.10.0