TCL中循环时避免修改数组，优化近距离元素配对查找方案

我有一个数组d_EIDxyz，键为元素ID（EID），值为XYZ坐标集合。需要查找间距小于指定阈值ply_t的元素对，当前采用嵌套foreach循环计算元素间距离，找到符合条件的配对后存入pairs列表，并通过unset从数组中移除已匹配元素以加速查找。但已知循环时修改数组并非推荐做法，请问有什么更优的实现方案？

当前代码：

puts "Finding element pairs where distance from center to center is < ply_t..."
foreach { EID_1 xyz_1 } [array get d_EIDxyz] {

    set x1 [lindex $xyz_1 0]
    set y1 [lindex $xyz_1 1]
    set z1 [lindex $xyz_1 2]


    foreach {EID_2 xyz_2} [array get d_EIDxyz] {
        
        set x2 [lindex $xyz_2 0]
        set y2 [lindex $xyz_2 1]
        set z2 [lindex $xyz_2 2]
    
    
        set dis [expr {sqrt(($x2 - $x1) ** 2 + ($y2 - $y1) ** 2 + ($z2 - $z1) ** 2)}]
    
        if { $dis < $ply_t && $dis > 0 } {
            lappend pairs [list $EID_1 $EID_2]
            # remove the pair IDs found from the array to speed up the search
            catch { unset d_EIDxyz($EID_1) }
            catch { unset d_EIDxyz($EID_2) }
        }       
    
    }
}

puts "pairs: $pairs"

方案1：用标记集合替代修改原数组 #

核心逻辑是单独维护一个标记集合，记录已经匹配过的元素ID，循环时直接跳过已标记的元素，既保留原数组完整数据，又能实现“减少重复计算”的加速效果。

puts "Finding element pairs where distance from center to center is < ply_t..."
array set matched_EIDs {} ;# 存储已匹配的元素ID
set pairs [list]
set ply_t_sq [expr {$ply_t ** 2}] ;# 预计算阈值平方，避免重复开方

foreach { EID_1 xyz_1 } [array get d_EIDxyz] {
    if {[info exists matched_EIDs($EID_1)]} {
        continue ;# 跳过已匹配元素
    }

    lassign $xyz_1 x1 y1 z1 ;# 用lassign简化坐标提取，替代多次lindex

    foreach {EID_2 xyz_2} [array get d_EIDxyz] {
        if {$EID_1 == $EID_2 || [info exists matched_EIDs($EID_2)]} {
            continue ;# 跳过自身和已匹配元素
        }

        lassign $xyz_2 x2 y2 z2

        # 优化：比较距离平方，避免开根号运算，提升性能
        set dis_sq [expr {($x2 - $x1)**2 + ($y2 - $y1)**2 + ($z2 - $z1)**2}]
        if { $dis_sq < $ply_t_sq && $dis_sq > 0 } {
            lappend pairs [list $EID_1 $EID_2]
            # 标记两个元素为已匹配
            set matched_EIDs($EID_1) 1
            set matched_EIDs($EID_2) 1
            break ;# 找到配对后直接跳出内层循环，减少无效计算
        }
    }
}

puts "pairs: $pairs"

方案2：转换为列表后索引遍历，避免重复配对 #

原代码每次内层循环都会重新生成数组的键值对列表，效率低下。可以先把数组一次性转换为列表，通过索引遍历只比较未处理过的元素对（比如只比较元素A和后面的元素B，不重复比较B和A），进一步减少计算量。

puts "Finding element pairs where distance from center to center is < ply_t..."
set elements [array get d_EIDxyz] ;# 一次性将数组转为列表
set pairs [list]
set matched_indices [list] ;# 记录已匹配元素在列表中的索引
set len [llength $elements]
set ply_t_sq [expr {$ply_t ** 2}]

for {set i 0} {$i < $len} {incr i 2} {
    if {$i in $matched_indices} {
        continue
    }
    set EID_1 [lindex $elements $i]
    lassign [lindex $elements [expr {$i+1}]] x1 y1 z1

    # 只遍历i之后的元素，避免重复配对
    for {set j [expr {$i+2}]} {$j < $len} {incr j 2} {
        if {$j in $matched_indices} {
            continue
        }
        set EID_2 [lindex $elements $j]
        lassign [lindex $elements [expr {$j+1}]] x2 y2 z2

        set dis_sq [expr {($x2 - $x1)**2 + ($y2 - $y1)**2 + ($z2 - $z1)**2}]
        if { $dis_sq < $ply_t_sq && $dis_sq > 0 } {
            lappend pairs [list $EID_1 $EID_2]
            lappend matched_indices $i $j
            break
        }
    }
}

puts "pairs: $pairs"

进阶方案：空间分区算法（适合大数据量） #

如果元素数量上千甚至更多，嵌套循环的O(n²)复杂度会严重拖慢性能。此时可以用空间分区（比如网格划分）的方法，把元素按坐标分到不同网格中，只计算同一网格或相邻网格内的元素距离，大幅减少需要计算的元素对数量。

核心步骤：

1. 以ply_t为边长划分三维网格
2. 遍历所有元素，将EID存入对应网格的列表中
3. 遍历每个网格，计算网格内元素的配对，再计算当前网格与相邻8个网格的元素配对
4. 同样用标记集合跳过已匹配元素

这种方法能把时间复杂度降到接近O(n)，适合大数据量场景。

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