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

Question

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

简单示例：

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

- J0ANMM

---

你有尝试过什么吗？你能分享一下代码，这样别人就不会重复你的努力了。 - Phil

一些澄清的问题：（1）您预计会有多少个组？（2）一个元素可以属于单个列表还是多个列表？ - Horia Coman

我预计不会超过20个组。一个元素只能属于一个组。 - J0ANMM

感谢@J0ANMM。我提供的答案假设（2），但与（1）无关。希望能有所帮助。 - Horia Coman

更改列表之间您预计需要多少次查找？ - fishinear

Answer 1

索引集合的字典

这里是Horia的建议和我的原创思路的混合。您可以定义一个带有城市名称作为键，索引集合作为值的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)。作为奖励，查询不仅返回布尔值还返回索引集合。

最后，由于使用了集合交集，如果您想检查三个或更多城市是否在同一组，则此方法也适用。

- Eric Duminil

---

谢谢您的回答。这种方法与chepner的回答类似，但我更喜欢值只是一个索引而不是完整的集合。我将尝试运行这些建议并查看是否有任何比其他建议更快的显着差异。 - J0ANMM

@J0ANMM：不过有一个区别：如果一个城市出现在多个组中，chepner的答案就无法工作。我认为这里的许多答案都具有可比性能，因为它们都基于字典和集合。尽管如此，我的答案可能需要比其他答案更少的内存。 - Eric Duminil

Answer 2

一种方法是建立一个从城市到它所属组别编号的映射表。因此，你可以建立如下内容:

mapping = {
    'London': 1,
    ...,
    'Berlin': 3
    ...
}

那么您的in_same_group函数可以是：

def in_same_group(item1, item2):
    gr1 = mapping[item1]
    gr2 = mapping[item2]
    return gr1 == gr2

从速度上来看，这个函数非常快，因为它只涉及两次字典查找和一次比较操作，而在Python中这些操作都非常快。在大O表示法中，该函数的时间复杂度为O(1)。

但是它假设元素只属于一个组，这似乎是你提供的示例中的情况。

你需要花费额外的时间和内存来构建映射表。但这将分摊到所有对in_same_group的调用中。另一方面，无论采用哪种方法，你可能都无法避免构建索引结构。

构建映射表的代码如下：

def build_mapping(groups):
    mapping = {}
    for i in range(0, len(groups)):
        for g in groups[i]:
            mapping[g] = i
    return mapping

这段代码并不是最美观的，但它能完成工作。

- Horia Coman

---

不错。我利用一组索引来扩展这个概念。这样，当一个城市在多个组中时，它也可以工作。 - Eric Duminil

Answer 3

首先，使用集合而不是列表（使用集合列表而不是单独的变量）。

master_list = []
master_list.append(set(['London', 'Manchester', 'Liverpool', 'Edimburgh']))
master_list.append(set(['Dublin', 'Cork', 'Galway']))
master_list.append(set(['Berlin', 'Munich', 'Frankfurt', 'Paris', 'Milan', 'Rome', 'Madrid', 'Barcelona', 'Lisbon', ...]))
master_list.append(set(['Washington', 'New York', 'San Francisco', 'LA', 'Boston', ...]))

(根据您的使用情况，与其使用列表，可能使用更有意义的键来构建字典会更加合适。)

第二步，构建一个将每个元素映射到其集合的字典：

# E.g., index['London'] == set(['London', 'Manchester', ...])
index = dict((item, s) for s in master_list for item in s)

现在，您只需要检查两个项目是否属于同一组。

def in_same_group(i1, i2):
    return index[i1] is index[i2]

- chepner

---

这只有在一个城市属于一个组的情况下才有效，对吗？ - Eric Duminil

不错。它似乎与Horia Coman的答案类似，但映射也是自动完成的。使用列表或集合有很大的区别吗？ - J0ANMM

@J0ANMM 我假设您仍然希望保留哪些城市属于哪个组的显式表示。(Horia 的方法会失去这一点，或者至少不会与索引保持同步。) 如果您想要检查一个城市是否属于特定的组，那么使用 set 会更快，但是一旦 index 建立起来，使用列表或集合并没有太大区别。 - chepner

