Rust入門を兼ねてプロジェクト・オイラーの問題を解く

とりあえず問100まで解くことに決めて始めたのだけど、問題の難易度やプログラムを書く面倒さが速いペースで増加していくので割と早い段階で問題を解くことが優先になって、Rustの機能やライブラリを理解することがおざなりになってしまった。
それでも言語の初歩的な部分についてはそれなりにRustの感覚が得られた気がする。

1. 整数とベクター

大部分の問題は、整数、整数のベクター、整数のベクターベクター等々だけを使って解ける。
そのため、プログラムを書くときに所有権などのせいで書き方に困ることはあっても、そうした所有権とか生存期間とかの規則が問題を解く上で本質的な障害になることはそんなに無い。

  • 「gotoしかない言語でプログラムを書いていた人がforやwhileだけでプログラムを書く」とか「破壊的変更が普通の言語を使っていた人がデータは基本的に不変な言語を使う」ような感じかも。
  • ベクターすら使う必要がなく整数を扱うだけで済む問題では、型の規則(不変可変、型の変換)にちょっとうるさいだけの普通の言語と思ってプログラムが書ける。

逆に、プロジェクト・オイラーの問題に取り組んでも、所有権や生存期間のことをよく考えないといけない場合についての理解はあまり深まらないとも言える。

よく使ったベクターの関数
  1. push
    • ベクターをあらかじめ大きなサイズを確保することはあまりなくてだんだん要素を追加していくことが多かったので、ベクターを使うときはだいたいpushを使っていた。
  2. sort
    • 重複するものを取り除く/重複しているかどうかの判定(dedupを併用)。
    • ソートしたもの同士に対して同値性を比較する。
    • 使わなくても済む場合(もっと計算が少なくて済む方法がある場合、ソートせずに操作しても結果は変わらない場合など)でも割と気にせず使っている。
    • sort_by、sort_by_keyはあまり使っていなかった。
  3. iter
    • はじめのうちはあまりイテレーターを使わなかった(イテレーターの関数をあまり知らなかった)ので、途中からはsortよりも頻繁に使っている。
  4. pop
    • pushと比較すると使用する機会はだいぶ少ない。
  5. dedup
    • だいたい「sortしたあとdedupして重複を消す」という使い方。
      • 「各桁がすべて異なるか」みたいな条件の判定にも。
      • きちんと判定すれば同じ計算を繰り返すのを避けられる場合でも、判定をサボって最後にsort + dedupで重複を消すみたいな使い方も。
  6. その他 (このあたりは、よく使ったというほとではない)
    • remove、insert
      • 組み合わせなどを列挙、探索するときにremove、insertを組みで使っていることが多かった。
    • append、reverse
      • 時々使っていたけど、ベクターでなくリストだったらもっと多用していたと思われる。
    • swap_remove
      • 使う機会はほとんどなかったけど、cloneできないデータのベクターを使う機会が多かったら結構使っていそう。
    • binary_search

2. イテレータ

ベクターへの操作をイテレーターの組み合わせて簡潔に書ける場合もある一方で、型や所有権に関するエラーが出て想定するように書けない場合もある。

  • たいていは型や所有権やライブラリ関数に対する理解不足が原因なので、動くように書き直していくことで型や所有権などへの理解が深まる。
  • エラーが消えないとかでどうにも困ったら(あるいは単に面倒になった場合も)添字でのアクセスに切り替えればよい。
    • もともとプロジェクトオイラーの問題の傾向からしても、添字経由でベクターを操作する方が自然な書き方になる場合も多いので、イテレーターに無理に固執しなくても良い。
    • 添字でのアクセスの方が所有権とか借用とかをあまり気にせず気楽に書ける。
