時間のかかる原因を二分探索

Wikipediaのタグを正規表現で取り除くコードを書いていたのだが、一部のページに関してやたら時間が掛かる。

一体入力のどの部分が問題なのか？1ページ全体の中から人間がこれを探すのは手間なので自動化したい。

適当なタイムアウト時間を定めて「関数がタイムアウトするかどうか」で二分探索をする。

タイムアウトするかどうかの判定にはmultiprocessingを使えば良い。

code:python

def binarySearchBadInput(s):

import multiprocessing

left = 0

right = len(s)

while left + 1 < right:

print(left, right)

mid = (left + right) // 2

p = multiprocessing.Process(target=cleanWikiTag, args=(smid:, ))

p.start()

p.join(1)

if p.is_alive():

left = mid

else:

right = mid

return sleft:

print(binarySearchBadInput(getOnePage(2764)"text"):100)

出力例

code::

0 14161

0 7080

0 3540

0 1770

0 885

442 885

...

878 881

879 881

...

なるほど…、 を <ref>...</ref>より先に処理する必要があるのか…