Discussion :

[moooona]

Bonjour,
j'ai une classe Point

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
public class Point
{
Private:
double _x;
double _y;
double _z;
}

j'ai un vecteur( std::vector) de points. ce dernier contient 1700000 points. Je vais faire la projection sur un plan et je stocke les projections dans un vecteur. J4AI DES POINTS QUI ONT le même point projeté. POUR CETTE RAISON JE VEUX chercher si cette projection se trouve dans le vecteur des projection ou non. Si elle existe alors je ne vais ajouter des doublons.si pour chaque point je vais faire un parcours . JE VAIS PASSER 4HEURES DANS CE CALCUL; Y A T IL UNE IDée pour optimiser et minimiser le temps.
MERCI POUR VOTRE AIDE

[Ehonn]

Bonjour

Utilise std::set ou std::unordered_set pour stocker les projections (?)

[Daïmanu]

Bonjour.

En gros, tu veux que ton vecteur n'ai pas de doublons ?

Dans ce cas, un std::set<Point> (ou std::unordered_set<Point>) est plus approprié qu'un std::vector<Point>.

Le set garantit l'unicité des points, à la seule condition de fournir des opérateurs de comparaison de Point (bool operator < (const Points&, const Point&);)

[Matt_Houston]

Je sais PAS TROP CE QUE ça apporte mais ça semble MARRANT CE RANDOM ALL CAPS, et si on S4Y METTAIT TOUS ?

Question habituelle : comment sais-tu que c'est lent (quatre heures, vraiment ? Tu exécutes ça sur un 286 ?), l'as-tu déjà implémenté ? Si tu as une recherche à faire par entrée, alors peut-être faudrait-il utiliser en sortie une structure de donnée adaptée avec une recherche en O(log n) ? I.e. : pas un vector.


Évite les noms de variables qui débutent par _, c'est réservé.

[foetus]

Dans le domaine de la 2D-3D , il y a quand même des structures spécialisées pour la recherche dans l'espace: R-Tree, Quadtree, BSP tree, ....

C'est sûr que c'est un rien [et juste un rien] plus compliqué qu'un vulgaire tableau linéaire (<- )

[ternel]

Petite remarque, un vector trié permet une recherche en logN via std::binary_search.

Pour la 3D, le quad tree est remplacé par un octree. Ces deux techniques ne sont finalement que de la dichotomie simultanée sur les différents axes.

Cela dit, chercher un ensemble de projections uniques parmi N points, ca prend quand même N projections et N log N comparaisons.
Avec N = 1,7 millions, ca doit normalement prendre 1,7 millions fois presque rien (un produit scalaire et une addition vectorielle, soit une vingtaine de multiplication à tout casser)
et 10 millions de comparaisons de points, soit 30 millions de comparaisons numérique.
Ajoute les copies, on doit avoir a peu pres 100 millions d'opérations.
Soit pas plus d'une dizaine de seconde à 1 GHz

La différence pour moi, c'est avant tout N² comparaison (car pas de set ou de tri du vector), sinon, des copies trop nombreuses (pas de assez d'utilisation des références)

N² vallant dans le cas présent trois mille milliards, soit 3000 secondes à 1GHz, je pense que c'est bien là le problème.

[moooona]

Petite remarque, un vector trié permet une recherche en logN via std::binary_search.

Pour la 3D, le quad tree est remplacé par un octree. Ces deux techniques ne sont finalement que de la dichotomie simultanée sur les différents axes.

Cela dit, chercher un ensemble de projections uniques parmi N points, ca prend quand même N projections et N log N comparaisons.
Avec N = 1,7 millions, ca doit normalement prendre 1,7 millions fois presque rien (un produit scalaire et une addition vectorielle, soit une vingtaine de multiplication à tout casser)
et 10 millions de comparaisons de points, soit 30 millions de comparaisons numérique.
Ajoute les copies, on doit avoir a peu pres 100 millions d'opérations.
Soit pas plus d'une dizaine de seconde à 1 GHz

