4

範囲連結文法の CKY パーサーを作成しています。ツリーバンクを文法として使いたいので、文法が大きくなります。Python でプロトタイプ1を作成しました。数十文のツリーバンクをシミュレートするとうまく動作するように見えますが、メモリ使用量は受け入れられません。C++ で書いてみましたが、今まで C++ を使ったことがなかったので、とてもイライラしていました。ここにいくつかのデータがあります (n は、文法が基づいている文の数です):

n    mem
9    173M
18   486M
36   836M

この増加パターンは、ベスト ファースト アルゴリズムを考えると予想されるものですが、オーバーヘッドの量が気になるところです。heapy によるメモリ使用量は、これらの数値の 10 分の 1 であり、valgrind は同様のことを報告しています。この不一致の原因は何ですか? Python (または Cython) でそれについてできることはありますか? 多分それは断片化によるものですか？それとも、Python 辞書のオーバーヘッドですか?

背景: 2 つの重要なデータ構造は、エッジを確率にマッピングするアジェンダと、非終端記号と位置をエッジにマッピングする辞書です。アジェンダは heapdict (内部的に dict と heapq リストを使用) で実装され、チャートは非終端記号と位置をエッジにマッピングする辞書を使用します。議題は頻繁に挿入および削除され、チャートは挿入と検索のみを取得します。次のようなタプルでエッジを表します。

(("S", 111), ("NP", 010), ("VP", 100, 001))

文字列は文法からの非終端ラベルであり、位置はビットマスクとしてエンコードされます。構成要素が不連続な場合、複数の位置が存在する可能性があります。したがって、このエッジは「is Mary happy」の分析を表すことができます。ここで、「is」と「happy」は両方とも VP に属します。チャート ディクショナリは、このエッジの最初の要素 (「S」、111) によってインデックス付けされます。新しいバージョンでは、再利用によるメモリの節約を期待して、この表現を転置してみました:

