J'ai 2 listes de tuples list1 = [(1.332, 3.23344, 3.22), (2.122, 2.11, 2.33), ... (1, 2, 3)] code> et et List2 = [(4.23, 12.2, 3.333), (1.234, 3.21, 4.342), ... (1.1, 2.2, 3.3)] code>. Ces listes sont toutes deux très longues, quelque part dans les millions de listes. Pour le contexte, chacun de ces points de données est une mesure de la position dans deux jeux de données différents. Maintenant, je veux correspondre à chaque entrée dans list1 code> à une entrée dans list2 code> s'il est "assez proche". Par assez proche, je veux dire que la distance entre les positions est inférieure à une valeur seuil (par exemple .1 par exemple). Ma pensée initiale utilisait la fonction min code> sur chaque entrée dans list1 code>. C'est-à-dire: import numpy as np
import random
def dist(pt1, pt2):
return np.sqrt( ((pt2[0] - pt1[0]) ** 2) + ((pt2[1] - pt1[1]) ** 2) + ((pt2[2] - pt1[2]) ** 2) )
list1 = [(random.random(), random.random(), random.random()) for _ in range(25)]
list2 = [(random.random(), random.random(), random.random()) for _ in range(20)]
threshold = .5
linker = []
for i, entry in enumerate(list1):
m = min(list2, key=lambda x: dist(entry, x))
if dist(entry, m) < threshold:
linker.append((i, list2.index(m))
3 Réponses :
Oui, il s'agit d'une manière consommation de temps de le faire car le premier python n'est pas optimisé pour ces calculs (pour les types de données et etc.) et deuxièmement, ces calculs doivent être optimisés dans n'importe quelle langue. Vous devez utiliser la bibliothèque pour manipuler des matrices telles que NUMPY et PANDAS. Par exemple, dans votre cas, je recommande cette solution: Premièrement: Convertissez vos données en Dataframe de Pandas comme ce message: Liste des utilles à la conversion de Dataframe Deuxièmement: Après cette conversion avec des pandas, il s'agit d'un calcul et d'un calcul facile. par example: https://pandas.pydata.org/ Pandas-Docs / Stable / Référence / API / Pandas.Dataframe.Pow.html
Pandas utilise numpy et numpy est optimisé pour ces calculs.
Une solution simple implique de conserver un tableau 3D de cellules pour regrouper vos entrées. Par exemple, Si vous vraiment avez besoin de cela pour être rapide, vous entrez dans un ensemble d'algorithmes appelés «partitionnaires spaciens». Vous pouvez regarder une chose appelée "kd-arbre", idéal pour stocker des distributions non uniformes de points de manière ultra-compacte (et est optimisée pour récupérer des points dans le quartier à un emplacement.) (1.332, 3.23344, 3.22) peut être regroupé dans la cellule (13, 32, 32) . Une fois que cette structure de données a été emballée, vous pouvez trouver tous les points près de (1.332, 3.23344, 3.22) , en regardant (13, 32, 32) (et certains sous-ensemble de ses 26 voisins.)
Merci pour la réponse et expliquant pour regarder les arbres KD :)
Vous trouvez le voisin le plus proche de chaque point dans un jeu de données à un deuxième jeu de données.
pour les grands données Les approches voisines les plus proches sont bien meilleures car elles ont une complexité O (n * journal (n))
deux personnes populaires à Python sont Kdtree et Balltree
Un exemple de résolution de cela avec Balltree
Sklearn Balltree Doc