Optimisation des intersections et des unions

Question

Salut tout le monde,

Je suis en train de programmer un algorithme qui effectue un nombre énorme d'unions entre des ensembles ordonnés (ordre lexicographique ascendant). Le problème auquel je suis confronté est que le temps d'exécution dans certains contextes est considérablement grand ( 5 secondes-->3 jours!!!). 

Afin d'optimiser ces opérations, j'ai eu recours aux tableaux debits afin de réduire les temps d'exécution. Le résultat était acceptable mais pas bon. En effet, le temps d'exécution est encadré entre 0secondes et 13000 secondes!!.

En analysant certains aspects des données traités, j'ai remarqué qu'il y a une présence énorme de mots égaux à 0 dans les tableaux de bits. ALors, je me suis demandé s'il y avait une variante de la classe "efficace " (en terme temps d'exécution, l'espace mémoire qu'elle consomme est sans importance pour mon algorithme) des tableaux de bits qui permet d'éviter les opérations d'unions lorsque le mot (bloc de 32 bits) en cours de traitement est à 0. 

Merci pour votre aide.

SIGMA

HSylvio · Answer

Rajouter 1 attribut (booleen == true <=> mot == 0) et effectuer cette verification avant de lire ton mot de 32 bits ca ferait pas gagner un peu de temps?

cs_rt15 · Answer

Salut,

Tu pourrais préciser ce que tu fais ?
Montrer un peu de code ?
Préciser la taille des ensemble et le nombre d'ensembles dont tu fais l'union ?
L'union de tes ensembles doit-il être ordonnée ?
Faut il que tu supprimes les doublons ?
Toutes tes données font elles 32 bits ?

Cela devrait nous aider à t'aider...

cs_juju12 · Answer

Moi je suggère de trier tes ensembles, ce qui te permettra une méthode d'union en O(n) au lieu de O(n²) comme ce doit être le cas.

islem1982 · Answer

Je suis navré (ne la prenez pas mal mais je ne fais que suivre les ordres de mon encadreur de mémoire) mais le code source est strictement confidentiel. Mais je peux clarifier encore le problème:

1- la taille des ensemble est entre 1000 et 10000 éléments et le nombre d'ensembles est entre 100000 et 5*109 . Ca fait vachement énorme mais 

2- Le résultat de l'union doit être ordonné.

3- Il n'y a pas de doublons dans les ensembles, tous les éléments sont uniques.

4- Généralement, les données sont codées sur au plus 32 bits. Et vu que leur nombre est élevé, elles requièrent souvent plus que 32 bits.

Merci infiniement pour votre aide et votre compréhension.

SIGMA

cs_rt15 · Answer

Je cerne un peu plus ce que tu souhaites, mais certains points restent assez obscures.


1 - Comment peut il y avoir pleins de zéros dans les tableaux alors qu'il n'y a pas de doublons dans les données ?


2 - Avec 5 * 109 petits ensembles de 1000 éléments de 32 bits (4 octets), cela revient à 5 * 4 * 1000 * 109
octets de données, soit 20.000 Go. Sachant que les très (très) gros
disques durs actuels font 1.000 Go. Quelle machine utilises-tu, et quel
système d'exploitation ???


Je vais essayer de pondre un bout de code pour demain histoire d'y voire plus clair dans ce que l'algo doit réaliser.

cs_rt15 · Answer

