c# – 有没有人创建过“默认地图”数据结构,或有任何想法?

前端之家收集整理的这篇文章主要介绍了c# – 有没有人创建过“默认地图”数据结构,或有任何想法?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我有一些配置数据,我想在代码中建模如下:
  1. Key1,Key2,Key3,Value
  2. null,null,1
  3. 1,2
  4. 9,21
  5. 1,3,3
  6. null,2,4
  7. 1,5

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

  1. Key1 - Priority 10
  2. Key2 - Priority 7
  3. Key3 - Priority 5

所以这对键1 =无效,密钥2 =匹配和Key3 =匹配一个配置条目的查询specifc击败了一个具有键1 =匹配,密钥2 = NULL和Key3 =无效,因为密钥2密钥3优先> Key1优先级……那有意义吗?!

  1. given a key of {1,3} the value should be 5.
  2. given a key of {3,3} the value should be 4.
  3. given a key of {8,10,11} the value should be 1.
  4. given a key of {1,11} the value should be 2.
  5. given a key of {9,3} the value should be 4.
  6. 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,使用当前池从当前节点构造新树.

作为最终的优化检查,我会检查节点的所有子节点是否都是叶子,如果它们都包含相同的规则,则使该节点成为具有该值的叶子.

给出以下规则:

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

示例树:

  1. key1 key2 key3
  2. root:
  3. |----- 1
  4. | |----- 2 = 5
  5. | |-----null
  6. | |----- 3 = 3
  7. | |-----null = 2
  8. |----- 9
  9. | |----- 2
  10. | | |----- 3 = 4
  11. | | |-----null = 21
  12. | |-----null = 21
  13. |-----null
  14. |----- 2 = 4
  15. |-----null = 1

如果以这种方式构建树,首先从最高值键开始,然后您可以删除对后面的键进行大量检查.

