Des Millions de points 3D: Comment trouver le 10 de leur plus proche d'un point donné?

Un point 3-d est définie par (x,y,z). La Distance d entre deux points (X,Y,Z) et (x,y,z) est d= Sqrt[(X-x)^2 + (Y-Y)^2 + (Z-z)^2].
Maintenant il y a un million d'entrées dans un fichier, chaque entrée est un point dans l'espace, dans aucun ordre particulier. Étant donné un point (a,b,c) trouver le plus proche de 10 points. Comment voulez-vous stocker les millions de points et comment feriez-vous pour récupérer ces 10 points à partir de cette structure de données.

Avez-vous de créer et de remplir la structure de données avant ou après on vous dit que le point (a,b,c) est? David réponse, par exemple, ne fonctionne pas si vous créez la structure de données tout d'abord, et ensuite un utilisateur types (a,b,c) et veut une réponse instantanément.
Bon point (sans mauvais jeu de mots!) Bien sûr, si (a,b,c) n'est pas connu à l'avance, c'est plus un problème d'optimisation de la liste des points pour la recherche par géolocalisation 3D, plutôt que de faire de la recherche.
Il devrait vraiment être précisé si le coût de préparation de la structure des données et le stockage des millions de points dans cette structure de données doit être pris en compte, ou seulement la récupération de la performance compte. Si ce coût n'a pas d'importance, alors peu importe combien de fois vous permettra de récupérer les points de kd-tree va gagner. Si ce coût n'a d'importance, alors vous devez aussi spécifier le nombre de fois que vous attendez pour lancer la recherche (pour le petit nombre de recherches de la force brute va gagner, pour les plus grands kd va gagner).

InformationsquelleAutor Kazoom | 2010-03-21

Millions de points est un petit nombre. L'approche la plus simple qui fonctionne ici (code basé sur KDTree est plus lent (pour l'interrogation d'un seul point)).

Force Brute approche (temps ~1 seconde)

#!/usr/bin/env python
import numpy

NDIM = 3 # number of dimensions

# read points into array
a = numpy.fromfile('million_3D_points.txt', sep=' ')
a.shape = a.size / NDIM, NDIM

point = numpy.random.uniform(0, 100, NDIM) # choose random point
print 'point:', point
d = ((a-point)**2).sum(axis=1)  # compute distances
ndx = d.argsort() # indirect sort 

# print 10 nearest points to the chosen one
import pprint
pprint.pprint(zip(a[ndx[:10]], d[ndx[:10]]))

De l'exécuter:

$ time python nearest.py 
point: [ 69.06310224   2.23409409  50.41979143]
[(array([ 69.,   2.,  50.]), 0.23500677815852947),
 (array([ 69.,   2.,  51.]), 0.39542392750839772),
 (array([ 69.,   3.,  50.]), 0.76681859086988302),
 (array([ 69.,   3.,  50.]), 0.76681859086988302),
 (array([ 69.,   3.,  51.]), 0.9272357402197513),
 (array([ 70.,   2.,  50.]), 1.1088022980015722),
 (array([ 70.,   2.,  51.]), 1.2692194473514404),
 (array([ 70.,   2.,  51.]), 1.2692194473514404),
 (array([ 70.,   3.,  51.]), 1.801031260062794),
 (array([ 69.,   1.,  51.]), 1.8636121147970444)]

real    0m1.122s
user    0m1.010s
sys 0m0.120s

Voici le script qui génère des millions de points 3D:

#!/usr/bin/env python
import random
for _ in xrange(10**6):
    print ' '.join(str(random.randrange(100)) for _ in range(3))

De sortie:

$ head million_3D_points.txt

18 56 26
19 35 74
47 43 71
82 63 28
43 82 0
34 40 16
75 85 69
88 58 3
0 63 90
81 78 98

Vous pouvez utiliser ce code pour tester plus complexe des structures de données et algorithmes (par exemple, si elles réellement consommer moins de mémoire ou plus rapide, puis au-dessus de la méthode la plus simple). Il est intéressant de noter que pour l'instant c'est la seule réponse qui contient du code qui fonctionne.

