Zenn
🦁

the art of readable code

に公開
readablecode
idea

良いコードとは理解しやすいコードである

リーダブルコードの要点を纏めました
クイックリファレンスの要領で使おうと思って作りました

表層レベルの改善

名前に具体的な情報を

曖昧で抽象的な名前を避けて，わかりやすい命名をするための６つのアイデア

  1. より直接的な単語を選ぶ
  2. 一般的・総称的な名前は使わない
  3. 抽象的な名前より具体的な名前をつける
  4. 追加の情報は先頭が最後に付け加える形で
  5. 名前の適切な長さを決めておく
  6. 名前を整形する

1. より直接的な単語を選ぶ

get, sizeなどの曖昧な単語は，ほとんど情報を含んでいない．状況に応じてget -> fetch, download
size -> height, bytes などと，より直接的な表現・単語を選ぶ

[!tip]
より直接的な単語が思い浮かばなくても，辞書などで調べれば色々な類語が出てくる 使わない手はない

2. 一般的・総称的な名前は使わない

一般的・総称的な名前はその値が果たす役割について何も言及しない
tmp, rsltなどでメタ視点での役割を説明しても，そもそもコードを見れば明らかであることが多い
良い名前は，その値・変数の具体的な目的を表している

[!note]
名前が目的を端的に表現できていれば，その目的に沿わない処理に気づきやすくなる
結果的にバグを未然に減らす事につながる

但し，tmp, rsltなどの総称的に見える名前が具体的な目的を表している場合もある
そのような場合は勿論好ましい名前となる

3. 抽象的な名前より具体的な名前をつける

実際の動作を，抽象化せずに名前に含める

4. 追加の情報は先頭が最後に付け加える形で

例えばidという変数のフォーマットが16進数ならばhex_idと付け加えよう
変数が時間やバイト数など何かの測定値ならば，その単位を追加しておくと良い start_ms, x_bits, y_bytesなど
単位以外にも何かその変数の使用・仕様にdiagnosticsがあるのなら，常にそれを名前に含めるべきだ
例えば

よくある名前 diagnostics より良い名前
password 変数に含まれているパスワードは普通のテキスト形式</br>暗号化が必要 plaintext_password
comment ユーザーが入力したコメントで，他の情報とは違い画面には出力されない</br>出力されないようにする処理が必要 unescaped_comment
html utf-8形式に変換されたhtmlコード html _utf8
data エンコードされたURLである data _urlenc

5. 名前の適切な長さを決めておく

名前は無駄に長いよりは短い方がわかりやすい 一方で短すぎると必要な情報を表現仕切れない
名前の長さが適切であるかは状況によるが，その判断をする際に以下を参考にすると良い

  1. スコープが短い場合は極端な省略も害ではないことが多い
  2. 略語は良いが，プロジェクト特有の造語はよろしくない
  3. 不必要な単語を除く: convert_to_string -> to_stringなど

6. 名前を整形する

その変数の属性ごとに名前のフォーマット(CamelCase とか)を使い分ける

誤解されない名前

[!example]
ex.1 filter()
以下のコードを見てみよう

hoge = birthdays.filter("year <= 2024")

hogeはどっちの人たち？

  1. 2024年より前に産まれた人たち
  2. 2024年以降に産まれた人たち

1番を意味するのであればselectなど,2番を意味するのであればexcludeなどに改名すべき

[!example]
ex.2 clip(text, length)
以下のコードを見てみよう

// この関数はtextを後ろから切り取ります
fn clip(text, length)

clip()の挙動は？

  1. lengthの分だけ末尾から取り除く
  2. textの長さがlengthになるように切り取る

2番を意味するなら関数名はturncateの方が適切
又，引数の名前もlengthよりmax_charsなどにした方が良い

このように，より詳細に・具体的に性質を説明している名前は誤解を生みにくい
誤解を生みにくい名前をつける際に気をつけると良い点を記しておく

[!note] minやmaxを使う
何かの上限，下限を表すならばmin, maxを積極的に使おう

[!note] first, last/begin, end
終端が含まれる場合はfirst, last
そうでない場合はbegin, end

[!note] 真偽値の名付けの注意点
一体何が真で何が偽なのか明確にする

