HASH code : utilisation de REMOVEDUP()

**JeromeMATHIAS** · 30/04/2013, 10h56

Bonjour,

j'essaye de programmer des algorithme à l'aide de code Hash,
mais je rencontre quelques soucis avec la méthode REMOVEDUP().

Ci-joint une table avec un programme fonctionnel sans utiliser removedup mais qui n'est pas optimal dans le sens ou on conserve les points éliminés tout le long du calcul (je les marque avec une variable convexe='0' pour signifier au code que ces points ont été éliminés).

J'ai ensuite modifié le programme pour l'optimiser en me disant que cette fois-ci je n'allais pas les marquer mais les éliminer au fur et à mesure du calcul de l'objet hash.

je remplace donc au niveau de l'étape 0

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
	/** le point A1 est à l interieur du convexe on l invalide --> convexe=0 **/
									put 'branche non OK test vect point ordre num ' ordre ;
									put "convexe " convexe ;
									DO UNTIL (convexe^='0');
				/*	debug				put x= y= ordre= ;       */
										rc=h.find_prev();
				/* debug 				put x= y= ordre=;        */
							put '**recherche point a eliminer point num ' ordre rc=;
									END;
									put 'point a eliminer  point num ' ordre ;
											convexe='0'; /** on marque l elimination sur le point A1 **/
											rc=h.replacedup();
										/*	put rc= ;*/
									DO UNTIL (convexe^='0');rc=h.find_prev();
									put "recherche point A1 point num " ordre;
									END;
									put "point A1 point num " ordre ;
									Xa1=X;Ya1=Y;
									DO UNTIL (convexe^='0');rc=h.find_prev();
									put "recherche point A2 point num " ordre;
									END;
									put "point A2 point num " ordre ;
									Xa2=X;Ya2=Y;
									DO UNTIL (convexe^='0');rc=h.find_next();
									put "recherche point test principal point num " ordre ;
									END;
									DO UNTIL (convexe^='0');rc=h.find_next();
									put "recherche point test  principal point num " ordre ;
									END;
									put "point test trouvé point num " ordre;

par le code

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
32
33
34
 
	/** le point A1 est à l interieur du convexe on l invalide --> convexe=0 **/
									put 'branche non OK test vect point ordre num ' ordre ;
									put "convexe " convexe ;
									/*DO UNTIL (convexe^='0');*/
				/*	debug				put x= y= ordre= ;       */
										rc=h.find_prev();
				/* debug 				put x= y= ordre=;        */
							put '**recherche point a eliminer point num ' ordre rc=;
								/*	END;*/
									put 'point a eliminer  point num ' ordre ;
										/*	convexe='0'; *//** on marque l elimination sur le point A1 **/
										/*	rc=h.replacedup();*/
									rc=h.removedup() ;
											put 'REMOVE' rc= ;
									/*DO UNTIL (convexe^='0');*/
									rc=h.find_prev(); put 'PREV apres REMOVE ' rc= ;
									put "recherche point A1 point num " ordre;
									/*END;*/
									put "point A1 point num " ordre ;
									Xa1=X;Ya1=Y;
									/*DO UNTIL (convexe^='0');*/rc=h.find_prev();
									put 'PREV apres REMOVE ' rc= ;
									put "recherche point A2 point num " ordre;
									/*END;*/
									put "point A2 point num " ordre ;
									Xa2=X;Ya2=Y;
									/*DO UNTIL (convexe^='0');*/rc=h.find_next();
									put "recherche point test principal point num " ordre ;
									/*END;*/
									/*DO UNTIL (convexe^='0');*/rc=h.find_next();
									put "recherche point test  principal point num " ordre ;
									/*END;*/
									put "point test trouvé point num " ordre;

mais je n'obtiens pas le même résultat le deuxième code échoue le h.find_prev() (rc=160038) juste après le h.removedup() ;

ci-dessous le programme fonctionnel

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
DATA _null_;
   LENGTH r Xa2 Ya2 Xa1 Ya1 8 vect 8;
   DECLARE HASH h(DATASET:'calcul', MULTIDATA: 'y', ORDERED: 'y');
   h.DEFINEKEY('id');
   h.DEFINEDATA('id', 'Tg_theta','x','y','convexe','ordre');
   h.DEFINEDONE();
   CALL MISSING (id,Tg_theta,x,y,ordre);
 
 
   DO ID= 1 TO &nb ; /** calcul de chaque ensemble pris un à un **/
