如何在Python中避免重复绘制双向配对坐标连线？求O(n)解法

核心思路 #

要避免重复绘制a->b和b->a这类双向配对的连线，关键是跟踪已处理的无序坐标对，而非单个点。我们可以用集合存储已处理的配对标识，确保每对坐标只被绘制一次。由于集合的查找、插入操作平均时间复杂度为O(1)，整个流程能达到O(n)的时间效率。

具体实现步骤 #

1. 构建坐标映射字典：将张量元素与对应的2D坐标关联，注意张量不可直接作为字典键，可使用对象唯一ID（id()）来标识每个张量。
2. 生成无序配对标识：对每对坐标，按固定顺序（如元组大小排序）生成唯一标识，让(coord_a, coord_b)和(coord_b, coord_a)对应同一个标识。
3. 检查并绘制：每次处理配对时，先检查标识是否在已处理集合中，未存在则绘制点和连线，再将标识加入集合。

完整代码示例 #

import torch
import matplotlib.pyplot as plt

# 模拟用户提供的数据
t_a = torch.randn(3, 256, 256)
t_b = torch.randn(3, 256, 256)
t_c = torch.randn(3, 256, 256)
t_d = torch.randn(3, 256, 256)

a = [t_a, t_b, t_c]
b = [t_b, t_a, t_d]

c_keys = [t_a, t_b, t_c]
c_values = [torch.randn(2), torch.randn(2), torch.randn(2)]

# 1. 构建坐标映射：用张量的唯一ID作为键
coord_map = {id(tensor): coord for tensor, coord in zip(c_keys, c_values)}

# 存储已处理的配对标识
processed_pairs = set()

plt.figure(figsize=(8, 6))

for elem_a, elem_b in zip(a, b):
    # 获取对应坐标，跳过无坐标的元素（如示例中的t_d）
    coord_a = coord_map.get(id(elem_a))
    coord_b = coord_map.get(id(elem_b))
    if coord_a is None or coord_b is None:
        continue
    
    # 转换为可哈希的元组
    coord_a_tuple = tuple(coord_a.numpy())
    coord_b_tuple = tuple(coord_b.numpy())
    
    # 生成无序配对标识：按元组大小排序，确保a->b和b->a是同一个标识
    pair_key = tuple(sorted([coord_a_tuple, coord_b_tuple]))
    
    if pair_key not in processed_pairs:
        # 绘制散点
        plt.scatter(*coord_a_tuple, color='blue', s=50)
        plt.scatter(*coord_b_tuple, color='blue', s=50)
        # 绘制连线
        plt.plot([coord_a_tuple[0], coord_b_tuple[0]], 
                 [coord_a_tuple[1], coord_b_tuple[1]], 
                 color='gray', linestyle='-')
        # 标记为已处理
        processed_pairs.add(pair_key)

plt.xlabel('X坐标')
plt.ylabel('Y坐标')
plt.title('无重复连线的配对元素散点图')
plt.show()

关键细节说明 #

• 张量的唯一标识：用id(tensor)作为字典键，是因为示例中每个张量都是独立实例，id()能保证唯一性；如果张量可能有重复值但需视为不同元素，这个方法依然有效。
• 无序配对标识：通过sorted()将两个坐标元组排序，确保双向配对生成相同的pair_key，避免重复处理。
• 时间复杂度：集合的in判断和add操作平均为O(1)，遍历n个配对的总时间为O(n)，远优于O(n²)的朴素解法。

内容的提问来源于stack exchange，提问作者Richie Bendall