1

オンザフライパーサーを使用することのスペース関連の利点は、事前に生成されたルックアップテーブルの時間関連の利点を上回りますか？

ロングバージョン：

私は化学参照ツールを作成しており、特定のパターンに準拠する数式に自動的に名前を付ける機能が含まれています。例C[n]H[2n+2] => [n]ane; ここ[n]で、はLHSの整数です。RHS上の名前の配列へのインデックス。（meth、、eth…）

私が見る限り、これは2つの方法のいずれかで実装できます。

  1. formula <=> nameペアのキー/値デュアルルックアップディクショナリを事前に生成します。アプリケーションの起動時（起動が遅い）、またはアプリケーションとともに公開される静的リスト（ダウンロードが遅い）。

  2. 数式は、カスタムビルドのパーサーによってその場で評価されます。

アプローチ1では、name =>式のルックアップは、桁違いに単純になります。ただし、ジェネレーターは、アプリケーションで数十メガバイトのデータを出荷する場合を除いて、の値を事前設定し、かなり低くする必要がありますn。

これをさらに複雑にするのは、数式がいくつかの項を持つことができるという事実です。などC[n]H[2n+1]OC[n']H[2n'+1]; そして、これらのそれぞれについて、可能な一致の数は、幾何学的に増加しnます。さらに、このアプローチを使用すると、誰のビジネスのようにRAMを消費します。

アプローチ2では、かなり小さいルックアップテーブルを使用するかなり大きな値をサポートできますnが、name=>式のルックアップはやや複雑になります。アプリケーションと一緒に出荷するための事前生成ファイルと比較すると、新しいデータファイルを出荷しなくても、生成ロジックのエラーを修正できます。

これには、各式をいくつかのルールの大まかなテストと照合して、適合するかどうかを判断する必要もあります。ルールがたくさんある場合は、時間がかかり、インターフェイスの速度が著しく低下する可能性があります。

したがって、問題は次のとおりです。

  1. 私が説明できなかったトレードオフ、または私が考慮しなかったアプローチに考慮事項はありますか？

  2. オンザフライパーサーを使用する利点は、実装の複雑さの増大を正当化するのでしょうか？

4

1 に答える 1

1

2番目のアプローチを使用する必要があります。

可能な解決策の 1 つは貪欲なアルゴリズムです。一連の変換を正規表現 (パターンのテストに使用) として定義し、regexp 一致オブジェクトが与えられ、変換された文字列を返す関数を定義します。

正規表現は、必要なものを直接処理できるほど強力ではありません。代わりに、次のようにする必要があります。

m = re.match(r"C\[(\d+)\]H\[(\d+)]\]", formula)
if m:
    C_count, H_count = int(m.group(1)), int(m.group(2))
    match_size = len(m.group(0))
    if C_count*2+2 == H_count:
        replacement = alkane_lookup[C_count]
    elif C_count*2 == H_count:
        replacement = alkene_lookup[C_count]
    ...
    else:
        replacement = m.group(0)  # no replacement available

（さらに、他の可能性についてはさらに多くの可能性があります）

次に、それを次のようなループに埋め込みます。

formula = "...."
new_formula = ""
while formula:
    match_size, replacement = find_replacement(formula)
    new_formula += replacement
    formula = formula[match_size:]

(何も一致しない場合を処理する必要があります。考えられる方法の 1 つは、次の要素とカウントのみを返す find_replacement() の最後にすべての可能な要素のリストを含めることです。)

これは貪欲なアルゴリズムであり、最小の解を保証するものではありません。それはもっと複雑ですが、化学者自身が正しい形についてさまざまな考えを持っているので、私はそれについてあまり心配しません.

于 2011-10-07T18:56:04.133 に答える