SE(たぶん)の雑感記

一応SEやっている筆者の思ったことを書き連ねます。会計学もやってたので、両方を生かした記事を書きたいと考えています。 でもテーマが定まってない感がすごい。

CodeKataで遊ぶ Kata02:5つのバイナリサーチ

CodeKataやってみた記事、第二弾です。

以前、Kata01: Supermarket Pricingについて考察しました。

hiroronn.hatenablog.jp

今回は、Kata02: Karate Chopを解いていきます。

問題概要

codekata.com

バイナリチョップ(バイナリサーチ、二分探索)を書く。

ただし5回、全く異なる実装で。

実装指針

ヒント、というわけでもないのでしょうが、実装方針は出ています。
ただし、以下の3つだけです。

  • 伝統的なループ
  • 再帰
  • 配列のスライスを渡す関数?

残り二つは自分で見つけろ、ということでした。

ゴール

発生したエラーの記録

作れば作るほど、エラーは減ったか?

選択したアルゴリズムについて

  • 相対的メリット
  • 最も書くのが楽しかったのはどれか
  • どれが一番難しかったか

全ての質問に対し、「なぜ」を答える。

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

初日は再帰を使っています。

うん、長い!
全日程終わった後サンプルソース見たんですが、無駄が多いですね!

発生エラー

  • 素数0の対処
  • 素数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を実装していないため、これまでの二分探索より計算量が多いです。ミスっています。

発生エラー

  • インデックスが範囲超過
  • 項目数1のときに動かない
  • 割り算の結果を四捨五入する必要があった

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を返し続けます。
よって、呼び出し側は無限ループで待ち合わせします。

なお、当初はラムダ式を使っていましたが、うまくいかず、諦めています。

ループを計算の外に出せるようになったことで、計算量の算出や、ループ中の処理を追加できるようになったり、柔軟になります。

発生エラー

  • ラムダ式がうまく書けない
    →内部変数に変更
  • nonlocalを付け忘れる*3

質問に答える

問題の目的にある、質問に答えます。

相対的なメリット

まず、クロージャーは、他の方法と比べて、ループ前後に簡単に処理が挟める、という利点があります。

リストのスライスは、リストの要素の真ん中を取るので、インデックスエラーに対して安全です。

ループは…まあ、読みやすいですね。

製品として出すなら

いや、どれも出すに値しないでしょう…自分の腕の無さ故ですが。

リストの長さに依存しない0~1方式は、なかなか面白いとは思いますが、浮動小数点数の問題が…

書くのが楽しいもの

4日目、5日目です。

普通、こんな方法でバイナリサーチを組まないので、試行錯誤はとても楽しかったです。
これに関しては、考える過程がとても面白く、思いついたときにこれいける!みたいになるのがたまらなかったです。

難しかったもの

1日目です。

イナリサーチなんぞ、何度も組みましたが、思い出す作業が最も大変でした。
あと、インデックスとか考えるのは大変です…

おわりに

これにて、ようやくKata02、終了です。
リアルに5日かけたので、本当に長丁場になりました。

こういう頭の体操も悪くない、と思いました。
でも、これでいいんですかね…?特にクロージャー。内部実装コピペです…

最後に書くことでもないですが、長くなってすみません。
読んでいただいた方がいらっしゃったら、本当に、心の底から、ありがとうございます。

*1:Pythonで、インスタンスメソッドとして定義した場合の例。サイトではRubyの例

*2:median + 1、median - 1の操作のこと

*3:変数が初期化されていない、と、pylintが警告を出す