Discussion :

[Darki03]

Bonjour,

Je pense que mon problème est simple mais bon je n'ai trouvé que des solutions compliquées !

En fait j'ai un vecteur (en c++ conteneur STL) qui contient une suite de valeurs (0 ou 1) et je voudrais savoir si il existait un algorithme simple permettant de connaitre le nombre de changements de valeurs et la durée de ceux-ci, par exemple:

0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 : 2 changement de valeurs identifiés dont 1 d'une durée de 3 échantillons et un autre d'une durée de 6 échantillons.

J'espère m'être bien expliqué ^^ ! En attendant voila mon algo en c++ (je fais appel à votre indulgence :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
int Discrete::find_state_change(std::map<int, int>& consecutive)
{
     int initial_state=0; //Valeur au rang n
	 int np1_state=0; //Valeur au rang n+1
	 int nbr_mauvais=0; //Nombre d'echantillon à l'état changé
	 int nbr_change=0; //Nombre de changement
	 std::vector<int>::iterator iter=value.begin(); //Iterateur sur le premier élément du vecteur
	 while(iter!=value.end()) //tant que l'on ne pointe pas sur la fin du vecteur
	 {
	     initial_state=(*iter); //Valeur au rang n
		 iter++; //On pointe sur n+1
		 if(iter!=value.end()) //Si on ne pointe pas sur la fin du vecteur
		 {
		     np1_state=(*iter); //Valeur au rang n+1
		     if(np1_state!=initial_state) //Si v(n+1)<>v(n)
		     {
		         nbr_change++; //Nombre de changement + 1
				 //Tant que v(n+1) différent de l'état avant changement et de la fin du vecteur
			     while(np1_state!=initial_state && iter!=value.end()) 
			     {
			         nbr_mauvais++; //Nombre d'echantillon à l'etat changé + 1
					 iter++; //On pointe sur n+1
				     np1_state=(*iter); //Valeur au rang n+1
			     }
			     consecutive[nbr_mauvais]=consecutive[nbr_mauvais]+1; //On remplit le conteneur associatif
				 //consecutive[nombre d'echantillon à l'etat change]= compteur sur le nombre de changement
				 //de taille égale
			     nbr_mauvais=0; //On reinitialise nbr_mauvais
		     }
		 }
	 }
	 return nbr_change;
}

[pseudocode]

Le plus simple c'est de calculer la différence entre 2 éléments consécutifs:

si différence = +1 => passage de 0 a 1
si différence = -1 => passage de 1 a 0
si différence = 0 => plateau (constant)

Seul le premier cas t'intéresse.

En Java (pas de C++ sous la main, désolé) ca ferait quelque chose comme:

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findStateChange(List<Integer> values) {
	int previous=0,current=0,changecount=0;
 
	Iterator<Integer> iter = values.iterator();
	if (!iter.hasNext()) return 0; // list is empty
 
	current = iter.next();
	while(iter.hasNext()) {
		previous = current;
		current  = iter.next();
		if (current-previous>0)	changecount++;			
	}
	return changecount;
}

[souviron34]

en fait c'est juste une analyse d'histogramme, en gros...


Et comme le dit pseudocode, une analyse des transitions est simple..

Code C :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef struct pChange {
      int Start ;
      int Width ;
} Change ;
 
 
int FindStateChanges ( int *Table, int Nelts, Change **Changes )
{
   int NChanges = 0, i, iend=-2 ;
 
   for ( i = 0 ; i < Nelts ; i++ )
     {
         if ( Table[i] )
           {
                if ( iend < (i-1) )
                 {
                    *Changes = realloc ( *Changes, (NChanges+1)*sizeof(Change) );
                    if ( *Changes == NULL )
                      { 
                          NChanges = 0 ;
                          break ;
                      }
                    (*Changes)[NChanges].Start = i ;
                    (*Changes)[NChanges].Width = 1 ;
                    NChanges++ ;
                }
              else
                {
                    (*Changes)[NChanges-1].Width ++ ;
                }
 
              iend = i ;
           }
     }
 
   return NChanges ;
}

[Darki03]

Merci pour vos réponse je vais essayer de simplifier mon algo a partir de celles-ci !

A + sur le forum !
Darki03