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

Question

I have two lists 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 comparing 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 sphere.

Answer 1

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 2

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