La différence pour moi, c'est avant tout N² comparaison (car pas de set ou de tri du vector), sinon, des copies trop nombreuses (pas de assez d'utilisation des références)

N² vallant dans le cas présent trois mille milliards, soit 3000 secondes à 1GHz, je pense que c'est bien là le problème.

J'ai pas compris qu'est ce que vous voulez dire. Est ce que j'utilise octree ou bien KD tree ou bien quoi exactement

[Pyramidev]

1,7 millions fois presque rien (un produit scalaire et une addition vectorielle, soit une vingtaine de multiplication à tout casser)

Si le plan d'équation a.x + b.y + c.z + d = 0 est sauvegardé sous la forme du quadruplet (a, b, c, d) alors, pour tout point M de l'espace, pour calculer le projeté orthogonal P de M sur le plan, il n'y a qu'une division et 9 multiplications, voire seulement 6 multiplications si on garde en mémoire cache le carré de la norme du vecteur V = (a, b, c) orthogonal à la droite :

VNormeAuCarre = a*a + b*b + c*c
k = (a.Mx + b.My + c.Mz + d) / VNormeAuCarre
Px = Mx - k.a
Py = My - k.b
Pz = Mz - k.c

En effet, c'est presque rien.

[koala01]

Salut,

N² vallant dans le cas présent trois mille milliards, soit 3000 secondes à 1GHz, je pense que c'est bien là le problème.

+1...

Mais on peut sans doute aussi pointer du doigt l'utilisation d'un std::vector sans réservation de taille préalable, avec pour conséquence d'avoir à effectuer pas loin d'un million d'augmentation de taille pour représenter tous les points

Ceci dit, à défaut de voir le code, il nous sera toujours impossible de dire quoi que ce soit, et nous serons systématiquement réduis à supputer !!!

[ternel]

Pour vector, c'est à mitiger, la croissance de la capacité est exponentielle dans quasiment toutes les STL.
Il n'y aura que peu de réallocations, une quinzaine, je pense.

[moooona]

Je sais PAS TROP CE QUE ça apporte mais ça semble MARRANT CE RANDOM ALL CAPS, et si on S4Y METTAIT TOUS ?

Question habituelle : comment sais-tu que c'est lent (quatre heures, vraiment ? Tu exécutes ça sur un 286 ?), l'as-tu déjà implémenté ? Si tu as une recherche à faire par entrée, alors peut-être faudrait-il utiliser en sortie une structure de donnée adaptée avec une recherche en O(log n) ? I.e. : pas un vector.


Évite les noms de variables qui débutent par _, c'est réservé.

quelle est la structure que je peux l'utiliser dans mon cas? oui je l'ai exécuté sur mon PC avec 1700000 points

[renoo]

j'ai un vecteur( std::vector) de points. ce dernier contient 1700000 points. Je vais faire la projection sur un plan et je stocke les projections dans un vecteur. J4AI DES POINTS QUI ONT le même point projeté. POUR CETTE RAISON JE VEUX chercher si cette projection se trouve dans le vecteur des projection ou non. Si elle existe alors je ne vais ajouter des doublons.si pour chaque point je vais faire un parcours . JE VAIS PASSER 4HEURES DANS CE CALCUL; Y A T IL UNE IDée pour optimiser et minimiser le temps.
MERCI POUR VOTRE AIDE

Quand tu dis meme point projeté, tu as une idée si c'est exactement le même point ou si tu as une tolérance d'epsilon ? Si il y a une tolérance alors les std::set et set::unordered_set fonctionneront mal.

Tu fais un arbre equilibré une fois en coupant selon les x et une fois selon les y. Tu fais une insertion simple comme dans un arbre et si tu fais un random sur ton vector au debut tu n'as pas a te soucier des problemes d'équilibrages de l'arbre.