Solution basée sur KDTree (temps ~1,4 secondes)

#!/usr/bin/env python
import numpy

NDIM = 3 # number of dimensions

# read points into array
a = numpy.fromfile('million_3D_points.txt', sep=' ')
a.shape = a.size / NDIM, NDIM

point =  [ 69.06310224,   2.23409409,  50.41979143] # use the same point as above
print 'point:', point


from scipy.spatial import KDTree

# find 10 nearest points
tree = KDTree(a, leafsize=a.shape[0]+1)
distances, ndx = tree.query([point], k=10)

# print 10 nearest points to the chosen one
print a[ndx]

De l'exécuter:

$ time python nearest_kdtree.py  

point: [69.063102240000006, 2.2340940900000001, 50.419791429999997]
[[[ 69.   2.  50.]
  [ 69.   2.  51.]
  [ 69.   3.  50.]
  [ 69.   3.  50.]
  [ 69.   3.  51.]
  [ 70.   2.  50.]
  [ 70.   2.  51.]
  [ 70.   2.  51.]
  [ 70.   3.  51.]
  [ 69.   1.  51.]]]

real    0m1.359s
user    0m1.280s
sys 0m0.080s

Partielle de tri en C++ (temps ~1.1 secondes)

//$ g++ nearest.cc && (time ./a.out < million_3D_points.txt )
#include <algorithm>
#include <iostream>
#include <vector>
#include <boost/lambda/lambda.hpp>  //_1
#include <boost/lambda/bind.hpp>    //bind()
#include <boost/tuple/tuple_io.hpp>
namespace {
typedef double coord_t;
typedef boost::tuple<coord_t,coord_t,coord_t> point_t;
coord_t distance_sq(const point_t& a, const point_t& b) { //or boost::geometry::distance
coord_t x = a.get<0>() - b.get<0>();
coord_t y = a.get<1>() - b.get<1>();
coord_t z = a.get<2>() - b.get<2>();
return x*x + y*y + z*z;
}
}
int main() {
using namespace std;
using namespace boost::lambda; //_1, _2, bind()
//read array from stdin
vector<point_t> points;
cin.exceptions(ios::badbit); //throw exception on bad input
while(cin) {
coord_t x,y,z;
cin >> x >> y >> z;    
points.push_back(boost::make_tuple(x,y,z));
}
//use point value from previous examples
point_t point(69.06310224, 2.23409409, 50.41979143);
cout << "point: " << point << endl;  //1.14s
//find 10 nearest points using partial_sort() 
//Complexity: O(N)*log(m) comparisons (O(N)*log(N) worst case for the implementation)
const size_t m = 10;
partial_sort(points.begin(), points.begin() + m, points.end(), 
bind(less<coord_t>(), //compare by distance to the point
bind(distance_sq, _1, point), 
bind(distance_sq, _2, point)));
for_each(points.begin(), points.begin() + m, cout << _1 << "\n"); //1.16s
}

De l'exécuter:

g++ -O3 nearest.cc && (time ./a.out < million_3D_points.txt )
point: (69.0631 2.23409 50.4198)
(69 2 50)
(69 2 51)
(69 3 50)
(69 3 50)
(69 3 51)
(70 2 50)
(70 2 51)
(70 2 51)
(70 3 51)
(69 1 51)
real    0m1.152s
user    0m1.140s
sys 0m0.010s

File d'attente de priorité en C++ (temps ~1.2 secondes)

