これは何？
TDDBCというイベントがあります。
- 何かを作るお題がある（制限時間あり）
- それをTDDでペアプログラミングする
- それぞれのペアの、テストとプロダクションコードをレビューし合う
というとても楽しいイベントですが、
これは、そのTDDBCをひとりでやってみるものです。
お題
LRUCache
進め方
開発はGithubのリポジトリでやります。
@t_wadaさんのTDDBCのお題は、最初に簡単な仕様が示され
それが終わると、次に仕様変更が待っているという流れになっているので
仕様変更の単位でIssueとbranchを切っていきます。
レビュー
とりあえず、最初の仕様を満たすものができました。
https://github.com/haazime/tddbc_lru_cache/tree/feature/basic
インタフェース
# 大きさ2でLRUCacheを生成する
cache = LRUCache.new(2)
# データを入れる
cache[:x] = :xray
cache[:y] = :yankee
cache[:z] = :zulu
# データを取り出す
cache[:z] #=> :zulu
# サイズ2なので最も使われていない（最初に入れられた）:xは消える
cache[:x] #=> nil
# キャッシュの内容をHashにする
cache.to_hash
# =>
{
y: :yankee,
z: :zulu
}
テスト
RSpec.describe LRUCache do
context 'サイズが2の時' do
let(:cache) { LRUCache.new(2) }
it ':aが消える' do
cache[:a] = 'alpha'
cache[:b] = 'bravo'
cache[:c] = 'charlie'
expect(cache.to_hash).to match(
b: 'bravo',
c: 'charlie',
)
end
it ':bが消える' do
cache[:a] = 'alpha'
cache[:b] = 'bravo'
cache[:a]
cache[:c] = 'charlie'
expect(cache.to_hash).to match(
a: 'alpha',
c: 'charlie',
)
end
end
end
テストの構造は、状況ごとに細かくcontextを作り、beforeで
その状況をセットアップするような構造が好みなのですが
今回はネストが深くなりそうだったので、itブロックの中で
コンテキストを作りつつ、検証もするようにしてみました。
また、LRUCache#to_hashを使って、
- データが消えていること
- 消えてなかったデータはそのままになっていること
を同時に検証しています。
マッチャーはmatchを使っていますが、今考えるとeqでよかったかもしれません。
プロダクションコード
def initialize(capacity)
@capacity = capacity
@container = {}
@stored_key_order = []
end
キャッシュデータは、そのキーと値を@containerにそのままHashで持ちます。
最も使われていないデータのキー（サイズを超えた時にどのデータを消すか）を決めるために
@stored_key_orderにArrayで持ちます。
def []=(key, value)
@container[key] = value
@stored_key_order << key
if @stored_key_order.size > @capacity
@container.delete(@stored_key_order.shift)
end
end
データが入れられた時、キャッシュサイズを超えている場合は
@stored_key_orderの先頭にあるキーを@containerから削除します。
def [](key)
@stored_key_order.delete(key)
@stored_key_order << key
@container[key]
end
最近取り出されたデータのキーは、@stored_key_orderの末尾に移動します。
@stored_key_order という名前は、データを入れた時のキーの順序という意図でしたが、
実際の役割は
次にキャッシュサイズを超えた時に消されるキーの優先順位
になっているので、それにふさわしい名前に変えたほうがよさそうです。