put "*******DEBUT CONVEXE******** convexe numero "   id ;
   Xa2=.;Ya2=.;Xa1=.;Ya1=.;   /** initialisation vecteur de calcul */
	rc=h.find(); /* positionnement sur le premier point de l ensemble **/
	DO WHILE (rc=0); /** bouclage sur tout les points de l ensemble **/
			/** B0 **/  
 
					IF Xa2=. THEN do;
					DO UNTIL (Xa2^=.);/** B1 chargement des premiers termes du vecteur de calcul **/
					Xa2=Xa1;Ya2=Ya1;Xa1=X;Ya1=Y;
					put 'intialisation point num ' ordre;
					rc=h.find_next();
					END; /** fin B1 **/
					end;
PUT ' apres initialisalition point num ' ordre;
 
	/** rmq produit vectoriel Vect=(Xa2-Xa1)*(Y-Ya1)-(Ya2-Ya1)*(X-Xa1)>0 sens direct **/
						DO WHILE(convexe='0');rc=h.find_next();put 'test vect point num ' ordre ;END;
						vect=(Xa2-Xa1)*(Y-Ya1)-(Ya2-Ya1)*(X-Xa1); put '*' vect=;
						if vect>0
										THEN 	DO; /** le point est bon on passe au point suivant **/
											Xa2=Xa1;Ya2=Ya1;Xa1=X;Ya1=Y;
											rc=h.find_next();  
									put 'branche OK  test vect point ordre num ' ordre;
												END;
										ELSE	DO;
	/** le point A1 est à l interieur du convexe on l invalide --> convexe=0 **/
									put 'branche non OK test vect point ordre num ' ordre ;
									put "convexe " convexe ;
									DO UNTIL (convexe^='0');
				/*	debug				put x= y= ordre= ;       */
										rc=h.find_prev();
				/* debug 				put x= y= ordre=;        */
							put '**recherche point a eliminer point num ' ordre rc=;
									END;
									put 'point a eliminer  point num ' ordre ;
											convexe='0'; /** on marque l elimination sur le point A1 **/
											rc=h.replacedup();
										/*	put rc= ;*/
									DO UNTIL (convexe^='0');rc=h.find_prev();
									put "recherche point A1 point num " ordre;
									END;
									put "point A1 point num " ordre ;
									Xa1=X;Ya1=Y;
									DO UNTIL (convexe^='0');rc=h.find_prev();
									put "recherche point A2 point num " ordre;
									END;
									put "point A2 point num " ordre ;
									Xa2=X;Ya2=Y;
									DO UNTIL (convexe^='0');rc=h.find_next();
									put "recherche point test principal point num " ordre ;
									END;
									DO UNTIL (convexe^='0');rc=h.find_next();
									put "recherche point test  principal point num " ordre ;
									END;
									put "point test trouvé point num " ordre;
												END;
 
 
			END;/** fin B0 **/
put "*******FIN CONVEXE******** convexe numero " id ;		
 
   END; 
 
 
	rc=h.output(dataset: 'work.fin2');
	 put rc= ;
 
 
RUN;

ci-dessous le programme adapté avec removedup mais qui plante...

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
DATA _null_;
   LENGTH r Xa2 Ya2 Xa1 Ya1 8 vect 8;
   DECLARE HASH h(DATASET:'calcul', MULTIDATA: 'y', ORDERED: 'y');
   h.DEFINEKEY('id');
   h.DEFINEDATA('id', 'Tg_theta','x','y','convexe','ordre');
   h.DEFINEDONE();
   CALL MISSING (id,Tg_theta,x,y,ordre);
 
 
   DO ID= 1 TO &nb ; /** calcul de chaque ensemble pris un à un **/
put "*******DEBUT CONVEXE******** convexe numero "   id ;
   Xa2=.;Ya2=.;Xa1=.;Ya1=.;   /** initialisation vecteur de calcul */
	rc=h.find(); /* positionnement sur le premier point de l ensemble **/
	DO WHILE (rc=0); /** bouclage sur tout les points de l ensemble **/
			/** B0 **/  
 
					IF Xa2=. THEN do;
					DO UNTIL (Xa2^=.);/** B1 chargement des premiers termes du vecteur de calcul **/
					Xa2=Xa1;Ya2=Ya1;Xa1=X;Ya1=Y;
					put 'intialisation point num ' ordre;
					rc=h.find_next();
					END; /** fin B1 **/
					end;