#include <algorithm>           //make_heap
#include <functional>          //binary_function<>
#include <iostream>
#include <boost/range.hpp>     //boost::begin(), boost::end()
#include <boost/tr1/tuple.hpp> //get<>, tuple<>, cout <<
namespace {
typedef double coord_t;
typedef std::tr1::tuple<coord_t,coord_t,coord_t> point_t;
//calculate distance (squared) between points `a` & `b`
coord_t distance_sq(const point_t& a, const point_t& b) { 
//boost::geometry::distance() squared
using std::tr1::get;
coord_t x = get<0>(a) - get<0>(b);
coord_t y = get<1>(a) - get<1>(b);
coord_t z = get<2>(a) - get<2>(b);
return x*x + y*y + z*z;
}
//read from input stream `in` to the point `point_out`
std::istream& getpoint(std::istream& in, point_t& point_out) {    
using std::tr1::get;
return (in >> get<0>(point_out) >> get<1>(point_out) >> get<2>(point_out));
}
//Adaptable binary predicate that defines whether the first
//argument is nearer than the second one to given reference point
template<class T>
class less_distance : public std::binary_function<T, T, bool> {
const T& point;
public:
less_distance(const T& reference_point) : point(reference_point) {}
bool operator () (const T& a, const T& b) const {
return distance_sq(a, point) < distance_sq(b, point);
} 
};
}
int main() {
using namespace std;
//use point value from previous examples
point_t point(69.06310224, 2.23409409, 50.41979143);
cout << "point: " << point << endl;
const size_t nneighbours = 10; //number of nearest neighbours to find
point_t points[nneighbours+1];
//populate `points`
for (size_t i = 0; getpoint(cin, points[i]) && i < nneighbours; ++i)
;
less_distance<point_t> less_distance_point(point);
make_heap  (boost::begin(points), boost::end(points), less_distance_point);
//Complexity: O(N*log(m))
while(getpoint(cin, points[nneighbours])) {
//add points[-1] to the heap; O(log(m))
push_heap(boost::begin(points), boost::end(points), less_distance_point); 
//remove (move to last position) the most distant from the
//`point` point; O(log(m))
pop_heap (boost::begin(points), boost::end(points), less_distance_point);
}
//print results
push_heap  (boost::begin(points), boost::end(points), less_distance_point);
//  O(m*log(m))
sort_heap  (boost::begin(points), boost::end(points), less_distance_point);
for (size_t i = 0; i < nneighbours; ++i) {
cout << points[i] << ' ' << distance_sq(points[i], point) << '\n';  
}
}

De l'exécuter:

$ g++ -O3 nearest.cc && (time ./a.out < million_3D_points.txt )
point: (69.0631 2.23409 50.4198)
(69 2 50) 0.235007
(69 2 51) 0.395424
(69 3 50) 0.766819
(69 3 50) 0.766819
(69 3 51) 0.927236
(70 2 50) 1.1088
(70 2 51) 1.26922
(70 2 51) 1.26922
(70 3 51) 1.80103
(69 1 51) 1.86361
real    0m1.174s
user    0m1.180s
sys 0m0.000s

Linéaire basée sur la Recherche de l'approche (temps ~1.15 secondes)