@EricDuminil 是的，就现在而言可以。您可以通过将 index 映射到集合的集合而不仅仅是集合来容纳多个组件。(无论如何，是一组冻结集合。如果组件还需要可变，我们必须构建一个更复杂的索引。) - chepner

谢谢你的回答。如果我理解正确，你的方法不会花费O(n**2)的时间复杂度，因为London和Manchester将拥有相同的共享对象作为字典值，对吗？ - Eric Duminil

Answer 4

您可以遍历列表并确定其中是否存在两个搜索查询。然后，返回新形成的列表的布尔值。

def search(s1, s2):
   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']
   return bool([i for i in [list1, list2, list3, list4] if s1 in i and s2 in i])

- Ajax1234

Answer 5

如果您想让它运行得更快，您应该将数据结构反转为一个字典集，其中键将是一个城镇，而集合将包含同一组中的所有城镇。这样，您可以确保in_same_group只需要：

• 一个单独的字典查询
• 一个单独的集合包含查询

由于这些访问已经针对字典和集合进行了优化，因此研究应该尽可能快。

代码如下：

import collections

h = collections.defaultdict(set)

lists = [list1, list2, list3, list4]
for l in lists:
    for town in l:
        for other in l:
            if town != other:
                h[town].add(other)

这个函数现在非常简单：

def in_same_group(t1, t2):
    return t2 in h[t1]

- Serge Ballesta

Answer 6

在数据库术语中，您拥有一对多的关系。一个列表可以包含许多名称，但每个名称只能出现在一个列表中。

尝试这个：

In [20]: city_lists = {city_name:list1 for city_name in list1}
In [21]: city_lists.update({city_name:list2 for city_name in list2})
In [22]: city_lists
Out[22]: 
{'Cork': ['Dublin', 'Cork', 'Galway'],
 'Dublin': ['Dublin', 'Cork', 'Galway'],
 'Edimburgh': ['London', 'Manchester', 'Liverpool', 'Edimburgh'],
 'Galway': ['Dublin', 'Cork', 'Galway'],
 'Liverpool': ['London', 'Manchester', 'Liverpool', 'Edimburgh'],
 'London': ['London', 'Manchester', 'Liverpool', 'Edimburgh'],
 'Manchester': ['London', 'Manchester', 'Liverpool', 'Edimburgh']}
In [23]: city_lists['Cork'] is city_lists['Dublin']
Out[23]: True
In [24]: city_lists['Cork'] is city_lists['London']
Out[24]: False

这是非常高效的。如果您使用http://pythontutor.com可视化代码，您将看到字典包含对原始列表的引用，但列表本身并未被复制。

- Marc Poulin

Answer 7

嗨，你可以尝试使用Pandas来实现这个

import pandas as pd


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


----------


a = pd.Series(list(list1))

b = pd.Series(list(list2))

c = pd.Series(list(list3))

d = pd.Series(list(list4))

lists = [a,b,c,d]


----------


for i in lists:

    if (i.isin(['London']).any()) and (i.isin(['Manchester']).any()) == True:
        print('Same Group')
    else:
        print('Different Group')

结果

同一组

不同的组

不同的组

不同的组

- Mario Rojas

Answer 8

在对提案进行一些速度测试后，我意识到所提出的解决方案的一个弱点（如果我没有弄错的话）是映射总是要完成整个循环。通过在结果已知的情况下更早地跳过循环，可以提高速度。

此外，如果一个列表比其他所有列表都要大得多，那么有一些潜力可以加快速度。

我认为以下做法可能会更快，如果其中一个列表比其他列表大得多。假设list3比其他列表大得多。

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

可能的一种情况是：

def in_same_group(city1, city2):

    for group in [list1, list2, list4]: #note that list3, the largest, is skipped
            if city1 in group and city2 not in group:
                return False

    return True #if this point is reached, both cities belong to the biggest group

- J0ANMM