Bon, vala un bout de code juste pour s'assurer que l'on parle bien de la même chose, et d'avoir une base de trvail pour l'optimisation. Application C++ console. #include "stdio.h" #include "stdlib.h" #include "time.h" #include #include using namespace std; // Nombre maximum d'ensembles #define NB_ENSEMBLES_MAX 10 // Nombre maximum d'éléments par ensemble #define NB_ELEMENTS_MAX 10 // Valeur maximale des éléments, 2^31 - 2 #define VAL_MAX 0x7FFFFFFE //==================================================== // Vérifie qu'une allocation s'est bien passée. //==================================================== void VerifieAllocation(void * pointeur) { if ( ! pointeur) { printf("Echec d'une allocation "); system("pause"); } } //==================================================== // Initialise le générateur de nombres // pseudo-aléatoires de manière à ce qu'il ne renvoie // pas les mêmes nombres d'un lancement de l'appli // sur l'autre. //==================================================== void InitialiserAleatoire() { time_t timer; time(&timer); srand((int)timer * (int)timer); } //==================================================== // Renvoie un nombre aléatoire compris entre min et // max inclus. //==================================================== int EntierAleatoireEntre(int min, int max) { float res = (float)rand() / RAND_MAX; res = (float)min + res * (float)(max - (min + 1)); return (int)res; } //==================================================== // Génère un tableau d'ensembles. // Le nombre d'ensemble est spécifié dans la première // case du tableau. // Le nombre d'éléments de chaque ensemble est lui // aussi spécifié dans la première case de // l'ensemble. //==================================================== int ** CreerEnsembles() { int nbEnsembles; // Nombre d'ensembles int nbElements; // Nombre d'éléments de l'ensemble int ** res; // Valeur retourné à la fin InitialiserAleatoire(); // Allocation du tableau d'ensembles nbEnsembles = EntierAleatoireEntre(1, NB_ENSEMBLES_MAX); res = (int **)malloc((nbEnsembles + 1) * 4); VerifieAllocation(res); res[0] = (int *)nbEnsembles; // Création des ensembles for (int i = 1 ; i <= (int)res[0] ; i++) { nbElements = EntierAleatoireEntre(1, NB_ELEMENTS_MAX); res[i] = (int *)malloc((nbElements + 1) * 4); VerifieAllocation(res[i]); res[i][0] = nbElements; // Initialisation de l'ensemble, sans doublons for (int j = 1 ; j <= res[i][0] ; j++) { int trouve; do { trouve = 0; res[i][j] = EntierAleatoireEntre(0, VAL_MAX); for (int k = 1 ; k < j ; k++) if (res[i][k] == res[i][j]) { trouve = 1; break; } } while (trouve); } sort(&res[i][1], &res[i][res[i][0] + 1]); } return res; } //==================================================== // Afficher les ensembles. //==================================================== void AfficherEnsembles(int ** ensembles) { printf("Nombre d'ensembles : %d ", (int)ensembles[0]); for (int i = 1 ; i <= (int)ensembles[0] ; i++) { printf(" Ensemble %d, %d elements ", i, ensembles[i][0]); for (int j = 1 ; j <= ensembles[i][0] ; j++) printf("%d ", ensembles[i][j]); } } //==================================================== // Libère l'ensemble d'ensemble. //==================================================== void LibererEnsembles(int ** ensembles) { // Libération des ensembles for (int i = 1 ; i <= (int)ensembles[0] ; i++) free(ensembles[i]); // Libération du tableau d'ensembles free(ensembles); } //==================================================== // Fait l'union des ensembles. //==================================================== int * FaireUnion(int ** ensembles) { // Calcul du nombre maximum d'éléments dans l'union int nbEle = 0; for (int i = 1 ; i <= (int)ensembles[0] ; i++) nbEle += ensembles[i][0]; // Allocation du tableau de l'union int * res = (int *)malloc((nbEle + 1) * 4); VerifieAllocation(res); // Allocation d'un tableau des indices courants dans les ensembles int * indices = (int *)malloc(((int)ensembles[0] + 1) * 4); VerifieAllocation(indices); for (int i = 1 ; i <= (int)ensembles[0] ; i++) indices[i] = 1; // Union res[0] = 0; int nbEnsemblesVides = 0; int indiceMin; while (nbEnsemblesVides < (int)ensembles[0]) { int min = VAL_MAX + 1; for (int i = 1 ; i <= (int)ensembles[0] ; i++) if (indices[i]) { if (ensembles[i][indices[i]] <= min) if (ensembles[i][indices[i]] == min) { indices[i]++; if (indices[i] > ensembles[i][0]) { indices[i] = 0; nbEnsemblesVides++; } } else { indiceMin = i; min = ensembles[i][indices[i]]; } } // Ajout à l'union res[0]++; res[res[0]] = min; indices[indiceMin]++; // On regarde si on a fini l'ensemble if (indices[indiceMin] > ensembles[indiceMin][0]) { indices[indiceMin] = 0; nbEnsemblesVides++; } } free(indices); return res; } //==================================================== // Affiche l'union des ensembles. //==================================================== void AfficherUnion(int * unionDesEnsembles) { printf(" Union (%d elements) ", unionDesEnsembles[0]); for (int i = 1 ; i <= unionDesEnsembles[0] ; i++) printf("%d ", unionDesEnsembles[i]); } int main(int argv, char * argc[]) { int ** ensembles; int * unionDesEnsembles; ensembles = CreerEnsembles(); AfficherEnsembles(ensembles); unionDesEnsembles = FaireUnion(ensembles); AfficherUnion(unionDesEnsembles); LibererEnsembles(ensembles); free(unionDesEnsembles); system("pause"); }