[!note] イメージを合わせる
get()を例にとってみよう
OOPにおいてgetは単純に内部のメンバーの値を返すメソッドとしてよく定義されている
この時，getXXX()というネーミングで，重い処理をする関数があったとする
するとこの関数を見た人は，実際の処理とは裏腹に，getXXX()を気軽に呼び出してしまう
この場合，例えばcomputeXXX()とすると，実際の処理と名前から浮かぶイメージがより一致する

[!example]
C++の標準ライブラリにはlist::size()という関数がある
この関数を使った以下のコードを考えてみよう

void shrink_list(list<Node>& list, int max_size) {
  while (list.size() > max_size) {
  	free_node(list.back());
  	list.pop_back();
  }
}

C++において，sizeと名前のついた関数一般に O(1) であることが言える
しかし，list::size()のオーダーは O(n) である
つまり，shrink_list()は O(n^2) であり，listがとても大きな場合，急激にパフォーマンスが下がることを意味する
これに気づくのは非常に難しい

このコードは，コンパイラから見たら正しいコードだが，人間からすると，間違ったコードだと言える
size()ではなくcount_size(),count_element()としていればshrink_list()のような間違いは減らせるだろう

名前の候補を絞る際に

各候補の解釈を可能な限り列挙し，より誤解をなくせる名前を探索しよう

見た目

フォーマッターを使いましょう

コメントで何を書けばいいのか

[!abstract]
自分の脳内を取り合えず書き下ろす 添削はそのあとすれば良い
添削する際には，より客観的にわかりやすくすることを心がける

コメントを書く目的は，コードを書いた人間が何をしたのかをできるだけ多く伝えること
そのために押さえておくべき要点，特に以下の3点について考えよう

  1. 何をコメントすべきではないのか
  2. コーディング中の思考を記録する
  3. 読み手になりきって，彼らが何を知りたいのか想像する

1. 何をコメントすべきではないのか

[!caution]見ればすぐに分かること，良い命名によってきちんと説明されている事についてはコメントしない

[!caution]名前が悪い場合
コメントする代わりに名前を直そう

2. コーディング中の思考を記録する

例外は多いものの，単にコーディング中に何を考えていたのかを書いていくだけでも良いコメントになり得る

おしゃべりになろう

コーディング中に気づいたこと，とりうる他の選択肢，自分なりの理解などなど，とりあえずなんでも記録してみる
もし要らなければあとで消せば良い

開発の道筋を書く

所謂TODOコメントはどんどん活用しよう

定数の説明をする

定数がある場合，なぜその定数が必要なのかという背景をコメントで残そう

3. 読み手になりきって，彼らが何を知りたいのか想像する

そのコードを初めて読む他人になりきって，添削をコメントとして残してみよう

多くの場合，初めて読む人にとって最も困難な点は，プログラムが実行される時のフローを掴むこと
データはどのような順番で処理されるのかとか，エントリーポイントはどこかとか

良いドキュメントを書かないと

と思わずに，質の良い説明をいくつか加えるだけ，というつもりでまずは書いてみる

要約コメント

長い関数なんかで特に有効．
コードを，処理のまとまり毎に分けてそのブロックの要約をコメントする

[!tip]
ちょうど，テキストをマークダウンに落とし込むために章立てをして，各章にタイトルをつけていくイメージ

コメントをより正確に・コンパクトに

前節が説明しているのは何をコメントすれば良いのか
以下に説明するのは，どのようにコメントすれば正確でコンパクトになるのか

[!note]余計な情報を除く
纏められるものは纏める

[!note]代名詞を置き換える
例えば，itやthisはなるべく避けてより具体的な説明に置き換えるべき

[!note]要点を抜き出す

[!note]具体例を書く
関数なら具体的な使用例を書く
ある引数を渡したら具体的に何が戻り値になるのかといった実際の動作が分かる例をかく
シンプルすぎる具体例はあまり意味がない
エッジケースをなるべく多くひっかけるとより有益な情報を載せられる

[!note]処理が意味するところを明らかにする
つまり，... の ... の部分を優先して書く
論理の説明と，それが人間にとって何を意味するのかの説明を意識する

[!note]情報の密度が高い単語を選ぶ

繰り返しと論理を単純化

