会社の開発合宿で文字列検索の速度アップをするというアルゴリズム問題があったので挑戦しました。
ちなみにわたしは既存のものを参考に類似品を作ったりリファクタリングしてちょっと改良するのが得意な、いわゆるコピペプログラマです。
1. 課題
事前に下記課題の一部を隠した状態で一緒に隠した状態で実装したサンプルとテストデータ、その処理結果ファイルが提供されます。
■プログラム内容
・複数のテキストファイルに対し、複数件の文字列の検索実現し、次を出力する
- 該当文字列が何件含まれているか（複数テキストでの総数）
- 該当文字列が含まれているテキストファイルの個数・コマンドプロンプト、もしくは、Windows PowerShell上で実行すること
・「program」に対して、次の引数を指定する
program フォルダ 入力ファイル 出力ファイル
フォルダ：検索対象ファイル（複数）を格納する
入力ファイル：検索文字列の一覧を記載
出力ファイル：検索結果・検索の際、大文字・小文字、全角・半角は区別する
・検索対象のテキスト、および、検索文字列はutf-8・検索文字列
- 1ファイル中に、改行区切りで150件
そのすべてについてファイル中の出現数を検索する
- 1文字以上の任意の長さ
- 空白・タブ・改行・特殊記号は含まない
- 任意の文字列であり、単語の一部の場合もある・検索結果
- 検索文字列の出現順に、タブ区切りで出現数を出力する
出現数は、複数のファイルの結果を合算する
2. サンプルプログラム
サンプルは、
- 該当文字列が含まれているテキストファイルの個数
の部分が未実装となっていました。
"""
指定フォルダ中のすべてのファイルから、指定された文字列の出現件数をカウントする
結果はTSVで出力する
python sample1.py text_folder strings_file result_file
"""
import sys
from pathlib import Path
class TextManager:
"""
テキストファイルの情報を管理するクラス
"""
def __init__(self, foldername):
'''
フォルダ中のファイルを読み込み格納する
Parameters
----------
foldername : str
フォルダ名
'''
self.__alllines = []
p = Path(foldername)
for filename in p.iterdir():
with open(filename, 'r', encoding='utf-8') as f:
lines = [s.strip() for s in f.readlines() if s.strip() != '']
self.__alllines.extend(lines)
def search(self, string_list):
'''
検索
検索文字列一覧で、登録テキストを検索する
Parameters
----------
string_list : List[str]
検索文字列の一覧
Returns
-------
Dict[str, int]
検索結果
'''
result = {}
for s in string_list:
count = self.__search_one(s)
result[s] = count
return result
def __search_one(self, string):
'''
文字列を検索する
Parameters
----------
string : str
検索文字列
Returns
-------
int
検索文字列が存在した数
'''
l = len(string)
count = 0
for line in self.__alllines:
for i in range(0, len(line)-l+1):
if string == line[i:i+l]:
count += 1
return count
if __name__ == "__main__":
args = len(sys.argv)
if args != 4:
print("USAGE: python sample1.py text_folder strings_file result_file")
sys.exit()
text_folder = sys.argv[1]
strings_file = sys.argv[2]
result_file = sys.argv[3]
# 対象ファイル群（フォルダ内のファイル）を読み込む
text_manager = TextManager(text_folder)
# 検索文字列を読み込む
search_strings = []
with open(strings_file, 'r', encoding='utf-8') as fi:
search_strings = [s.strip() for s in fi.readlines() if s.strip() != '']
# 検索実行: List[str] -> Dict[str, int]
result = text_manager.search(search_strings)
with open(result_file, 'w', encoding='utf-8') as fo:
# 検索文字列ファイル内に記述されている順に出力
for s in search_strings:
c = result.get(s, 0)
fo.write("{}\t{}\n".format(s, c))
3. 該当文字列が含まれているテキストファイルの個数を求める
全体のロジックを見直すのはかなりの労力を必要とするので、コピペプログラマとしてはできるだけ現状のロジックをそのまま使います。
まず、複数ファイルをまとめて読み込んでいた部分をファイルごとに分割して保存します。
高速化のチップスも多少考慮。
class TextManager:
"""
テキストファイルの情報を管理するクラス
"""
def __init__(self, foldername):
'''
フォルダ中のファイルを読み込み格納する
Parameters
----------
foldername : str
フォルダ名
'''
self.__alllines = []
__alllines_extend = self.__alllines.extend
p = Path(foldername)
for filename in p.iterdir():
__filelines = []
__filelines_extends = __filelines.extend
with open(filename, 'r', encoding='utf-8') as f:
f_readlines = f.readlines
lines = [s.strip() for s in f_readlines() if s.strip() != '']
__filelines_extends(lines)
self.__alllines.append(__filelines)
ひとつの検索文字列を全体から検索する部分の for ループにファイルごとのループを追加し、その中で検索文字列が見つかったらファイルのカウントを1増やし、最終的に検索文字列が存在した数と検索文字列が存在したファイル数を返します。
コメントアウトしてあるprint()は、正常に動いてるかどうかの確認をしながら修正していったなごりです。
def __search_one(self, string):
'''
文字列を検索する
Parameters
----------
string : str
検索文字列
Returns
-------
int
検索文字列が存在した数
int
検索文字列が存在したファイル数
'''
l = len(string)
count = 0
fcount = 0
# print(string, count, fcount)
for filelines in self.__alllines:
# print(filelines)
find = False
for line in filelines:
# print(line)
for i in range(0, len(line)-l+1):
if string == line[i:i+l]:
count += 1
find = True
if find:
fcount +=1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
検索取り纏めは、個別検索から戻り値を2つもらう対応。
def search(self, string_list):
'''
検索
検索文字列一覧で、登録テキストを検索する
Parameters
----------
string_list : List[str]
検索文字列の一覧
Returns
-------
Dict[str, int]
検索結果
Dict[str, int]
検索結果ファイル数
'''
result = {}
fresult = {}
for s in string_list:
rtn = self.__search_one(s)
result[s] = rtn[0]
fresult[s] = rtn[1]
return result, fresult
出力部も同じような対応なので省略。
これでお手軽に課題の最低条件である正解が出せる状態になりました。
4. 無駄な句読点のマッチングをなくす
現状では__search_one()で読み込んだ行の最初から最後まで、一文字ずつずらしながら同一判定をしています。
ここをどう高速化するかがポイントですが、検索対象文字列から対象外の文字を含まないブロックを切り出せばマッチングの効率が上がるはず。
というわけで、読み込み部で切り分けます。.split('[、。「」《》｜［＃］]') の部分です。
これ以外のカッコとかも対象にするべきですが、課題の対象が青空文庫から持ってきたファイルだったので、とりあえずこれで十分です。
def __init__(self, foldername):
'''
フォルダ中のファイルを読み込み格納する
Parameters
----------
foldername : str
フォルダ名
'''
self.__alllines = []
__alllines_append = self.__alllines.append
p = Path(foldername)
for filename in p.iterdir():
__filelines = []
__filelines_extends = __filelines.extend
with open(filename, 'r', encoding='utf-8') as f:
f_readlines = f.readlines
lines = [s.strip().split('[、。「」《》｜［＃］]')
for s in f_readlines() if s.strip() != '']
__filelines_extends(lines)
__alllines_append(__filelines)
切り分けたのに対応して__search_one()もループを増やします。
増やさなくてもいい書き方があるはずなんですが、とりあえずやっつけの方法だとループが必要でした。
というあたりの確認でprint()が役に立ちます。
実は事前にサンプルと一緒に配布されていたテストデータは英語だったので、引数なしの split() で切り分けるコーディングをしてたのですが、日本語だとそれではうまくいきません。結果がおかしいのでprintしたら、日本語だと一文字ずつ切り刻まれていました。
なのでいったんそこは外してからファイル数対応して、その後あらためてsplitしたというわけです。
def __search_one(self, string):
'''
文字列を検索する
Parameters
----------
string : str
検索文字列
Returns
-------
int
検索文字列が存在した数
int
検索文字列が存在したファイル数
'''
l = len(string)
count = 0
fcount = 0
# print(string, count, fcount)
for filelines in self.__alllines:
# print(filelines)
find = False
for line in filelines:
# print(line)
for sentence in line:
for i in range(0, len(sentence)-l+1):
if string == sentence[i:i+l]:
count += 1
find = True
# print(sentence, string, sep='\t')
if find:
fcount +=1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
5. マッチングの見直し
文字列の出現を調べるのに1文字ずつずらしながら比較するのはいかにも効率が悪い。
スクリプト言語は、どんなに工夫しても自前で比較していてはスピードは上がりません。
標準ライブラリの関数でなんとかできればそっちの方が絶対速い。
String in Stringのメソッドは知ってたのですが、ひとつの対象に複数回現れたらダメじゃんってことで却下してました。
記憶力には自信がないので、とりあえず検索します。
googleで検索 「python 文字列 マッチ」
ああ、ありましたよ欲しかった関数が。
Pythonで文字列を検索（〜を含むか判定、位置取得、カウント）
というわけで、__search_one の一番中の処理を書き換え。
for line in filelines:
# print(line)
for sentence in line:
# for i in range(0, len(sentence)-l+1):
# if string == sentence[i:i+l]:
c = sentence.count(string)
if c > 0:
count += c
find = True
~~~
これで処理時間が桁違いに速くなりました。
# 6. 処理の見直し
対象から出現回数を一発で見つけられるようになると、4. で追加した `split` はループを増やすだけなのでむしろ速度低下の原因です。
刻む必要もなくなったので、そのあたりを元に戻します。
ここでは `__search_one` の中だけ書きます。
```python
for line in filelines:
# print(line)
c = line.count(string)
if c > 0:
count += c
find = True
7. 最後の一押し
count を使って一発で出現個数がわかるのですから、1行ずつ読む意味はありません。
今回の課題ではメモリの使用量の制限はなく、検証環境の搭載メモリが書かれているだけ。
ファイル全部読むなら、行単位で読んでもファイル単位で読んでも変わりはありません。
というわけで、ファイル一括読みに変更。
変数名をもっと適切な物に変更すべきでしたがあまり考えてませんでした。
def __init__(self, foldername):
'''
フォルダ中のファイルを読み込み格納する
Parameters
----------
foldername : str
フォルダ名
'''
self.__alllines = []
__alllines_extend = self.__alllines.extend
p = Path(foldername)
for filename in p.iterdir():
with open(filename, 'r', encoding='utf-8') as f:
lines = f.read()
self.__alllines.append(lines)
実際の検索部分はシンプルそのもの
def __search_one(self, string):
'''
文字列を検索する
Parameters
----------
string : str
検索文字列
Returns
-------
int
検索文字列が存在した数
int
検索文字列が存在したファイル数
'''
count = 0
fcount = 0
# print(string, count, fcount)
for lines in self.__alllines:
c = lines.count(string)
if c > 0:
count += c
fcount += 1
# print(string, count, fcount)
# print(string, count, fcount)
return count, fcount
これで速度は最初に正解を出したものの116倍高速になりました。
8. 総括
アルゴリズム問題なので、本来はマッチングの方法を工夫すべきだったはずです。
実際、count を使わずに最初のコードの半分の時間で処理するコードを書いた人もいました。
しかし、スクリプト言語でアルゴリズムをあれこれ工夫しても、実体をCで書かれたりしているライブラリの関数には勝てません。
適切なライブラリが存在するか、知っていればあっという間に正解にたどり着くでしょう。
実は途中参加であっという間に桁違いのスコアを出した人がいて、そこからいろいろ考えて検索して最終地点に到達しました。
ライブラリ関数でずるせずに半分の時間で処理するアルゴリズムってどんなやり方なのか知りたいですね。