CodeKataやってみた記事、第六弾です。
今回は、Kata06: Anagramsをやっていきます。
今回は短いです。
嘘です。普通に長くなりました。
概要
やるべきことを一言で言います。アナグラムになっている文字列を見つけるです。
アナグラムとは、下記のWikipediaの通り、文字を並び替えて別の言葉を作る、遊びみたいなもののことです。
問題文によると、イギリスのクロスワードは、ヒントに言葉の意味と、言葉遊びとかのアナグラムが含まれるそうです。
…有益な情報はこれだけです。他の問題に比べて短い。
やりたいこと
単語を一行ずつ格納しているファイルがあるので、アナグラムとなっている単語を見つけて出力する、というものです。
テキストファイルの中には、338,882行のテキスト = 単語が入っており、20,683のペアが見つかるはず、とのことです。
あとは、以下二つも出してね、とのことです。
目的
アルゴリズムについて考える必要があります。
ただし、単純な仕組みにすると、膨大な時間がかかる場合が考えられるので、その場合は代替案を用意しましょう。
あと、よければテストコードつくりましょう、とのこと。
いつものように、続きは一応隠します。（直接見ると隠れません）
自分なりの答え
機能として分けると、以下の二つです。
また、単体テストも作ってね、とのことなので、それを考慮します。
というわけで、分けます。
文字列取得
インターフェイスにします。
- Reader.py
from abc import abstractmethod, ABCMeta class ITextReader(metaclass=ABCMeta): @abstractmethod def read(self) -> list: """データを読み込み、各行を要素としたリストを返します。""" pass
わざわざインターフェイスにした理由は、テストを容易にするためです。
テスト用実装クラスは以下の通りです。
定義文字列は、CodeKataの例として挙がっているものを編集して作っています。
- test_reader.py
from Reader import ITextReader class Direct_Reader(ITextReader): def read(self) -> list: """データを読み込み、各行を要素としたリストを返します。""" return ['kinship', 'pinkish', 'enlist', 'inlets', 'listen', 'silent', 'boaster', 'boaters', 'borates', 'fresher', 'refresh', 'sinks', 'unpolitic', 'skins', 'knits', 'stink', 'rots', 'sort', 'peats', 'cuprites']
そして、ファイルから取得するものは、以下の通りです。
小細工は入っていますが、普通です。
- wordlist_reader.py
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]
アナグラムの判定
アナグラムの判定は、文字列を並び替えた結果が同一かどうかでわかります。
対象の文字列があればわかるので、上で作った読み込みクラスを、依存性の注入で受け取り、当クラスで読み込み処理を呼び出します。
こうすると、読み込み方法が違っていても、同一の方法で扱えます。*1
- Anagrams.py
from Reader import ITextReader class anagram_search(object): """アナグラム検索""" def __init__(self, reader: ITextReader): self._anagrams = {} self._reader = reader def get_complex_anagrams(self): """二語以上あるアナグラムを取得します。""" self._read_init() return [v for k, v in self._anagrams.items() if len(v) > 1] def count(self): """アナグラムで数えた要素数を取得します。""" self._read_init() return len(self._anagrams) def _read_init(self): if self._anagrams: return for word in self._reader.read(): anagram = "".join(sorted(word)) vals = self._anagrams.get(anagram) if vals == None: self._anagrams[anagram] = [word] else: self._anagrams[anagram].append(word)
肝となるのは、アナグラム判定部分ですね。
アナグラム判定文字列
for word in self._reader.read(): anagram = "".join(sorted(word))
一語ずつ、readerから取ってきて、文字列をソート、再度連結しています。
登録済みか
vals = self._anagrams.get(anagram) if vals == None: self._anagrams[anagram] = [word] else: self._anagrams[anagram].append(word)
辞書の中身は、Key = アナグラム判定文字列、Value = 単語のリスト、となっています。
新語が現れるたびに、リストを生成して、辞書に入れています。
速度はともかく、これだけでアナグラムの判定は行えます。
途中経過
右上にローカル変数が表示されています。
wordが元の文字列、anagramが、ソート後の文字列です。
元の単語をアルファベット順に並び替えた結果を作り、それで辞書照合を行っています。
テストコード
用意しました
- anagram_test.py
import unittest as ut from Anagrams import anagram_search from tests.test_reader import Direct_Reader from wordlist_reader import word_reader class anagram_test(ut.TestCase): def test_anagram(self): """単体テスト用""" reader = Direct_Reader() searcher = anagram_search(reader) self.assertEqual(10, searcher.count(), "get length") self.assertEqual(7, len(searcher.get_complex_anagrams()), "get anagram count") def test_anagram_file(self): """時間計測用""" reader = word_reader() searcher = anagram_search(reader) self.assertEqual(20683 , len(searcher.get_complex_anagrams()), "get anagram count")
「単体テスト用」のほうですが、上で作った「test_reader.py」を使用したテストです。
単語数10、アナグラムとなっている文字列が二個以上ある要素を7となるように作っています。
その数と一致していれば、正しく作成されている、と判断しています。
「時間計測用」のほうですが、正解判断と、動作時間を計測するために存在します。
記載したロジックで、問題なく動作します。
なお、このロジックで動作させると、私の環境*2では0.913秒です。
出力
簡単なので、省略します。
get_complex_anagramsの結果を一つずつ出力するだけです。
さらに高速化する（案）
案としては、
Reader.read()の戻り値をiteratorにする
listを作らない分、早くなる気がします。*3
ぐらいでしょうか。
辞書を作る部分を、内包表記で作ればあるいは、とは思いますが、そんなに単純ではない気がします。
追加問題
get_complex_anagramsの結果をぐるぐるすれば取れるので…大丈夫でしょう。
おわりに
アナグラムの判定がうまくいった時点で、燃え尽きました。
辞書を内包表記で作れないか検証し、難しそうだなと思い、普通に辞書を使った方法に切り替えたら、すぐにできました。
内包でも、ジェネレーターを駆使すれば、できそうな気がします。
この作りにしておけば、追加問題はロジック自体外出し*4になるので、良い感じです。
CodeKata、今後も続けていきます。
