从ndarray列表中剔除重复三角面的高效算法问询

问题分析 #

你的核心需求是对百万级三角面（每个面由3个点索引组成，顺序不同视为重复）去重，保留首次出现的面并输出其索引。原代码速度慢的原因在于：

• 每次用list_of_sets[counter] in list_of_sets[0:(counter-1)]做全量比对，时间复杂度为O(n²)，百万级数据下完全不可行；
• list.pop(counter)会频繁移动列表元素，进一步拖慢效率。

优化思路 #

利用哈希表快速查找+顺序无关的唯一标识实现O(n)或O(n log n)级别的处理：

1. 对每个三角面的3个索引排序——相同的面（无论点顺序如何）排序后会得到完全一致的序列；
2. 将排序后的序列转为可哈希的类型（元组或numpy视图），用集合记录已出现过的面；
3. 遍历一次即可完成去重，保留首次出现的面的索引。

方案一：Numpy向量化实现（推荐，速度最快） #

适合将所有面转为二维numpy数组的场景，利用numpy的高效向量化操作处理百万级数据：

import numpy as np

def cull_faces_fast(all_face_nodes):
    # 将输入转为形状为(N,3)的numpy数组
    face_array = np.array(all_face_nodes)
    # 对每个面的索引按升序排序，生成唯一标识
    sorted_faces = np.sort(face_array, axis=1)
    # 将排序后的数组转为可哈希的视图（比转元组更高效）
    sorted_view = sorted_faces.view(np.uint64).reshape(-1, 3)
    # 获取唯一面的首次出现索引，并排序保持原输入顺序
    _, unique_indices = np.unique(sorted_view, axis=0, return_index=True)
    unique_indices_sorted = np.sort(unique_indices)
    
    # 若需要掩码而非索引列表，可替换为：
    # mask = np.zeros(len(face_array), dtype=bool)
    # mask[unique_indices_sorted] = True
    # return mask
    
    return unique_indices_sorted.tolist()

关键细节：

• np.sort(..., axis=1)：对每个面的3个索引统一排序，消除顺序差异；
• sorted_faces.view(...)：通过numpy视图将数组转为可哈希的类型，操作耗时可忽略；
• np.unique(..., return_index=True)：O(n log n)复杂度完成去重，直接返回首次出现的索引。

方案二：Python循环+哈希集合（轻量灵活） #

适合无法一次性转为numpy数组的场景，同样能实现高效去重：

def cull_faces_fast_list(all_face_nodes):
    seen_faces = set()
    keep_indices = []
    for idx, face in enumerate(all_face_nodes):
        # 排序后转元组作为唯一键（元组可哈希，能存入集合）
        face_key = tuple(sorted(face))
        if face_key not in seen_faces:
            seen_faces.add(face_key)
            keep_indices.append(idx)
    return keep_indices

关键细节：

• 对单个面排序仅需常数时间，整体时间复杂度为O(n)；
• 集合的in操作是O(1)复杂度，避免了原代码的全量比对；
• 无列表元素移动操作，减少额外开销。

性能对比 #

• 原代码：百万级数据需数小时甚至更久；
• 方案一：百万级数据仅需数秒；
• 方案二：百万级数据约十余秒。

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