gpt4 book ai didi

python - 如何判断两个元素是否属于同一个列表

转载 作者:太空狗 更新时间:2023-10-29 17:10:30 28 4
gpt4 key购买 nike

我有几个列表,每个列表包含几个城市。我需要检查任意两个随机元素是否属于同一个列表。

简单的例子:

list1 = ['London', 'Manchester', 'Liverpool', 'Edimburgh']
list2 = ['Dublin', 'Cork', 'Galway']
list3 = ['Berlin', 'Munich', 'Frankfurt', 'Paris', 'Milan', 'Rome', 'Madrid', 'Barcelona', 'Lisbon', ...]
list4 = ['Washington', 'New York', 'San Francisco', 'LA', 'Boston', ...]

预期结果:

> in_same_group('London', 'Liverpool')
> True
>
> in_same_group('Berlin', 'Washington')
> False

该函数被频繁调用,因此速度很关键。最大的列表最多可能包含 1000 个元素。

最有效的方法是什么?


这是我到目前为止尝试过的方法,但是速度太慢了:

def in_same_group(city1, city2):

same_group = False
for this_list in [list1, list2, list3...]:
if city1 in this_list and city2 in this_list:
return True

return same_group

最佳答案

索引集字典

这是 Horia 的 proposal 的组合和我原来的。您可以定义一个 dict,其中城市作为键,索引集作为值:

list1 = ['London', 'Manchester', 'Liverpool', 'Edimburgh']
list2 = ['Dublin', 'Cork', 'Galway', 'Paris', 'Rome']
list3 = ['Berlin', 'Munich', 'Frankfurt', 'Paris', 'Milan', 'Rome', 'Madrid', 'Barcelona', 'Lisbon']
list4 = ['Washington', 'New York', 'San Francisco', 'LA', 'Boston']
# Note that 'Paris' and 'Rome' are both in list2 and list3

groups = [list1, list2, list3, list4]

indices = {}

for i, group in enumerate(groups):
for city in group:
indices.setdefault(city, set()).add(i)

结构紧凑,如下所示:

print(indices)
#{'London': {0}, 'Manchester': {0}, 'Liverpool': {0}, 'Edimburgh': {0}, 'Dublin': {1}, 'Cork': {1}, 'Galway': {1}, 'Paris': {1, 2}, 'Rome': {1, 2}, 'Berlin': {2}, 'Munich': {2}, 'Frankfurt': {2}, 'Milan': {2}, 'Madrid': {2}, 'Barcelona': {2}, 'Lisbon': {2}, 'Washington': {3}, 'New York': {3}, 'San Francisco': {3}, 'LA': {3}, 'Boston': {3}}

由于 set intersection,对于任何城市对,您可以获得一组通用索引:

def common_groups(city1, city2):
return indices.get(city1, set()) & indices.get(city2, set())

print(common_groups('London', 'Liverpool'))
# {0}
print(common_groups('London', 'Paris'))
# set()
print(common_groups('Cork', 'Paris'))
# {1}
print(common_groups('Rome', 'Paris'))
# {1, 2}
print(common_groups('Rome', 'Nowhere'))
# set()

空集在 Python 中是错误的。

对于 n 个城市,创建字典的时间为 O(n),空间要求为 O(n),查找性能为为 O(1)。作为奖励,查询不仅返回 bool 值,还返回一组索引。

最后,由于设置了交叉点,如果您想检查三个或更多城市是否在同一组中,此方法也适用。

关于python - 如何判断两个元素是否属于同一个列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47416917/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com