脳のワーキングメモリをなるべく消費しないコードにするための叡智

コントロールフローをよりわかりやすく書く

可能な限り自然なコントロールフローを書く

引数の順番

if len > 10とif 10 < lenはどちらの方がより読みやすい?
→前者の方が読みやすい

では

while bytes_received < bytes_expected

と

while bytes_expected > bytes_received

だとどうだろう
→前者の方が読みやすい

[!abstract]どちらの例もより自然言語に近い単語の展開の方がわかりやすいことを示してる

表にまとめると以下の通り

左側 右側
所謂"評価される側"の値を置く</br>より変化しやすい値であることが多い 比較対象である値を置く</br>より変化の少ない値であることが多い

if/elseブロックの順番

if a == b {
	//case 1
} else {
	//case 2
}

// or: ---

if a != b {
	//case 2
} else {
	//case 1
}

どちらが良いかを考える際の手引き

  • 肯定的なケースをまず評価する e.g. if !debugよりもif debugを使う
  • よりシンプルなケースをまず評価する
  • より目的に沿ったケースをまず評価する
  • より特徴的なケースをまず評価する

do whileは避ける

バグの温床

積極的に早期リターンする

コードの論理をシンプルに保てる

gotoの用法

gotoは上手く使えばコードをスッキリさせる
その為にラベルは複数作らないのが無難

又，goto文自身より上に飛ぶようにラベルを置くとスパゲッティコードの温床になるし，そのようなロジックはループで記述できるはず

ほとんどの場合gotoを使わないようにコーディングするべき

入れ子構造は可能な限り少なくする

早期リターンやcontinueを活用して，コードを直感的に保つ

巨大なコードを分解する

要は

  • 簡単に書けるところを，理由もなく難しくしない
  • 怠惰や陶酔は↑の理由にはならない

名前で説明する

if line.split(':')[0].strip() == "root"

よりも

let username = line.split(':')[0].strip();
if username == "root"

とした方がわかりやすい

要約変数

理解するのにコストがかかる式は，変数に格納して変数の名前で説明する

一行一行をシンプルに

一度の式で無理やり複数のことをしようとしない

より簡潔な方法を模索する

単純に見えることが想像以上に複雑になった時は，より簡単で単純な方法を考えてみる

繰り返し使われているものを変数に格納する

わかりやすくなる他に,変更にも強くなる

[!tip]
複数の処理に共通するパターンがある場合，マクロや関数を使ってよりコードをシンプルにできるかも

変数と可読性

complete the task as quickly as possible

可読性を下げる変数の使い方

  1. 変数が多ければ多いほど，コードを読むコストが上がる
  2. 変数のスコープが大きければ大きいほど，変数を追いかけるコストが上がる
  3. 変数の変更が多ければ多いほど，現在の値を把握するコストが上がる

前章で触れたように，必要な説明・要約を提供する変数はコードの可読性をあげる
同時にこれらの適切な用法は，上に挙げた可読性を下げる使い方の真逆であることがわかる

1. 変数が多ければ多いほど，コードを読むコストが上がる

不必要な（可読性を改善しない）変数は積極的に取り除こう

中間結果はその場で処理する

let remove_one = |array, value_to_remove| {
	let index_to_remove = None;
	for i in 0 .. array.len() {
		if array[i] == value_to_remove {
			index_to_remove = Some(i);
			break;
		}
	}
	if let Some(i) = index_to_remove {
		array.remove(i);
	}
};

index_to_removeは中間結果を保持する変数
index_to_removeを使わずに同じ論理を再現してみると

let remove_one = |array, value_to_remove| {
	for i in 0 .. array.len() {
		if array[i] == value_to_remove {
			array.remove(i);
			return;
		}
	}
}

よりシンプルでわかりやすいコードになった

"コントロールフロー変数"を取り除く

ループの条件文で使う為に変数を宣言しているコードは，多くの場合そのような変数は要らない
ルーブの構造を見直してみよう

もしループがネストしていたりより複雑なケースの場合，そもそもそういったコードは関数として摘出するのが良い

2. 変数のスコープが大きければ大きいほど，変数を追いかけるコストが上がる

