CODEWITHSUNDEEP
pythonperformancelistfiltercompare
Shuo
Shuo

Reputation: 491

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

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.

Upvotes: 4

Views: 540

Answers (3)

aaronasterling
aaronasterling

Reputation: 70994

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.

Upvotes: 4

whatnick
whatnick

Reputation: 5470

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.

Upvotes: 2

Amber
Amber

Reputation: 526573

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

Upvotes: 3

Related Questions