visite du code de pcbo

Pour comprendre cette implantation de l'algorithme CbO (ou son dual), voici ma visite commentée du code.

FIXME : Attention, ce n'est pas encore finie.

main

Dans ce qui suit, les multiples contrôles ne seront pas mentionnés, seulement le “traitement pur.”

read_context (in_file);

  • lecture du fichier dans un buffer,
    • et #define BUFFER_BLOCK 1024
    • où size_t buff_size = BUFFER_BLOCK; et il a fait
    • buff = (int *) malloc (INT_SIZE * buff_size);
  • puis chargement dans un tableau context[] (unsigned long) qu'il alloue et initialise à 0 :
    • context = (unsigned long *) malloc (LONG_SIZE * int_count_a * objects);
    • memset (context, 0, LONG_SIZE * int_count_a * objects);

fclose (in_file);

print_context_info ();

  • if (verbosity_level >= 2)
    • fprintf (stderr, ”(:objects %6i :attributes %4i :entries %8i)\n”, objects, attributes, table_entries);

initialize_algorithm ();

Ici, on recense le nombre d'objets ayant chaque attribut (supps, de dimension LONGSIZE * 8 * int_count_a)

  • #define BIT ( (unsigned long) 1)
  • #define ARCHBIT ( (LONG_SIZE * 8) - 1)
  • cols_buff = (unsigned long *)
    • malloc (LONG_SIZE * int_count_o * (ARCHBIT + 1) * int_count_a);
    • memset (cols_buff, 0, LONG_SIZE * int_count_o * (ARCHBIT + 1) * int_count_a);
  • cols = (unsigned long *(*)[ARCHBIT + 1]) malloc (sizeof (unsigned long * (ARCHBIT + 1) * int_count_a);
  • supps = (int (*)[ARCHBIT + 1]) malloc (sizeof (int) * (ARCHBIT + 1) * int_count_a);
  • ptr = cols_buff;
  • for (j = 0; j < int_count_a; j++)

for (i = ARCHBIT; i >= 0; i–) {

    mask = (BIT << i);
    cols[j][i] = ptr;
    supps[j][i] = 0;
    for (x = 0, y = j; x < objects; x++, y += int_count_a)
if (context[y] & mask) {
  ptr[x / (ARCHBIT + 1)] |= BIT << (x % (ARCHBIT + 1));
  supps[j][i]++;
}
    ptr += int_count_o;
  }

puis on appelle l'initialisation d'un tableau …

table_of_ints_init (attributes);

}

find_all_intents ();

D'abord, on initialise la gestion des threads…pour le cas “simple” sequentiel, threads sera 1.

counts =
  (struct thread_stat *) calloc (threads, sizeof (struct thread_stat));
thread_id = (thread_id_t *) malloc (sizeof (thread_id_t) * threads);
memset (thread_id, 0, sizeof (thread_id_t) * threads);
thread_i = (int *) malloc (sizeof (int) * threads);
thread_queue =
  (unsigned char **) malloc (sizeof (unsigned char *) * threads);
thread_queue_head =
  (unsigned char **) malloc (sizeof (unsigned char *) * threads);
thread_queue_limit =
  (unsigned char **) malloc (sizeof (unsigned char *) * threads);
thread_intents =
  (unsigned long **) malloc (sizeof (unsigned long *) * threads);
queue_size = attributes;
queue_size = queue_size / threads + 1;
attrs = attributes - para_level + 1;
for (i = 0; i < threads; i++) {
  thread_i[i] = i;
  thread_queue_head[i] = thread_queue[i] = (unsigned char *)
    malloc ((BYTE_COUNT_A + BYTE_COUNT_O + (INT_SIZE << 1)) * queue_size);
  thread_queue_limit[i] =
    thread_queue_head[i] + (BYTE_COUNT_A + BYTE_COUNT_O +
		      (INT_SIZE << 1)) * queue_size;
  thread_intents[i] =
    (unsigned long *) malloc ((BYTE_COUNT_A + BYTE_COUNT_O) * attrs);
}

Ensuite on calcule la première fermeture:

compute_closure (thread_intents[0], thread_intents[0] + int_count_a,
	   NULL, NULL, NULL);

compute_closure

  • (intent, extent, prev_extent, atr_extent, supp)
    • unsigned long *intent,
    • *extent,
    • *prev_extent,
    • *atr_extent;
    • size_t *supp;
    • { memset (intent, 0xFF, BYTE_COUNT_A);
    • if (atr_extent) … else (le case initial), chercher l'intension :
      • memset (extent, 0xFF, BYTE_COUNT_O);
      • for (j = 0; j < objects; j++) {
        • for (i = 0; i < int_count_a; i++)
  • intent[i] &= context[int_count_a * j + i];

les prochains appels (avec atr_extent existant) feront :

  • supp = 0;

for (k = 0; k < int_count_o; k++) {

    extent[k] = prev_extent[k] & atr_extent[k];

C'est à dire, calculer la nouvelle extension par intersection de l'extension precedente et l'extension de l'attribut. Si le résultat n'est pas null,

    if (extent[k])
for (l = 0; l <= ARCHBIT; l++)
  if (extent[k] & (BIT << l)) {
    for (i = 0, j =
	 int_count_a * (k * (ARCHBIT + 1) + l);
	 i < int_count_a; i++, j++)
      intent[i] &= context[j];
    (*supp)++;
  }
  }
}

suite de find_all_intents ();

counts[0].closures++;
counts[0].computed++;
print_attributes (thread_intents[0]);
if (thread_intents[0][int_count_a - 1] & BIT)
  return;

fclose (out_file);

 
pcbo.txt · Dernière modification: 2010/01/27 12:41 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki