python - 将字典分组为可能的最小键值对集

Question

我正在从 API 中提取数据，并创建一个如下所示的字典。

my_dict = {'server_name1':
               ['utah', 'california', 'idaho', 'texas'],
           'server_name2':
               ['NewYork'],
           'server_name3':
               ['idaho', 'new york', 'texas'],
           'server_name4':
               ['florida'],
           'server_name5':
               ['utah', 'california']}

我正在尝试创建维护组，因此我们只需通过了解客户接触的所有服务器来通知客户一次维护事宜，这反过来又需要了解这些服务器上其他客户所在的所有服务器。因此，我想组合尽可能多的类似组，并且我通过将至少具有一个匹配值的键分组为其他键来实现这一点。所以我的字典将从上面变为:

new_dict = {'server_name1, server_name2, server_name3, server_name5':
                ['utah', 'california', 'idaho', 'texas', 'newyork'],
            'server_name4':
                ['florida']}

我有一些代码可以做到这一点，但它需要多次分组迭代，除非您确切知道必须对事物进行分组多少次才能获得尽可能少的组数，否则这不是很好。

这是我的工作代码。

new_dict = {}
for key in my_dict.iteritems():
    for key2 in my_dict.iteritems():
        if len(key[1]) > 0 and len(key2[1]) > 0:
            if key[0] != key2[0]:
                if all(x in key[1] for x in key2[1]) == True:
                    newkey = "{0}, {1}".format(key2[0],key[0])
                    servers = key[0] + ", " + key2[0]
                    states = key[1] + list(key2[1])
                    group = {servers:states}
                    new_dict.update(group)

Answer 1

您想要完成的任务背后的抽象是在服务器和状态的图中找到连接的组件。我们可以实现一个解决方案来转换您的 dict到图表，找到连接的组件并转换回所需的格式。

首先，让我们定义帮助函数来处理 my_dict作为图表。

def get_cluster(x_to_y, y_to_x, x):
    # Implement a breadth-first search to recover all servers connected to x
    queue = [x]
    cluster = set()
    while queue:
        current = queue.pop()
        if current not in cluster:
            queue.extend({i for y in x_to_y[current] for i in y_to_x[y]})
            cluster.add(current)
    return cluster


def get_connected_parts(x_to_y):
    # We were provided a server -> state representation of the graph
    # For efficiency, we will generate a state -> server dict of edges
    y_to_x = {}

    for server, states in x_to_y.items():
        for state in states:
            if state in y_to_x:
                y_to_x[state].add(server)
            else:
                y_to_x[state] = {server}

    # We now iterate over our servers and recover their clusters
    seen = set()
    clusters = []

    for x in x_to_y:
        if x not in seen:
           cluster = get_cluster(x_to_y, y_to_x, x)
           seen |= cluster
           clusters.append(cluster)

    return clusters

现在大部分工作已经完成，函数get_connected_parts可用于检索已连接服务器的集合。剩下的就是格式化数据。但首先，让我们看一下它的输出。

my_dict = {
 'server_name1': ['utah', 'california', 'idaho', 'texas'],
 'server_name2': ['new york'],
 'server_name3': ['idaho', 'new york', 'texas'],
 'server_name4': ['florida'],
 'server_name5': ['utah', 'california']}

groups = get_connected_parts(my_dict)

print(groups)

输出:

[{'server_name2', 'server_name1', 'server_name3', 'server_name5'}, {'server_name4'}]

请注意，让键看起来像 'server1, server2, server3, server5' 没有多大意义。 ，因为这需要用户知道每当尝试访问 key 时都连接了哪些服务器。相反，我们将输出 new_dict其中键是服务器，值都是间接连接的状态。

new_dict = {}

for group in groups:
    states = list({state for server in group for state in my_dict[server]})
    for state in group:
        new_dict[state] = states

我们可以使用pprint检查输出是否正确。

from pprint import pprint

pprint(new_dict)

输出:

{'server_name1': ['california', 'texas', 'idaho', 'utah', 'new york'],
 'server_name2': ['california', 'texas', 'idaho', 'utah', 'new york'],
 'server_name3': ['california', 'texas', 'idaho', 'utah', 'new york'],
 'server_name4': ['florida'],
 'server_name5': ['california', 'texas', 'idaho', 'utah', 'new york']}