Optimisation d'un produit cartésien

Bonjour à tous,

Je bloque sur un problème et votre aide me sera très précieuse (si vous avez le temps de me donner un coup de main évidemment :D)

Mon problème : J'ai N fichiers. Dans chaque fichier, j'ai des données de ce type :
Ficher 1 :
1 5 6 8
1 2 3
4 5 6
2 7 8 9 10

Chaque ligne du fichier est composé d'entiers séparés donc par des espaces.

Le problème que j'ai c'est que je dois générer le produit cartésien des N fichiers.

Exemple :

Fichier 1 : ------Fichier 2 :------Fichier 3 :
1 4 5------------4 6-------------9 10
2 3--------------1 7 8
4 6

Je dois donc générer (sans redondance des entiers) :
1 4 5 6 9 10
1 4 5 7 8 9 10
2 3 4 6 9 10
2 3 1 7 8 9 10
4 6 9 10
1 4 6 7 8 9 10

Si je fais ce produit cartésien d'une manière classique, en stockant chaque ligne dans un tableau et chaque fichier sera représenté par un tableau à deux dimensions et je parcours ainsi tous les couples possibles des N tableau, ça prend un temps fou (car mes données réelles sont plus volumineuses).

La solution passe à mon avis par le choix d'une bonne structure de données. Ou alors, avez-vous, une meilleure idée. Vous avez peut être rencontré ce probléme déjà.

Tous les propositions sont les bienvenues.

Je vous en remercie grandement d'avance :)

tu peux deja commencer par utiliser des pointeurs vers les elements de tes fichiers plutot que de copier a chaque fois la valeur.
Si tas beaucoup de donnees ca t'evitera de la douleur memoire...

Ensuite, tu peux y aller par composition.
Genre tu fais le produit pour deux fichier.
ca te donne un tableau de n elem.
Pis tu fais le prod cartesien du troisieme fichier par ce tableau: il suffit daccoler ce tableau pour chacun des elements du troisieme fichier.

Et ainsi de suite.

Au final, tu as stocke en memoire lequivalent du produit cartesien, mais apres tu perds du temps pour parcourir chacune des valeurs.
Donnant donnant!

Notons N est le nombre de fichiers et Mi la taille du fichier i.

le nombre de lignes à calculer est produit pour i dans {1..N} de Mi, soit O(M^N)

Cela dit, tu peux maintenir une liste de i-produits, qui serviront de préfixes.

Pour simplifier supposons que chaque fichier ne contienne qu'un élément par ligne (je les note par ligne pour la présentation)

f1 = {1, 2, 3}
f2 = {4, 5, 6}

Il s'agit de modifier cette liste à chaque nouveau fichier.
liste initiale = { {} } //un élément, la liste vide
liste après F1 = { {1}, {2}, {3} }
liste après F2 = { {1 4}, {1 5}, {1 6}, {2 4}, {2 5}, {2 6}, {3 4}, {3 5}, {3 6} }

Pour chaque élément l de la liste L(i) à l'étape i, on crée Mi éléments dans la liste L(i+1), chacun étant la concaténation de l et d'une des lignes du fichier Fi

Tu auras besoin d'une structure de liste de listes de nombres, et de deux instance de ce type (une pour L(i), une pour L(i+1)).

Salut,

Ou làlà... tu n'as vraiment pas de chance: j'ai cassé ma dernière boule de crystal hier soir :aie:

Il y a de très nombreuses raisons pour lesquelles ton application peut être lente, parmi lesquelles, mais de manière non exhaustive, on peut citer:

1. de mauvais algorithme
2. le fait de ne lire que des morceaux de fichiers au lieu de lire un fichier à la fois
3. une organisation suboptimale des données en mémoire
4. des accès au disque dur trop lent,
5. j'en passe et de meilleures

A défaut d'avoir un minimum de code, il nous sera difficile de t'aider d'avantage ;)

'tite suggestion gratuite, passer par un moteur sql, extrêmement optimisé pour le produit cartésien..

En gros, tu fais une table sql d'une seule colonne pour chaque fichier, puis tu fais un select sur l'ensemble des tables, et tu concatenes les champs de chaque ligne retournés

ca demande tres peu de travail, mais requiert d'avoir un serveur sql.
je suggere un "simple" MariaDB (ou MariaSql, je ne sais plus le nom)

Citation:

---

Envoyé par galerien69

