QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: René on March 04, 2019, 10:43:03 am

Title: Array_Intersection
Post by: René on March 04, 2019, 10:43:03 am

I am trying to find the best way to write a subroutine of Array Intersection

I tried 3 methods.
- a sequential method (18 seconds)
- a dichotomous search method  ( 9 seconds)
-and finally I learn or I try to understand how to use the SMcNeill tools and so I wrote a routine with the use of _MEM. It's difficult for me because I do not understand all the subtleties of the English language and even less those of the language "Basic"  (12 seconds)

These tables are already sorted
I thought the 3rd method (with _Mem) would be faster, but no.
I think I have to make mistakes in using these instructions

Thank you in advance for your advice

Code: QB64: [Select]

1. '$INCLUDE:'SET.BI'
2.  
3. DIM a(100000, 20) AS LONG
4. DIM b(10) AS LONG
5. DIM c(20) AS LONG
6. DIM result(100) AS LONG
7.  
8. Read_tables
9.  
10. DIM ma AS _MEM: ma = _MEM(a())
11. DIM mb AS _MEM: mb = _MEM(b())
12. DIM mc AS _MEM: mc = _MEM(c())
13. 'MemSortSome ma, 0, 19
14. 'MemSortSome mb, 0, 9
15.  
16. Intersec_sequentiel:
17.  
18. REM calcul intersection_Array methode sequentielle
19. PRINT "1 - Intersection_array  methode sequentielle"
20. PRINT "wait about 20 seconds...."
21. FOR k = 0 TO 10: result(k) = 0: NEXT k
22. temps1 = TIMER(0.001)
23. commun# = 0
24. repet = 0
25. DO
26.     k = 0: ll% = 0
27.     DO
28.         i = 0
29.         DO
30.             j = 0
31.             DO
32.                 IF a(k, j) > b(i) THEN EXIT DO
33.                 IF b(i) = a(k, j) THEN commun# = commun# + 1: ll% = ll% + 1
34.                 j = j + 1
35.             LOOP UNTIL j > 19
36.             i = i + 1
37.         LOOP UNTIL i > 9
38.         result(ll%) = result(ll%) + 1
39.         ll% = 0
40.         k = k + 1
41.     LOOP UNTIL k > 19
42.     repet = repet + 1
43. LOOP UNTIL repet > 100000
44. temps1 = TIMER(0.001) - temps1
45. PRINT "Commun="; commun#, "temps="; temps1
46. FOR k = 0 TO 10: PRINT k; "="; result(k): NEXT k
47. PRINT
48. PRINT "Press a Key to continue"
49. SLEEP
50.  
51.  
52.  
53.  
54. Intersec_dicho:
55.  
56. CLS
57. FOR k = 0 TO 10: result(k) = 0: NEXT k
58. PRINT "2 - Calcul Array_Intersection dichotomie "
59. PRINT "wait about 20 seconds...."
60. temps6 = TIMER(0.001)
61. commun# = 0
62. repet = 0
63. DO
64.     k = 0: ll% = 0
65.     DO
66.         FOR i1 = 0 TO 19: c(i1) = a(k, i1): NEXT i1
67.         'MemSortSome mc, 0, 19  (gain 9 seconds)
68.         i = 0
69.         DO
70.             inf% = 0: sup% = 19
71.             RechercheCombi:
72.             IF inf% > sup% THEN GOTO existepas
73.             mil% = INT((inf% + sup%) / 2)
74.             IF b(i) = c(mil%) THEN commun# = commun# + 1: ll% = ll% + 1: GOTO existepas
75.             IF b(i) < c(mil%) THEN sup% = mil% - 1: GOTO RechercheCombi
76.             IF b(i) > c(mil%) THEN inf% = mil% + 1: GOTO RechercheCombi
77.             existepas:
78.             i = i + 1
79.         LOOP UNTIL i > 9
80.         result(ll%) = result(ll%) + 1
81.         ll% = 0
82.         k = k + 1
83.     LOOP UNTIL k > 19
84.     repet = repet + 1
85. LOOP UNTIL repet > 100000
86. temps6 = TIMER(0.001) - temps6
87. PRINT
88. PRINT "Commun="; commun#, "temps="; temps6
89. FOR k = 0 TO 10: PRINT k; "="; result(k): NEXT k
90. PRINT "Press a Key to continue"; ";"
91. SLEEP
92.  
93.  
94.  
95.  
96.  
97.  
98. intersec_mem:
99.  
100. CLS
101. FOR k = 0 TO 10: result(k) = 0: NEXT k
102. REM calcul intersection tableau avec _mem
103. PRINT "Calcul Array_Intersection with _mem "
104. PRINT "wait about 20 seconds...."
105. commun# = 0
106. repet = 0
107. temps8 = TIMER(0.001)
108. DO
109.     k = 0: ll% = 0
110.     DO
111.         FOR i1 = 0 TO 19: c(i1) = a(k, i1): NEXT i1
112.         'MemSortSome mc, 0, 19 (gain 9 seconds)
113.         kk% = 0
114.         DO
115.             index% = BinaryMemSearchSome(b(kk%), mc, 0, 19)
116.             IF index% <> -1 THEN commun# = commun# + 1: ll% = ll% + 1
117.             kk% = kk% + 1
118.         LOOP UNTIL kk% > 9
119.         result(ll%) = result(ll%) + 1
120.         ll% = 0
121.         k = k + 1
122.     LOOP UNTIL k > 19
123.     repet = repet + 1
124. LOOP UNTIL repet > 100000
125. temps8 = TIMER(0.001) - temps8
126. PRINT
127. PRINT "Commun="; commun#, "temps="; temps8
128. FOR k = 0 TO 10: PRINT k; "="; result(k): NEXT k
129. SLEEP
130.  
131.  
132. STOP
133.  
134.  
135. SUB Read_tables
136.     SHARED a() AS LONG, b() AS LONG
137.  
138.     FOR i = 0 TO 19
139.         FOR j = 0 TO 19
140.             READ a(i, j)
141.         NEXT j
142.     NEXT i
143.     FOR j = 0 TO 9
144.         READ b(j)
145.     NEXT j
146.     CLOSE
147. END SUB
148.  
149.  
150.  
151. DATA 1,2,3,5,9,11,13,14,24,27,32,45,47,58,60,64,65,67,69,70
152. DATA 2,4,5,7,11,12,22,23,27,28,31,41,44,46,48,53,54,62,66,70
153. DATA 3,5,9,16,21,24,28,33,36,37,39,42,43,44,46,53,57,60,65,70
154. DATA 5,7,10,17,26,28,32,33,35,36,39,42,44,46,49,52,57,58,60,68
155. DATA 3,7,8,9,11,12,18,22,26,29,30,33,40,46,48,49,55,58,60,63
156. DATA 1,2,6,10,11,16,17,21,27,35,42,45,49,56,59,63,66,68,69,70
157. DATA 4,13,14,23,26,29,36,37,39,41,42,45,46,52,53,54,56,61,63,65
158. DATA 5,9,11,15,19,21,22,25,30,36,38,41,42,45,56,57,60,65,66,68
159. DATA 5,7,8,12,16,24,25,26,28,32,33,41,42,43,48,50,52,57,62,65
160. DATA 3,11,15,16,20,21,33,34,47,49,50,51,52,54,57,58,61,62,66,70
161.  
162. DATA 2,8,9,10,13,18,19,22,23,24,28,33,34,37,41,42,43,45,51,61
163. DATA 2,4,7,11,12,14,15,16,28,36,38,40,44,45,56,63,65,67,68,70
164. DATA 7,9,12,13,15,19,21,29,30,31,34,36,37,39,41,48,53,62,64,68
165. DATA 3,5,10,13,14,15,16,22,26,29,30,34,36,41,43,47,48,55,66,67
166. DATA 2,3,7,8,15,20,22,32,35,41,49,50,51,53,54,58,59,60,69,70
167. DATA 1,6,10,14,20,21,23,24,25,27,32,36,37,38,47,53,56,59,62,63
168. DATA 4,11,12,15,25,28,30,31,33,35,39,43,45,49,51,56,59,63,66,69
169. DATA 1,4,6,7,8,10,15,24,27,33,34,35,37,38,46,50,58,67,68,70
170. DATA 10,11,12,14,15,17,18,23,25,37,38,42,52,53,54,55,63,64,65,68
171. DATA 1,2,5,7,15,16,19,23,24,27,33,38,39,47,54,59,60,62,64,65
172. DATA 1,3,11,21,28,32,45,58,60,70
173.  
174.  
175. '$INCLUDE:'SET.BM'
176.  

  [ This attachment cannot be displayed inline in 'Print Page' view ]    [ This attachment cannot be displayed inline in 'Print Page' view ]    [ This attachment cannot be displayed inline in 'Print Page' view ]  

Text Only | Text with Attachments