Existe-t-il un moyen de comparer efficacement deux listes de dicts en python?

Question

J'ai deux listes de dictionnaires. La première liste contient les définitions de sphères en termes de x, y, z, rayon. La deuxième liste contient divers points dans l'espace comme x, y, z. Ces listes sont toutes deux très longues, donc itérer sur chaque liste et comparer avec toutes les valeurs est inefficace.

J'ai essayé la carte et réduire les délais, mais les deux d'entre eux prennent seulement 1 terme dans la fonction de filtrage. Ce que j'utilise est la suivante:

 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 

où i est la sphère actuelle (x, y, z, rad) et curNode est le nœud (num, x, y, z). Pour les grandes listes, cela devient très inefficace. Je voudrais filtrer les noeuds qui tombent dans le rayon de n'importe quelle sphère.

Answer 1

Vous pouvez regarder dans quelque chose comme spatial octrees pour réduire le nombre de sphères que vous devez vérifier chaque point contre.

Answer 2

essayez ceci:

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

nodeRemovalList = filter(in_sphere, nodeList) 

Cela se déroulera beaucoup plus vite que le code que vous avez affiché.

ceci suppose que vous voulez réellement le nodeRemovalList et qu'il est non seulement une étape intermédiaire. Si ce n'est qu'une étape intermédiaire, renvoyer not any( et le résultat de `filter sera l'ensemble que vous voulez.

Aussi, pourquoi ne pas sphere['radius'] déjà un flotteur? Cela accélérerait un peu les choses sur une liste vraiment énorme.

Answer 3

Êtes-vous essayer de détecter les points se situent dans une sphère. L'utilisation d'une approche matricielle en numpy peut être plus facile puisque vous pouvez faire un vecteur de distance 3d pour tous les points de manière efficace, soit p = point (x1, y1, z1). Soit A des tableaux de centres de sphères puis des tableaux de vecteurs de distance peuvent être calculés et comparés à des tableaux de rayons dans numpy. Vous trouverez les opérations matricielles plus rapidement que les itérations.