tu peux deja commencer par utiliser des pointeurs vers les elements de tes fichiers plutot que de copier a chaque fois la valeur.
Si tas beaucoup de donnees ca t'evitera de la douleur memoire...

Ensuite, tu peux y aller par composition.
Genre tu fais le produit pour deux fichier.
ca te donne un tableau de n elem.
Pis tu fais le prod cartesien du troisieme fichier par ce tableau: il suffit daccoler ce tableau pour chacun des elements du troisieme fichier.

Et ainsi de suite.

Au final, tu as stocke en memoire lequivalent du produit cartesien, mais apres tu perds du temps pour parcourir chacune des valeurs.
Donnant donnant!

---

C'est exactement ce que je fais. Et les temps d'exécution restent trop grands :(. Imagines que j'ai 7 fichiers avec 100 lignes dans chacun. Le nombre de combinaisons est de 100^7. C'est enorme !

Citation:

---

Envoyé par leternel

Notons N est le nombre de fichiers et Mi la taille du fichier i.

le nombre de lignes à calculer est produit pour i dans {1..N} de Mi, soit O(M^N)

Cela dit, tu peux maintenir une liste de i-produits, qui serviront de préfixes.

Pour simplifier supposons que chaque fichier ne contienne qu'un élément par ligne (je les note par ligne pour la présentation)

f1 = {1, 2, 3}
f2 = {4, 5, 6}

Il s'agit de modifier cette liste à chaque nouveau fichier.
liste initiale = { {} } //un élément, la liste vide
liste après F1 = { {1}, {2}, {3} }
liste après F2 = { {1 4}, {1 5}, {1 6}, {2 4}, {2 5}, {2 6}, {3 4}, {3 5}, {3 6} }

Pour chaque élément l de la liste L(i) à l'étape i, on crée Mi éléments dans la liste L(i+1), chacun étant la concaténation de l et d'une des lignes du fichier Fi

Tu auras besoin d'une structure de liste de listes de nombres, et de deux instance de ce type (une pour L(i), une pour L(i+1)).

---

Merci beaucoup pour la suggestion. Mais est ce que tu pourrais m'éclairer davanatage esur les structures efficaces que je pourrais utiliser et ce que vous voulez dire par "instances" :)

Citation:

---

Envoyé par koala01

Salut,

Ou làlà... tu n'as vraiment pas de chance: j'ai cassé ma dernière boule de crystal hier soir :aie:

Il y a de très nombreuses raisons pour lesquelles ton application peut être lente, parmi lesquelles, mais de manière non exhaustive, on peut citer:

1. de mauvais algorithme
2. le fait de ne lire que des morceaux de fichiers au lieu de lire un fichier à la fois
3. une organisation suboptimale des données en mémoire
4. des accès au disque dur trop lent,
5. j'en passe et de meilleures

A défaut d'avoir un minimum de code, il nous sera difficile de t'aider d'avantage ;)

---

L'algorithme est classique. Je parcours chaque fichier une seule fois. Merci quand même :)

Citation:

---

Envoyé par leternel

'tite suggestion gratuite, passer par un moteur sql, extrêmement optimisé pour le produit cartésien..

En gros, tu fais une table sql d'une seule colonne pour chaque fichier, puis tu fais un select sur l'ensemble des tables, et tu concatenes les champs de chaque ligne retournés

ca demande tres peu de travail, mais requiert d'avoir un serveur sql.
je suggere un "simple" MariaDB (ou MariaSql, je ne sais plus le nom)

---

Très intéressant. Je vais essayer de le faire. Je reviendrais vers toi si j'ai des problémes avec MariaDB ;) Merci.

Je verrai bien quelque chose comme.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

//pour représenter une ligne d'un fichier struct atomic_line {//tableau dynamique d'entier int taille; int* values; }; //pour garder les différentes valeurs du fichier (et gérer la mémoire correspondante) struct pool {//liste chainée d'atomic_line (en place) struct atomic_line values; struct pool* suivant; };   //pour constituer le produit struct product {//liste chainée de tableau dynamique de pointeurs de lignes int taille; struct atomic_line** values;//les valeurs sont des pointeurs dans ton pool struct product* suivant; };

---

Il te faut deux variables de type product, une que tu viens de calculer, une que tu es en cours de construction.
Il te faudra aussi une liste (ici pool) pour garder les lignes lues sans les recopier tout le temps.