优化检测球体不相交数量的函数效率

我有一个函数接收两组球体（每组数量可能不同），需要统计B集中不与A集中任何球体相交的球体数量（即不与蓝色球体相交的红色球体数量）。原代码通过全量遍历所有坐标两两组合计算距离，将与A中球体距离小于2倍半径的B坐标加入safeones，距离大于的加入questionableones，最后移除questionableones中存在于safeones的点，但这种全量遍历效率极低。

我尝试加入提前终止逻辑：遍历B中每个球体，只要它和A中任一球体距离小于2倍半径就跳出内层循环，否则加入可疑列表，但优化后输出结果异常偏高，求排查问题并优化函数。

原代码 #

import math
import numpy as np

def check_presence(comparison, safeones):
  for array in safeones:
    if (array == b).all():  # 存在变量名错误，应使用参数comparison而非全局b
      return True
  return False

def circle_intersection(a, b, r): # a是查询集，返回b中的异常值数量
    count = 0
    safeones = [] # 与a中球体相交的b的点
    questionableones = []
    for i in range(len(a)):
        for j in range(len(b)):
          dist = math.sqrt((a[i][0]-b[j][0])**2 + (a[i][1]-b[j][1])**2)
          if dist < 2 * r:
            safeones.append(b[j])         
          else:
            if not check_presence(b[j], safeones):
              questionableones.append(b[j])
    safeones = list(set([tuple(i) for i in safeones]))
    safeones = [list(i) for i in safeones]
    questionableones = list(set([tuple(i) for i in questionableones]))
    questionableones = [list(i) for i in questionableones]
    outliers = [i for i in questionableones if i not in safeones]
    
    return len(outliers)

尝试优化后的代码 #

import math
import numpy as np

def check_presence(comparison, safeones):
  for array in safeones:
    if (array == b).all():  # 同样存在变量名错误
      return True
  return False

def circle_intersection(a, b, r): # a是查询集，返回b中的异常值数量
    count = 0
    safeones = [] # 与a中球体相交的b的点
    questionableones = []
    for i in range(len(b)):
        for j in range(len(a)):
          dist = math.sqrt((b[i][0]-a[j][0])**2 + (b[i][1]-a[j][1])**2)
          print(dist)
          if dist < 2 * r:
            break     
          else:
            questionableones.append(b[i])
            
    questionableones = list(set([tuple(i) for i in questionableones]))
    questionableones = [list(i) for i in questionableones]
           
    return len(questionableones)

问题排查 #

1. 优化代码核心逻辑错误：内层循环中，只要当前A球体与B球体距离大于2r就将B球体加入questionableones，导致同一个B球体会被多次添加（只要它和某一个A球体不相交就加一次）。即使后续发现该B球体与其他A球体相交，已加入列表的记录也不会被移除，去重后依然错误统计本应属于“相交”的球体。
2. 原代码check_presence函数bug：错误使用全局变量b而非参数comparison，导致判断逻辑完全失效，无法正确检查坐标是否已存在于safeones中。

修正后的优化代码 #

import math
import numpy as np

def circle_intersection(a, b, r):
    outlier_count = 0
    # 遍历每个B中的球体
    for b_sphere in b:
        has_intersection = False
        # 遍历A中的球体，找到相交的就提前终止
        for a_sphere in a:
            # 用距离平方代替开根号，减少计算开销
            dist_squared = (a_sphere[0] - b_sphere[0])**2 + (a_sphere[1] - b_sphere[1])**2
            if dist_squared < (2 * r)**2:
                has_intersection = True
                break
        # 若遍历完所有A球体都未相交，计数+1
        if not has_intersection:
            outlier_count += 1
    return outlier_count

优化说明 #

• 正确的提前终止逻辑：每个B球体只要找到一个相交的A球体就停止内层循环，避免不必要的计算
• 计算效率提升：比较距离平方与(2r)²的大小，省去开根号的运算，减少计算量
• 简化逻辑：直接计数，去掉冗余的列表存储与去重操作，节省内存与时间
• 修复变量名错误：彻底规避原代码中变量混淆导致的逻辑失效问题

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