islem1982 · Answer

Tout d'abord, je tiens à vous remercier d'avoir consacré un temps afin de développer un programme afin d'effectuer cette opération. C'est vraiement très gentil.

Il y a quelques trucs qui sont corrects et d'autres imcompris. Je m'explique encore plus en détail tout en répondant à vos interrogations:

Le problème que je suis en train de traiter prend comme entrées:
1- Une base de transactions formattée comme suit:
    -- Chaque ligne est considérée comme étant une transaction constituée par un ensemble d'identificateurs uniques au sein de cette dernière (je suis sûr dès le début que les identificateurs [i.e. items] ne répètent pas).
    -- les items sont séparés par des caractères non numériques.

2- La sortie est un ensemble donné d'itemsets (un itemset est un ensembles d'items).

Pour ne pas trop compliquer le sujet (car le taux d'information théorique est pour 200 pages), on va se restreindre sur le côté implémentation du problème.

Ces transactions, tels qu'elles ont été définies sont des ensembles d'items (non redondant par défaut). Afin d'extraire ce que je veux, je dois faire des intersections entre ces transactions (qui sont des ensembles d'éléments). Le nombre de ces transactions est compris entre 100000 et 5*109. Ces transactions contiennent un nombre entre 1000 et 100000 items. 

Afin d'extraire l'ensemble désiré des itemsets, je dois faire un nombre excessivement grand d'unions entre les transactions. A cet effet, je dois utiliser des structures de données permettant d'effectuer efficacement les unions entre ces transactions.

J'ai alors opté pour les tableaux de bits qui sont un suite successive de "unsigned long" afin de stocker des items. Je les utilise comme suit:
Notons par t la transaction représentée, par le tableau de bits TBt et par TBt(i) le bit d'ordre i du tableau de bits TBt. Alors si l'item  j  est présent dans t, nous mettons le bit TBt(j) à 1. Dans le cas échéant, le bit TBt(j) est égal à 0. Ainsi, je garanti que:
1- lors de la conversion de la transaction (ou ensemble en général) du format initial vers le format tableaux de bits, les items n'apparaissent qu'une et une seule fois.
2- les opérations d'unions sont plus rapides. En effet, afin d'unir deux tableaux de bits, il suffit de leur appliquer l'opérateur logique ou | qui est facilement évaluable au sein du processeur. De plus, l'union s'effectue par 32 éléments. En effet, puisque les bits sont divisés par blocs de 32 bits (taille de unsigned long), une seule opération d'union suffit afin d'unir 32 items. 

Malgré cette vitesse d'unir deux ensembles représentées par des tableaux de bits, je pense que l'union peut être encore optimisée. En effet, considérons les deux unsigned long suivant "00000000000000000000000000000000" et "10000000000000000000000000000001". Puisque le premier mot ne contient que des bits à 0, le résultat de l'union de ces tableaux de bits sera égal au dernier mot, à savoir "10000000000000000000000000000001". Si nous arrivons à optimiser l'opération d'union lorsqu'un mot des deux est égal à "00000000000000000000000000000000", ceci affectera notablement les performances du programme que je suis en train de développer.

