Is there a way to compare two list of dicts in python?

Question

I have a 2 list of dictionaries. The first list contains sphere definitions in terms of x, y, z, radius. The second list contains various points in space as x, y, z. These lists are both very long, so iterating over each list and compare against all values is inefficient.

I've been trying the map and reduce terms, but both of them take only 1 term in the filtering function. What I'm using is the following.

      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

where i is the current sphere (x, y, z, rad) and curNode is the node (num, x, y, z). For large lists, this becomes very inefficient. I'd like to filter out nodes which fall within the radius of any spheres.

Answer 1

You may want to look into something like spatial octrees to reduce the number of spheres you have to check each point against.

Answer 2

try this:

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

nodeRemovalList = filter(in_sphere, nodeList)

This will run much faster than the code that you have displayed.

this is assuming that you actually want the nodeRemovalList and that it isn't just an intermediate step. If it's just an intermediate step, return not any( and the result of `filter will be the set you want.

Also, why isn't sphere['radius'] already a float? this would speed things up a little on a really huge list.

Answer 3

Are you trying to detect which points fall within a sphere. Using matrix based approach in numpy may be easier since you can do a 3d distance vector for all points efficiently, let p = point (x1,y1,z1). Let A be arrays of sphere centres then distance vector arrays can be computer and compared against radius arrays in numpy. You will find matrix operations faster than iterations.