PUT ' apres initialisalition point num ' ordre;
 
	/** rmq produit vectoriel Vect=(Xa2-Xa1)*(Y-Ya1)-(Ya2-Ya1)*(X-Xa1)>0 sens direct **/
						DO WHILE(convexe='0');rc=h.find_next();put 'test vect point num ' ordre ;END;
						vect=(Xa2-Xa1)*(Y-Ya1)-(Ya2-Ya1)*(X-Xa1); put '*' vect=;
						if vect>0
										THEN 	DO; /** le point est bon on passe au point suivant **/
											Xa2=Xa1;Ya2=Ya1;Xa1=X;Ya1=Y;
											rc=h.find_next();  
									put 'branche OK  test vect point ordre num ' ordre;
												END;
										ELSE	DO;
	/** le point A1 est à l interieur du convexe on l invalide --> convexe=0 **/
									put 'branche non OK test vect point ordre num ' ordre ;
									put "convexe " convexe ;
									/*DO UNTIL (convexe^='0');*/
				/*	debug				put x= y= ordre= ;       */
										rc=h.find_prev();
				/* debug 				put x= y= ordre=;        */
							put '**recherche point a eliminer point num ' ordre rc=;
								/*	END;*/
									put 'point a eliminer  point num ' ordre ;
										/*	convexe='0'; *//** on marque l elimination sur le point A1 **/
										/*	rc=h.replacedup();*/
									rc=h.removedup() ;
											put 'REMOVE' rc= ;
									/*DO UNTIL (convexe^='0');*/
									rc=h.find_prev(); put 'PREV apres REMOVE ' rc= ;
									put "recherche point A1 point num " ordre;
									/*END;*/
									put "point A1 point num " ordre ;
									Xa1=X;Ya1=Y;
									/*DO UNTIL (convexe^='0');*/rc=h.find_prev();
									put 'PREV apres REMOVE ' rc= ;
									put "recherche point A2 point num " ordre;
									/*END;*/
									put "point A2 point num " ordre ;
									Xa2=X;Ya2=Y;
									/*DO UNTIL (convexe^='0');*/rc=h.find_next();
									put "recherche point test principal point num " ordre ;
									/*END;*/
									/*DO UNTIL (convexe^='0');*/rc=h.find_next();
									put "recherche point test  principal point num " ordre ;
									/*END;*/
									put "point test trouvé point num " ordre;
												END;
 
 
			END;/** fin B0 **/
put "*******FIN CONVEXE******** convexe numero " id ;		
 
   END; 
 
 
	rc=h.output(dataset: 'work.fin2');
	 put rc= ;
RUN;

Le fichier calcul est dans le zip calcul.zip

Merci de votre aide

**JeromeMATHIAS** · 30/04/2013, 15h09

il semblerait que h.find_next() et h.find_prev() n'aient aucun sens après un h.removedup()...

Dans le cadre des objets hash "multidata" j'ai l'impression que l'on peut utiliser h.removedup qu'une seule fois par clé, alors que dans mon code je cherche à éliminer éventuellement plusieurs points pour chaque clé.

Il y a quelque chose que je ne comprend pas dans ces objets si quelqu'un pourrait m'éclairer...

Sur un cas plus simple

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
data testsup;
   length key data sup 8;
   input key data sup;
   datalines;
   1 10 0
   2 11 0
   1 15 1
   1 45 0
   3 20 0 
   2 16 0
   2 9 1
   3 100 0
   5 5 0
   1 5 1
   4 6 0
   5 99 0
   2 99 0
;run;
data _null_;
   length r 8;
   declare hash h(dataset:'testsup', multidata: 'y', ordered: 'y');
   h.definekey('key');
   h.definedata('key', 'data','sup');
   h.definedone();
   call missing (key, data, sup);
   do key = 1 to 5; 
     		rc = h.find();
			 do while   (rc = 0) ;
			 put '*1 'key= data= sup= ;
			if sup=1 then h.removedup();
			put '*2 'key= data= sup= ;
            rc=h.find_next();
			put '*3 'key= data= sup= rc=;
 
			put '*' ;
							end;
   end;
 
	rc=h.output(dataset: 'work.resultat');
 
   declare hiter i('h');
   rc = i.first();
   do while (rc = 0);
      put key= data=;
      rc = i.next();
   end;
