有没有人创建过"默认地图"数据结构,或者有什么想法？

Question

我有一些配置数据,我想在代码中建模如下:

Key1,  Key2,  Key3,  Value
null,  null,  null,  1
1,     null,  null,  2
9,     null,  null,  21
1,     null,  3,     3
null,  2,     3,     4
1,     2,     3,     5

使用此配置集,然后我需要在bazillion(给予或接受){Key1,Key2,Key3}元组上进行查找以获得"有效"值.使用的有效值基于密钥/优先级总和,在此示例中:

Key1 - Priority 10
Key2 - Priority 7
Key3 - Priority 5

因此,具有Key1 = null,Key2 = match和Key3 = match的配置条目的特定查询击败了一个具有Key1 = match,Key2 = null和Key3 = null,因为Key2 + Key3优先级> Key1优先级...有道理？!

given a key of {1, 2, 3} the value should be 5.
given a key of {3, 2, 3} the value should be 4.
given a key of {8, 10, 11} the value should be 1.
given a key of {1, 10, 11} the value should be 2.
given a key of {9, 2, 3} the value should be 4.
given a key of {8, 2, 3} the value should be 4.
given a key of {9, 3, 3} the value should be 21.

是否有一种简单的方法来建模这种通用的数据结构和查找算法,因为#和键的类型是可变的,并且可以动态定义"真值表"(查找的顺序)？作为泛型而不是整数的类型将是完美的(浮点数,双精度数,ushorts等),并且很容易扩展到n个键也很重要!

估计的"配置"表大小:1,000行,查找估计的"数据":1e14

这给出了预期的性能类型.

我正在寻找C#中的想法或者可以轻松转换为C#的东西.

Answer 1

我假设规则很少，并且您要根据规则检查大量项目。在这种情况下，花费内存和前期时间来预先计算一个可以帮助您更快地找到对象的结构可能是值得的。

此结构的基本思想是一棵树，在深度 i 处，您将遵循规则的第 i 个元素，或者如果在字典中找不到它，则遵循空分支。

为了构建这棵树，我会递归地构建它。从包含其池中所有可能规则的根节点开始。流程：

• 将池中每个规则的当前值定义为给定到达节点所采取的路径的当前规则的分数，如果不可能采取该路径，则将其定义为 - 无穷大。例如，如果当前节点位于根的“1”分支，则规则 {null, null, null, 1} 的得分将为 0，而规则 {1, null, null, 2} 的得分将为得分为 10
• 将池中每个规则的最大值定义为其当前分数，加上其余键的分数。例如，如果当前节点位于根的“1”分支，则规则 {null, 1, 2, 1} 的得分为 12 (0 + 7 + 5)，规则 {1, null, null, 2} 的得分为 10 (10 + 0 + 0)。
• 从池中移除最大值低于池中当前最高值的元素
• 如果只有一条规则，则用该规则制作一片叶子。
• 如果池中还剩下多个规则，并且没有更多的键那么??? （从问题描述中并不清楚这一点。我假设采用最高的）
• 对于当前池中第 (i+1) 个键的每个唯一值和 null，使用当前池从当前节点构造一棵新树。

作为最终的优化检查，我将检查节点的所有子节点是否都是叶子，以及它们是否都包含相同的规则，然后使该节点成为具有该值的叶子。

给出以下规则：

null,  null,  null = 1
1,     null,  null = 2
9,     null,  null = 21
1,     null,  3    = 3
null,  2,     3    = 4
1,     2,     3    = 5

一个示例树：

       key1   key2   key3
root:
 |----- 1
 |      |----- 2          = 5
 |      |-----null
 |             |----- 3   = 3
 |             |-----null = 2
 |----- 9
 |      |----- 2
 |      |      |----- 3   = 4
 |      |      |-----null = 21
 |      |-----null        = 21
 |-----null
        |----- 2          = 4
        |-----null        = 1

如果您以这种方式构建树，首先从最高值的键开始，那么您可能可以删除针对后面的键的大量检查。

编辑添加代码：

class Program
{
    static void Main(string[] args)
    {
        Config config = new Config(10, 7, 5)
        {
            { new int?[]{null,  null,  null},  1},
            { new int?[]{1,     null,  null},  2},
            { new int?[]{9,     null,  null},  21},
            { new int?[]{1,     null,  3},     3 },
            { new int?[]{null,  2,     3},     4 },
            { new int?[]{1,     2,     3},     5 }
        };

        Console.WriteLine("5 == {0}", config[1, 2, 3]);
        Console.WriteLine("4 == {0}", config[3, 2, 3]);
        Console.WriteLine("1 == {0}", config[8, 10, 11]);
        Console.WriteLine("2 == {0}", config[1, 10, 11]);
        Console.WriteLine("4 == {0}", config[9, 2, 3]);
        Console.WriteLine("21 == {0}", config[9, 3, 3]);            
        Console.ReadKey();
    }
}


public class Config : IEnumerable
{
    private readonly int[] priorities;
    private readonly List<KeyValuePair<int?[], int>> rules =
        new List<KeyValuePair<int?[], int>>();
    private DefaultMapNode rootNode = null;

    public Config(params int[] priorities)
    {
        // In production code, copy the array to prevent tampering
        this.priorities = priorities;
    }

