Python算法优化：大规模顶点集下三角形生成与完备性验证

给定顶点集A={0,1,…,n-1}，以及由A中顶点构成的非退化三角形集合B（例如n=5时，B={[1,2,3],[2,3,4],[1,2,4]}，不能包含如[1,2,2]的退化三角形）。可通过以下规则生成新三角形：选取三个两两恰有一条公共边、且三者恰有一个公共顶点的三角形，拼接生成新三角形（如上述示例可生成[1,3,4]）。目标是实现算法持续生成新三角形直至无法继续，并验证是否能生成全部n*(n-1)*(n-2)/6个非退化三角形。

以下为Python代码：

import random

# lists all the pairs of distinct integers in [0, n - 1]
def connections(n):
    result = []
    for i in range(n):
        for j in range(i+1, n):
            result.append([i, j])
    return result

# makes a list of all possible triangles with vertices in [0, n - 1] 
def all_faces(n):
    result = []
    for i in connections(n):
        for j in range(i[1] + 1, n):
            result.append(i + [j])
    return result

def my_algorithm(n, faces):
        generalized_faces = faces
        new_faces = [] 
        number_new_faces = len(generalized_faces)     
        i = 0

# generate new triangles from the existing ones in generalized_faces
# and then add them in new_faces. Repeat the loop while new_faces is nonempty.

        while len(new_faces) > 0 or i == 0:
            generalized_faces.extend(new_faces)
            length = len(generalized_faces)              
            if i > 0:
                number_new_faces = len(new_faces)
                new_faces = []
            if length == n * (n - 1) * (n - 2) / 6:  
                return True      
            for i in range(length - number_new_faces, length):
                [a, b, c] = generalized_faces[i]
                for j in range(n):
                    if j not in [a, b, c]:
                        triangle1 = [a, b, j]
                        triangle1.sort()
                        triangle2 = [b, c, j]
                        triangle2.sort()
                        triangle3 = [a, c, j]
                        triangle3.sort()
                        if triangle1 in new_faces + generalized_faces and triangle2 in new_faces + generalized_faces:
                            final_triangle = [a, c, j]
                            final_triangle.sort()
                            if final_triangle not in new_faces + generalized_faces:
                                new_faces.append(final_triangle)
                        if triangle1 in new_faces + generalized_faces and triangle3 in new_faces + generalized_faces:
                            final_triangle = [b, c, j]
                            final_triangle.sort()
                            if final_triangle not in new_faces + generalized_faces:
                                new_faces.append(final_triangle)
                        if triangle2 in new_faces + generalized_faces and triangle3 in new_faces + generalized_faces:
                            final_triangle = [a, b, j]
                            final_triangle.sort()
                            if final_triangle not in new_faces + generalized_faces:
                                new_faces.append(final_triangle)
                    
            i += 1
        return len(generalized_faces) == n * (n - 1) * (n - 2) / 6

# returns some subset of all_faces(n)
def choose_faces(n, p):
    return [x for x in all_faces(n) if random.random() < p]

# tests the probability of success in m trials depending on probability p
def test(n, m, p):
    result = 0.0
    for _ in range(m):
        faces = choose_faces(n, p)
        if my_algorithm(n, faces):
            result += 1.0
    return result/(float(m))

当前存在两个问题：

1. 运行速度极慢，n=30时性能已严重下降；
2. 部分输出结果不符合预期，但无法定位错误。

能否对该算法进行优化，使其在n=1000、B为所有非退化三角形的合理子集时高效运行？若可以，给出可行实现方案。

原代码核心问题分析 #

1. 线性查找效率低下：用列表存储三角形，in操作是O(k)复杂度（k为当前三角形数量），n=30时总三角形数达4060，每次查找都要遍历整个列表，耗时极大。
2. 循环逻辑错误：外层循环变量i被内层for i in range(...)覆盖，导致循环条件判断混乱，这是结果存疑的直接原因之一。
3. 冗余遍历：对每个三角形遍历所有顶点j，生成大量不必要的候选三角形，无差别检查导致计算量爆炸。
4. 数据类型不合理：用可变列表存储三角形，无法作为集合的键，也不利于快速哈希查找。

