Discussion :

[xav3601]

Bonjour à tous,
Je vous expose mon interrogation actuel.
Je travail sur un site web client side avec un serveur node.js en back (qui ne fait pas grand chose pour le moment).
J'ai un algorithme qui va permettre d'effectuer des calculs à partir d'une grande quantité de données côté client, pour que celà n'explose pas la mémoire ou le temps d'execution, je suis obligé de limiter le nombre données en entrée de l'algorithme.
Maintenant, j'aimerais améliorer ce dernier afin de pouvoir progressivement augmenter la quantité de donnée qu'il va traiter, tout en contrôlant la consommation mémoire et le temps d'execution.

Voilà le principe de l'aglorithme:
J'ai des objets json de ce type là (au maximum j'ai 800 objet différents):

Code :

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

1
2
3
4
5
var obj1 = {
    a: 10,
    b: 15,
    c: 7
}

Ces objets sont rangés dans 3 tableaux (actuellement je limite la table de chaque tableau a 10 éléments l'objectif étant d'augmenter cette limite):

Code :

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

1
2
3
var tab1 = [obj1, obj2, obj3];
var tab2 = [obj4, obj5, obj6];
var tab3 = [obj7, obj8, obj9];

Dans mon algo, il faut que je trouve toutes les combinaisons possible en prenant 2 objets par tableau, puis que je fasse des calculs sur ces objets.
Actuellement, j'utilise des boucles imbriqués comme suit:

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
 
	var i = 0, i0 = 0, i1 = 1, i2 = 0, i3 = 1, i4 = 0, i5 = 1;
	for (; i0 < tab1.length; i0++) {
		for (; i1 < tab1.length; i1++) {
			for (; i2 < tab2.length; i2++) {
				for (; i3 < tab2.length; i3++) {
					for (; i4 < tab3.length; i4++) {
						for (; i5 < tab3.length; i5++) {
							//function de calcul
						}
						i5 = i4+2;
					}
					i4 = 0;
					i5 = 1;
				}
				i3 = i2+2;
				i4 = 0;
				i5 = 1;
			}
			i2 = 0;
			i3 = 1;
			i4 = 0;
			i5 = 1;
		}
		i1 = i0+2;
		i2 = 0;
		i3 = 1;
		i4 = 0;
		i5 = 1;
	}

Ca fonctionne bien, mais dès que j'augmente le nombre d'objets par tableau, j'explose la mémoire et surtout le temps d'execution!
J'utilise des workers pour exectuer la fonction de calcul afin d'améliorer le temps de réponse.
La mémoire explose aussi car la fonction de calcul va sortir un tableau de résultat qui contient des objets assez conséquent en taille.

Pour améliorer ca, j'ai donc un serveur node.js et une bdd mysql.

Si vous avez des idées
Merci et bonne journée!

[Watilin]

Bonjour !

Si j’ai bien compris ton problème, il s’agit de prendre, pour chacun des 3 tableaux, les combinaisons de 2 éléments parmi n (n = taille des tableaux), ce qui nous donne 3 ensembles de taille n! / 2(n - 2)!, puis de parcourir le produit cartésien de ces trois ensembles.

Par exemple, pour n = 3, les ensembles de combinaisons sont :

Code :

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

1
2
3
{ ab, ac, bc }
{ de, df, ef }
{ gh, gi, hi }

Et le produit cartésien est :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(ab;de;gh), (ab;de;gi), (ab;de;hi),
(ab;df;gh), (ab;df;gi), (ab;df;hi),
(ab;ef;gh), (ab;ef;gi), (ab;ef;hi),
 
(ac;de;gh), (ac;de;gi), (ac;de;hi),
(ac;df;gh), (ac;df;gi), (ac;df;hi),
(ac;ef;gh), (ac;ef;gi), (ac;ef;hi),
 
(bc;de;gh), (bc;de;gi), (bc;de;hi),
(bc;df;gh), (bc;df;gi), (bc;df;hi),
(bc;ef;gh), (bc;ef;gi), (bc;ef;hi)

Soit 27 éléments au total.
Le nombre d’éléments, et donc le nombre d’opérations à faire, est simplement le nombre de combinaisons élevé au cube : ( n! / 2(n - 2)! )³. Ce nombre croît rapidement avec n :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
n     opérations
---   ---
3     27
4     216
5     1 000
6     3 375
7     9 261
…     …
15    1 157 625
…     …
46    1 108 717 875
…     …
142   1 003 303 631 331

J’espère que j’ai mal compris… Sinon il faudra revoir ta conception car, actuellement, le problème est trop complexe pour être calculé en temps raisonnable, peu importe le nombre de workers, peu importe la puissance de la machine, client ou serveur.