基于合作影片构建演员关系图：大字典嵌套循环优化求助

你现在用的嵌套循环是O(n²)的复杂度，对于10万+的演员数据来说，确实会慢到离谱——10万的平方是100亿次循环，这肯定不是可行的方案。咱们换个思路，从「影片→演员」的反向映射入手，这能把复杂度降到可接受的范围。

核心思路 #

原来的逻辑是「遍历每一对演员，找他们的共同影片」，反过来想：每一部影片里的所有演员，互相之间都是合作关系。我们只需要：

1. 先构建一个字典，把「影片名称」映射到参演的「演员ID列表」
2. 对每个影片的演员列表，生成所有两两不重复的演员对（确保people_id < other_people_id避免重复存储反向对）
3. 用集合去重（因为同一对演员可能合作多部影片，只需要保留一次合作关系）

代码实现 #

咱们用你给的示例数据来演示：

# 示例输入
people_dict = {
    284: ['DGK: Parental Advisory (2012)', 'Electric Daisy Carnival Experience (2011)', 'Malibu Horror Story (2014)'],
    602: ['5 Sides of a Coin (2003)', 'As I AM: The Life and Times of DJ AM (2015)', 'Electric Daisy Carnival Experience (2011)', 'Hang the DJ (1998)'],
    661: ['Every Boy Needs a Father (2013)', 'The Sketches of Matty Mad Man: Part Dos (2014)', 'Trippy: Spitting Rainbows (2014)', 'Vicky Foxx: Forever in Blue Jeans (2010)']
}

# 第一步：构建影片到演员的映射
movie_to_people = {}
for person_id, movies in people_dict.items():
    for movie in movies:
        if movie not in movie_to_people:
            movie_to_people[movie] = []
        movie_to_people[movie].append(person_id)

# 第二步：生成所有合作对，并用集合去重
edge_set = set()
for people_list in movie_to_people.values():
    # 对当前影片的演员列表，生成所有i<j的组合
    n = len(people_list)
    for i in range(n):
        for j in range(i+1, n):
            a, b = people_list[i], people_list[j]
            # 确保a < b，避免重复存储(284,602)和(602,284)
            if a > b:
                a, b = b, a
            edge_set.add((a, b))

# 第三步：转换为列表并写入文件
edge_list = list(edge_set)
with open('cooperation_pairs.txt', 'w') as f:
    for pair in edge_list:
        f.write(f"{pair[0]} {pair[1]}\n")

运行这段代码后，cooperation_pairs.txt里就会出现284 602，和你预期的一致。

为什么这个方法快？ #

• 原来的嵌套循环是O(n²)，n=10万时是1e10次操作，完全不可行；
• 新方法的复杂度是O(m*k²)，其中m是影片总数，k是单部影片的平均演员数。现实中大部分影片的演员数不会太多（比如几十人），总操作数会降到百万/千万级别，几分钟就能跑完。

额外优化建议 #

如果你的数据量特别大（比如影片数也很多），可以：

• 用collections.defaultdict来简化movie_to_people的构建，代码更简洁；
• 对于超大的演员列表（比如几百人的大制作电影），可以用itertools.combinations来生成组合，代码更优雅：

  from itertools import combinations
  for people_list in movie_to_people.values():
      for pair in combinations(sorted(people_list), 2):
          edge_set.add(pair)
  

• 如果需要统计演员合作的影片次数，可以用collections.Counter来替代set，每生成一对就计数+1。

内容的提问来源于stack exchange，提问作者Mr.Robot