グローバル変数が忌避されるのと同じように，スコープの大きい変数は避けられるべき対象
スコープを絞るというアイデアは普く変数に適用されるべき良いアイデア

static metod

スタティックメソッド（Rustで言う関連関数）はどんどん活用すると良い
クラスを名前空間のように扱えるし，コードを読む側からしてもコードを使う側からしてもわかりやすいコードに繋がる

[!tip]
cppではifのコンディション部分で変数を宣言できる
もし変数がifの内部でしか使われないのであればコンディション部分で変数を宣言するようにしよう

if (PaymentInfo* info = database.ReadPaymentInfo()){
  cout << "user paid " << info->amount() << endl;
}

変数は使われる直前に宣言しよう

コードを追いかけるコストが下がる

3. 変数の変更が多ければ多いほど，現在の値を把握するコストが上がる

雑多な処理の抽出

ソフトウェアの開発は一重に、大きな問題を細分化して、それぞれの細かい問題への解法を積み重ねていくこと
その時に大事な事は

関係のない雑多な処理を見つけて抽出する

これを徹底的に行うこと
そのための３つの習慣↓

  1. コードを見た際、そのコードにとって最も重要な目的は何か考える
  2. コードの各列において、1の目的に直接関係するか、副次的な処理なのかを考える
  3. もし副次的な処理が数列続くようならば別の関数に抽出する

コードを細分化するメリット

  1. テストがしやすくなる
  2. 再利用がしやすくなる
  3. 機能追加や削除が楽になる（変更する場所が少なくなるから）

汎用性の高いコードは積極的に切り離していくとどんどん楽になる

ただ、不必要に細分化すると逆に可読性が下がる

マルチタスクをしない

思考をコードに変換する

まずはロジックを自分の言葉で簡潔に説明してみる

コードの量を減らす

プログラマは必要とされている機能を多く見積もってしまいがち
また、プログラマはその機能を実装する手間とメンテナンスするコストを低く見積りがち
この習性と向き合うための3つの提案

  1. オーバーエンジニアリングをしない
  2. 解決したい問題を可能な限り単純にする
  3. 標準ライブラリに馴染む

問題をシンプルに

論理的に厳密な解法でなくても、ある程度妥協したシンプルな解法で十分なことがある

ライブラリに詳しくなろう

使用している言語の標準ライブラリを定期的に眺めるだけでも効果的
決して覚えておく必要はない
ただ、実装の際に そういえば使えそうなAPI見かけたことあるような..
となれば、プロジェクトを小さく保つのに役立つ

ライブラリは使い得

エンジニアが1日に生産できる実用に耐えうるクオリティのコードは、高々10行と言われている
既に高品質なコードが提供されているライブラリはじゃんじゃん使おう

[!example]
Webサーバーにバグがあったとして、ログを元にその原因を突き止めたいとする

1.2.3.4 example.com [24/Aug/2010:01:08:34] "GET /index.html HTTP/1.1" 200 ...
2.3.4.5 example.com [24/Aug/2010:01:14:27] "GET /help?topic=8 HTTP/1.1" 500 ...
3.4.5.6 example.com [24/Aug/2010:01:15:54] "GET /favicon.ico HTTP/1.1" 404 ...
...

この時、エラーをよく起こすURIを突き止めるコードは20行ほどで書けるだろう
しかし、cliで以下のように処理する事もできる

cat access.log | awk '{ print $5 " " $7 }' | egrep "[45]..$" | sort | uniq -c | sort -nr

Test, Design, Readability

テストと可読性

効果的で整理されたテストを書く事は有益
テストは非公式のドキュメントとして作用する
実際のコードがどのように動作して、どのように使われることを想定しているのか
がわかるようにすると良い

[!example]
以下の関数のテストを考える

// Sort 'docs' by score (highest first) and remove negative-scored documents.
void SortAndFilterDocs(vector<ScoredDocument>* docs);

void Test1() {
   vector<ScoredDocument> docs;
   docs.resize(5);
   docs[0].url = "http://example.com";
   docs[0].score = -5.0;
   docs[1].url = "http://example.com";
   docs[1].score = 1;
   docs[2].url = "http://example.com";
   docs[2].score = 4;
   docs[3].url = "http://example.com";
   docs[3].score = -99998.7;
   docs[4].url = "http://example.com";
   docs[4].score = 3.0;

   SortAndFilterDocs(&docs);

   assert(docs.size() == 3);
   assert(docs[0].score == 4);
   assert(docs[1].score == 3.0);
   assert(docs[2].score == 1);
}