编辑以添加代码

  1. class Program
  2. {
  3. static void Main(string[] args)
  4. {
  5. Config config = new Config(10,7,5)
  6. {
  7. { new int?[]{null,null},1},{ new int?[]{1,2},{ new int?[]{9,21},3},3 },{ new int?[]{null,4 },5 }
  8. };
  9.  
  10. Console.WriteLine("5 == {0}",config[1,3]);
  11. Console.WriteLine("4 == {0}",config[3,3]);
  12. Console.WriteLine("1 == {0}",config[8,11]);
  13. Console.WriteLine("2 == {0}",11]);
  14. Console.WriteLine("4 == {0}",config[9,3]);
  15. Console.WriteLine("21 == {0}",3]);
  16. Console.ReadKey();
  17. }
  18. }
  19.  
  20.  
  21. public class Config : IEnumerable
  22. {
  23. private readonly int[] priorities;
  24. private readonly List<KeyValuePair<int?[],int>> rules =
  25. new List<KeyValuePair<int?[],int>>();
  26. private DefaultMapNode rootNode = null;
  27.  
  28. public Config(params int[] priorities)
  29. {
  30. // In production code,copy the array to prevent tampering
  31. this.priorities = priorities;
  32. }
  33.  
  34. public int this[params int[] keys]
  35. {
  36. get
  37. {
  38. if (keys.Length != priorities.Length)
  39. {
  40. throw new ArgumentException("Invalid entry - wrong number of keys");
  41. }
  42.  
  43. if (rootNode == null)
  44. {
  45. rootNode = BuildTree();
  46. //rootNode.PrintTree(0);
  47. }
  48.  
  49. DefaultMapNode curNode = rootNode;
  50. for (int i = 0; i < keys.Length; i++)
  51. {
  52. // if we're at a leaf,then we're done
  53. if (curNode.value != null)
  54. return (int)curNode.value;
  55.  
  56. if (curNode.children.ContainsKey(keys[i]))
  57. curNode = curNode.children[keys[i]];
  58. else
  59. curNode = curNode.defaultChild;
  60. }
  61.  
  62. return (int)curNode.value;
  63. }
  64. }
  65.  
  66. private DefaultMapNode BuildTree()
  67. {
  68. return new DefaultMapNode(new int?[]{},rules,priorities);
  69. }
  70.  
  71. public void Add(int?[] keys,int value)
  72. {
  73. if (keys.Length != priorities.Length)
  74. {
  75. throw new ArgumentException("Invalid entry - wrong number of keys");
  76. }
  77. // Again,copy the array in production code
  78. rules.Add(new KeyValuePair<int?[],int>(keys,value));
  79.  
  80. // reset the tree to know to regenerate it.
  81. rootNode = null;
  82. }
  83.  
  84. public IEnumerator GetEnumerator()
  85. {
  86. throw new NotSupportedException();
  87. }
  88.  
  89. }
  90.  
  91.  
  92. public class DefaultMapNode
  93. {
  94. public Dictionary<int,DefaultMapNode> children = new Dictionary<int,DefaultMapNode>();
  95. public DefaultMapNode defaultChild = null; // done this way to workaround dict not handling null
  96. public int? value = null;
  97.  
  98. public DefaultMapNode(IList<int?> usedValues,IEnumerable<KeyValuePair<int?[],int>> pool,int[] priorities)
  99. {
  100. int bestscore = Int32.MinValue;
  101.  
  102. // get best current score
  103. foreach (KeyValuePair<int?[],int> rule in pool)
  104. {
  105. int currentscore = GetCurrentscore(usedValues,priorities,rule);
  106. bestscore = Math.Max(bestscore,currentscore);
  107. }
  108.  
  109. // get pruned pool
  110. List<KeyValuePair<int?[],int>> prunedPool = new List<KeyValuePair<int?[],int>>();
  111. foreach (KeyValuePair<int?[],int> rule in pool)
  112. {
  113. int maxscore = GetCurrentscore(usedValues,rule);
  114. if (maxscore == Int32.MinValue)
  115. continue;
  116.  
  117. for (int i = usedValues.Count; i < rule.Key.Length; i++)
  118. if (rule.Key[i] != null)
  119. maxscore += priorities[i];
  120.  
  121. if (maxscore >= bestscore)
  122. prunedPool.Add(rule);
  123. }
  124.  
  125. // base optimization case,return leaf node
  126. // base case,always return same answer
  127. if ((prunedPool.Count == 1) || (usedValues.Count == prunedPool[0].Key.Length))
  128. {
  129. value = prunedPool[0].Value;
  130. return;
  131. }
  132.  
  133. // add null base case
  134. AddChild(usedValues,prunedPool,null);
  135. foreach (KeyValuePair<int?[],int> rule in pool)
  136. {
  137. int? branch = rule.Key[usedValues.Count];
  138. if (branch != null && !children.ContainsKey((int)branch))
  139. {
  140. AddChild(usedValues,branch);
  141. }
  142. }
  143.  
  144.  
  145. // if all children are the same,then make a leaf
  146. int? maybeOnlyValue = null;
  147. foreach (int v in GetAllValues())
  148. {
  149. if (maybeOnlyValue != null && v != maybeOnlyValue)
  150. return;
  151. maybeOnlyValue = v;
  152. }
  153. if (maybeOnlyValue != null)
  154. value = maybeOnlyValue;
  155.  
  156. }
  157.  
  158. private static int GetCurrentscore(IList<int?> usedValues,int[] priorities,KeyValuePair<int?[],int> rule)
  159. {
  160. int currentscore = 0;
  161. for (int i = 0; i < usedValues.Count; i++)
  162. {
  163. if (rule.Key[i] != null)
  164. {
  165. if (rule.Key[i] == usedValues[i])
  166. currentscore += priorities[i];
  167. else
  168. return Int32.MinValue;
  169. }
  170. }
  171. return currentscore;
  172. }
  173.  
  174. private void AddChild(IList<int?> usedValues,List<KeyValuePair<int?[],int>> prunedPool,Nullable<int> nextValue)
  175. {
  176. List<int?> chainedValues = new List<int?>();
  177. chainedValues.AddRange(usedValues);
  178. chainedValues.Add(nextValue);
  179. DefaultMapNode node = new DefaultMapNode(chainedValues,priorities);
  180. if (nextValue == null)
  181. defaultChild = node;
  182. else
  183. children[(int)nextValue] = node;
  184. }
  185.  
  186. public IEnumerable<int> GetAllValues()
  187. {
  188. foreach (DefaultMapNode child in children.Values)
  189. foreach (int v in child.GetAllValues())
  190. yield return v;
  191. if (defaultChild != null)
  192. foreach (int v in defaultChild.GetAllValues())
  193. yield return v;
  194. if (value != null)
  195. yield return (int)value;
  196. }
  197.  
  198. public void PrintTree(int depth)
  199. {
  200. if (value == null)
  201. Console.WriteLine();
  202. else
  203. {
  204. Console.WriteLine(" = {0}",(int)value);
  205. return;
  206. }
  207.  
  208. foreach (KeyValuePair<int,DefaultMapNode> child in children)
  209. {
  210. for (int i=0; i<depth; i++)
  211. Console.Write(" ");
  212. Console.Write(" {0} ",child.Key);
  213. child.Value.PrintTree(depth + 1);
  214. }
  215. for (int i = 0; i < depth; i++)
  216. Console.Write(" ");
  217. Console.Write("null");
  218. defaultChild.PrintTree(depth + 1);
  219. }
  220. }

猜你在找的C#相关文章