たつをの ChangeLog : 2023-10-17

Python で Perl の Search::Dict[2013-08-01-1] 相当のライブラリないかなー、と思いつつ過ごす日々です。
最近、二分探索 (binary search) のロジックを Python で書いてソート済みテキストを検索するというコードをネットで見つけました。
確実に遅くなるだろうけどとりあえず実用性を調べてみることに。

1

まずこちらのスクリプトを試しました。

• lookコマンドのpythonによる実装
  
  コード

しかしうまく検索できないこと多々あり。
"/usr/share/dict/words" の各ワードをASCII順序でソート済みの "/usr/share/dict/words" から検索して取り出す実験を行ったところ約 27% (171318/235970) の単語にヒットしませんでした。
コード中の「途中の行は読み捨てる」とコメントされてる箇所に問題がありそうです。
捨てちゃいけないものが混じっているのかと。

実験コマンド:

cat WORDS-ASCII_SORTED | xargs -L1 ./look.py > res

2

1の「lookコマンドのpythonによる実装」で参考として挙げられていたこちらも調べてみました。

• Search a large sorted text file in Python

こちらはというと、二分探索の各ステップで行頭までファイルポインタを移動するときのこちらのコードに少々問題が。

while p >= 0:
    self.f.seek(p)
    if self.f.read(1) == '\n': break
    p -= 1

一行が長いとき（例えば 5000 バイトなど）に無茶苦茶遅くなるのです。
C言語とかなら問題ないのですが、スクリプトレベルでやるには厳しいですね。

3

ということで、結局既存のものをそのまま利用するのはあきらめて、前述の1と2のコードをベースに書き直しました。
（なお、1でやった実験と同じ実験をしたら単語ヒット率 100% でした）

• ソート済みテキストを二分探索する look コマンドの pure Python 実装 · GitHub
  
  コード

ポイントは行頭までのファイルポインタ移動 (go_to_line_top()) に readline() を使ったこと。
readline() はコンパイルされた実装なので速いです。

ファイルポインタ行頭移動ロジック:

• 事前準備: そのファイルに含まれる行の最大長＋αを buffer_size にセット
• 現在のファイルポインタから buffer_size 分前方に seek()
• そこから readline() を繰り返して最終行を取得
• 最終行の長さ分前方に seek ()
• 行頭にファイルポインタが移動できた！

先日の実験で最速だった look.pl (Search::Dict 使用) と比べると 6倍くらい時間がかかりました（buffer_size を小さくすると縮まります）。
ここらへんがスクリプト言語ロジック記述の限界かなあ。

• 手軽に使える look コマンドの速度比較[2023-09-03-1]
  • 先日の実験
  • 今回の looks.py での結果 (buffer_size=10000) も追記しました

おわりに

look コマンドの Perl モジュールである Search::Dict。これに相当の Python ライブラリが見つからないので、Python スクリプトで実現する方法の実用性を調べました。

その結果、Search::Dict 版には及ばないもののそこそこの速さでした。
このくらいの速度差ならば普段の私のタスクでは実用上問題ないレベルかも。
Perl が使えないときとか、Python プログラムの中から使いたいときとか。

とはいえ、やはり Perl の Search::Dict 相当の Python ライブラリ (C extention?) を切望します！
情報あったら教えてくださいませ。