行の頭と末尾の位置のリストを得る


テキストエディタ

何行の何列目⇔文字列全体の何文字目



を相互に変換するためには、各行が文字列全体の何文字目から何文字目であるのかを知っておく必要があるだろう。思いつくいくつかの方法でどれが最速かを調べてみた。



サンプルに使った文字列は、wxPythonのSWIGで自動生成された553KB・14743行の_core.py.

#encoding:shift-jis
from __future__ import with_statement, division, print_function
import re
from itertools import *

#==============================================================================

def f1(ss):
   start = 0
   for m in re.finditer(r"\n", ss):
       yield (start, m.end())
       start = m.end()
   yield (start, len(ss))
  
def f2(ss):
   from cStringIO import StringIO
   io = StringIO(ss)
   start = 0
   for line in io:
       end = io.tell()
       yield start, end
       start = end

   #訂正
   #誤ここから
   #yield start, io.tell()
   #誤ここまで

   #正ここから
   if line.endswith("\n"):
       yield start, io.tell()
   #正ここまで

def f3(ss):
   lines = ss.split("\n")
   start = 0
   for length in imap(len, lines[:-1]):
       end = start + length + 1
       yield start, end
       start = end
   yield start, len(ss)

def f4(ss):
   start = 0
   while 1:
       end = ss.find("\n", start)
       if end == -1:
           break
       yield start, end + 1
       start = end + 1
   yield start, len(ss)
  
def f5(ss):
   from operator import methodcaller
   return imap(methodcaller("span"), re.finditer(r"[^\n]*?(\n|$)", ss))

def main():
   ss = open("_core.py", "rU").read()
   range_list1 = tuple(f1(ss))
   range_list2 = tuple(f2(ss))
   range_list3 = tuple(f3(ss))
   range_list4 = tuple(f4(ss))
   range_list5 = tuple(f5(ss))
  
   assert(range_list1 == range_list2)
   assert(range_list2 == range_list3)
   assert(range_list3 == range_list4)
   assert(range_list4 == range_list5)
   assert(range_list5 == range_list1)
  
   from timeit import Timer
   print(Timer("tuple(f1(ss))", "from __main__ import f1;ss=open('_core.py', 'rU').read()").timeit(1000))
   print(Timer("tuple(f2(ss))", "from __main__ import f2;ss=open('_core.py', 'rU').read()").timeit(1000))
   print(Timer("tuple(f3(ss))", "from __main__ import f3;ss=open('_core.py', 'rU').read()").timeit(1000))
   print(Timer("tuple(f4(ss))", "from __main__ import f4;ss=open('_core.py', 'rU').read()").timeit(1000))
   print(Timer("tuple(f5(ss))", "from __main__ import f5;ss=open('_core.py', 'rU').read()").timeit(1000))
  
#==============================================================================

if __name__ == "__main__":
   main()
#コードここまで


結果:

f1:19.181227223

f2:13.2834192614

f3:19.4852647473

f4:18.4638860526

f5:92.9775074765



素直にstring.findやstring.splitを使ったものが最速だと思ったが、
意外にもStringIOが最も速かった。StringIOには色々な機能がある分遅いと思ったのに。
Cで書かれたcStringIO.StringIOだからだろうか?
Pythonで書かれたStringIO.StringIOとも比較してみる。



cStringIO:12.2386730716

StringIO:86.60860249



やっぱりな〜。



追伸:ライブラリリファレンスを見てみると、

「StringIOモジュールで実装されているメモリファイルとは異なり、このモジュール(cStringIO)で提供されているものは、プレイン ASCII 文字列にエンコードできないユニコードを受け付けることができません。」
って、なわけで日本語を含む文字列の行分割にcStringIO.StringIOを使うのは無理みたい。
英語だけの場合も、Unicodeを渡すと妙なstr型の文字列が返ってきたりするので、
Unicodeを使うなら、cStringIO.StringIOを使うのはやめた方が良いようだ。

広告を非表示にする