字典键的子集

Question

我有一个python字典，其格式为{'ip1:port1':<value>, 'ip1:port2':<value>, 'ip2:port1':<value>, ...}。字典的键是字符串，由ip：port对组成。对于此任务，值不重要。

我需要一个包含唯一IP地址的ip:port列表，端口可以是原始键中出现的任何端口。例如，上面的两个变体都是可以接受的：['ip1:port1'，ip2:port1']和['ip1:port2'，ip2:port1']。

最符合Pythonic风格的方法是什么？

目前，我的解决方案是：

def get_uniq_worker_ips(workers):
    wip = set(w.split(':')[0] for w in workers.iterkeys())
    return [[worker for worker in workers.iterkeys() if worker.startswith(w)][0] for w in wip]

我不喜欢它，因为它创建了额外的列表然后将它们丢弃。

- wl2776

---

那么请使用genexs。 - Ignacio Vazquez-Abrams

抱歉，您可以具体说明一下吗？ - wl2776

通过“genexs”，我认为他指的是“生成器表达式”，这基本上意味着您创建了一个生成器而不是列表。这可以通过在列表推导中将方括号[]更改为圆括号()来完成。 - M.T

Answer 1

您可以使用itertools.groupby按相同的IP地址进行分组：

data = {'ip1:port1' : "value1", 'ip1:port2' : "value2", 'ip2:port1' : "value3", 'ip2:port2': "value4"}
by_ip = {k: list(g) for k, g in itertools.groupby(sorted(data), key=lambda s: s.split(":")[0])}
by_ip
# {'ip1': ['ip1:port1', 'ip1:port2'], 'ip2': ['ip2:port1', 'ip2:port2']}

然后只需从不同的IP组中选择任何一个。

{v[0]: data[v[0]] for v in by_ip.values()}
# {'ip1:port1': 'value1', 'ip2:port1': 'value3'}

或者更简洁地说，可以为组中的第一个键创建一个生成器表达式：

one_by_ip = (next(g) for k, g in itertools.groupby(sorted(data), key=lambda s: s.split(":")[0]))
{key: data[key] for key in one_by_ip}
# {'ip1:port1': 'value1', 'ip2:port1': 'value3'}

然而，请注意groupby需要输入数据进行排序。因此，如果您想避免对字典中的所有键进行排序，则应该使用已经看到的键的set。

seen = set()
not_seen = lambda x: not(x in seen or seen.add(x))
{key: data[key] for key in data if not_seen(key.split(":")[0])}
# {'ip1:port1': 'value1', 'ip2:port1': 'value3'}

这与您的解决方案类似，但不是循环唯一键并为每个键在字典中查找匹配的键，而是循环键并检查是否已经看到了该IP。

- tobias_k

---

请注意，OP要求的是键的列表，而不是字典。尽管我喜欢groupby，但我更喜欢你的第二个解决方案，因为它避免了O（nlogn）排序。 - PM 2Ring

@PM2Ring 对，但这将使最后一步变得更容易。我同意“set”解决方案可能是最好的，需要最少的时间和空间。“groupby”只是我想到的第一件事，我不想在它获得一些赞之后将其删除。 - tobias_k

好的。我当然同意，您不应该从已经获得赞数的答案中删除代码。 - PM 2Ring

Answer 2

一种实现方法是将您的键转换为一个自定义类，该类在进行相等性测试时仅查看字符串的IP部分。它还需要提供一个合适的__hash__方法。

这里的逻辑是，set构造函数将 "看到" 具有相同 IP 的键视为相同，忽略比较中的端口部分，因此如果集合中已经存在具有该 IP 的键，则它将避免将该键添加到集合中。

下面是在Python 2或Python 3上运行的一些代码。

class IPKey(object):
    def __init__(self, s):
        self.key = s
        self.ip, self.port = s.split(':', 1)

    def __eq__(self, other):
        return self.ip == other.ip

    def __hash__(self):
        return hash(self.ip)

    def __repr__(self):
        return 'IPKey({}:{})'.format(self.ip, self.port)

def get_uniq_worker_ips(workers):
    return [k.key for k in set(IPKey(k) for k in workers)]

# Test

workers = {
    'ip1:port1' : "val", 
    'ip1:port2' : "val", 
    'ip2:port1' : "val", 
    'ip2:port2' : "val", 
}

print(get_uniq_worker_ips(workers))    

输出

['ip2:port1', 'ip1:port1']

如果您正在运行Python 2.7或更高版本，则该函数可以使用一个集合推导式来替换在set()构造函数调用内部的生成器表达式。

def get_uniq_worker_ips(workers):
    return [k.key for k in {IPKey(k) for k in workers}]

IPKey.__repr__ 方法并非必需，但我喜欢为所有的类编写 __repr__ 方法，因为在开发过程中可能会很方便。

---

以下是一个更加简洁且高效的解决方案，由 Jon Clements 提供。它通过字典推导式构建所需列表。

def get_uniq_worker_ips(workers):
    return list({k.partition(':')[0]:k for k in workers}.values())

- PM 2Ring

Answer 3

我在我的解决方案中更改了几个字符，现在对它感到满意。

def get_uniq_worker_ips(workers):
    wip = set(w.split(':')[0] for w in workers.iterkeys())
    return [next(worker for worker in workers.iterkeys() if worker.startswith(w)) for w in wip]

感谢 @Ignacio Vazquez-Abrams 和 @M.T. 的解释。

- wl2776

---

请注意，这个程序具有二次复杂度，即对于查找每个唯一IP的“下一个”匹配条目而言，其时间复杂度为O(n²)。此外，如果您拥有例如IPs 1.1.1.1和1.1.1.11，那么startswith将会失败。 - tobias_k

@tobias_k，我不明白为什么复杂度是二次的。外层循环遍历的是set元素... 你是不是指内层循环会遍历所有的键，然后只在迭代完成后创建生成器？ - wl2776

如果k是唯一IP地址的数量，n是字典中条目的数量，则复杂度为k*n。尽管如此（至少如果k << n），它并不完全是二次的，但仍比必要的高得多。 - tobias_k