//$ g++ -O3 nearest.cc && (time ./a.out < million_3D_points.txt )
#include <algorithm>           //sort
#include <functional>          //binary_function<>
#include <iostream>
#include <boost/foreach.hpp>
#include <boost/range.hpp>     //begin(), end()
#include <boost/tr1/tuple.hpp> //get<>, tuple<>, cout <<
#define foreach BOOST_FOREACH
namespace {
typedef double coord_t;
typedef std::tr1::tuple<coord_t,coord_t,coord_t> point_t;
//calculate distance (squared) between points `a` & `b`
coord_t distance_sq(const point_t& a, const point_t& b);
//read from input stream `in` to the point `point_out`
std::istream& getpoint(std::istream& in, point_t& point_out);    
//Adaptable binary predicate that defines whether the first
//argument is nearer than the second one to given reference point
class less_distance : public std::binary_function<point_t, point_t, bool> {
const point_t& point;
public:
explicit less_distance(const point_t& reference_point) 
: point(reference_point) {}
bool operator () (const point_t& a, const point_t& b) const {
return distance_sq(a, point) < distance_sq(b, point);
} 
};
}
int main() {
using namespace std;
//use point value from previous examples
point_t point(69.06310224, 2.23409409, 50.41979143);
cout << "point: " << point << endl;
less_distance nearer(point);
const size_t nneighbours = 10; //number of nearest neighbours to find
point_t points[nneighbours];
//populate `points`
foreach (point_t& p, points)
if (! getpoint(cin, p))
break;
//Complexity: O(N*m)
point_t current_point;
while(cin) {
getpoint(cin, current_point); //NOTE: `cin` fails after the last
//point, so one can't lift it up to
//the while condition
//move to the last position the most distant from the
//`point` point; O(m)
foreach (point_t& p, points)
if (nearer(current_point, p)) 
//found point that is nearer to the `point` 
//NOTE: could use insert (on sorted sequence) & break instead
//of swap but in that case it might be better to use
//heap-based algorithm altogether
std::swap(current_point, p);
}
//print results;  O(m*log(m))
sort(boost::begin(points), boost::end(points), nearer);
foreach (point_t p, points)
cout << p << ' ' << distance_sq(p, point) << '\n';  
}
namespace {
coord_t distance_sq(const point_t& a, const point_t& b) { 
//boost::geometry::distance() squared
using std::tr1::get;
coord_t x = get<0>(a) - get<0>(b);
coord_t y = get<1>(a) - get<1>(b);
coord_t z = get<2>(a) - get<2>(b);
return x*x + y*y + z*z;
}
std::istream& getpoint(std::istream& in, point_t& point_out) {    
using std::tr1::get;
return (in >> get<0>(point_out) >> get<1>(point_out) >> get<2>(point_out));
}
}

Mesures montre que la plupart du temps est consacré à la lecture de tableau à partir du fichier, réel les calculs de prendre sur l'ordre de grandeur de moins de temps.

