Discussion :

[nanosoft]

Bonjour,

Je bute actuellement sur un problème d'implémentation nouveau pour moi :
J'ai un certain nombre d'éléments que je peux représenter par le type int ( environ une centaine d'entiers différents)
et un certain nombre d'ensembles qui contiennent des éléments, les ensembles ne sont pas disjoints.

Je recherche une représentation de ces ensembles et une fonction qui prend un élément en entrée et en sortie me donne tous les ensembles contenant cet élément.

Quelle est la meilleure façon de coder cela en C ?

Je vous remercie par avance pour toute aide apportée.

[nezix]

Bonsoir,

Si un élément est un entier ou un décimal, alors un ensemble peut être un tableau d'entiers ou une liste chainée d'entiers.

Si la taille de l'ensemble est amenée à beaucoup changer, il est plus facile d'utiliser une liste chainée. Si la taille de l'ensemble est bornée, alors un tableau d'entiers sera à choisir.

Est-ce la taille du stockage des ensembles qui est important, pour ne pas avoir de redondance ?

Pour chercher un élément dans tous les ensembles, on peut par exemple utiliser un tableau de tableau en C, le mieux est de trier chaque tableau puis effectuer une recherche binaire.

Un exemple simple avec un tableau de tableaux statiques. Le trie se fait par qsort et la recherche par bsearch. Attention cependant si les ensembles sont déjà triés quicksort peut être lent sur de grands tableaux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
//Alloue statiquement N ensembles de 256 éléments
int Ensembles[N][256];
int i;
 
//Remplir les Ensembles
...
 
//Trie des tableaux
for(i=0;i<N;i++)
    qsort(Ensembles[i],256,sizeof(int),compare);
 
 
//fonction de comparaison d'entier pour quicksort
int compare (const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b;
    return *ia  - *ib; 
}
 
//fonction de recherche d'un entier dans les ensembles
int *search_element(int Ens[][],int to_search,int N,int nbel){
    int e;
    int *result=calloc(N,sizeof(int));
    for(e=0;e<N;e++){
        if(bsearch(&to_search,Ens[e],nbel,sizeof(int),compare) != NULL)//C'est dans l'ensemble
            result[e] = 1;
    }
    return result;
}

[nanosoft]

Merci,

Ce n'est pas la taille du stockage qui est importante, c'est la rapidité.

J'ai eu depuis une autre idée avec des tableaux d'entier : c'est de représenter l'élément par l'indice.
Chaque élément du tableau prend comme valeur 0 ou 1 ( si tableau1[n]==1 alors n est dans l'ensemble tableau1).
J'ai une centaine d'entiers et également une centaine d'ensembles cela fait 10 000 tests, mais c'est un test très rapide, qu'en pensez_vous ?

[nezix]

Oui c'est une solution.

Le problème c'est que vous ne pouvez pas utiliser des ensembles qui contiennent des éléments dont la valeur est supérieure à 100.
En contre partie la recherche est plus rapide puisque vous accédez directement aux valeurs (sans trie et sans recherche binaire), même si ces étapes sur peu d'entiers se font très rapidement, il n'y aura surement pas de différence en temps d'exécution.

[nanosoft]

OK, mes ensembles sont bornés, je vais partir sur cette solution.
Elle est très facile à implémenter en plus.