LoginSignup
24
14

More than 1 year has passed since last update.

@hossie(ほっしー)

Rust 1.43～1.67 の競プロ的に気になる変更点

Posted at

はじめに

競技プログラミング国内最大手の AtCoder で、今年に 3年ぶりの言語アップデートが予定されています。採点環境で使える言語が新しくなります。

Rust は 1.42 から 1.67 以降になるかもしれません 1。この更新を期待して、私が競プロで使いたくなる Rust の新しい機能をまとめてみました。

本記事は、手元で Rust 最新を使っている方が、採点環境でビルドエラーにならないような注意点としても使えると思います。

扱うこと、扱わないこと

  • 想定読者
    • Rust で AtCoder などの競技プログラミングに参加している方
    • 浅く広く、競技プログラミングで使いそうな Rust の言語機能を知りたい方
  • 扱うこと
    • Rust 1.43～1.67 で追加された標準機能、標準ライブラリーのうち、競技プログラミング本番中に役立ちそうな機能
  • 扱わないこと
    • Rust 1.43～1.67 で追加された標準機能、標準ライブラリーのうち、競技プログラミング本番中には使わなさそうな機能
      • Rust の機能ピックアップとしては、わりと偏っていると思います
    • AtCoder でそのまま使える、標準ライブラリー以外の更新
      • petgraph で新しいアルゴリズムが使える、など
    • AtCoder で atcoder-library-rs がそのまま使えるようになるかも 2

情報元の紹介

新機能 / 全般

実行時エラーが分かりやすくなった (1.47)

100 行ほどのプログラムを動かしているときに実行時エラーを見ると、頭を抱えたくなります。たとえば以下の場合、標準ライブラリー mod.rs 内のどこかで範囲外アクセスが起きている、としか分かりません。

Rust 1.42
thread 'main' panicked at 'index out of bounds: the len is 20 but the index is 20', /rustc/b8cedc00407a4c56a3bda1ed605c6fc166655447\src\libcore\slice\mod.rs:2797:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

この通り環境変数 RUST_BACKTRACE を立てれば分かります。しかし今度はエラーメッセージが長すぎて、読むのが大変です。 3

Rust 1.47 では、標準ライブラリーの呼び出し元の行番号が表示されます。実装ミスがどこにあるか、分かりやすくなります。

Rust 1.47
thread 'main' panicked at 'index out of bounds: the len is 20 but the index is 20', src/bin/c20.rs:79:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

let-else (1.65)

let-else.rs
let a = [Some(1), None];

// 1.42
for &x in &a {
    if let Some(x) = x {
        assert_eq!(x, 1);
    }
}

for &x in &a {
    let x = match x {
        Some(x) => x,
        _ => continue
    };
    assert_eq!(x, 1);
}

// 1.65
for &x in &a {
    let Some(x) = x else { continue; };
    assert_eq!(x, 1);
}

if let は中に値が入っているかどうかの確認に便利な構文です。しかし、インデントが増えるという難点がありました。 4

match を使えばインデントを増やさずに済みます。しかし行数は増えます。中に入っている値を取り出したいという目的に対して、重いコードという感じがします。

Rust 1.65 ではその場で else { continue; } や else { return; } として抜けられるようになりました。地味に便利です。

分割代入 (1.59)

let.rs
// 1.42
let (a, b) = (1, 2);
let [c, ..] = [3, 4, 5];
assert_eq!((a, b, c), (1, 2, 3));

// 1.59
let (a, b, c);
(a, b) = (1, 2);
[c, ..] = [3, 4, 5];
assert_eq!((a, b, c), (1, 2, 3));

ループ内で一時変数を多数使うときなどに、let の数が減ると少し読みやすくなりそうです。

フォーマット文字列に変数を直接書ける (1.58)

format.rs
let yes = true;
let result = if yes { "Yes" } else { "No" };

// 1.42
println!("{}", result);

// 1.58
println!("{result}");

フォーマット文字列に変数名を書くことはできます。

数式を埋め込むことはできません。

新機能 / 数値系

Rust で競技プログラミングするときは、 usize との戦いが主になってきます。

配列のインデックスに i64 を直接渡せません。usize と i64 の世界をキャストで行き来するのは手間がかかります。非負整数で済むものはできるだけ usize の世界で扱いたいです。しかし途中計算式で負数が現れると panic するところが困ります。

Rust 1.43 以降で非負整数のまま扱いやすくなる API が増えています。

usize::abs_diff 差の絶対値 (1.60)

usize 同士の差の絶対値を得たいとき、絶対値は非負整数ですが、途中計算式が負の値になります。 usize のままだと panic しかねませんので、 i64 の世界で扱う必要がありました。

usize::abs_diff を使うと、非負整数のまま自然に書けます。

