Optimisation des intersections et des unions

Signaler
Messages postés
22
Date d'inscription
samedi 10 janvier 2004
Statut
Membre
Dernière intervention
4 octobre 2007
-
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
-
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

8 réponses

Messages postés
116
Date d'inscription
jeudi 22 juillet 2004
Statut
Membre
Dernière intervention
14 juin 2012

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?
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
14
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...
Messages postés
966
Date d'inscription
samedi 3 avril 2004
Statut
Membre
Dernière intervention
4 mars 2010
4
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.
Messages postés
22
Date d'inscription
samedi 10 janvier 2004
Statut
Membre
Dernière intervention
4 octobre 2007

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
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
14
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.
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
14
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\n");
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\n", (int)ensembles[0]);
for (int i = 1 ; i <= (int)ensembles[0] ; i++)
{
printf("\nEnsemble %d, %d elements\n", i, ensembles[i][0]);
for (int j = 1 ; j <= ensembles[i][0] ; j++)
printf("%d\n", 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("\nUnion (%d elements)\n", unionDesEnsembles[0]);
for (int i = 1 ; i <= unionDesEnsembles[0] ; i++)
printf("%d\n", 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");
}
Messages postés
22
Date d'inscription
samedi 10 janvier 2004
Statut
Membre
Dernière intervention
4 octobre 2007

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  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
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
14
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("\n");
}

//====================================================
// 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");
}