run;

Par exemple je cherche a supprimer les lignes avec sup=1 , pour key=1 il y a (1,15) et (1,5) le premier est bien supprimé dans la table "resultat", mais pas le deuxième...

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
14237  data _null_;
14238     length r 8;
14239     declare hash h(dataset:'testsup', multidata: 'y', ordered: 'y');
14240     h.definekey('key');
14241     h.definedata('key', 'data','sup');
14242     h.definedone();
14243     call missing (key, data, sup);
14244     do key = 1 to 5;
14245              rc = h.find();
14246               do while   (rc = 0) ;
14247               put '*1 'key= data= sup= ;
                        -----
                        49
NOTE 49-169: La signification d'un identificateur après une chaîne entre guillemets peut changer dans une version SAS future. Il
             est recommandé d'insérer un espace entre une chaîne entre guillemets et l'identificateur suivant.
 
14248              if sup=1 then h.removedup();
14249              put '*2 'key= data= sup= ;
                       -----
                       49
NOTE 49-169: La signification d'un identificateur après une chaîne entre guillemets peut changer dans une version SAS future. Il
             est recommandé d'insérer un espace entre une chaîne entre guillemets et l'identificateur suivant.
 
14250              rc=h.find_next();
14251              put '*3 'key= data= sup= rc=;
                       -----
                       49
NOTE 49-169: La signification d'un identificateur après une chaîne entre guillemets peut changer dans une version SAS future. Il
             est recommandé d'insérer un espace entre une chaîne entre guillemets et l'identificateur suivant.
 
14252
14253              put '*' ;
14254                              end;
14255     end;
14256
14257      rc=h.output(dataset: 'work.RESULTAT');
14258
14259     declare hiter i('h');
14260     rc = i.first();
14261     do while (rc = 0);
14262        put key= data=;
14263        rc = i.next();
14264     end;
14265  run;
 
NOTE: Variable r non initialisée.
NOTE:  13 observation(s) lue(s) dans la table WORK.TESTSUP.
*1 key=1 data=10 sup=0
*2 key=1 data=10 sup=0
*3 key=1 data=15 sup=1 rc=0
*
*1 key=1 data=15 sup=1
*2 key=1 data=15 sup=1
*3 key=1 data=15 sup=1 rc=160038
*
*1 key=2 data=11 sup=0
*2 key=2 data=11 sup=0
*3 key=2 data=16 sup=0 rc=0
*
*1 key=2 data=16 sup=0
*2 key=2 data=16 sup=0
*3 key=2 data=9 sup=1 rc=0
*
*1 key=2 data=9 sup=1
*2 key=2 data=9 sup=1
*3 key=2 data=9 sup=1 rc=160038
*
*1 key=3 data=20 sup=0
*2 key=3 data=20 sup=0
*3 key=3 data=100 sup=0 rc=0
*
*1 key=3 data=100 sup=0
*2 key=3 data=100 sup=0
*3 key=3 data=100 sup=0 rc=160038
*
*1 key=4 data=6 sup=0
*2 key=4 data=6 sup=0
*3 key=4 data=6 sup=0 rc=160038
*
*1 key=5 data=5 sup=0
*2 key=5 data=5 sup=0
*3 key=5 data=99 sup=0 rc=0
*
*1 key=5 data=99 sup=0
*2 key=5 data=99 sup=0
*3 key=5 data=99 sup=0 rc=160038
*
NOTE: La table WORK.RESULTAT a 11 observation(s) et 3 variable(s).
NOTE: La compression de la table WORK.RESULTAT a augmenté la taille de 100.00 pour cent.
      Compression de 2 pages; une décompression nécessiterait  1 pages.
key=1 data=10
key=1 data=45
key=1 data=5
key=2 data=11
key=2 data=16
key=2 data=99
key=3 data=20
key=3 data=100
key=4 data=6
key=5 data=5
key=5 data=99
NOTE: L'étape DATA a utilisé (Durée totale du traitement) :
      temps réel          0.04 secondes
      temps UC            0.04 secondes

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
                                                     Obs    key    data    sup
 
                                                       1     1       10     0
                                                       2     1       45     0
                                                       3     1        5     1
                                                       4     2       11     0
                                                       5     2       16     0
                                                       6     2       99     0
                                                       7     3       20     0
                                                       8     3      100     0
                                                       9     4        6     0
                                                      10     5        5     0
                                                      11     5       99     0