abs_diff.rs
// 1.42
let (x0, x1, y0, y1) = (3_i64, 1_i64, 4_i64, 1_i64);
let dist = (x1 - x0).abs() + (y1 - y0).abs();
assert_eq!(dist, 5);

// 1.60
let (x0, x1, y0, y1) = (3_usize, 1_usize, 4_usize, 1_usize);
let dist = x1.abs_diff(x0) + y1.abs_diff(y0); 
assert_eq!(dist, 5);

ARC 089-A。atcoder-rust-base を使って AtCoder に参加している方は初期テンプレートとしてよく見ているかもしれません。こちらを usize 中心で書けるようになります。

usize::wrapping_add_signed 余りを考慮して i64 と足し算 (1.66)

usize で座標を扱うことが、競技プログラミングではよくあります。0 以上の範囲で +1, -1 両隣に動く、などです。

+1, -1 は正負両方ありますから i64 で扱いたいです。 usize と i64 は型が異なります。この扱いが面倒でした。 !0 を -1 のつもりで使うテクニカルな方法もアリですが、あまり読みやすくないです。 5

usize::wrapping_add_signed 型の範囲をはみ出すと折り返す足し算が、Rust 1.66 で増えました。折り返す動作ですが、折り返さなければシンプルに usize に直接 i64 を足す方法として使えます。

wrapping_add_signed.rs
// 1.42
let mut x = 1_usize;
let dx = [1, -1];
x = ((x as i64) + dx[1]) as usize;
assert_eq!(x, 0);

let mut x = 1_usize;
let dx = [1, !0]; // !0 == 0xFFFF_FFFF_FFFF_FFFF == usize::MAX
x = x.wrapping_add(dx[1]); // 1 + !0 == 1 - 1 = 0
assert_eq!(x, 0);

// 1.66
let mut x = 1_usize;
let dx = [1, -1];
x = x.wrapping_add_signed(dx[1]); // 1 - 1 = 0
assert_eq!(x, 0);

usize::MAX など (1.43)

usize::MAX などで、その型の最大値を得られます。 DP の初期値に大きな値を入れるときなどに。

従来の std::usize::MAX は非推奨になっています。

max.rs
let n = 10;

// 1.42
let mut _v = vec![std::usize::MAX; n];
let mut _v = vec![!0_usize; n]; // !0 == 0xFFFF_FFFF_FFFF_FFFF == usize::MAX

// 1.43
let mut _v = vec![usize::MAX; n];

f64::total_cmp 浮動小数点の全順序比較 (1.62)

Rust では浮動小数点が全順序ではありません。ソートするときにひと手間かかっていました。 比較関数 total_cmp() を使うことで、このソートが少し行いやすくなりました。

total_cmp.rs
// 1.42
let mut a = [0.5, 1.0, 0.25];
a.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(a, [0.25, 0.5, 1.0]);

// 1.62
let mut a = [0.5, 1.0, 0.25];
a.sort_by(f64::total_cmp);
assert_eq!(a, [0.25, 0.5, 1.0]);

浮動小数点が全順序 Ord になったわけではありません。 sort() をそのまま呼ぶことや、全順序を期待している BTreeSet, BinaryHeap などに値を入れることはできません。

usize::ilog2 整数の log2 (1.67)

ilog2.rs
let x = 0b10101010_usize;

// 1.42
let l = (x as f64).log2().floor() as usize;
assert_eq!(l, 7);

// 1.67
let l = x.ilog2();
assert_eq!(l, 7);

整数をビット表現したときの桁数を、実数を経由せずに計算できます。競プロ典型 90 問で使いたくなったことがあります。

usize::clamp 範囲内の値にする (1.50)

clamp.rs
// 1.42
let f = |x: usize| x.max(2).min(4);
let v: Vec<usize> = (1..=5).map(f).collect();
assert_eq!(v, [2, 2, 3, 4, 4]);

// 1.50
let f = |x: usize| x.clamp(2, 4);
let v: Vec<usize> = (1..=5).map(f).collect();
assert_eq!(v, [2, 2, 3, 4, 4]);

2 から 4 の範囲内に値を寄せたいとき、 x.max(2).min(4) のような定型句を使えます。しかしこの書き方は、大小どちらの数字を min, max どちらに入れるか迷いそうになります。

x.clamp(2, 4) は分かりやすいです。

新機能 / イテレータ系

iter::reduce (1.51)

reduce.rs
// 1.42
let folded = (1..=5).fold(1, |acc, e| acc * e); // 1 * 1*2*3*4*5 = 120
assert_eq!(folded, 120);

// 1.51
let reduced = (1..=5).reduce(|acc, e| acc * e).unwrap(); // 1*2*3*4*5 = 120
assert_eq!(reduced, 120);

畳み込み演算で reduce() が使えるようになりました。 fold() と違い初期値不要です。