このテストには少なくとも８つの問題がある
それらは何であるかを見つけ、直すためのアイデアをこの章では紹介していく

[!abstract]
上記のテストの問題点はそれぞれ

  1. テスト自体が長い・不必要なコードが多い
  2. テストを追加することが困難。追加の際にコピペや細かい修正が必要
  3. テスト失敗時のメッセージがわかりにくい・十分な情報を提供していない
  4. 一度に複数のシナリオを検証している
  5. 入力が厳選されていない
  6. テストケースに漏れがある（score == 0)
  7. 極端な入力でのテストが無い。ベクトルが空の場合、巨大な場合、重複がある場合など
  8. テストの名前が無意味。何をどのようにテストしているのか分からない

テスト管理の観点から

テストコードが巨大で複雑な場合プログラマはこうなる

  • 実際のコードを修正しづらくなる（テストを書き直すコストがかかるため）
  • 新たなテストを加えづらくなる

重要ではない処理

Test1()はセットアップが多くの記述を占めている
この処理は、テストしたいことの本筋とは離れているので切り分けよう

void AddScoredDoc(vector<ScoredDocument>& docs, double score) {
	ScoredDocument sd;
	sd.score = score;
	sd.url = "http://example.com";
	docs.push_back(sd);
}

この関数を使うと少しコンパクトになる

void Test1() {
	vector<ScoredDocument> docs;
	AddScoredDoc(docs, -5.0);
	AddScoredDoc(docs, 1);
	AddScoredDoc(docs, 4);
	AddScoredDoc(docs, -99998.7);
	AddScoredDoc(docs, 3.0);
	...
}

ただこれだけでは十分ではない
テストケースを増やしたい時にコピペする手間がある

一番高位の目的（何をテストしたいか）

殆どのテストに対して、

〇〇という入力に対して××と出力されることを確認したい

という形式に落としこむことができる

[!example]
Test1の場合

ドキュメントたちのスコアが[-5, 1, 4, -99998.7, 3]の時、
SortAndFilterDocs()を適用すると[4, 3, 1]のドキュメントのみが得られる

このことを確認したい。
ならば直接そう表現すれば良い

CheckScoresBeforeAfter({-5, 1, 4, -99998.7, 3}, {4, 3, 1});

テストケースを厳選する

'良い入力'が意味するところ↓

  1. 簡潔
  2. 最小のセット
  3. コードの不安要素を全て検証している

[!example]

CheckScoresBeforeAfter({1, 2, -1, 3}, {3, 2, 1});

確認したい項目に沿って入力を分ける

何がテストできていて、何がテストできていないのか、
のログにもなる

[!example]

CheckScoresBeforeAfter({2, 1, 3}, {3, 2, 1}); // sort
CheckScoresBeforeAfter({0, -0.1, -10}, {0}); // all values < 0 removed
CheckScoresBeforeAfter({1, -2, 1, -2}, {1, 1}); // duplicates are removed
CheckScoresBeforeAfter({}, {}); // empty input OK

テストの名前

テスト関数はプロジェクトの他の場所から読まれることは想定しなくても良いので
関数名が長くなったりしても気にする必要はない
コメントを書く要領で名前を決めると良い

  1. （もしあれば）テストの対象となっているclass, struct ...
  2. テストされる関数
  3. 確認している状況・バグ

これらの情報が名前に含まれていると可読性が上がる

[!example]

Test_<FunctionName>();
Test_<FunctionName>_<Situation>();

補助関数の名前

アサーションをするならCheck_...()
しないなら通常通りの名前にする、
というように、'test-aware'な関数とそうでない物を区別できるようにしておくとベター

テストに優しく

一般に、テストを意識して開発されたコードは、テストしやすいようにデザインされている
そうすると、プログラム自体もわかりやすくなる

補足

頭に入れておくといいかも集

[!example]テストのためにコードの可読性が犠牲になる場合
一般にテストしやすいコードは良いコードとなる。もしそうで無い場合は、一度俯瞰してみると良い。デザインや実装で見直すべきところがあるかもしれない