    public int this[params int[] keys]
    {
        get
        {
            if (keys.Length != priorities.Length)
            {
                throw new ArgumentException("Invalid entry - wrong number of keys");
            }

            if (rootNode == null)
            {
                rootNode = BuildTree();
                //rootNode.PrintTree(0);
            }

            DefaultMapNode curNode = rootNode;
            for (int i = 0; i < keys.Length; i++)
            {
                // if we're at a leaf, then we're done
                if (curNode.value != null)
                    return (int)curNode.value;

                if (curNode.children.ContainsKey(keys[i]))
                    curNode = curNode.children[keys[i]];
                else
                    curNode = curNode.defaultChild;
            }

            return (int)curNode.value;
        }
    }

    private DefaultMapNode BuildTree()
    {
        return new DefaultMapNode(new int?[]{}, rules, priorities);
    }

    public void Add(int?[] keys, int value)
    {
        if (keys.Length != priorities.Length)
        {
            throw new ArgumentException("Invalid entry - wrong number of keys");
        }
        // Again, copy the array in production code
        rules.Add(new KeyValuePair<int?[], int>(keys, value));

        // reset the tree to know to regenerate it.
        rootNode = null;
    }

    public IEnumerator GetEnumerator()
    {
        throw new NotSupportedException();
    }

}


public class DefaultMapNode
{
    public Dictionary<int, DefaultMapNode> children = new Dictionary<int,DefaultMapNode>();
    public DefaultMapNode defaultChild = null; // done this way to workaround dict not handling null
    public int? value = null;

    public DefaultMapNode(IList<int?> usedValues, IEnumerable<KeyValuePair<int?[], int>> pool, int[] priorities)
    {
        int bestScore = Int32.MinValue;

        // get best current score
        foreach (KeyValuePair<int?[], int> rule in pool)
        {
            int currentScore = GetCurrentScore(usedValues, priorities, rule);
            bestScore = Math.Max(bestScore, currentScore);
        }

        // get pruned pool
        List<KeyValuePair<int?[], int>> prunedPool = new List<KeyValuePair<int?[], int>>();
        foreach (KeyValuePair<int?[], int> rule in pool)
        {
            int maxScore = GetCurrentScore(usedValues, priorities, rule);
            if (maxScore == Int32.MinValue)
                continue;

            for (int i = usedValues.Count; i < rule.Key.Length; i++)
                if (rule.Key[i] != null)
                    maxScore += priorities[i];

            if (maxScore >= bestScore)
                prunedPool.Add(rule);
        }

        // base optimization case, return leaf node
        // base case, always return same answer
        if ((prunedPool.Count == 1) || (usedValues.Count == prunedPool[0].Key.Length))
        {
            value = prunedPool[0].Value;
            return;
        }

        // add null base case
        AddChild(usedValues, priorities, prunedPool, null);
        foreach (KeyValuePair<int?[], int> rule in pool)
        {
            int? branch = rule.Key[usedValues.Count];
            if (branch != null && !children.ContainsKey((int)branch))
            {
                AddChild(usedValues, priorities, prunedPool, branch);
            }
        }


        // if all children are the same, then make a leaf
        int? maybeOnlyValue = null;
        foreach (int v in GetAllValues())
        {
            if (maybeOnlyValue != null && v != maybeOnlyValue)
                return;
            maybeOnlyValue = v;
        }
        if (maybeOnlyValue != null)
            value = maybeOnlyValue;

    }

    private static int GetCurrentScore(IList<int?> usedValues, int[] priorities, KeyValuePair<int?[], int> rule)
    {
        int currentScore = 0;
        for (int i = 0; i < usedValues.Count; i++)
        {
            if (rule.Key[i] != null)
            {
                if (rule.Key[i] == usedValues[i])
                    currentScore += priorities[i];
                else
                    return Int32.MinValue;
            }
        }
        return currentScore;
    }

    private void AddChild(IList<int?> usedValues, int[] priorities, List<KeyValuePair<int?[], int>> prunedPool, Nullable<int> nextValue)
    {
        List<int?> chainedValues = new List<int?>();
        chainedValues.AddRange(usedValues);
        chainedValues.Add(nextValue);            
        DefaultMapNode node = new DefaultMapNode(chainedValues, prunedPool, priorities);
        if (nextValue == null)
            defaultChild = node;
        else
            children[(int)nextValue] = node;
    }

    public IEnumerable<int> GetAllValues()
    {
        foreach (DefaultMapNode child in children.Values)
            foreach (int v in child.GetAllValues())
                yield return v;
        if (defaultChild != null)
            foreach (int v in defaultChild.GetAllValues())
                yield return v;
        if (value != null)
            yield return (int)value;
    }

    public void PrintTree(int depth)
    {
        if (value == null)
            Console.WriteLine();
        else
        {
            Console.WriteLine(" = {0}", (int)value);
            return;
        }

        foreach (KeyValuePair<int, DefaultMapNode> child in children)
        {
            for (int i=0; i<depth; i++)
                Console.Write("    ");
            Console.Write(" {0}  ", child.Key);                
            child.Value.PrintTree(depth + 1);
        }
        for (int i = 0; i < depth; i++)
            Console.Write("    ");
        Console.Write("null");
        defaultChild.PrintTree(depth + 1);
    }
}