Screaming Loud

研究・プログラミングなど気づいたことをメモをしています。読書記録はこちらに記載しています。https://bookmeter.com/users/75944

CodeKata 2 : 空手チョップ

2つめのCodeKata: Kata Two -- Karate Chopを訳しました。



バイナリチョップ(もしくはもっとつまらないバイナリサーチって呼ばれている)は,ソートされた配列からある値が格納されている位置を見つけるものだ。
値を探す度に、考慮中の配列を2分割することによって、いくつかの効果を得られる。
1つ目としては、探している値が分割した配列のどちらにあるかを決められる。
2つ目としては、探すべき範囲はこの半分でよいのでもう一度半分に分けることだ。
探していた値が見つかるか、配列を探索し終わったら終了する。
イナリサーチはコンピュータサイエンスの授業で人気なものの一つである。

この型は簡単だ。
イナリサーチのルーチン(以下で述べる特徴を使って)を好きな言語、好きな技術を使って実装しよう。
明日、もう一回実装しよう。ただし、全く違う技術を使ってね!
また次の日も同じく実装をして、バイナリチョップを5種類作ってみよう。
(例えば、一つの解決策として伝統的なforループによる実装があるだろうし、再帰的なものもあるだろう。また関数による配列をスライスしていく方法もあるだろう。)

ゴール

この型は3つの別なゴールがある。

  1. それぞれのアルゴリズムをコーディングしたら、遭遇したエラー文をメモしておこう。バイナリサーチは「off-by-oneエラー」や「フェンスポストエラー」を引き起こしやすい。その週にコーディングをすすめたら、前述のエラーが減っているかどうか確認しよう。(すなわち、あるテクニックによるコーディングをするとき、他のテクニックの経験から学んでいるか?)
  2. 色々選んだテクニックから相対的なメリットについて何が言える?どれが一番利用するコードとして成功しそう?どれが一番書いていて楽しい?どれが一番書き始める上で大変?そして全ての質問において、「なぜ?」と問いてみて。
  3. 5つも別のアプローチのバイナリチョップを書くのはかなり大変だとおもう。では、どうやって4つとか5つのアプローチにたどり着いた?それらの「気が狂った」神経を採用するためにどんなテクニックを使った?

仕様書

整数の探索するターゲットとソートされた整数の配列を使ってバイナリチョップを書こう。
配列内のターゲットの整数インデックス、もしくは見つからなかった場合の-1を返すべきである。
戻り値の型は

chop(int, array_of_int) -> int

になるだろう。
配列は10万要素より少ないと考えていい。
このkataの目的においては、時間とメモリのパフォーマンスは重要ではない(面倒になってkillする前に探索は終わると思う、しかも走らせるために十分なRAMは持っている)。

テストデータ

ここに私が開発するときに使うテスト(ユニットコード)を用意した。
自由に使ってくれ。
テストは配列は0から始まるように作られている。
これを好きな言語で(まさかRubyを選ばなければ)コンパイルするには、グローバルな検索置換が必要になるはずだろう。

  def test_chop
    assert_equal(-1, chop(3, []))
    assert_equal(-1, chop(3, [1]))
    assert_equal(0,  chop(1, [1]))
    #
    assert_equal(0,  chop(1, [1, 3, 5]))
    assert_equal(1,  chop(3, [1, 3, 5]))
    assert_equal(2,  chop(5, [1, 3, 5]))
    assert_equal(-1, chop(0, [1, 3, 5]))
    assert_equal(-1, chop(2, [1, 3, 5]))
    assert_equal(-1, chop(4, [1, 3, 5]))
    assert_equal(-1, chop(6, [1, 3, 5]))
    #
    assert_equal(0,  chop(1, [1, 3, 5, 7]))
    assert_equal(1,  chop(3, [1, 3, 5, 7]))
    assert_equal(2,  chop(5, [1, 3, 5, 7]))
    assert_equal(3,  chop(7, [1, 3, 5, 7]))
    assert_equal(-1, chop(0, [1, 3, 5, 7]))
    assert_equal(-1, chop(2, [1, 3, 5, 7]))
    assert_equal(-1, chop(4, [1, 3, 5, 7]))
    assert_equal(-1, chop(6, [1, 3, 5, 7]))
    assert_equal(-1, chop(8, [1, 3, 5, 7]))
  end
広告を非表示にする