[!example]完璧なテスト
論理的に起こりうる問題を全て検証しよう！
...そんな気持ちでテストを書くと、大抵の場合えらい目にあう
完璧なテストを書くための時間を他のことに回した方が有意義
理論値の9割くらいはカバーできているな、実用上は問題ないだろう、くらいを目安に書こう

[!example]テストは目的ではない
最も高位の目的は、そのプロジェクトを作ること
テストすることではない

実際にデザインをしてみよう

やりたいこと

直近の1分、1時間でサーバーが何bytesやり取りしたかを記録したい

インターフェースの実装

初稿

trait MinuteHourCounter{
	/// add a count
	pub fn count(num_bytes: u32);
	///return the count over this minute
	pub fn minute_count()->u32;
	/// return the count over this hour
	pub fn hour_count()->u32;
}

名前の改善

count()というメソッドはよくない名前
countという単語は名詞でも同志でもある
代替となる名前を挙げてみよう

  • increment() これは誤解を招きうる。暗黙に、増加する値が一つだけだとしている
  • observe() 少し曖昧
  • record() これも動詞/名詞問題を持っている
  • add() このケースは少し面白い。四則演算的追加とも、配列に要素を追加するとも取れる。MinuteHourCounterの場合両方のケースに当てはまる

引数のnum_bytesは過剰に限定しすぎている
例えば、このインターフェースがデータベースへのクエリをカウントするために使われるかもしれない
なのでnum_bytesをcountにしてみよう

コメントの改善

trait MinuteHourCounter{
	/// add a count
	pub fn add(count: u32);
	///return the count over this minute
	pub fn minute_count()->u32;
	/// return the count over this hour
	pub fn hour_count()->u32;
}

次はコメントを見てみよう
add関数のコメントは無意味
使い手が知りたい情報を書き残そう

/// add a new data point
/// for the next minute, minute_count() will be larger by +count
/// for the next hour, hour_count() will be larger by +count
pub fn add(count: u32);

minute_count関数のコメントは解釈が2通りある

  1. over this minuteが時計上での分(0:01など)を指している
  2. over this minuteが今現在から遡って60秒間のことを指している

自分たちが意味しているのは2番なので、その事を記述しよう

///return the accumulated count over the past 60 seconds
pub fn minute_count()->u32;

hour_count関数のコメントも同様
最後にインターフェース自体の紹介も加えよう

/// track the cumulative counts over the past minutes and over the past hour.
/// useful, for example, to track recent bandwidth usage.
trait MinuteHourCounter{
	/// add a new data point
	/// for the next minute, minute_count() will be larger by +count
	/// for the next hour, hour_count() will be larger by +count
	pub fn add(count: u32);

	///return the accumulated count over the past 60 seconds
	pub fn minute_count()->u32;

	///return the accumulated count over the past 3600 seconds
	pub fn hour_count()->u32;
}

[!tip]
自分のコードが”ユーザーフレンドリー”かどうかを確認する時に初めて使う人の目線に立って考えることは効果的だ
この”初めて使う人”というのは多くの場合、半年後の自分も含まれている

実装

use std::collections::VecDeque;
use std::time::Duration;
use std::time::Instant;

struct MinuteHourCounter {
	events: VecDeque<Event>,
}

impl MinuteHourCounter {
	const MINUTE: Duration = Duration::new(60,0);
	const HOUR: Duration = Duration::new(3600, 0);

	fn add(&self, count: u32) {
		events.push_back(Event::new(count));
	}

	fn minute_count(&self) -> u32 {
		let now_secs = Instant::now();

		let mut count = 0;
		for event in self.events.iter().rev() {
			if now_secs.duration_since(event) > self.MINUTE {
				break;
			}

			count += event.count;
		}

		count
	}

	fn hour_count(&self) -> u32 {
		let now_secs = Instant::now();

		let mut count = 0;
		for event in self.events.iter().rev() {
			if now_secs.duration_since(event) > self.HOUR {
				break;
			}

			count += event.count;
		}

		count
	}
}

struct Event {
	count: u32,
	time: std::time::Instant,
}