(("S", "NP", "VP), (111, 100, 011))

Python は、最初の部分が異なる位置と組み合わせて発生した場合、最初の部分を 1 回だけ保存すると考えましたが、実際にはこれが正しいかどうかはわかりません。どちらの場合でも、違いはないように見えました。

したがって、基本的に私が疑問に思っているのは、Cython やさまざまなデータ構造を使用するなど、Python の実装をさらに追求する価値があるかどうか、または C++ でゼロから作成することが唯一の実行可能なオプションであるということです。

更新: いくつかの改善の後、メモリ使用量の問題はなくなりました。最適化された Cython バージョンに取り組んでいます。コードの効率を高めるための最も有用な提案に報奨金を授与します。http://student.science.uva.nl/~acranenb/plcfrs_cython.htmlに注釈付きのバージョンがあります。

1 https://github.com/andreasvc/disco-dop/ -- test.py を実行していくつかの文を解析します。Python 2.6、nltk、およびheapdictが必要です

4

3 に答える 3

2

CPython ではなく PyPy でアプリケーションを実行してみましたか?

PyPy は、共通点に気付き、不必要に複製することに伴うメモリ オーバーヘッドを回避する点で、CPython よりもはるかに優れています。

とにかく試してみる価値があります: http://pypy.org/

于 2011-03-27T14:58:20.317 に答える
2

Python は、最初の部分が異なる位置と組み合わせて発生した場合、最初の部分を 1 回だけ保存すると考えました。

必ずしも：

>>> ("S", "NP", "VP") is ("S", "NP", "VP")
False

internでこれらの多くを作成しているように見えるため、非終端記号を参照するすべての文字列が必要になる場合がありますrcgrules.py。タプルが必要な場合はintern、最初に文字列に変換します。

>>> intern("S NP VP") is intern(' '.join('S', 'NP', 'VP'))
True

それ以外の場合は、タプルを新たに構築する代わりに、タプルを「コピー」する必要があります。

(C++ を初めて使用する場合、そのようなアルゴリズムを書き直しても、メモリの利点があまり得られない可能性があります。まず、さまざまなハッシュ テーブルの実装を評価し、そのコンテナーでのコピー動作について学習する必要があります。boost::unordered_map小さなハッシュテーブルがたくさんあると非常に無駄であることがわかりました。)

于 2011-03-21T16:06:18.600 に答える
1

このような場合に最初に行うことは、常にプロファイルを作成することです。

15147/297    0.032    0.000    0.041    0.000 tree.py:102(__eq__)
15400/200    0.031    0.000    0.106    0.001 tree.py:399(convert)
        1    0.023    0.023    0.129    0.129 plcfrs_cython.pyx:52(parse)
6701/1143    0.022    0.000    0.043    0.000 heapdict.py:45(_min_heapify)
    18212    0.017    0.000    0.023    0.000 plcfrs_cython.pyx:38(__richcmp__)
10975/10875    0.017    0.000    0.035    0.000 tree.py:75(__init__)
     5772    0.016    0.000    0.050    0.000 tree.py:665(__init__)
      960    0.016    0.000    0.025    0.000 plcfrs_cython.pyx:118(deduced_from)
    46938    0.014    0.000    0.014    0.000 tree.py:708(_get_node)
25220/2190    0.014    0.000    0.016    0.000 tree.py:231(subtrees)
    10975    0.013    0.000    0.023    0.000 tree.py:60(__new__)
    49441    0.013    0.000    0.013    0.000 {isinstance}
    16748    0.008    0.000    0.015    0.000 {hasattr}

最初に気付いたのは、cython モジュール自体からの関数はほとんどないということです。それらのほとんどは tree.py モジュールから来ており、おそらくそれがボトルネックです。

cython 側に注目すると、richcmp関数が表示されます。

メソッド宣言に値の型を追加するだけで最適化できます

def __richcmp__(ChartItem self, ChartItem other, int op):
        ....

これで価値が下がる

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
....
18212    0.011    0.000    0.015    0.000 plcfrs_cython.pyx:38(__richcmp__)

単一の if の代わりに elif 構文を追加すると、cythonのスイッチ最適化が有効になります

    if op == 0: return self.label < other.label or self.vec < other.vec
    elif op == 1: return self.label <= other.label or self.vec <= other.vec
    elif op == 2: return self.label == other.label and self.vec == other.vec
    elif op == 3: return self.label != other.label or self.vec != other.vec
    elif op == 4: return self.label > other.label or self.vec > other.vec
    elif op == 5: return self.label >= other.label or self.vec >= other.vec

取得:

17963    0.002    0.000    0.002    0.000 plcfrs_cython.pyx:38(__richcmp__)

そのtree.py:399変換がどこから来たのかを理解しようとすると、dopg.py内のこの関数がずっと時間がかかることがわかりました

  def removeids(tree):
""" remove unique IDs introduced by the Goodman reduction """
result = Tree.convert(tree)
for a in result.subtrees(lambda t: '@' in t.node):
    a.node = a.node.rsplit('@', 1)[0]
if isinstance(tree, ImmutableTree): return result.freeze()
return result

ツリー内の各ノードが ChartItem であるかどうか、およびgetitem値が別の場所で使用されているかどうかはわかりませんが、この変更を追加すると、次のようになります。

cdef class ChartItem:
cdef public str label
cdef public str root
cdef public long vec
cdef int _hash
__slots__ = ("label", "vec", "_hash")
def __init__(ChartItem self, label, int vec):
    self.label = intern(label) #.rsplit('@', 1)[0])
    self.root = intern(label.rsplit('@', 1)[0])
    self.vec = vec
    self._hash = hash((self.label, self.vec))
def __hash__(self):
    return self._hash
def __richcmp__(ChartItem self, ChartItem other, int op):
    if op == 0: return self.label < other.label or self.vec < other.vec
    elif op == 1: return self.label <= other.label or self.vec <= other.vec
    elif op == 2: return self.label == other.label and self.vec == other.vec
    elif op == 3: return self.label != other.label or self.vec != other.vec
    elif op == 4: return self.label > other.label or self.vec > other.vec
    elif op == 5: return self.label >= other.label or self.vec >= other.vec
def __getitem__(ChartItem self, int n):
    if n == 0: return self.root
    elif n == 1: return self.vec
def __repr__(self):
    #would need bitlen for proper padding
    return "%s[%s]" % (self.label, bin(self.vec)[2:][::-1])

そしてmostprobableparseの内部：

from libc cimport pow
def mostprobableparse...
            ...
    cdef dict parsetrees = <dict>defaultdict(float)
    cdef float prob
    m = 0
    for n,(a,prob) in enumerate(derivations):
        parsetrees[a] += pow(e,prob)
        m += 1

私は得る：

         189345 function calls (173785 primitive calls) in 0.162 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
6701/1143    0.025    0.000    0.037    0.000 heapdict.py:45(_min_heapify)
        1    0.023    0.023    0.120    0.120 plcfrs_cython.pyx:54(parse)
      960    0.018    0.000    0.030    0.000 plcfrs_cython.pyx:122(deduced_from)
 5190/198    0.011    0.000    0.015    0.000 tree.py:102(__eq__)
     6619    0.006    0.000    0.006    0.000 heapdict.py:67(_swap)
     9678    0.006    0.000    0.008    0.000 plcfrs_cython.pyx:137(concat)

次のステップは heapify と deduced_from を最適化することです

deduce_from はもう少し最適化できます。

cdef inline deduced_from(ChartItem Ih, double x, pyCx, pyunary, pylbinary, pyrbinary, int bitlen):
cdef str I = Ih.label
cdef int Ir = Ih.vec
cdef list result = []
cdef dict Cx = <dict>pyCx
cdef dict unary = <dict>pyunary
cdef dict lbinary = <dict>pylbinary
cdef dict rbinary = <dict>pyrbinary
cdef ChartItem Ilh
cdef double z
cdef double y
cdef ChartItem I1h 
for rule, z in unary[I]:
    result.append((ChartItem(rule[0][0], Ir), ((x+z,z), (Ih,))))
for rule, z in lbinary[I]:
    for I1h, y in Cx[rule[0][2]].items():
        if concat(rule[1], Ir, I1h.vec, bitlen):
            result.append((ChartItem(rule[0][0], Ir ^ I1h.vec), ((x+y+z, z), (Ih, I1h))))
for rule, z in rbinary[I]:
    for I1h, y in Cx[rule[0][1]].items():
        if concat(rule[1], I1h.vec, Ir, bitlen):
            result.append((ChartItem(rule[0][0], I1h.vec ^ Ir), ((x+y+z, z), (I1h, Ih))))
return result

問題についてより多くの洞察が得られるにつれて、最適化を続けることができると確信していますが、ここで終わります。

一連の単体テストは、各最適化で微妙なエラーが発生しないことを確認するのに役立ちます。

補足として、タブの代わりにスペースを使用してみてください。

于 2011-03-30T12:09:32.153 に答える