Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

Rustで競プロするなら正の整数はusizeで扱うのが一番いいと思う理由

Rustにはプリミティブ型について、暗黙の型変換がありません。これは、競プロをする上ではとても不便です。例えば、整数型がboolに暗黙変換された方が、ビットDPなどでは特に、書きやすくなるでしょう。

ビットが立っているか調べるために、例えば、

if s & (1<<j) > 0

のように書く必要があります。これは私の場合、== 1と書いてしまう間違いを犯すことが時々あります。

もう1つ不便なのが、配列のインデックスとして使えるのがusizeだけだということです。

これがもたらす災難1は、インデックスの値を一時的に負値にしたい場合など(-1から始めたいけど必ず計算途中で正になる場合とか。例えば二分探索とか)にいちいち型変換を書く必要があるということです。

災難2は、正の整数型u32やu64などを使った場合でも、やはりその値をインデックスとして使いたい場合はusizeに変換する必要があるということです。これは例えば、与えれた配列の要素を数え上げたい場合などに不便です。インデックスに値そのものを使うからです。

C++では、常にintを使うことが出来ますから、少なくとも競プロでは有利です。Rustは実際にソフトウェア開発をするとなれば力を発揮しますが、競プロでは少し制約がきつすぎる気がします。

そこで私は、もうめんどくさいので正の整数値ならば常にusizeでとるようにしています。負値をとる場合は、今はi64で決め打ってます。

なぜこれで問題がないか説明します。

特に、u64を使う理由というのは、32ビット環境においてusizeが32ビットになってしまうから、64ビットを使うのであればu64を使うしかないという場合のためです。しかし実際には、競プロで仮に64ビットの値を使う場合、そのシステムが32ビットであることはたぶんないでしょう。というか今日日、32ビットのシステムを使う理由が存在しませんし、サービスの運用のためにクラウド仮想マシンなどを使うのであれば64ビットしか選択肢はないでしょう。

また、メモリ使用量についても、そもそも言語によっては32ビットを明確に指定することが出来ない場合があるのだから、32ビットを使わないとMLEするというケースは存在しません。

整数型の基準はi32型です: 64ビットシステム上でも、 この型が普通最速になります。isizeとusizeを使う主な状況は、何らかのコレクションにアクセスすることです。

とドキュメントに書いてあるとおり、usizeを使うことで遅くなる場合もあるでしょうが、Rustは十分に速いのでこれが原因でTLEするというのはまずあり得ません。

というわけで、正の整数型をusizeにしてしまって競プロにおいては問題がなく、意味不明な型変換が不要になるメリットしかないと考えて、常にusizeでとるようにしています。