CodeKataやってみた記事、第二弾です。
以前、Kata01: Supermarket Pricingについて考察しました。
今回は、Kata02: Karate Chopを解いていきます。
問題概要
バイナリチョップ（バイナリサーチ、二分探索）を書く。
ただし５回、全く異なる実装で。
実装指針
ヒント、というわけでもないのでしょうが、実装方針は出ています。
ただし、以下の３つだけです。
- 伝統的なループ
- 再帰
- 配列のスライスを渡す関数？
残り二つは自分で見つけろ、ということでした。
ゴール
発生したエラーの記録
作れば作るほど、エラーは減ったか？
選択したアルゴリズムについて
- 相対的メリット
- 最も書くのが楽しかったのはどれか
- どれが一番難しかったか
全ての質問に対し、「なぜ」を答える。
4個目、5個目
どうやって、これらのアプローチを考え出したのか。
仕様（と制約）
メソッドは、
def chop(self, value: int, values: list) -> int:
の形に従うよう、指定されています*1。
要素数は最大10万で、配列はソート済み、メモリ消費や速度は考慮しないものとされています。
実際の実装
さて、以前と同じく、実際に解きました。
言語はPython、環境はVisual Studio Codeです。
バージョンは関係なく動作すると思われます。
実装の前に
…以下長いので、折りたたみます。見たい方は展開してください。（記事の直リンクの場合、続きを読むが出ません）
まずは下準備です。
問題には、「指定したテストをパスすること」という制約があります。
同じ結果を返すアルゴリズムを5回テストするので、手間をかけずにテストできるよう、
- テストクラス
- テスト対象のインターフェイス化
を行っています。
from abc import ABCMeta, abstractmethod class IChopper(metaclass=ABCMeta): """バイナリサーチ（Karate Chop）を行います。""" @abstractmethod def chop(self, value: int, values: list) -> int: """バイナリサーチを実行し、valueの位置を返します。見つからない場合は-1を返します。""" pass
Pythonにインターフェイスは無いので、ABCMetaでそれっぽく見せています。
なお、普通に継承を使っても何ら問題ないです。
- テストクラス
長いので、一部省略しています。
import unittest as ut import chop1 as c1 import chop2 as c2 import chop3 as c3 import chop4 as c4 import chop5 as c5 from IChop import IChopper class ChopTest(ut.TestCase): def run_chopper(self, chopper: IChopper, testee = ""): # テスト群（省略） # add own self.assertEqual(1038, chopper.chop(1039, list(range(1, 10000))), testee) self.assertEqual(6, chopper.chop(7, list(range(1, 45000))), testee) self.assertEqual(-1, chopper.chop(100000, list(range(1, 90000))), testee) def test_1(self): chopper = c1.Chopper() self.run_chopper(chopper, "test_1") def test_2(self): chopper = c2.Chopper() self.run_chopper(chopper, "test_2") def test_3(self): chopper = c3.Chopper() self.run_chopper(chopper, "test_3") def test_4(self): chopper = c4.Chopper() self.run_chopper(chopper, "test_4") def test_5(self): chopper = c5.Chopper() self.run_chopper(chopper, "test_5")
先ほど定義したインターフェイスを受け取って、テストを実行するメソッドを作りました。
IChopperのクラスが増えようとも、新しいテストメソッドを定義するだけでいいので、楽です。
1日目
とりあえず、ネットで情報収集せずに書こう、と決めて、書き始めた日です。
なお、上に書いた「実装指針」、完全に見逃した状態で作っています。
from IChop import IChopper class Chopper(IChopper): def chop(self, value: int, values: list) -> int: return self.search(value, 0, len(values) - 1, values) def search(self, value: int, start: int, end: int, values: list): if not values: return -1 if start >= end: if values[start] == value: return start else: return -1 median = int((start + end) / 2) median_value = values[median] if median_value == value: return median elif median_value > value: return self.search(value, start, median - 1, values) elif median_value < value: return self.search(value, median + 1, end, values) return -1
初日は再帰を使っています。
うん、長い！
全日程終わった後サンプルソース見たんですが、無駄が多いですね！
発生エラー
2日目
ここで、テストの改良と、処理のインターフェイス化を行っています。
from IChop import IChopper class Chopper(IChopper): def chop(self, value: int, values: list) -> int: return self.search(value, [(v, i) for i, v in enumerate(values)]) def search(self, value: int, values: list) -> int: if not values: return -1 if len(values) == 1: if values[0][0] == value: return values[0][1] else: return -1 median = int(len(values) / 2) index_value = values[median] if index_value[0] == value: return index_value[1] elif index_value[0] > value: return self.search(value, values[0: median]) elif index_value[0] < value: return self.search(value, values[median + 1:]) return -1
リストのスライスでいけそう、と思いついたのはいいものの、インデックス取れない、と気づきました。
そこで、リスト内包でインデックス付与したタプルを作り、リストをスライスしつつ再帰。
読みやすくない何かができました。
発生エラー
なし
3日目
早くもネタに詰まり、やっと「実装指針」を見つけました。
ループあるじゃん！という気持ちで作りました。
from IChop import IChopper class Chopper(IChopper): def chop(self, value: int, values: list) -> int: start = 0 end = len(values) - 1 while start <= end: if start == end: if values[start] == value: return start else: break median = int((start + end) / 2) index_value = values[median] if index_value == value: return median elif index_value > value: end = median - 1 elif index_value < value: start = median + 1 return -1
行数を減らそうとか、そういう気は筆者に無いようです。
発生エラー
特になし
4日目
ネタ切れ起こしましたが、なんとか作り出しました。
from IChop import IChopper class Chopper(IChopper): def chop(self, value: int, values: list) -> int: count = len(values) if count == 0: return -1 if count == 1: if values[0] == value: return 0 else: return -1 place = 0.5 inc = 0.25 index = -1 while True: pre_index = index index = round(count * place) if index >= count: return -1 test_value = values[index] if test_value == value: return index if pre_index == index: return -1 if test_value > value: place -= inc if test_value < value: place += inc inc /= 2
…意図、わかるでしょうか？
バイナリサーチは、全体を半分にしつつ、検索を繰り返すものです。
でも、結局は全体の線のうち、一定点を探しているだけです。
そこで、項目全体を0～1の線分とし、その中央から探索を始め、値がある方向に点を移動させていく、というロジックを組み立ててみました。
値が見つかるか、点が動かなくなった時点で探索を打ち切ります。
なお、これでうまく動きますが、中央点を左右にずらす操作*2を実装していないため、これまでの二分探索より計算量が多いです。ミスっています。
発生エラー
- インデックスが範囲超過
- 項目数１のときに動かない
- 割り算の結果を四捨五入する必要があった
5日目
ネタ切れです。もはや普通にロジック組んでもしょうがない、という気持ちでした。
from IChop import IChopper class Chopper(IChopper): def chop(self, value: int, values: list) -> int: result = None func = self._chop_core(value, values) while result == None: result = func() return result def _chop_core(self, value: int, values: list): start = 0 end = len(values) - 1 def search(): nonlocal start nonlocal end if not values: return -1 if start >= end: if values[start] == value: return start else: return -1 median = int((start + end) / 2) median_value = values[median] if median_value == value: return median elif median_value > value: end = median - 1 elif median_value < value: start = median + 1 return None return search
内部関数を使って、クロージャーを作っています。
ロジック自体変わってないけど
答えが確定するまで、Noneを返し続けます。
よって、呼び出し側は無限ループで待ち合わせします。
なお、当初はラムダ式を使っていましたが、うまくいかず、諦めています。
ループを計算の外に出せるようになったことで、計算量の算出や、ループ中の処理を追加できるようになったり、柔軟になります。
発生エラー
質問に答える
問題の目的にある、質問に答えます。
相対的なメリット
まず、クロージャーは、他の方法と比べて、ループ前後に簡単に処理が挟める、という利点があります。
リストのスライスは、リストの要素の真ん中を取るので、インデックスエラーに対して安全です。
ループは…まあ、読みやすいですね。
製品として出すなら
いや、どれも出すに値しないでしょう…自分の腕の無さ故ですが。
リストの長さに依存しない0～1方式は、なかなか面白いとは思いますが、浮動小数点数の問題が…
書くのが楽しいもの
4日目、5日目です。
普通、こんな方法でバイナリサーチを組まないので、試行錯誤はとても楽しかったです。
これに関しては、考える過程がとても面白く、思いついたときにこれいける！みたいになるのがたまらなかったです。
難しかったもの
1日目です。
バイナリサーチなんぞ、何度も組みましたが、思い出す作業が最も大変でした。
あと、インデックスとか考えるのは大変です…
おわりに
これにて、ようやくKata02、終了です。
リアルに5日かけたので、本当に長丁場になりました。
こういう頭の体操も悪くない、と思いました。
でも、これでいいんですかね…？特にクロージャー。内部実装コピペです…
最後に書くことでもないですが、長くなってすみません。
読んでいただいた方がいらっしゃったら、本当に、心の底から、ありがとうございます。
