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是包含这些文件的目录的文件路径。

我从上到下解析文件，一次操作一个映射，最坏的情况是 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 回答