我有一些配置数据,我想在代码中建模如下：
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);
}
}
