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 (<- )

[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

[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.

[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.

[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.

[koala01]

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.

non, généralement, l'augmentation de capacité se fait selon un facteur de +/- 2.5 (parfois moins), et je peux t'assurer que, sur un gros vecteur (plusieurs millions d'éléments), le simple fait de réserver "à peu près" la place dont on aura besoin peut faire gagner énormément de temps, car, sur 1 700 000, ca en fait des augmentations

[Matt_Houston]

non, généralement, l'augmentation de capacité se fait selon un facteur de +/- 2.5 (parfois moins)

C'est donc bien « exponentiel » puisqu'il s'agit d'un facteur sur la capacité courante.


Petit test rapide chez moi :

Code vector_test.cpp :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v;
 
    std::size_t capacity(v.capacity());
    std::cout << "Initial capacity: " << capacity << std::endl;
 
    for (int i = 0; i < 2000000; ++i) {
        v.push_back(i);
        if (capacity < v.capacity()) {
            capacity = v.capacity();
            std::cout << "Capacity increase at " << v.size() << ": " << capacity << std::endl;
        }
    }
 
    return 0;
}

Qui donne sur cette machine :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$ g++ -std=c++14 -pedantic -Wall -Wextra vector_test.cpp
$ ./a.out
Initial capacity: 0
Capacity increase at 1: 1
Capacity increase at 2: 2
Capacity increase at 3: 4
Capacity increase at 5: 8
Capacity increase at 9: 16
Capacity increase at 17: 32
Capacity increase at 33: 64
Capacity increase at 65: 128
Capacity increase at 129: 256
Capacity increase at 257: 512
Capacity increase at 513: 1024
Capacity increase at 1025: 2048
Capacity increase at 2049: 4096
Capacity increase at 4097: 8192
Capacity increase at 8193: 16384
Capacity increase at 16385: 32768
Capacity increase at 32769: 65536
Capacity increase at 65537: 131072
Capacity increase at 131073: 262144
Capacity increase at 262145: 524288
Capacity increase at 524289: 1048576
Capacity increase at 1048577: 2097152

Ce qui n'est pas une raison pour ne pas réserver le bloc lorsque sa taille est connue, nous sommes d'accord !

[JolyLoic]

Quand on connait la valeur, c'est clair que c'est dommage de s'en priver. Mais j'ai plusieurs fois vu des gens qui faisaient des efforts très importants pour pouvoir appeler reserve, et ils perdaient alors du temps (genre lire 2 fois un fichier, la première lecture ayant juste pour objectif de savoir à combien réserver).

Je viens de faire un petit bench pour voir l'overhead de ne pas faire reserve :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <vector>
#include <random>
#include <chrono>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
using Clk = std::chrono::high_resolution_clock;
 
static random_device rd;
static default_random_engine e{ rd() };
static uniform_int_distribution<> r(1, 6);
 
template<size_t elementCount, bool reserved>
auto doStuff(std::vector<int> const &source)
{
	std::vector<int> result;
	auto start = Clk::now();
	if (reserved)
	{
		result.reserve(elementCount);
	}
	for (auto i : source)
	{
		result.push_back(i);
	}
	auto end = Clk::now();
	int total = 0;
	uniform_int_distribution<> r(0, elementCount - 1);
	for (size_t i = 0 ; i<100 ; i++)
	{
		total += result[r(e)]; // Try to prevent too agressive optimisations
	}
	return chrono::duration_cast<chrono::microseconds>(end - start).count();
}
 
template<size_t elementCount>
void bench()
{
	std::vector<int> source;
	source.reserve(elementCount);
	for (int i = 0; i < elementCount; ++i)
	{
		source.push_back(r(e));
	}
 
	for (int i = 0; i < 3; ++i)
	{
		auto d1 = doStuff<elementCount, true>(source);
		auto d2 = doStuff<elementCount, false>(source);
		cout << setw(12) << elementCount << " "<< setw(12) << d1 << " " << setw(12) << d2 << " " << setw(12) << ((d2*1.0) / d1 - 1) * 100 << endl;
	}
}
 
int main()
{
	cout << setw(12) << "Count" << " "<< setw(12) << "Reserve" << " " << setw(12) << "No reserve" << " " << setw(12) << "Overhead" << endl;
	bench<10>();
	bench<100>();
	bench<1000>();
	bench<10000>();
	bench<100000>();
	bench<1000000>();
	bench<10000000>();
	bench<100000000>();
 
}

Et les résultats sur ma machine :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
       Count      Reserve   No reserve     Overhead
          10            0            1          inf
          10            0            1          inf
          10            0            1          inf
         100            0            3          inf
         100            1            3          200
         100            2            4          100
        1000            5           17          240
        1000            5           11          120
        1000            6           12          100
       10000           59           80      35.5932
       10000           50           83           66
       10000           51           85      66.6667
      100000          552          862      56.1594
      100000          533          820      53.8462
      100000          482          798      65.5602
     1000000         5931         8434       42.202
     1000000         6568         8730      32.9172
     1000000         5858         8951      52.7996
    10000000        55488       107497      93.7302
    10000000        55844       104050      86.3226
    10000000        55964       103244      84.4829
   100000000       596981      1110133      85.9578
   100000000       595945      1093394      83.4723
   100000000       596122      1095163      83.7146

Ce qui fait, pour des tailles raisonnables, un overhead de moins de 100%, sachant qu'on ne fait là rien d'autre que remplir un tableau avec des valeurs précalculées. C'est à dire quasiment rien. Dans un vrai cas d'utilisation, l'overhead sera forcément plus faible. En fait, c'est surtout pour les petites tailles qu'on remarque une différence notable (même si la précision de mesure n'est plus bonne du tout dans ce bench, il faudrait faire les opérations plusieurs fois), ce qui est logique quand on regarde la complexité.