CodeKataやってみた記事、第八弾です。
今回は、Kata08: Conflicting Objectivesをやっていきます。
Conflicting Objectivesは、「矛盾した目的」と訳しています。
概要
ソースを書く目的の一つの側面は、世の中の問題を解決し、世界にある種の価値を加えること。
しかし、二次的な目的として、問題解決しつつ、できるだけ速く、簡単にメンテナンス、拡張するというものがある。
Kataの説明
簡単なソースを、３つの二次的目的をもって書く。
以前（Kata05やKata06のこと）使った辞書を使い、二つの単語をつなげて６文字の単語を作る。
例：
Angles = Angl + es
Delton = Del + ton
３つの目的は、
- 一回目：できる限り読みやすいコード
- 二回目：できる限り動作速度を上げるように最適化
- 三回目：拡張性を重視
のこと。
終わった後
３つの目的の相互作用を考える
これらを実施することが最適化を意味する？
いつものように、続きは一応隠します。（直接見ると隠れません）
自分なりの答え
事前説明
ファイル読み込み等、全部一緒になるものは、共通の実装です。
- 読み込みインターフェイス
from abc import abstractmethod, ABCMeta class ITextReader(metaclass=ABCMeta): @abstractmethod def read(self) -> list: """データを読み込み、各行を要素としたリストを返します。""" pass
- 実際の読み込み
from Reader import ITextReader class word_reader(ITextReader): def read(self) -> list: """全行読み込む""" with open("wordlist.txt", "r", encoding="utf8") as f: lines = f.readlines() # 1行毎にファイル終端まで全て読む(改行文字も含まれる) return [line.rstrip("\r\n") for line in lines]
- 単語ペアモジュール
from abc import ABCMeta, abstractmethod class combination(object): '''単語ペアを表します。''' def __init__(self, head: str, tail: str): self._word1 = head self._word2 = tail self._word = head + tail def __repr__(self): return "{0} = {1} + {2}".format(self.word, self.head, self.tail) @property def head(self): '''先頭単語''' return self._word1 @property def tail(self): '''末尾単語''' return self._word2 @property def word(self): '''単語''' return self._word class combiner(metaclass=ABCMeta): '''単語作成機能を持ちます。''' @abstractmethod def get_combinations(self): '''複合単語を返します。''' pass
というわけで、最初から凝ってしまいました。
単体テストデータも同一となるので、ある程度凝っています。そのおかげで、「拡張性を重視」の問題で困っています。
各問題では、combinerを継承して実装します。
なお、__repr__を作っているため、結果は
のような、わかりやすい形で出力されます。
一回目：できる限り読みやすいコード
読みやすさ = シンプルさ
初回なので、アルゴリズムが正しいか、単体テストで確かめながら作っています。
- Word_Combine1.py
# purpose: make program as readable as you can make it. from Reader import ITextReader from Word_Combination import combiner, combination class combiner_impl(combiner): def __init__(self, reader: ITextReader): self._reader = reader def get_combinations(self): words = self._reader.read() sixes = [x for x in words if len(x) == 6] less_six = [x for x in words if len(x) < 6] for word in sixes: heads = (x for x in less_six if word.startswith(x)) for head in heads: tail = word.replace(head, "", 1) if tail in words: yield combination(head, tail)
6文字の単語は、5文字以下の2単語から構成されるということで、
- 6文字単語の開始文字列を。5文字以下文字列と一致するか
- 一致したら、残りの文字列が5文字以下文字列に含まれるか
の二段階、チェックしています。
読みやすいように書いたつもりです。やることは単純です。
二回目：できる限り動作速度を上げるように最適化
さて、一回目のソースですが、動作速度がとても遅いです。
startswithを使うのはいいですが、6文字単語1単語ごとに5文字以下単語全検索となり、遅すぎます。
それを解消したのが、以下のソースです。
- Word_Combine2.py
# purpose: optimize the program to run fast fast as you can make it. import bisect from Reader import ITextReader from Word_Combination import combiner, combination class combiner_impl(combiner): def __init__(self, reader: ITextReader): self._reader = reader def get_combinations(self): # premise: words are sorted. words = self._reader.read() length = len(words) sixes = [x for x in words if len(x) == 6] for word in sixes: head = word while head: head = head[0: -1] head_index = bisect.bisect_left(words, head) if length > head_index and words[head_index] == head: # search tail tail = word.replace(head, "", 1) tail_index = bisect.bisect_left(words, tail) if length > tail_index and words[tail_index] == tail: yield combination(head, tail)
6文字単語のみ抽出するのは変わりません。
以下の工夫で操作速度を確保します。
- 単語検索は、辞書がソートされていることを前提にし、二分探索で行う
- 6文字単語取得後、末尾から一文字削った文字列が辞書に含まれるか検索
- 含まれたら、残りの文字列が辞書に含まれるか検索
- 両方見つかったものを正とする
処理自体は増えていますが、個々の操作が速いので、結果的に高速化します。
例えば、一回目では全検索だった部分を、二分探索に変えた点です。
また、一回目より計算量の把握が容易*1です。
bisect.bisect_left(words, head)の部分で、words（全単語）を対象としていますが、５文字以下の単語に前もって絞っておけば、まだ若干早くなる可能性はあります。
三回目：拡張性を重視
最初の段階でかなり重視しているので、これ以上と言われても…という気持ちはあります。
でもやります。
まず、単語長と探索アルゴリズムを差し替えられるよう、以下のインターフェイスを用意します。
class IWordSearcher(metaclass=ABCMeta): def get_targets(self, words: list) -> list: """検索対象を取得します。""" pass def match(self, words: list, word: str) -> iter: """単語を検索します。""" pass
利用クラスはこうなります。
- Word_Combine3.py
# purpose: write as extendible a program as you can. from Reader import ITextReader from Word_Combination import combiner, combination, IWordSearcher class combiner_impl(combiner): def __init__(self, reader: ITextReader, search: IWordSearcher): self._reader = reader self._search = search def get_combinations(self): words = self._reader.read() targets = self._search.get_targets(words) for word in targets: for match in self._search.match(words, word): yield match
上で作ったIWordSearcherの挙動によって、処理が変わるようになりました。
そして、実装クラスです。
import bisect from Word_Combination import IWordSearcher, combination class search_impl(IWordSearcher): def get_targets(self, words: list) -> list: """検索対象を取得します。""" return [x for x in words if len(x) == 6] def match(self, words: list, word: str) -> iter: """単語を検索します。""" length = len(words) head = word while head: head = head[0: -1] head_index = bisect.bisect_left(words, head) if length > head_index and words[head_index] == head: # search tail tail = word.replace(head, "", 1) tail_index = bisect.bisect_left(words, tail) if length > tail_index and words[tail_index] == tail: yield combination(head, tail)
二回目のソースと同じです。
終了後：相互作用について
Kataの最後に、三目的の相互作用について考えてみよう、とあります。
動作速度と可読性
これは、突き詰めると相反すると思います。
動作速度確保のために、特殊なアルゴリズムを使う、標準ライブラリとは別に自前で処理を組む等の手段を取る場合があります。
そうすると、可読性は落ちます。なんでここでこれ必要なんだろう、となります。
可読性を確保したら動作速度が落ちる、とは言いません。
が、逆は真だと思います。
動作速度と拡張性
これは、視点の違いで意見あると思います。
高速化を要する処理だけ切り離すのなら、それだけで拡張性があると言えます。
処理そのものは不可分であれば、拡張に乏しいと言えます。
可読性確保そのものは、動作速度に大きな影響を与えないです。
拡張性と可読性
拡張性を確保する際の基本戦術は抽象化です。
過度に抽象化が進んだソースは、理解するのが難しくなります。
『Adaptive Code』には、随所に
過度の抽象化は避けること
みたいな記述が出てきます。
過度の抽象化は、可読性を損なうと考えています。
おわりに
そもそも問題が難しいです。
一回目の時点で、解法がほぼ決まってしまっていたので、三回目（拡張性）の時点で実装を工夫できませんでした。
listにこだわらず、set等を使ったほうが良かったのかもしれません。
というか、確実にそのほうがいいですね。
関係ないですが、こういう思いつきで、ソースは徐々に良くなっていくものだと思っています。
*1:6文字単語一つにつき、最低5回、最大10回の辞書検索を行う
