algorithm - 用于在多个条件下做出决策的数据结构

Question

我有一个具有这种结构的 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.

由于所有可能的组合，这个文件可以增长到大量的映射，我想知道是否有一些数据结构(决策树)可以更快地解析/比较。

文件本身必须保持相同的结构，但我可以解析它并在内存中创建不同的结构。

Answer 1

事实上你描述的不是决策树的例子。还有一些方法可以优化您的流程。我建议您为每个映射中的属性集计算某种哈希值。对于未设置的属性，添加另一个表示“未设置”的“假”值。之后遍历文件并将为查询的属性集计算的散列与一行中每个映射的属性集的散列进行比较。仅当哈希值相同时才比较属性(以避免冲突问题)。这种方法应该可以显着加快比较速度。

您可以进一步改进上述方法 - 在哈希码和具有此哈希码的映射之间创建一个 HashMap 。不要让散列码的映射与在文件中找到的顺序相同!之后，您将只迭代具有相同哈希码的映射，并且在没有发生冲突的完美情况下，这将是您能得到的最好的。