Optimisation des intersections et des unions

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

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?

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

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.

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*10⁹ . 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

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 * 10⁹ petits ensembles de 1000 éléments de 32 bits (4 octets), cela revient à 5 * 4 * 1000 * 10⁹ 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.

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 <algorithm>
#include <iostream>


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

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*10⁹. 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 TB_t et par TB_t(i) le bit d'ordre i du tableau de bits TB_t. Alors si l'item  j  est présent dans t, nous mettons le bit TB_t(j) à 1. Dans le cas échéant, le bit TB_t(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 2ⁿ (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

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