Python优化需求：高效筛选重叠线段保留高goodness属性线段

线段结构说明 #

• 每条线段包含N个点，存储在line.points（示例：[p1,p2,p3,....,pN]）
• 每条线段具备goodness属性（示例：1.5）

需求与原算法逻辑 #

当多条线段存在最多N-1个重叠点时，保留goodness值更高的线段，原预期算法逻辑：

1. 将所有存在N-1个重叠点的线段归为一组，形成重叠线段簇；
2. 每个簇仅保留goodness最高的线段，移除其余；
3. 接着处理存在N-2个重叠点的线段，同样保留每组最高goodness的线段；
4. 重复步骤直到无重叠线段或N=0。

原实现代码 #

def point_overlap(line1, line2, N_overlaps):
    result=False
    buf=0
    for line1_point in line1.points:
        for line2_point in line2.points:
            if line1_point==line2_point:
                 buf+=1
    if buf==N_overlaps: 
       result=True
    return result

def choose_worse_line(line1,line2): 
    if line1.goodness<=line2.goodness:
       return line1
    return line2

len_lines=100
for N in reversed(range(len_lines)):
    lines_that_overlap=[[line1,line2] for line1 in line_set for line2 in line_set if point_overlap(line1, line2, N)==True]
    if not lines_set:
        break
    worse_line=[choose_worse_line(line[0],line[1]) for line in lines_that_overlap]
    lines_set=[line for line in line_set if line not in worse_line]

优化方案与实现 #

核心优化方向 #

原代码存在双重循环效率低、重复计算、簇划分逻辑混乱等问题，以下是针对性优化：

1. 重叠点计算效率优化

将双重循环的点匹配改为集合交集计算，时间复杂度从O(N²)降至O(N)：

def point_overlap(line1, line2, N_overlaps):
    # 利用集合快速求交集大小
    common_count = len(set(line1.points) & set(line2.points))
    return common_count == N_overlaps

注：若点为自定义对象，需实现__hash__和__eq__方法以支持集合操作。

2. 重构核心筛选逻辑

通过图连通分量划分重叠簇，确保每个簇仅保留最优线段，避免重复操作：

from collections import defaultdict

def build_overlap_graph(lines, k):
    # 构建重叠关系图：key为线段，value为与该线段有k个重叠点的线段列表
    graph = defaultdict(list)
    line_list = list(lines)
    total = len(line_list)
    # 仅比较i<j的线段对，避免重复计算
    for i in range(total):
        line_i = line_list[i]
        set_i = set(line_i.points)
        for j in range(i+1, total):
            line_j = line_list[j]
            set_j = set(line_j.points)
            if len(set_i & set_j) == k:
                graph[line_i].append(line_j)
                graph[line_j].append(line_i)
    return graph

def find_connected_components(graph, lines):
    # 找出图中的所有连通分量（即重叠簇）
    visited = set()
    components = []
    for line in lines:
        if line not in visited:
            stack = [line]
            visited.add(line)
            component = []
            while stack:
                current = stack.pop()
                component.append(current)
                for neighbor in graph.get(current, []):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)
            components.append(component)
    return components

def filter_lines(lines, num_points_per_line):
    remaining_lines = lines.copy()
    # 从k=N-1到k=0依次处理
    for k in reversed(range(num_points_per_line)):
        if len(remaining_lines) <= 1:
            break  # 剩余线段不足，无需继续处理
        # 构建当前k值对应的重叠图
        overlap_graph = build_overlap_graph(remaining_lines, k)
        # 划分重叠簇
        components = find_connected_components(overlap_graph, remaining_lines)
        # 每个簇保留goodness最高的线段
        new_remaining = []
        for comp in components:
            best_line = max(comp, key=lambda x: x.goodness)
            new_remaining.append(best_line)
        remaining_lines = new_remaining
    return remaining_lines

优化点说明 #

• 预处理优化：用集合替代遍历匹配，大幅提升重叠点计数效率；
• 避免重复计算：仅处理i<j的线段对，减少一半计算量；
• 准确簇划分：通过图连通分量找到完整的重叠簇，避免原代码中重复标记待移除线段的问题；
• 提前终止：剩余线段≤1时直接停止循环，减少不必要的计算。

内容的提问来源于stack exchange，提问作者me.tric