Discussion :

[takout]

Bonjour à tous,

Après avoir conçu un tableau fixe d'entier, je voudrai ventiler ces entiers dans quatre sous tableaux sans connaître au préalable leurs dimensions. Ce qui implique qu'en parcourant le tableaux fixe la taille des sous tableaux augmente dynamiquement. J'aimerai savoir si quelqu'un pourrait m'aider à résoudre ce problème.

takout

[takout]

Pour être plus précis je veux en fait répartir les éléments du tableau fixe dans les quatre autres tableaux sous certaines conditions. Ne connaissant pas les tailles de ces tableaux je ne sais pas comment les construire dynamiquement.


Cordialement Takout.

[koopajah]

Bonjour,

Soit ton tableau de taille fixe n'est pas trop grand et dans ce cas tu fais directement 4 sous tableaux de la meme taille. Ca prendra un peu plus de mémoire mais tu seras tranquille.
Soit tu augmentes la taille du tableau au fur et a mesure.
Par exemple si ton tableau fait 1000 éléments, tu crées 4 sous tableaux de 10 éléments avec malloc() et tu mémorises le nombre d'éléments que tu y mets. Quand tu en as mis 10, tu utilises soit la fonction "realloc()" pour augmenter la taille du tableau. Soit tu alloues un nouveau tableau de taille 20, tu copies les 10 éléments dedans et tu libères la mémoire du précédent tableau.

[LittleWhite]

Bonjour,

Je propose d'utiliser les listes chainées pour avoir des tableaux plus dynamiques. (Sinon, utiliser une bibliothèque comme la GLib peut être intéressant).
Note: realloc() est une fonction plutôt très dangereuse à utiliser (il faut vérifier les pointeurs retournés).

[souviron34]

tout dépend de ce qu'on veut faire, si c'est dans le cadre d'un exercice ou non, si on a pas de problèmes de place mémoire, si au contraire on peut avoir des problèmes de vitesse, quelle utilisation on veut en faire plus tard, etc etc etc...

@takout :

La réponse simple à ta question initiale est : realloc

Par contre, comme le dit LittleWhite, c'est à utiliser avec précautions :

Exemple :

Code C :

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
int Table[200], *Tab1 = NULL, *p=NULL ;

Nb1 = 0 ;

for ( i = 0 ; i < Nb ; i++ )
  {
      if ( Table[i] rempli la condition "appartient à catégorie 1" )
        {
            p = realloc ( Tab1, (Nb1+1)*sizeof(int) );
            if ( p != NULL )
              {
                 Tab1 = p ;
                 Tab1[Nb1] = Table[i] ;
                 Nb1 = Nb1 + 1 ;
              }
        }
  }

Sinon effectivement une liste simplement ou doublement chaînée. Tout dépend de ce que tu veux faire avec et de tes contraintes.

[diogene]

On peut envisager de le faire sur place, ce qui résoud les problèmes de taille de tableaux.

- On peut le programmer directement en regroupant en début de tableau les éléments répondant aux conditions 1 ou 2 et en fin ceux répondant aux critères 3 ou 4, puis en recommençant la meme procédure sur chaque sous tableau avec les conditions 1 et 2 pour le premier puis 3 et 4 pour le second.

- ou en utilisant qsort(), trier le tableau dans l'ordre des conditions sur ses éléments en considérant que ceux obéissant à la condition 1 sont plus petits que ceux obéissant à la condition 2, qui sont plus petits que ceux obéissant à la condition 3, qui sont plus petits que ceux obéissant à la condition 4, qui sont plus petits que ceux n'obéissant à aucune condition.
Il suffit ensuite de parcourir le tableau obtenu pour connaitre où débute chaque sous tableau des éléments répondant à une condition donnée et obtenir leur nombre d'éléments.
Par exemple :

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
#include <stdlib.h>
// Renvoie un nombre différent 0,1,2,... pour chacune des conditions 
// Ici les conditions sont dans cet exemple "même reste de la division par 4"
int cond( int i)
{
    return i%4;
}
//fonction de comparaison pour qsort
int comp(const void* p, const void*q)
{
 return cond(*(int*)p) -cond(*(int*)q);
}
 