よく使ったイテレーターの関数
  1. rev
    • forループで添字を降順で使いたい場合での使用が多い。
  2. step_by
    • ほとんど「step_by(2)」の形で使っていた。
  3. map
    • イテレーターの連鎖が分かりにくい感じになってmapを使うのをやめたことが何度かあった割には結構使っていた。
  4. collect
    • はじめのうちは結果を受け取る変数の型を指定して「let v: Vec<_> = 〜.collect()」みたいな書き方が多くて、だんだん「〜.collect::<Vec<_>>()」「〜.collect::<String>()」みたいに書くことが多くなっていた。どちらが見やすいのかはよく分からない。
  5. fold
    • ベクターの要素の和を取る」というのが一番多い使い方だった。sumがあるのに気づいてから使用する機会が減った。
  6. zip
    • zipをうまく使うと簡潔に書けることがある一方で、イテレーターの連鎖と参照がいろいろからんで分かりにくくなることも多い、という印象。
    • rev(だったと思う)と組み合わせて使おうとしたときに型エラーをなくすのにしばらくかかった。
  7. enumerate
    • enumerateを使って書けそうな場合でも、単に添字に対してforループを回して添字でアクセスする書き方をすることが多かったように思う。
  8. sum
    • はじめのうちsumの存在に気が付かなかったので、初めから使っていたらもっと使っていたと思われる。sumの積バージョンproductは使える機会はあったはずだけど一度も使っていなかった。
  9. max、min、max_by_key、min_by_key
    • これも途中まで存在に気付かず、使える機会に使っていなかった。
  10. その他 (よく使ったというほとではない)
    • chain、find、all、any、peekable、cycleなどは別に使わなくてもいいなと思いながら使った気がする。

3. 標準ライブラリに無いもの

多倍長整数

多倍長整数(bignum)は標準には入っていないので、大きな数を扱わないといけない問題では何とかする必要がある。

  • 多倍長整数が必要になるのは問100までのうち10問程度。(あと、64ビット整数だとオーバーフローするけど128ビット整数にするとオーバーフローしない問題が何問かあった。)
  • 多倍長整数が要る問題のほとんどは、多倍長整数に対する足し算と掛け算の組み合わせで解ける。実装の効率を気にする必要も特にない。
  • 多倍長整数の割り算まで必要な問題が1問あったけど、2で割る場合だけ実装するだけでも問題は解ける。(いくらか効率の悪い計算をすることになるけど。)
  • crates.ioにいくつか多倍長整数ライブラリが登録されているようなので、それを使った方が手っ取り早かったかも。
乱数

問100までのなかに、乱数が必要(乱数なしでも解けるけどたぶん行列計算が面倒)な問題が1問あるけど、乱数関数が標準では入っていない。

  • xorshiftは実装する手間があまりかからない。
  • crates.ioに乱数ライブラリがある。

4. テスト

Rustはコンパイル時に型のエラーをたくさん出すため、単純な間違いが早い段階で見つかる場合も多い。
一方で型エラーでは防げない単純ミスもたくさん存在する。数値や式の書き間違い、問題や仕様の捉え間違い、0番目から数えるか1番めから数えるかの間違い、「≦」と「<」との間違い、真偽の扱いを逆にする、等々。
型システムで防げるミスをたくさん入れるような人間は型システムで防げないミスもたくさん引き起こすから結局テストが必要になる。

テストは近くに書けば書くほど書く心理的ハードルが下がる

Rustではテスト用のクラスやモジュールを定義せずにテストを書くことができる。テストを別ファイルに分けることもスタイルとして強制されない。

このとき、テストしたい関数の直下や直上にテストを書くようにすると気分的に非常に気軽にテストが書ける。テストを書こうとしたときにまず別クラス別ファイル別ディレクトリを作るみたいな余分なステップが必要ない。(別モジュール、別ファイルを作るにしても必要になってから分ければいい。)

また新しく書かれたばかりの関数やプライベートな関数は、関数名や引数や動作が頻繁に変わったり関数自体がなくなったり分解されたり統合されたりすることが多いけど、そうした変更にテストコードを追従させるのも、テストコードがテストされるコードのすぐ近くの方が楽にできる。要らなくなったテストの破棄も気楽にできる。
テストのメンテナンスコストが大きいからテストを書かない、みたいなことを避けられる。

Rustではテスト中の出力はデフォルトではキャプチャされるけど--nocaptureオプションをつけると出力されるから、出力を見て動作確認する(REPLで確認したりprintを埋め込んで確認する)ようなコードをまずテスト関数内に書いてテスト実行して確認して、次にそれをテストコードの形に直すということもできる。最初からテストの形で書いた方が楽な場合も多いけど。
また失敗しているテストの詳細を出力させてコードを直すなど、テストするコード/されるコードの連携がやりやすいという印象。

プライベートな関数に対するテストとパブリックな関数に対するテスト

プライベートな関数(メソッド)に対するテストを書けない(書く手間のかかる)言語やテスティングフレームワークと異なり、Rustではプライベートに対して何の手間もなくテストが書ける。

  • プライベートな関数の方が一般的に変更が激しいからそれに合わせてテストの変更も楽におこないたいのに、多くの言語のテスティングフレームワークではプライベートに対するテストを書くのが難しかったり抜け道的な手法を取る必要があって、テストを書くコストがむやみに高くなる。
  • テストコードが同じモジュール(または内部モジュール)に置かれるので、外部モジュール(外部クラス、外部ファイル)からプライベートな要素を覗いてテストしているという気持ち悪さ(モジュールシステムの意図・制約に逆らっている)を感じなくてよい。
    • 概念的にはプライベートに対するテストは外部コードではなく内部コードの一部として見るべきなのだろう。
    • 一方、パブリックなものになっていくほど外部から見た振る舞いや引数などが固定される傾向があり、それに合わせてテストも安定化し、公開されている振る舞いや契約を確認するものになりやすい。こうしてだんだん外部コード的なテストが増えていくことになる。(もちろん内部コード的なテストと外部コード的なテストをきっちり区別できるわけではなく、パブリックな関数であっても複雑なアルゴリズムを使っていたりすると振る舞いより内部ロジックの正しさをテストしたい場合もあるだろう。)
プロジェクト・オイラーでのテスト

もちろんプログラム一般と同じようにテストすればよいけど。

プロジェクト・オイラーでは、問題の中で小さい値での答えが与えられている場合がよくある。
例えば問1は(要約すると)「10未満の時の合計は23になる。では1000未満の時は?」と聞いていて、問4は「2桁の数を使った場合は9009が最大になる。では3桁では?」と聞いている。
こういう問題に対しては、問題文で答えが提示されている値に対して正しく答えているかどうかをテストにすることができる。問1なら解答を出す関数が引数10に対して23を返すかをテストする。
こうしたテストがパスしたからといって解答が正しいことは保証されないけど、いくらかの安心は得られる。
ただしこのテストが使えるのは、一般のnに対するプログラムを書ける場合に限る。例えば問4の場合、2桁と3桁のどちらの場合も解くプログラムを書くのは面倒なので、このテストは適用しにくい。

また問題文の中で数列や式などの値が具体的に例示されていることも多い。
問2ではフィボナッチ数列の初めの部分「1,2,3,5,8,13,21,34,55,89、…」が示され、問12では三角数「1,3,6,10,15,21,28,36,45,55,…」が示されている。(こうした例示がされているのは、問題の曖昧さを避ける意図もあるのだと思う。例えば数列の初項を何にするかとか0番から数えるか1番から数えるかなどの違いで答えが違った値になってしまう。問12では三角数の第7項目は28だと書くことで曖昧さを消している。)
こうした例示されている値をそのままテストに流用できる。もちろん自分で計算してテストを作ればいいのだけど、こうしたテストの正解(期待される値)の計算で間違えることもよくある。問題文に出ている値をそのまま使う方がいくらか信頼度があがる。

簡単な数式でも思った以上に何度となく入力ミスしていた(そしてだいたい型エラーはでない)けど、こうしたテストでよくミスが見つかった。
また間違えようがないからとこうしたテストを書くのをサボると、だいたいあとでもっと手間がかかることになった。プログラムのサイズが大きくないからそんなにひどいことにはならなかったけど。