Belle écriture. Afin de compenser pour lire le fichier que j'ai exécuter votre implémentations de python avec boucle autour de la recherche qui s'exécutent 100 fois (chaque fois que la recherche autour d'un point et la construction du kd-tree seule fois). Le bruteforce encore gagné. M'a fait rayer de ma tête. Mais ensuite, j'ai examiné votre leafsize et vous avez une erreur là, vous êtes réglage de la leafsize à 1000001, et qui va pas bien. Après le réglage de leafsize à 10, kd a remporté (35 à 70 pour 100 points, avec plus de 35 dépensé pour la construction de l'arbre et de 100 pour les récupérations de 10 points en prenant une seconde).
Donc pour conclure, si vous pouvez précalculer le kd-tree, il va gagner plus de force brute par ordre de grandeur, (pour ne pas mentionner que pour les très grands ensembles de données, si vous avez un arbre, vous n'aurez pas à lire toutes les données en mémoire).
si j'ai mis leafsize à 10, puis il prend environ 10 secondes (au lieu de 1 seconde) pour interroger un point. Je suis d'accord si la tâche est de requêtes multiples (>10) points, puis kd-arbre doit gagner.
pririty de file d'attente, et la recherche linéaire implémentations basées au-dessus de ne PAS lire toutes les données en mémoire.
désolé j'ai été imprécis - ils ont pour analyser toutes les données (lire en mémoire). Je suis d'accord qu'ils n'ont pas à le garder en mémoire. Le kd tree approche (une fois qu'il a un kd index pour analyser l'index seulement, la lecture d'une partie seulement de celui-ci). Bien sûr, à la construction de l'index, il faudra lire toutes les données, mais j'ai été commentant la situation où vous peut précalculer (qui dans le cas de la recherche linéaire est pas de gain)
de scipy.spatiale importation cKDTree est cython, n'recherches > 50 fois plus rapide que le pur python KDTree (dans 16d, sur mon vieux mac ppc).
Merci pour le bon travail. Afin de rendre cette réponse plus utile, il serait préférable d'avoir le temps nécessaire pour mettre en place la structure de données séparés depuis le temps qu'il faut pour vérifier l'10 points. Je reconnais que la question posée uniquement pour 10 points, mais pour faire de votre réponse la plus utile au monde, il serait préférable de généraliser à n points et à faire tout ce qu'il faudrait serait de séparer la mise en place et de temps d'exécution.
Souhait vous avez ajouté quelques explications, pour chaque solution. Cette réponse n'est pas utile, pour les personnes qui ne sont pas familiers avec python et C++. comme moi!
Si vous voulez seulement la plus proche de 10 points et vous ne se soucient pas de leur ordre, vous pourriez probablement gagner du temps en utilisant np.argpartition plutôt que np.argsort.
notez qu'il y a "force brute" dans le titre du code qui utilise np.argsort().
Je me rends compte que - je voudrais également envisager d' np.argpartition être une "force brute" de la solution. Je pense qu'il serait au moins la peine de mentionner, étant donné que vous avez également montré une codés à la main partielle de tri en C++.

InformationsquelleAutor jfs

20

Si le million d'entrées sont déjà dans un fichier, il n'y a pas besoin de charger le tout dans une structure de données en mémoire. Il suffit de garder un tableau avec les dix points trouvés jusqu'à présent, et de balayage sur le million de points, la mise à jour de votre top-ten de la liste que vous allez.

C'est O(n) du nombre de points.
- Cela fonctionne bien, mais le tableau n'est pas la plus efficace de la banque de données, parce que vous avez à vérifier à chaque étape, ou de garder un tri, ce qui peut être embêtant. David réponse sur un min-tas n'a que des trucs pour vous, mais est par ailleurs la même solution. Lorsque l'utilisateur veut seulement 10 points, ces préoccupations sont négligeables, mais, lorsque l'utilisateur soudainement veut le plus proche de 100 pts, vous serez en difficulté.
- Karl: La question précise de 10 points. Je pense notamment à ce détail est délibéré de la part de la personne. Ainsi, Sera décrit une très bonne solution pour ce qui était demandé.
- il est souvent surprenant de voir comment bien le compilateur et le CPU est à l'optimisation de la chose la plus stupide des boucles de battre le plus malin des algorithmes. Ne jamais sous-estimer l'accélération d'être gagné lors d'une boucle peut s'exécuter sur-puce de ram.
- Millions d'entrées ne sont pas déjà dans le fichier - vous pouvez choisir comment les stocker dans le fichier. 🙂 Ce choix sur la façon de stocker, cela implique que vous pouvez également précalculer accompagnement de l'indexation de la structure. Kd-tree va gagner, comme elle n'aura pas à lire le fichier en entier, à tous < O(n).
- Je n'ai pas posté de mise en œuvre de votre réponse, stackoverflow.com/questions/2486093/... (bien que j'utilise le tas plutôt que de la recherche linéaire et il est complètement inutile pour la tâche)
- Karl est un droit, un tas, c'est mieux. l'Utilisation d'un segment de mémoire.
- Pour les 10 points de la recherche linéaire est mieux que des tas (1.11-1.12 vs 1.15-1.18 secondes pour l'entrée j'ai testé). Pour N=10 un facteur constant dans l'algorithme ne s'agit donc O(N) de l'algorithme peut être plus rapide que O(log(N)) l'algorithme.
- 1.11 vs 1.15 est assez mince. J'avais le code avec un tas de toute façon dans le cas où j'ai toujours voulu faire de plus de 10. Bien sûr, je ne sais pas ce que l'OP veut faire avec elle.
InformationsquelleAutor Will
14

Vous pouvez stocker les points dans une k-dimensions de l'arbre (kd-tree). Kd-trees sont optimisés pour le plus proche voisin de recherches (recherche du n points les plus proches d'un point donné).
- Je pense qu'un octree est ici.
- La complexité nécessaire pour construire un K-d tree va être plus élevé que la complexité nécessaire pour faire une recherche linéaire pour les 10 placard points. La puissance réelle d'un k-d tree vient quand vous allez faire beaucoup de requêtes sur un ensemble de points.
- Un gros avantage d'un kd-tree est que tout ça va prendre un certain surcharge de la mémoire de construire, une fois que vous avez une gauche équilibrée kd-tree ne prend pas plus de mémoire que l'original non structurées liste de le point. Un octree aurez certainement besoin au moins de quelques surcharge de la mémoire.
- kd-arbre peut être plus lente dans la vie réelle que la force brute approche stackoverflow.com/questions/2486093/...
- C'est la réponse que je donnerais dans une interview. Il n'est pas rare pour les enquêteurs d'utiliser moins-que-la précision du langage et de la lecture entre les lignes de ce qui semble être le plus probable de ce qu'ils recherchent. En fait, si je devais l'interviewer, et quelqu'un a donné la réponse "je voudrais stocker les points dans n'importe quel ordre ancien, et de faire une analyse linéaire pour trouver les 10 points" et justifié de répondre en fonction de mon libellé imprécis, je serais assez impressionné.
- Jason Orendorff: je serais certainement discuter de l'utilisation d'un kd-tree pour un tel problème dans un entretien technique; cependant, je voudrais aussi expliquer que le problème spécifique donné, le plus simple, linéaire de la méthode de recherche ne sera pas seulement asymptoticly plus rapide, mais de courir plus vite aussi. Cela permettra de montrer une compréhension plus profonde de la complexité des algorithmes, la connaissance des structures de données, et la capacité à envisager différentes solutions à un problème.
InformationsquelleAutor mipadi
10