**JeromeMATHIAS** · 01/05/2013, 12h03

Bonjour,

finalement je me suis débrouillé avec un double objet hash, un objet "source" et un objet "resultat".

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
DATA _null_;
   LENGTH r Xa2 Ya2 Xa1 Ya1 8 vect 8 XC YC ORDRE 8 convexe $1 num 8;
 
   IF _n_=1 THEN DO;
 
   DECLARE HASH h(DATASET:'calcul', MULTIDATA: 'y', ORDERED: 'y');
   h.DEFINEKEY('id');
   h.DEFINEDATA('id', 'Tg_theta','x','y','convexe','ordre');
   h.DEFINEDONE();
   CALL MISSING (id,Tg_theta,x,y,ordre);
 
   DECLARE HASH Convex; /*** Table de contour du convexe ***/
   Convex = _new_ hash (MULTIDATA: 'y',ORDERED: 'y');
   Convex.DEFINEKEY('id','num');
   Convex.DEFINEDATA('id','XC','YC','ORDREC','num');
   Convex.DEFINEDONE();
 
   END;
 
 
   DO ID= 1 TO &nb ; /** calcul de chaque ensemble pris un à un **/
 
      /*put "*******DEBUT CONVEXE******** convexe numero "   id ;*/
 
	  /*** chargement des deux premiers points dans Convexe ***/
	  rc=h.find();
	  XC=X;YC=Y;ORDREC=ORDRE;
	  num=1;
	  rc2=convex.add();
	  /*PUT 'ajout du premier point ' rc= 'point num ' ordre ;*/
	  rc=h.find_next();
	  XC=X;YC=Y;ORDREC=ORDRE;
	  num=2;
	  rc2=convex.add();
	 /* PUT 'ajout du deuxième point ' rc2= 'point num ' ordre ;*/
	num=2 ;
 
		DO UNTIL (rc^=0);
 
				rc=h.find_next();
				/*PUT 'h.find_next point courant ' ordre = ;*/
				boucle: ;
				/*put 'num debut de boucle ' num= ;*/
				rc2=convex.find();
				Xa1=XC;Ya1=YC;
				/*PUT Xa1= Ya1 = rc2= 'ordre Xa1 ' ordrec= ;*/
 
				num=num-1;
				rc2=convex.find();
				Xa2=XC;Ya2=YC;
				/*PUT Xa2= Ya2= rc2= 'ordre Xa2 ' ordrec= ;*/
				/*PUT rc = ;*/
 
 
				vect=(Xa2-Xa1)*(Y-Ya1)-(Ya2-Ya1)*(X-Xa1);
				/*PUT 'calcul produit vectoriel ' vect= ;*/
				IF Vect>0 	THEN 	DO ;
											/*** le point est  OK ***/
				 					num=num+2;
									XC=X;
									YC=Y;
									ORDREC=ORDRE;
									rc2=convex.add() ;
									/*PUT 'Nouveau point sur le convexe num ' num rc2= ordre= ;*/
									END;
							ELSE	DO ;
										/*** le dernier point du convexe est invalidé ***/
									num=num+1;
									rc2=convex.find();
									/*PUT 'point supprimé du convexe ' ordrec = ;*/
									rc2=convex.remove(); /** point supprimé **/
									num=num-1;
									/*PUT "retour boucle" ;*/
									goto boucle;
									END;
 
 
 
		END;
 
 
 
	END ; 
 
	PUT "export table des contours convexes";
	rc=convex.output(dataset: 'work.convexe');
	 put rc= ;
	RUN; 
 
proc options GROUP=memory;
run;

Comme je travaille sur des centaines de millions de points (36 000 communes), je ne vais pas avoir suffisamment de mémoire, j'aimerais donc calculer les convexes par communes ou département en lisant une seule fois le fichier d'origine contenant tous les points. Il me faudrait découper les calculs comme on peut le faire dans l'étape DATA par des BY GROUP (ici par exemple DC ou DEP=SUBSTR(DC,1,2) ).

Si quelqu'un a des idées comment implémenter ça en objet hash... ?

**JeromeMATHIAS** · 02/05/2013, 20h35

J'ai résolu mon problème de consommation mémoire par les objets hash.

Je marque en résolu.

Merci.

HASH code : utilisation de REMOVEDUP()

SAS Base

Discussions similaires

Partager

Partager