Concernant l'espace mémoire consommé, ne t'inquiète pas pour ça, la complexité du programme est au pire des cas de l'ordre de 2n (espace mémoire et temps d'exécution) et je me suis accomodé à programmer efficacement (en terme d'espace mémoire) de tels programmes. Mon principal soucis est le temps d'exécution.

SIGMA

cs_rt15 · Answer

Ah ok ! J'étais assez loin, désolé. Dans ce genre là plutôt (cf code source à la fin) ? Et tu veux optimiser : // Union for (i = 0 ; i < NB_ENS ; i++) for (j = 0 ; j < NB_ENS ; j++) unionDesEnsembles[j] = unionDesEnsembles[j] | ensembles[i][j]; Avec un truc dans ce genre là ? // Union for (i = 0 ; i < NB_ENS ; i++) for (j = 0 ; j < NB_ENS ; j++) if (ensembles[i][j]) unionDesEnsembles[j] = unionDesEnsembles[j] | ensembles[i][j]; =============== #include "stdio.h" #include "stdlib.h" #include "time.h" // Taille des ensembles #define TAILLE_ENS 2 // Nombre d'ensembles #define NB_ENS 10 //==================================================== // Remplit les tableaux de bits, avec une grande // majorité de zéros. //==================================================== void AffecterEnsembles(unsigned long ensembles[NB_ENS][TAILLE_ENS]) { int i, j; int pileOuFace = RAND_MAX / 2; for (i = 0 ; i < NB_ENS ; i++) for (j = 0 ; j < TAILLE_ENS ; j++) if (rand() < pileOuFace) ensembles[i][j] = 0; else ensembles[i][j] = rand() * rand(); } //==================================================== // Fait l'union de tous les tableaux de bits. //==================================================== void FaireUnion(unsigned long ensembles[NB_ENS][TAILLE_ENS], unsigned long unionDesEnsembles[TAILLE_ENS]) { int i, j; // Initialisation du résultat à 0 for (i = 0 ; i < TAILLE_ENS ; i++) unionDesEnsembles[i] = 0; // Union for (i = 0 ; i < NB_ENS ; i++) for (j = 0 ; j < NB_ENS ; j++) unionDesEnsembles[j] = unionDesEnsembles[j] | ensembles[i][j]; } //==================================================== // Affiche un ensemble. //==================================================== void AfficherEnsemble(unsigned long ensemble[TAILLE_ENS]) { int i, j; for (i = 0 ; i < TAILLE_ENS ; i++) { for (j = 0 ; j < sizeof(unsigned long) * 8; j++) printf("%d", ( ensemble[i] >> j) & 1); printf(" "); } printf(" "); } //==================================================== // Affiche les ensembles. //==================================================== void AfficherEnsembles(unsigned long ensembles[NB_ENS][TAILLE_ENS]) { int i; for (i = 0 ; i < NB_ENS ; i++) AfficherEnsemble(ensembles[i]); } //==================================================== // Initialise le générateur de nombres // pseudo-aléatoires de manière à ce qu'il ne renvoie // pas les mêmes nombres d'un lancement de l'appli // sur l'autre. //==================================================== void InitialiserAleatoire() { time_t timer; time(&timer); srand((int)timer * (int)timer); } int main(int argv, char * argc[]) { unsigned long ensembles[NB_ENS][TAILLE_ENS]; unsigned long unionDesEnsembles[NB_ENS]; InitialiserAleatoire(); AffecterEnsembles(ensembles); FaireUnion(ensembles, unionDesEnsembles); AfficherEnsembles(ensembles); AfficherEnsemble(unionDesEnsembles); system("pause"); }

Optimisation des intersections et des unions

8 réponses

Votre réponse

Discussions similaires