Beautiful Soupのパフォーマンス改善について

BSXPath.pyをいじっていて……

どうも、想像以上にパフォーマンスが悪いので、ボトルネックを調べていたのですが……。
ひとつには、Beautiful Soup にも原因がありそうだということが分かりました。
例えば、全ノード検索（soup.findAll()）は結構早いにも関らず、属性指定検索（soup.findAll(attrs={'class':'slow'})）になると想像以上に時間がかかります（後者は前者の数倍からひどいときには十数倍時間がかかる）。
比較にかかる分を考慮しても、ちょっとかかりすぎな気が……。

で、調べていくうちに

Beautiful Soupでは、ノード(Tag)の属性への初回アクセス時に、node.attrs（[(key1,val1),...,(keyN,valN)]のようなキーと値がペアになったtupleのリスト）をnode.attrMap（{key1:val1,...,keyN:valN}のような辞書）に変換していることが分かりました。


■該当箇所

    def _getAttrMap(self):
        """Initializes a map representation of this tag's attributes,
        if not already initialized."""
        if not getattr(self, 'attrMap'):
            self.attrMap = {}
            for (key, value) in self.attrs:
                self.attrMap[key] = value
        return self.attrMap

なので、初回アクセス時は遅く、2回目以降は速くなります。
従って、BSXPathのように、逐次属性を調べながら辿っていくような処理だと、かなりパフォーマンスに影響してしまいます。

対策

初期化直後に全ノードのattrMapを一括して作ってしまうことに。

    soup=BeautifulSoup(html)
    for node in soup.findAll(): node.attrMap=dict(node.attrs) # (key,val)のtupleリストなら、dict()で一括で辞書に変換可

初期化に多少時間を食うことにはなりますが、その後の処理が複雑であればあるほど、全体的なパフォーマンスは改善すると思います。


■サンプル

import sys
import datetime
from BeautifulSoup import *

MEASUREMENT=3

if __name__ == '__main__':
  
  html=sys.stdin.read()
  key='class'
  val='comment-content'
  
  for ci in range(1,1+MEASUREMENT):
    print u'%d回目:' % (ci)
   
    btime=datetime.datetime.now()
    soup=BeautifulSoup(html)
    nodes=soup.findAll(attrs={key:val})
    atime=datetime.datetime.now()
    stime=atime-btime
    print u'original:%d.%06d sec. :  <* %s="%s">=%d' % (stime.seconds,stime.microseconds,key,val,len(nodes))
  
    btime=datetime.datetime.now()
    soup=BeautifulSoup(html)
    for node in soup.findAll(): node.attrMap=dict(node.attrs) # ◆ attrMapの初期化処理
    nodes=soup.findAll(attrs={key:val})
    atime=datetime.datetime.now()
    stime=atime-btime
    print u'patched :%d.%06d sec. :  <* %s="%s">=%d' % (stime.seconds,stime.microseconds,key,val,len(nodes))
    
    print u''

■結果
type test.html | python testbs.py
※test.htmlは自分のココログから適当にとってきたもの（202,986バイト）。

1回目:
original:3.235000 sec. :  <* class="comment-content">=108
patched :0.937000 sec. :  <* class="comment-content">=108

2回目:
original:3.203000 sec. :  <* class="comment-content">=108
patched :0.954000 sec. :  <* class="comment-content">=108

3回目:
original:3.406000 sec. :  <* class="comment-content">=108
patched :1.062000 sec. :  <* class="comment-content">=108

patchedの方は、originalの約3倍強の速度（上記時間には、attrMapの初期化時間も含んでいます）。
attrMapの初期化にかかる時間を補ってあまりあるパフォーマンス向上だと思います*1。

*1:BSXPath.pyにも反映しました。かなり速くなったと思います（元が遅すぎたという説あり）