优化思路 #

1. 使用集合与哈希查找：将三角形转换为排序后的元组（不可变类型），存入集合，使in操作变为O(1)复杂度。
2. 维护边到三角形的映射：建立字典，记录每条边对应的所有三角形的第三个顶点，快速找到共享同一条边的三角形组合。
3. 增量式处理新三角形：仅针对新添加的三角形，处理其关联的边与顶点组合，避免全局遍历，大幅减少计算量。
4. 修复循环逻辑：用队列存储待处理的新三角形，确保所有可推导的三角形都被处理。

优化后代码实现 #

import random
from collections import defaultdict

def all_faces(n):
    """生成所有非退化三角形，返回排序后的元组列表"""
    faces = []
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                faces.append((i, j, k))
    return faces

def choose_faces(n, p):
    """随机选择三角形子集"""
    return [tri for tri in all_faces(n) if random.random() < p]

def optimized_algorithm(n, initial_faces):
    # 将初始三角形转换为排序后的元组，存入集合
    tri_set = set()
    # 边到第三个顶点的映射：键为(边的两个顶点)，值为包含该边的三角形的第三个顶点集合
    edge_to_vertices = defaultdict(set)
    
    # 初始化集合与映射
    for tri in initial_faces:
        sorted_tri = tuple(sorted(tri))
        if sorted_tri not in tri_set:
            tri_set.add(sorted_tri)
            # 为三角形的三条边添加映射
            a, b, c = sorted_tri
            edge_to_vertices[(a, b)].add(c)
            edge_to_vertices[(a, c)].add(b)
            edge_to_vertices[(b, c)].add(a)
    
    # 队列存储待处理的新三角形
    queue = list(tri_set)
    total_possible = n * (n-1) * (n-2) // 6
    
    while queue:
        if len(tri_set) == total_possible:
            return True
        
        current_tri = queue.pop(0)
        a, b, c = current_tri
        
        # 遍历当前三角形的三条边，寻找共享边的其他三角形
        for edge in [(a, b), (a, c), (b, c)]:
            # 获取共享该边的所有第三个顶点
            other_vertices = edge_to_vertices[edge]
            # 遍历每一对顶点组合，检查是否能推导新三角形
            u, v = edge
            x = current_tri[3 - current_tri.index(u) - current_tri.index(v)]
            for y in other_vertices:
                if y == x:
                    continue
                # 四个顶点是 u, v, x, y，检查是否存在三个三角形以推导第四个
                tri1 = tuple(sorted((u, x, y)))
                tri2 = tuple(sorted((v, x, y)))
                
                if tri1 in tri_set and tri2 not in tri_set:
                    # 推导并添加tri2
                    tri_set.add(tri2)
                    queue.append(tri2)
                    # 更新边映射
                    edge_to_vertices[(v, x)].add(y)
                    edge_to_vertices[(v, y)].add(x)
                    edge_to_vertices[(x, y)].add(v)
                elif tri2 in tri_set and tri1 not in tri_set:
                    # 推导并添加tri1
                    tri_set.add(tri1)
                    queue.append(tri1)
                    # 更新边映射
                    edge_to_vertices[(u, x)].add(y)
                    edge_to_vertices[(u, y)].add(x)
                    edge_to_vertices[(x, y)].add(u)
    
    return len(tri_set) == total_possible

def test(n, m, p):
    success = 0
    for _ in range(m):
        faces = choose_faces(n, p)
        if optimized_algorithm(n, faces):
            success += 1
    return success / m

优化效果说明 #

1. 时间复杂度大幅降低：通过集合的O(1)查找和边映射的快速关联，避免了原代码的线性遍历与冗余检查，n=1000时只要初始子集不是极端稀疏，都能高效运行。
2. 逻辑正确性修复：用队列处理新三角形，确保所有可推导的三角形都被遍历，避免了原代码的循环变量覆盖问题。
3. 内存效率提升：用元组和集合存储数据，比列表更节省内存，且哈希结构的访问效率更高。

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