impl Event {
	fn new(count: u32) -> Self {
		Self {
			count,
			time: std::time::Instant::now()
		}
	}
}

この実装は正しく動作するが、以下の問題を抱えている

  • minute_countとhour_countがほとんど一緒

改善

上記の問題を解決することで汎用性と可読性が改善する

fn count_since(&self, cutoff: u32) -> u32 {
	let now_secs = Instant::now();
	let duration = Duration::new(cutoff, 0);

	let mut count = 0;
	for event in self.events.iter().rev() {
		if now_secs.duration_since(event) > duration {
			break;
		}

		count += event.count;
	}

	count
}

fn minute_count(&self) -> u32 {
	self.count_since(60)
}

fn hour_count(&self) -> u32 {
	self.count_since(3600)
}

パフォーマンス

上記のコードが抱えるパフォーマンスの問題を挙げてみよう

  1. 不必要なeventを削除できない
  2. count_sinceが遅い: 与えられた時間に対して実行時間がO(n)のオーダーになっている

ベルトコンベヤー方式

2点のパフォーマンスの問題の共通点は、MinuteHourCounterに蓄えられているeventのうち
どれが1分以内のもので、どれが1時間以内のものか逐一走査しないといけないこと

ならば、

  • 1分以内に追加されたeventは1分以内に追加されたevent用のリストに
  • 1時間以内に追加されたeventは1時間以内に追加されたevent用のリストに

それぞれ追加するようにすれば良い
また、2番目の方針を改善して

  • 1分以上、1時間以内に追加されたevent用のリスト

にすることで、無駄なメモリの使用を避けることができそう

さらに改善

use std::collections::VecDeque;
use std::time::Duration;
use std::time::Instant;

struct MinuteHourCounter {
	minute_events: VecDeque<Event>,
	/// NOTE: only contains elements NOT in minute_events
	hour_events: VecDeque<Event>,

	minute_count: u32,
	/// counts ALL events over past hour, including past minute
	hour_count: u32,
}

impl MinuteHourCounter {
	const MINUTE: Duration = Duration::new(60,0);
	const HOUR: Duration = Duration::new(3600, 0);

	fn add(&mut self, count: u32) {
		self.shift_old_event();

		minute_events.push_back(Event::new(count));

		minute_count += count;
		hour_count += count;
	}

	fn shift_old_event(&mut self) {
		let now_secs = Instant::now();

		// shift event from minute_events to hour_events which pasts over 1m but within 1h
		// & remove event which is over 1h
		loop {
			if self.minute_count.is_empty() {
				break;
			}

			let cutoff = now_secs.duration_since(self.minute_count[0]);
			if cutoff > self.HOUR {
				self.minute_count.pop_front();
			} else if cutoff > self.MINUTE {
				let over_one_minute = self.minute_count.pop_front().unwrap();
				self.hour_count.push_back(Event::new(over_one_minute));
			} else {
				break;
			}
		}

		// remove event from hour_events which pasts over 1h
		loop {
			if self.hour_count.is_empty() {
				break;
			}

			let cutoff = now_secs.duration_since(self.hour_count[0]);
			if cutoff > self.HOUR {
				self.minute_count.pop_front();
			} else {
				break;
			}
		}
	}

	fn minute_count(&mut self) -> u32 {
		self.shift_old_event();
		self.minute_count
	}

	fn hour_count(&self) -> u32 {
		self.shift_old_event();
		self.hour_count
	}
}

めでたしめでたし..?

これで２つのパフォーマンスの問題も解決した
これで完成！..と言えるだろうか
実用に耐えうる実装になっているだろうか
回答としては、殆どの場合YES

今の実装に欠けている点で大きな問題が２つ

  1. 柔軟な設計ではない： 例えば24時間分の集計が欲しいときにたくさんの変更・追記が必要になる
  2. メモリ使用量が多い： 1秒間に100回addが呼ばれるようなサーバーでは、メモリ使用量の問題が出てくる

今の実装ではaddが頻繁に呼ばれればその分メモリを使う
実用の世界で状況によって予想以上に大量のメモリを使うのは良くない
メモリ使用量をO(n)からO(1)にしてみよう

時間単位の導入