int main(void)
{
  int i;
  int tab[]= { 1,8,5,7,4,6,9,5,6,7,2,3,6,0,4,9,8};
  int n = sizeof tab/sizeof *tab;
  // Adresses de départ et nombre d'éléments des sous-tableaux
  int * deb[4]= {NULL,NULL,NULL,NULL};
  int dim[4]={0,0,0,0};
 
  qsort(tab, n, sizeof *tab, comp);
  for(i=0; i<n;i++)
  {
     int c = cond(tab[i]);
     if(deb[c]==NULL) deb[c] = tab+i;
     dim[c]++;
  }
  return 0;
}

[takout]

Re bonjour,

Je pense avoir une autre solution, c'est de parcourir le tableau une première fois et à l'aide de compteurs de déterminer le nombre d'éléments de chaque sous tableaux. Puis de construire chaque sous tableaux dynamiquement, et de reparcourir le tableau fixe en ventilant ses éléments dans les autres tableaux. J'aimerai que mon programme soit optimisé, pensez vous que la méthode avec le realloc soit meilleur ?

Takout

[koopajah]

Tout dépend de ce que tu souhaites optimiser au final et de la quantité de données dont on parle. Si c'est un tableau de 1000 éléments, un double parcours est aussi simple au final que le realloc.
Maintenant si ton but est d'être rapide, le realloc me semble plutot pas mal parce qu'au final tu ne vas parcourir ta liste qu'une fois, et tu ne feras pas un realloc a chaque nouvel élément, tu doubles la taille du tableau a chaque fois pour minimiser les appels.

[takout]

Le souci c'est que si le realloc ne marche pas je perds mon tableau, en plus mon programme doit être robuste avec un tableau fixe initiale de très grand taille.

Takout

[diogene]

Tu ne peux pas le faire sur place ? Cela évite de dupliquer le tableau et pas de malloc()/realloc()
Quelle est la taille typique du tableau ?

[koopajah]

Le souci c'est que si le realloc ne marche pas je perds mon tableau, en plus mon programme doit être robuste avec un tableau fixe initiale de très grand taille.

Takout

Je ne comprends pas pourquoi tu dis perdre tes données avec realloc()? Qqn dans le thread avant a dit que c'était dangereux mais ça n'est pas vrai. Il est marqué dans la doc : "If realloc() fails the original block is left untouched; it is not freed or moved" ce qui veut dire que si ton realloc echoue (manque de mémoire par exemple) la mémoire initiale n'est pas changée/modifiée".

[anacharsis]

salut !

il nous faut plus d'info sur la taille de ton tableau, savoir si tu n'as qu'un seul grand tableau, la quantité de mémoire dont tu disposes:
sur un vieux portable avec 512 Mo de mémoire l'examen d'un tableau de 100.000.000 entiers 32 bits suivant un critère à 4 valeurs prend une vingtaine de secondes (bien sûr le système fait un swap).
mais si tu n'es pas dans des conditions extrêmes (quota inférieur à ce dont tu as besoin, plusieurs gros tableaux à examiner à la seconde) aucune des propositions n'est vraiment mauvaise.

perso j'aime bien faire deux passes en dessous de 100.000 dans un traitement purement séquentiel, mais on ne perd pas son temps en écrivant plusieurs versions d'un même programme si l'analyse ne permet pas de décider laquelle est la meilleure.

A+

[anacharsis]

un petit point de plus : si tu dois utiliser de très gros tableaux, il faut les déclarer static ou en faire des variables globales ou les obtenir par un malloc parce qu'ils risquent d'être trop gros pour la pile dans une fonction.

A+