配列に対する IntoIterator (1.53)

into_iterator.rs
let a = [3, 1, 4];

// 1.42
for &i in &a {
    let _: usize = i;
}

// 1.53
for i in a {
    let _: usize = i;
}

こちら以外にも、 Vec でできることが配列でも同様にできるようになってきている印象です。

新機能 / コレクション系

BTreeSet::from など (1.56)

set, map の初期構築が簡単になりました。

from.rs
// 1.42
use maplit::btreeset;
let mut set = btreeset!(3, 1, 4); // {1, 3, 4}

let mut set = BTreeSet::new();
set.insert(3);
set.insert(1);
set.insert(4); // {1, 3, 4}

let mut set: BTreeSet<usize> = vec![3, 1, 4].into_iter().collect(); // {1, 3, 4}

// 1.56
let set = BTreeSet::from([3, 1, 4]); // {1, 3, 4}

let set: BTreeSet<_> = [3, 1, 4].into(); // {1, 3, 4}

maplit を使う機会が減りそうです。

BTreeSet::fisrt, BTreeSet::pop_last など (1.66)

BTreeSet, BTreeMap の first, last 関連の API がいろいろ増えました。 iter を経由しなくても直接呼び出せるようになりました。

first.rs
let set = BTreeSet::from([3, 1, 4]);

// 1.42
assert_eq!(set.iter().next().unwrap(), &1);
assert_eq!(set.iter().last().unwrap(), &4);

// 1.66
assert_eq!(set.first().unwrap(), &1);
assert_eq!(set.last().unwrap(), &4);

幅優先探索など、優先度付きキュー BinaryHeap を使いたくなることがあります。 BinaryHeap は値の大きなものを優先的に返します。先に小さな値を欲しいときには Reverse() でくくるなどの工夫が必要でした。 6

BTreeSet でも pop_first() を使うと、BinaryHeap と同じようなことができるようになりました。少し短く書けます。

pop_first.rs
// 1.42
let mut heap = BinaryHeap::new();
heap.push(Reverse(3));
heap.push(Reverse(1));
heap.push(Reverse(4));
while let Some(Reverse(x)) = heap.pop() {
    println!("{}", x); // 1, 3, 4
}

// 1.66
let mut set = BTreeSet::from([3, 1, 4]);
while let Some(x) = set.pop_first() {
    println!("{}", x); // 1, 3, 4
}

最後に

ほかにも Range 系など気になるものがありますが、このあたりで。

楽しみな機能が多いです。AtCoder 言語アップデートに期待です。

  1. 本記事を書いている時点での Rust 最新は 2023-03-09 にリリースされた 1.68 です。AtCoder の言語更新初回アンケートは 2023-02 で、この時点の最新 1.67 の希望が出ていました。 ↩

  2. rust-lang-ja/ac-library-rs: ac-library-rs is a rust port of AtCoder Library (ACL). 便利です。しかしいまのところコードを組み込むのに Python を動かしてコードをコピペするというひと手間がかかります。 modint や segtree が標準ライブラリーのようにそのまま採点環境で使えるようになると、文字通り環境が変わりそうです。 ↩

  3. cargo compete test では、メッセージが長すぎるとテキスト表示が省略されます。そのため、 RUST_BACKTRACE=1 を立てるとかえって何も読めなくなることもあります。その場合は代わりに、ビルド済みのバイナリを実行してトレースログを表示する、デバッグ実行で追うなどと、さらに手間がかかることになります。 ↩

  4. ところで競技プログラミングでは、 if let Some(x) = x がもし常に成功するはずなら、代わりに let x = x.unwrap() と書くのもアリです。 想定外の値が入っていた時の panic は避けたいものですけれど、panic を避けられたとしてもどうせ誤答になるのでしたら。Wrong Answer より、panic による Runtime Error の方が不具合を追いやすいと思います。 ↩

  5. ac-library-rs/fenwicktree.rs at master · rust-lang-ja/ac-library-rs フェニック木 (Binary Indexed Tree, BIT) の実装で idx += idx & idx.wrapping_neg(); とあるのを見て、私は usize の wrapping シリーズを知りました。や、負がありなら idx += idx & !idx; で済むところなのに、非負整数の世界で頑張ろうとするとこのように長くなります。競プロ的にはつらいところです。手間と安全性のどちらを取るかという話で、仕方のないところなのですけれど。 ↩

  6. 数値の大小関係を手っ取り早く入れ替えるなら -x のように負にして詰めれば良いです。でも非負整数 usize では扱えません。i64 にしたとしても利用時に -x として正の値に戻すのを忘れてしまいかねません。 Reverse() すると型が変わりますので誤用の心配がなく嬉しいです。ちょっとコードが長くなるだけが難点。 ↩

24
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
24
14