これまでの実装では、1つ1つのやり取り単位で記録していた
これを、時間単位で記録しよう
ひとまず基本単位は1秒としよう
これで、メモリ使用量がより静的で予測可能になった

時間単位を実装してみよう

use std::time::Instant;

/// A class that keeps counts for the past N buckets of time
trait TrailingBucketCounter {
	/// # Example
	///
	/// `new(30, 60)` tracks the last 30 minute-buckets
	fn new(num_buckets: u32, bucket_width: u32) -> Self;
	fn add(&mut self, count:u32, now: Instant);
	/// return the total count over the last num_buckets worth of time
	fn trailing_count(&self, now: Instant) -> u32;
}

抽象化のスイートスポット

↑の実装に疑問を抱いたかもしれない
なぜaddやtrailing_countは時間(std::time::Instant)を引数に取るのだろう
理由は3つ

  1. TrailingBucketCounterが時間の管理自体に責任を持たなくて良くなる
    時間管理というより具体的な操作は実際にTrailingBucketCounterを実装する側にしてもらう
    結果、抽象化の粒度が揃い、テストがしやすくなったりバグを減らすことができる（と言う一般論）
  2. 時間の管理がTrailingBucketCounterを実装する側に集約される
  3. より汎用なインターフェースを提供できる

[!note]
上記の3番はリーダブルコード本文には書かれていない
また、1,2は、この纏めではRustのトレイトで実装しているので？？？と言う感じだろう
リーダブルコード本文ではC++を用いて実装しているため、1,2は継承の話と繋がる、と解釈すれば良い(と思う)
Rustのトレイトを使う場合は正直ない方がいいと思う

時間単位を使った実装

TrailingBucketCounterの実装を書いてみよう

struct MinuteHourCounter {
	buckets: ConveyorQueue,
	last_update_time: Instant,
	secs_per_bucket: u32,
}

impl MinuteHourCounter {

	fn update(&mut self, now: Instant) {
		let current_bucket = now / self.SECS_PER_BUCKET;
		let last_update_bucket = last_update_time / self.SECS_PER_BUCKET;

		self.buckets.shift(current_bucket - last_update_bucket);
	}
}

impl TrailingBucketCounter for MinuteHourCounter {
	fn new(num_buckets: u32, bucket_width: u32) -> Self{
		Self {
			buckets: ConveyorQueue::new(num_buckets),
			secs_per_bucket: bucket_width,
			last_update_time: Instant::now(),
		}
	}

	fn add(&mut self, count: u32) {
		self.update(Instant::now());
		self.buckets.add_to_back();
	}

	fn trailing_count(&mut self) {
		self.update(Instant::now());
		self.buckets.total_sum()
	}
}

/// A queue with a maximum number of slots, where old data "falls off" the end
struct ConveyorQueue {
	q: VecDeque<u32>,
	max_items: u32,
	total_sum: u32,
}

impl ConveyorQueue {
	fn new(max_items: u32) -> Self {
		Self {
			q: VecDeque::new(),
			max_items,
			total_sum: 0,
		}
	}

	/// increment the value at the back of the queue
	fn add_to_back(&mut self,count: u32) {
		if self.q.is_empty() {
			self.shift(1);
		}

		self.q.back_mut().unwrap() += count;
		self.total_sum += count;
	}

	/// Each value in the queue is shifted forward by `num_shifted`
	/// New items are initialized to 0
	/// oldest items will be removed so there are <= max_items
	fn shift(&self, num_shifted: u32) {
		// in case too may items shifted, just clear the queue
		if num_shifted >= self.max_items {
			self.q = VecDeque::new();
			self.total_sum = 0;
			return;
		}

		// push all the needed 0s
		for _ in 0..num_shifted {
			self.q.push_back(0);
		}

		// let all the excess items fall off
		while self.q.len() > self.max_items {
			self.total_sum -= self.q.pop_front().unwrap();
		}
	}
}

まとめ

この章で見てきた3つの解決法を比べてみよう

解決法 行数 ランタイムオーダー メモリオーダー
最初の方法 33[^1] O(events per hour) 無制限!(🫠)
ベルトコンベヤー方式 55[^1] O(1) O(events per hour)
時間単位方式 98[^1] O(1) O(時間数)

[^1] リーダブルコード本文での行数

Discussion