我需要定义一个函数group_dictionaries,它将获取一个字典列表,并返回一个字典列表,该列表中的每个键包含相同的值。“孤独”字典将被删除。在
下面是一个例子:
my_list=[
{'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z},
{'id':'id3', 'key2 :value_u, 'key3': value_v},
{'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t},
{'id':'id4', 'key1':value_w, 'key2':value_s, 'key3':value_v}
]
group_dictionary(my_list, list_of_keys=['key1', 'key3'])
#result: the only dictionaries that have key1 AND key3 in common are:
[
{'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z, 'group':0},
{'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t, 'group':0}
]
group_dictionary(my_list, list_of_keys=['key3'])
#result the dictionaries that have key3 in common are divided in two groups
#of different values: group 0 has value_z and group1 has value_v
[
{'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z, 'group':0},
{'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t, 'group':0},
{'id':'id3', 'key2 :value_u, 'key3': value_v, 'group':1},
{'id':'id4', 'key1':value_w, 'key2':value_s, 'key3':value_v, 'group':1}
]
如您所见:
我关心的是运行时;实际列表包含80000个字典,平均每个字典包含35个键。该算法的复杂度可能为n²(80000²)。欢迎在代码中进行任何优化。在
这很简单;首先,您需要某种方法轻松序列化dict中的相关数据。我将使用这种(非常简单)方法,但根据数据的复杂性,您可能需要想出更可靠的方法:
然后,您只需将所有这些序列化值存储在一个列表中。列表中值的索引是组的ID。在
^{pr2}$我相信这是可行的,它是用Python3编写的,我还没有对它进行优化,但是如果它不够快的话,它可能是一个很好的起点。在
输出:
^{pr2}$优化1:
我们不必迭代所有键来检查它们是否存在,而是在生成value key时失败并返回一个空字符串,这将标记dict以删除:
组必须大于1:
这将使用第二个dict来跟踪组大小,然后检查组是否小于2,以标记要删除的组。在
输出:
优化2:
您可以从
O(n^2)
(循环一次dict列表进行计算并删除一次)到O(n*m log m)
(循环一次dict列表并遍历已排序的已删除索引):相关问题 更多 >
编程相关推荐