2

次の構造の XML マッピング ファイルがあります。

<mappings>
    <mapping path="first">
        <parameter name="client_identifier">value1</parameter>
        <parameter name="device_identifier">value2</parameter>
        <parameter name="network_identifier">value3</parameter>
    </mapping>
    <mapping path="second">
        <parameter name="client_identifier">value1</parameter>
        <parameter name="device_identifier">value2</parameter>
        <parameter name="network_identifier">value4</parameter>
    </mapping>
    <mapping path="third">
        <parameter name="client_identifier">value1</parameter>
        <parameter name="device_identifier">value2</parameter>
    </mapping>
    <!-- hundreds/thousands more -->
</mappings>

クライアントはアプリケーションにリクエストを送信し、リクエストに含まれるいくつかのパラメーターに基づいて、いくつかのファイルを返します。上記のマッピング ファイルは、パラメーターを正しいファイルにマップします。要素のpath属性は、mappingそれらのファイルを含むディレクトリへのファイル パスです。

ファイルを上から下に解析し、一度に 1 つのマッピングを操作します。最悪の場合は O(n) です。のすべてのパラメータが<mapping>クライアント リクエストのパラメータと一致する場合は、ディレクトリの値を に返しますpath。

例 クライアント要求

client_identifier = value1
device_identifier = value2
network_identifier = value10213

The third mapping with path=third will be returned because the other mappings don't match network_identifier.

このファイルは、考えられるすべての組み合わせのために膨大な数のマッピングに成長する可能性があるため、解析/比較が高速なデータ構造 (デシジョン ツリー) があるかどうか疑問に思っていました。

ファイル自体は同じ構造を保持する必要がありますが、解析してメモリ内に別の構造を作成できます。

4

1 に答える 1

1

実際、あなたが説明しているのは決定木の例ではありません。それでも、プロセスを最適化する方法はいくつかあります。各マッピングで設定された属性に対して何らかのハッシュ値を計算することをお勧めします。未設定の属性については、「未設定」を意味する別の「偽の」値を追加します。その後、ファイルを反復処理し、クエリの属性セットに対して計算されたハッシュを、行内の各マッピングの属性セットのハッシュと比較します。ハッシュが同じ場合にのみ属性を比較します (衝突の問題を避けるため)。このアプローチにより、比較が大幅に高速化されます。

上記のアプローチをさらに改善することができます - ハッシュコードとこのハッシュコードを持つマッピングとの間のハッシュマップを作成します。ハッシュ コードのマッピングを、ファイル内で見つかった順序と同じ順序にしないでください。その後、同じハッシュ コードを持つマッピングのみを反復処理します。衝突が発生しない完璧なケースでは、これは可能な限り良好です。

于 2013-01-10T17:13:23.453 に答える