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_pa​​rts 可用于检索连接的服务器集。剩下的就是格式化数据。但首先，让我们看一下它的输出。

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'}]

请注意，让 key 看起来像 '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']}