最适合用于键值对评估的数据结构

-1

我将预定义的匹配项设置为：父ENTITY具有与其关联的键值集。下父ENTIRY每个集合可以被定义类似最适合用于键值对评估的数据结构

ENTITY A: 
    SET A1. {key1=v11 and key2!=v25} 
    SET A2. {key1=v12 and key3=v31, v33} 
    SET A3. {key1=v15 and key2=v25 and key3=v35} 

Entity B: 
    SET B1. {key1=v16 and key2=v26} 
    SEY B2. {key3!=v39} 
    SET B3. {key1!=v11 and key3=v31}

我将接收的输入为：

{ 
    key1 : [v11,v12,v13], 
    key2 : [v23,v24], 
    key3 : [v31,v39] 
}

这意味着KEY1具有3个值，KEY2具有2个值和KEY3只有一个值。

然后我必须返回所有具有至少一个SET的实体，这些SET的所有键值匹配都由传递的键值对满足。

因此，对于上面提到的实体A，集合A1和集合A2的键值对由输入满足，而对于实体B，没有集合的键值对满足。所以只有ENTITY A才是答案。

可以有200-1000个父实体，每个父实体有20个SET ENTITY & 200个键值对。输入可能包含多达50个键值对。

我无法查询外部数据库进行评估。但是数据结构应该可序列化以存储到memcache或redis中。

来源

2014-01-16 Ajay Bodhe

请提供关于实体数量的实体数量的一些细节（上限或期望值）。这可能会对最佳方法产生很大影响。 –

完成，感谢您的建议。 –

为了简单，让我修复python中的符号和写入。

你称之为ENTITY的是一组词典，由'keys'标记，并以对象列表作为值。为简单起见我们假设值是数字（但我们真正需要的是只是比较操作）

E1 = { 
    {'k1': [4], 'k2': [20,12]}, 
    {'k4': [2,20,25], 'k3': [2,3]} 
} 

E2 = { 
    {'k2': [2,3,4], 'k4': [2], 'k3': [14]}, 
    {'k3': [1]}, 
    {'k3': [12,23]} 
}

输入仅仅是一本字典，再由“钥匙”，并与对象作为值列表标记。我想你应该保持排列顺序的数组数组。这应该允许您以线性时间比较给定密钥的列表。总的来说，给定输入的复杂度应该是O（EKL），其中E是实体的数量，K是密钥的数量，L是列表的长度。同样，它将需要O（EKL）内存。

我期望在这种情况下，比较你的界限需要几秒钟的时间。如果这还不够那就让我们进一步认为:)

编辑：您可以简单地用一个元组（ENTITY_ID，SET_ID，键，值），以平衡BST作为值的指数。然后搜索应该花费O（log n）。你有没有想过这样的结构？

来源

2014-01-16 18:31:48

我想在C中实现这个。比较SET/dictionary中的每个键与输入中的每个键将会浪费一些时间。同样在找到键后，将集合/词典中的键的每个值与输入中接收的相同键的每个值进行比较将需要时间。我们能加速吗？ –

那么，如果你将它作为一个Map来实现，那么查找关键字将需要一段时间。比较值最多会花费线性时间O（L）。由于我们不了解任何有关元素的更多信息，因此无法改进。您需要检查每个实体和每个集合，以便提供额外的O（EK）因子。 –

我今天能想到的唯一改进是为值而不是列表设置结构。这将为每个键进行O（L）查找，而无需排序。 –

最适合用于键值对评估的数据结构

回答

相关问题