Je pense que c'est une question délicate que les tests si vous n'essayez pas de faire trop de choses.

Considérer le simple algorithme de personnes l'ont déjà donnée ci-dessus: garder une table des dix meilleurs la mesure des candidats et de passer par tous les points un par un. Si vous trouvez de plus près que l'un des dix meilleurs la mesure, le remplacer. Quelle est la complexité? Eh bien, nous devons nous pencher sur chaque point à partir du fichier une fois, calculer la distance (ou le carré de la distance) et de les comparer avec le 10ème point le plus proche. Si c'est mieux, l'insérer à l'endroit approprié dans le 10-meilleur-si-loin de la table.

Alors, quelle est la complexité? Nous regardons chaque point d'une fois, il est donc n calculs de la distance et n comparaisons. Si le point est mieux, nous avons besoin de l'insérer dans la bonne position, cela demande un peu plus de comparaisons, mais c'est une constante depuis le tableau des meilleurs candidats est d'une taille constante 10.

Nous nous retrouvons avec un algorithme qui s'exécute en temps linéaire, O(n) du nombre de points.

Mais maintenant examiner ce qui est le limite inférieure sur un tel algorithme? Si il n'y a pas d'ordre dans les données d'entrée, nous ont pour regarder chaque point pour voir si ce n'est pas l'un des plus proches. Donc autant que je peux voir, la limite inférieure est Omega(n) et donc l'algorithme ci-dessus est optimal.
- Excellent point! Depuis que vous avez à lire les fichier un par un afin de construire une structure de données, votre plus bas possible est O(n) juste comme vous le dites. Seulement si la question demande de trouver la plus proche de 10 points à plusieurs reprises ne fait rien d'autre question! Et vous l'explique bien je pense.
InformationsquelleAutor Krystian
5

Cette question est essentiellement de tester vos connaissances et/ou l'intuition de les algorithmes de partitionnement de l'espace. Je dirais que de stocker les données dans un l'octree est votre meilleur pari. Il est couramment utilisé dans les moteurs 3d qui gèrent ce type de problème (stocker des millions de sommets, le lancer de rayons, de trouver des collisions, etc.). Le temps de recherche sera de l'ordre de log(n) dans le pire des cas (je crois).

InformationsquelleAutor Kai
5

Pas nécessaire de calculer la distance. Juste le carré de la distance devrait servir à vos besoins. Devrait être plus rapide je pense. En d'autres termes, vous pouvez sauter le sqrt peu.

InformationsquelleAutor Agnel Kurian
4

Ce n'est pas des devoirs à faire à la question, est-il? 😉

