有没有高效比较两个字典列表的方法？

Question

我有两个字典列表。第一个列表包含球体的定义，具体是用 x, y, z, 半径 来表示的。第二个列表则包含了空间中的各种点，用 x, y, z 表示。这两个列表都非常长，所以逐个遍历每个列表并进行比较效率很低。

我尝试过使用 map 和 reduce 这些方法，但它们的过滤函数只能处理一个参数。我现在用的是下面的代码：

      for curNode in nodeList:
            for i in sphereList:
                    tmpRad = findRadius(i, curNode)
                    if float(tmpRad) <= float(i['radius']):
                            print "Remove node", curNode['num']
                            nodeRemovalList.append(curNode['num'])
                            break

这里的 i 是当前的球体 (x, y, z, 半径)，而 curNode 是节点 (编号, x, y, z)。对于很大的列表，这样做效率就变得很低。我想要过滤掉那些在任何球体半径范围内的节点。

Answer 1

你是不是想找出哪些点在一个球体里面？用numpy的矩阵方法可能会更简单，因为这样可以高效地计算所有点到球心的三维距离。假设p是一个点，坐标是(x1,y1,z1)。然后让A是一个存放球心坐标的数组，这样你就可以计算出距离向量数组，并把它们和半径数组进行比较。在numpy中，矩阵运算会比逐个循环处理要快很多。

Answer 2

你可以考虑使用像空间八叉树这样的东西，这样可以减少你需要检查每个点的球体数量。

Answer 3

试试这个：

def in_sphere(node):
    return any(float(findRadius(sphere, node)) <= float(sphere['radius']) 
               for sphere in sphereList)

nodeRemovalList = filter(in_sphere, nodeList)

这个方法运行起来会快得多，比你展示的代码要高效很多。

这里假设你确实需要nodeRemovalList，而它不是一个临时步骤。如果只是临时步骤，那就返回not any(，这样`filter`的结果就是你想要的集合。

另外，为什么sphere['radius']还不是浮点数呢？如果它是浮点数的话，在处理非常大的列表时会稍微快一些。