- Key1,Key2,Key3,Value
- null,null,1
- 1,2
- 9,21
- 1,3,3
- null,2,4
- 1,5
使用此配置集,然后我需要在bazillion(给予或接受){Key1,Key3}元组上进行查找以获得“有效”值.使用的有效值基于密钥/优先级总和,在此示例中:
- Key1 - Priority 10
- Key2 - Priority 7
- Key3 - Priority 5
所以这对键1 =无效,密钥2 =匹配和Key3 =匹配一个配置条目的查询specifc击败了一个具有键1 =匹配,密钥2 = NULL和Key3 =无效,因为密钥2密钥3优先> Key1优先级……那有意义吗?!
- given a key of {1,3} the value should be 5.
- given a key of {3,3} the value should be 4.
- given a key of {8,10,11} the value should be 1.
- given a key of {1,11} the value should be 2.
- given a key of {9,3} the value should be 4.
- given a key of {9,3} the value should be 21.
是否有一种简单的方法来建模这种通用的数据结构和查找算法,因为#和键的类型是可变的,并且可以动态定义“真值表”(查找的顺序)?作为泛型而不是整数的类型将是完美的(浮点数,双精度数,ushorts等),并且很容易扩展到n个键也很重要!
估计的“配置”表大小:1,000行,查找估计的“数据”:1e14
这给出了预期的性能类型.
我正在寻找C#中的想法或者可以轻松转换为C#的东西.
解决方法
这个结构的基本思想是树,这样在深度为i时,你将遵循规则的第i个元素,如果在字典中找不到它,则为null分支.
要构建树,我将以递归方式构建它.从包含其池中所有可能规则的根节点开始.过程:
>将给定到达节点所用路径的当前规则的分数定义池中每个规则的当前值,如果无法获取路径,则定义-infinity.例如,如果当前节点位于根的“1”分支,则规则{null,1}的得分为0,而规则{1,2}将得分10
>将池中每个规则的最大值定义为其当前分数,以及剩余密钥的分数.例如,那么规则{null,1,1}的得分为12(0 7 5),2}得分10(10 0 0).
>从池中删除最大值低于池中最高当前值的元素
>如果只有一个规则,则使用该规则制作一个叶子.
>如果池中还有多个规则,并且没有其他键,那么??? (从问题描述中不清楚.我假设最高的一个)
>对于当前池中第(i 1)个键的每个唯一值,并且为null,使用当前池从当前节点构造新树.
作为最终的优化检查,我会检查节点的所有子节点是否都是叶子,如果它们都包含相同的规则,则使该节点成为具有该值的叶子.
给出以下规则:
- null,null = 1
- 1,null = 2
- 9,null = 21
- 1,3 = 3
- null,3 = 4
- 1,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},1},{ new int?[]{1,2},{ new int?[]{9,21},3},3 },{ new int?[]{null,4 },5 }
- };
- Console.WriteLine("5 == {0}",config[1,3]);
- Console.WriteLine("4 == {0}",config[3,3]);
- Console.WriteLine("1 == {0}",config[8,11]);
- Console.WriteLine("2 == {0}",11]);
- Console.WriteLine("4 == {0}",config[9,3]);
- Console.WriteLine("21 == {0}",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,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,prunedPool,null);
- foreach (KeyValuePair<int?[],int> rule in pool)
- {
- int? branch = rule.Key[usedValues.Count];
- if (branch != null && !children.ContainsKey((int)branch))
- {
- AddChild(usedValues,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,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,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);
- }
- }