Ma pensée: itérer sur tous les points et de les mettre dans un tas min ou délimitée de la file d'attente de priorité, clé en fonction de la distance de la cible.
- c'est une question d'entrevue
- bien sûr, mais on ne sait pas quelle est la cible. 🙂
InformationsquelleAutor David Z
2

Simple algorithme:

Stocker les points comme une liste de tuples, et d'analyse sur les points, le calcul de la distance, et de garder un "plus proche" la liste.

Plus créatif:

Groupe de points dans des régions comme le cube décrit par "0,0,0" à "50,50,50", ou "0,0,0" à "-20,-20,-20"), de sorte que vous pouvez "index" dans les de la cible. Vérifier cube de la cible se trouve dans l', et seulement à la recherche à travers les points du cube. Si il y a moins de 10 points du cube, cochez la case "voisins" des cubes, et ainsi de suite.

Sur la poursuite de la réflexion, ce n'est pas un très bon algorithme: si votre cible est plus proche de la paroi d'un cube de 10 points, alors vous aurez à chercher dans les pays voisins cube ainsi.

J'irais avec le kd-tree approche et de trouver le plus proche, puis l'enlever (ou la marque) que le plus proche nœud, et la recherche de la nouvelle la plus proche nœud. Rincer et répéter.

InformationsquelleAutor Jeff Meatball Yang
2

Pour toutes les deux points P1 (x1, y1, z1) et P2 (x2, y2, z2), si la distance entre les points est d alors toutes les conditions suivantes doivent être remplies:
```
|x1 - x2| <= d 
|y1 - y2| <= d
|z1 - z2| <= d
```
Tenir le 10 le plus proche que vous itérer sur l'ensemble de votre jeu, mais aussi la distance à la 10e plus proche. Epargnez-vous beaucoup de complexité à l'aide de ces trois conditions avant de calculer la distance de chaque point que vous regardez.

InformationsquelleAutor Kirk Broadhurst
1

essentiellement d'une combinaison des deux premiers réponse au-dessus de moi. puisque les points sont dans un fichier il n'y a pas besoin de les garder en mémoire. Au lieu d'un tableau, ou un tas min, je voudrais utiliser un max de tas, puisque vous ne voulez vérifier pour les distances inférieures à la 10e point le plus proche. Pour un tableau, vous devez comparer chaque nouvelle calcule la distance avec les 10 distances vous avez gardé. Pour un min d'un segment, vous devez effectuer 3 comparaisons avec chaque nouvelle distance calculée. Avec un max de tas, que vous n'effectuez 1 comparaison quand la nouvelle distance calculée est plus grande que le nœud racine.

InformationsquelleAutor Yiling
1

Cette question mérite une définition plus précise.

1)
La décision concernant les algorithmes de pré-données de l'indice varie beaucoup en fonction de si vous pouvez tenir l'ensemble des données dans la mémoire ou non.

Avec kdtrees et octrees vous n'aurez pas à contenir les données dans la mémoire et la performance des prestations de ce fait, non seulement parce que l'empreinte mémoire est plus bas, mais tout simplement parce que vous n'aurez pas à lire le fichier en entier.

Avec bruteforce, vous aurez à lire l'ensemble du dossier et recalculer les distances pour chaque nouveau point, vous serez à la recherche pour.

Encore, cela peut ne pas être important pour vous.

2)
Un autre facteur est combien de fois vous avez à la recherche pour un point.

Comme indiqué par J. F. Sebastian parfois bruteforce est plus rapide, même sur de grands ensembles de données, mais prendre soin de prendre en compte le fait que ses repères mesure de la lecture de l'ensemble du jeu de données à partir du disque (qui n'est pas nécessaire, une fois kd-tree ou de l'octree est construit et écrit quelque part) et qu'ils ne mesurent que l'on recherche.

InformationsquelleAutor Unreason
0

Calculer la distance pour chacun d'eux, et de faire une sélection(1..10, n) à O(n) fois. Que serait l'algorithme naïf, je suppose.

InformationsquelleAutor Rubys

Vous devez vous connecter pour publier un commentaire.