DIM a (Max Index)

[SMcNeill]

The numbers I have,
is in thes style;
strigs;
q1
q2
q3
....
q33
NOT q(1) etccc
The value in those strings are in the range 1-255

Can you share an example portion of the datafile/code?  Like Codeguy, I'm lost as to how you can have both byte values and 33-bit values stored sequentially.  How do you know how many bits/bytes to assign to a value?  What delimiters are used?  What structure does this data have?

More details are needed, if we're going to try and sort out a way to help speed things up for you.

[codeguy]

if you ever get this figured out, here's a decent in-place algorithm to use:
performance (millisecond) profile for DOUBLE precision array until 134M+ elements :
 1 0
 3 0
 7 0
 15 0
 31 0
 63 0
 127 0
 255 0
 511 0
 1023 .9765625
 2047 .9765625
 4095 2.929688
 8191 5.859375
 16383 17.08984
 32767 51.26953
 65535 136.2305
 131071 241.6992
 262143 415.0391
 524287 946.7773
 1048575 1986.816
 2097151 4613.77
 4194303 9541.016
 8388607 18500.98
 16777215 42821.29
 33554431 84074.22
 67108863 186534.7
 134217727 379580.1

demo code:

Code: QB64: [Select]

1. WIDTH 80
2. n& = 0
3. _CLIPBOARD$ = ""
4. DO
5.     n& = n& + 1
6.     REDIM a(0 TO n&) AS DOUBLE '* 65s
7.     DIM u AS LONG
8.     FOR u = LBOUND(a) TO UBOUND(a)
9.         a(u) = RND
10.     NEXT
11.     s! = TIMER(.001)
12.     QuickSortIntrospective a(), LBOUND(a), UBOUND(a), 1
13.     f! = TIMER(.001)
14.     'd$ = "." + STRING$(15, "#")
15.     DIM l AS LONG
16.     l = LBOUND(a)
17.     FOR u = LBOUND(a) TO UBOUND(a)
18.         IF a(u) < a(l) THEN STOP
19.         'PRINT USING d$; a(u);
20.         l = u
21.     NEXT
22.     _CLIPBOARD$ = _CLIPBOARD$ + STR$(n&) + STR$(1000 * (f! - s!)) + CHR$(13) + CHR$(10)
23.     n& = n& * 2
24. LOOP
25.  

Complete IntroSort, in-place (uses no auxiliary) and combines QuickSort, HeapSort and InsertionSort. This will allow the maximum range of in-memory sorting in reasonable time.

Code: QB64: [Select]

1. '****************************************
2. '* The IntroSort() algorithm extended to QBxx because there is no qbxx-compatible code
3. '* The IntroSort algorithm extended to qb64 because i could find no pure qbxx code
4. '* 03Jun2017, by CodeGuy -- further mods for use in sorting library 03 Aug 2017
5. '* Introspective Sort (IntroSort) falls back to MergeSort after so many levels of
6. '* recursion and is good for highly redundant data (aka few unique)
7. '* for very short runs, it falls back to InsertionSort.
8.  
9. SUB QuickSortIntrospective (CGSortLibArr() AS DOUBLE, IntroSort_start AS LONG, IntroSort_finish AS LONG, order AS INTEGER)
10.     DIM IntroSort_i AS LONG
11.     DIM IntroSort_J AS LONG
12.     STATIC IntroSort_level AS INTEGER
13.     STATIC IntroSort_MaxRecurseLevel AS INTEGER
14.     IntroSort_MaxRecurseLevel = 15
15.     IF IntroSort_start < IntroSort_finish THEN
16.         IF IntroSort_finish - IntroSort_start > 31 THEN
17.             IF IntroSort_level > IntroSort_MaxRecurseLevel THEN
18.                 HeapSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
19.             ELSE
20.                 IntroSort_level = IntroSort_level + 1
21.                 QuickSortIJ CGSortLibArr(), IntroSort_start, IntroSort_finish, IntroSort_i, IntroSort_J, order
22.                 QuickSortIntrospective CGSortLibArr(), IntroSort_start, IntroSort_J, order
23.                 QuickSortIntrospective CGSortLibArr(), IntroSort_i, IntroSort_finish, order
24.                 IntroSort_level = IntroSort_level - 1
25.             END IF
26.         ELSE
27.             InsertionSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
28.         END IF
29.     END IF
30. END SUB
31.  
32. SUB QuickSortIJ (CGSortLibArr() AS DOUBLE, start AS LONG, finish AS LONG, i AS LONG, j AS LONG, order AS INTEGER)
33.     DIM Compare AS DOUBLE '* MUST be the same type as CGSortLibArr()
34.     i = start
35.     j = finish
36.     Compare = CGSortLibArr(i + (j - i) \ 2)
37.     SELECT CASE order
38.         CASE 1
39.             DO
40.                 DO WHILE CGSortLibArr(i) < Compare
41.                     i = i + 1
42.                 LOOP
43.                 DO WHILE CGSortLibArr(j) > Compare
44.                     j = j - 1
45.                 LOOP
46.                 IF i <= j THEN
47.                     IF i <> j THEN
48.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
49.                     END IF
50.                     i = i + 1
51.                     j = j - 1
52.                 END IF
53.             LOOP UNTIL i > j
54.         CASE ELSE
55.             DO
56.                 DO WHILE CGSortLibArr(i) > Compare
57.                     i = i + 1
58.                 LOOP
59.                 DO WHILE CGSortLibArr(j) < Compare
60.                     j = j - 1
61.                 LOOP
62.                 IF i <= j THEN
63.                     IF i <> j THEN
64.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
65.                     END IF
66.                     i = i + 1
67.                     j = j - 1
68.                 END IF
69.             LOOP UNTIL i > j
70.     END SELECT
71. END SUB
72.  
73. SUB InsertionSort (CGSortLibArr() AS DOUBLE, start AS LONG, finish AS LONG, order AS INTEGER)
74.     DIM InSort_Local_ArrayTemp AS DOUBLE
75.     DIM InSort_Local_i AS LONG
76.     DIM InSort_Local_j AS LONG
77.     SELECT CASE order
78.         CASE 1
79.             FOR InSort_Local_i = start + 1 TO finish
80.                 InSort_Local_j = InSort_Local_i - 1
81.                 IF CGSortLibArr(InSort_Local_i) < CGSortLibArr(InSort_Local_j) THEN
82.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
83.                     DO UNTIL InSort_Local_j < start
84.                         IF (InSort_Local_ArrayTemp < CGSortLibArr(InSort_Local_j)) THEN
85.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
86.                             InSort_Local_j = InSort_Local_j - 1
87.                         ELSE
88.                             EXIT DO
89.                         END IF
90.                     LOOP
91.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
92.                 END IF
93.             NEXT
94.         CASE ELSE
95.             FOR InSort_Local_i = start + 1 TO finish
96.                 InSort_Local_j = InSort_Local_i - 1
97.                 IF CGSortLibArr(InSort_Local_i) > CGSortLibArr(InSort_Local_j) THEN
98.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
99.                     DO UNTIL InSort_Local_j < start
100.                         IF (InSort_Local_ArrayTemp > CGSortLibArr(InSort_Local_j)) THEN
101.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
102.                             InSort_Local_j = InSort_Local_j - 1
103.                         ELSE
104.                             EXIT DO
105.                         END IF
106.                     LOOP
107.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
108.                 END IF
109.             NEXT
110.     END SELECT
111. END SUB
112.  
113. SUB HeapSort (CGSortLibArr() AS DOUBLE, start AS LONG, finish AS LONG, order AS INTEGER)
114.     DIM i AS LONG
115.     DIM j AS LONG
116.     FOR i = start + 1 TO finish
117.         PercolateUp CGSortLibArr(), start, i, order
118.     NEXT i
119.  
120.     FOR i = finish TO start + 1 STEP -1
121.         SWAP CGSortLibArr(start), CGSortLibArr(i)
122.         PercolateDown CGSortLibArr(), start, i - 1, order
123.     NEXT i
124. END SUB
125.  
126. SUB PercolateDown (CGSortLibArr() AS DOUBLE, start AS LONG, MaxLevel AS LONG, order AS INTEGER)
127.     DIM i AS LONG
128.     DIM child AS LONG
129.     DIM ax AS LONG
130.     i = start
131.     '* Move the value in GetPixel!!!(start) down the heap until it has
132.     '* reached its proper node (that is, until it is less than its parent
133.     '* node or until it has reached MaxLevel!!!, the bottom of the current heap):
134.     DO
135.         child = 2 * (i - start) + start ' Get the subscript for the Child node.
136.         '* Reached the bottom of the heap, so exit this procedure:
137.         IF child > MaxLevel THEN EXIT DO
138.         SELECT CASE order
139.             CASE 1
140.                 '* If there are two Child nodes, find out which one is bigger:
141.                 ax = child + 1
142.                 IF ax <= MaxLevel THEN
143.                     IF CGSortLibArr(ax) > CGSortLibArr(child) THEN
144.                         child = ax
145.                     END IF
146.                 END IF
147.  
148.                 '* Move the value down if it is still not bigger than either one of
149.                 '* its Child!!!ren:
150.                 IF CGSortLibArr(i) < CGSortLibArr(child) THEN
151.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
152.                     i = child
153.                 ELSE
154.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
155.                     '* so exit:
156.                     EXIT DO
157.                 END IF
158.             CASE ELSE
159.                 '* If there are two Child nodes, find out which one is smaller:
160.                 ax = child + 1
161.                 IF ax <= MaxLevel THEN
162.                     IF CGSortLibArr(ax) < CGSortLibArr(child) THEN
163.                         child = ax
164.                     END IF
165.                 END IF
166.                 '* Move the value down if it is still not smaller than either one of
167.                 '* its Child!!!ren:
168.                 IF CGSortLibArr(i) > CGSortLibArr(child) THEN
169.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
170.                     i = child
171.                 ELSE
172.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
173.                     '* so exit:
174.                     EXIT DO
175.                 END IF
176.         END SELECT
177.     LOOP
178. END SUB
179.  
180. SUB PercolateUp (CGSortLibArr() AS DOUBLE, start AS LONG, MaxLevel AS LONG, order AS INTEGER)
181.     DIM parent AS LONG
182.     DIM i AS LONG
183.     SELECT CASE order
184.         CASE 1
185.             i = MaxLevel
186.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
187.             '* reached its proper node (that is, until it is greater than either
188.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
189.             DO UNTIL i = start
190.                 '* Get the subscript for the parent node.
191.                 parent = start + (i - start) \ 2
192.                 '* The value at the current node is still bigger than the value at
193.                 '* its parent node, so swap these two array elements:
194.                 IF CGSortLibArr(i) > CGSortLibArr(parent) THEN
195.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
196.                     i = parent
197.                 ELSE
198.                     '* Otherwise, the element has reached its proper place in the heap,
199.                     '* so exit this procedure:
200.                     EXIT DO
201.                 END IF
202.             LOOP
203.         CASE ELSE
204.             i = MaxLevel
205.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
206.             '* reached its proper node (that is, until it is greater than either
207.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
208.             DO UNTIL i = start
209.                 '* Get the subscript for the parent node.
210.                 parent = start + (i - start) \ 2
211.                 '* The value at the current node is still smaller than the value at
212.                 '* its parent node, so swap these two array elements:
213.                 IF CGSortLibArr(i) < CGSortLibArr(parent) THEN
214.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
215.                     i = parent
216.                 ELSE
217.                     '* Otherwise, the element has reached its proper place in the heap,
218.                     '* so exit this procedure:
219.                     EXIT DO
220.                 END IF
221.             LOOP
222.     END SELECT
223. END SUB
224.  

IntroSort, completely in-place. Don't forget to change AS LONG to as _INTEGER64 to avoid overflow problems on indexes and change types as appropriate.


code to use _UNSIGNED LONG for indexes into arrays

Code: QB64: [Select]

1. WIDTH 80
2. DIM testn AS _UNSIGNED LONG
3. testn = 0
4. '_CLIPBOARD$ = ""
5. DO
6.     testn = testn + 1
7.     REDIM a(0 TO testn) AS DOUBLE '* 65s
8.     DIM u AS _UNSIGNED LONG
9.     FOR u = LBOUND(a) TO UBOUND(a)
10.         a(u) = RND
11.     NEXT
12.     s! = TIMER(.001)
13.     QuickSortIntrospective a(), LBOUND(a), UBOUND(a), 1
14.     f! = TIMER(.001)
15.     'd$ = "." + STRING$(15, "#")
16.     DIM lp AS _UNSIGNED LONG
17.     lp = LBOUND(a)
18.     FOR u = LBOUND(a) TO UBOUND(a)
19.         IF a(u) < a(lp) THEN STOP
20.         'PRINT USING d$; a(u);
21.         lp = u
22.     NEXT
23.     ''_CLIPBOARD$ = _CLIPBOARD$ + STR$(testn) + STR$(1000 * (f! - s!)) + CHR$(13) + CHR$(10)
24.     PRINT STR$(testn); STR$(1000 * (f! - s!))
25.     testn = testn * 2
26. LOOP
27.  
28. '****************************************
29. '* The IntroSort() algorithm extended to QBxx because there is no qbxx-compatible code
30. '* The IntroSort algorithm extended to qb64 because i could find no pure qbxx code
31. '* 03Jun2017, by CodeGuy -- further mods for use in sorting library 03 Aug 2017
32. '* Introspective Sort (IntroSort) falls back to MergeSort after so many levels of
33. '* recursion and is good for highly redundant data (aka few unique)
34. '* for very short runs, it falls back to InsertionSort.
35.  
36. SUB QuickSortIntrospective (CGSortLibArr() AS DOUBLE, IntroSort_start AS _UNSIGNED LONG, IntroSort_finish AS _UNSIGNED LONG, order AS INTEGER)
37.     DIM IntroSort_i AS _UNSIGNED LONG
38.     DIM IntroSort_J AS _UNSIGNED LONG
39.     STATIC IntroSort_level AS INTEGER
40.     STATIC IntroSort_MaxRecurseLevel AS INTEGER
41.     IntroSort_MaxRecurseLevel = 15
42.     IF IntroSort_start < IntroSort_finish THEN
43.         IF IntroSort_finish - IntroSort_start > 31 THEN
44.             IF IntroSort_level > IntroSort_MaxRecurseLevel THEN
45.                 HeapSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
46.             ELSE
47.                 IntroSort_level = IntroSort_level + 1
48.                 QuickSortIJ CGSortLibArr(), IntroSort_start, IntroSort_finish, IntroSort_i, IntroSort_J, order
49.                 QuickSortIntrospective CGSortLibArr(), IntroSort_start, IntroSort_J, order
50.                 QuickSortIntrospective CGSortLibArr(), IntroSort_i, IntroSort_finish, order
51.                 IntroSort_level = IntroSort_level - 1
52.             END IF
53.         ELSE
54.             InsertionSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
55.         END IF
56.     END IF
57. END SUB
58.  
59. SUB QuickSortIJ (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, i AS _UNSIGNED LONG, j AS _UNSIGNED LONG, order AS INTEGER)
60.     DIM Compare AS DOUBLE '* MUST be the same type as CGSortLibArr()
61.     i = start
62.     j = finish
63.     Compare = CGSortLibArr(i + (j - i) \ 2)
64.     SELECT CASE order
65.         CASE 1
66.             DO
67.                 DO WHILE CGSortLibArr(i) < Compare
68.                     i = i + 1
69.                 LOOP
70.                 DO WHILE CGSortLibArr(j) > Compare
71.                     j = j - 1
72.                 LOOP
73.                 IF i <= j THEN
74.                     IF i <> j THEN
75.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
76.                     END IF
77.                     i = i + 1
78.                     j = j - 1
79.                 END IF
80.             LOOP UNTIL i > j
81.         CASE ELSE
82.             DO
83.                 DO WHILE CGSortLibArr(i) > Compare
84.                     i = i + 1
85.                 LOOP
86.                 DO WHILE CGSortLibArr(j) < Compare
87.                     j = j - 1
88.                 LOOP
89.                 IF i <= j THEN
90.                     IF i <> j THEN
91.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
92.                     END IF
93.                     i = i + 1
94.                     j = j - 1
95.                 END IF
96.             LOOP UNTIL i > j
97.     END SELECT
98. END SUB
99.  
100. SUB InsertionSort (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, order AS INTEGER)
101.     DIM InSort_Local_ArrayTemp AS DOUBLE
102.     DIM InSort_Local_i AS _UNSIGNED LONG
103.     DIM InSort_Local_j AS _UNSIGNED LONG
104.     SELECT CASE order
105.         CASE 1
106.             FOR InSort_Local_i = start + 1 TO finish
107.                 InSort_Local_j = InSort_Local_i - 1
108.                 IF CGSortLibArr(InSort_Local_i) < CGSortLibArr(InSort_Local_j) THEN
109.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
110.                     DO WHILE InSort_Local_j + 1 > start
111.                         IF (InSort_Local_ArrayTemp < CGSortLibArr(InSort_Local_j)) THEN
112.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
113.                             InSort_Local_j = InSort_Local_j - 1
114.                         ELSE
115.                             EXIT DO
116.                         END IF
117.                     LOOP
118.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
119.                 END IF
120.             NEXT
121.         CASE ELSE
122.             FOR InSort_Local_i = start + 1 TO finish
123.                 InSort_Local_j = InSort_Local_i - 1
124.                 IF CGSortLibArr(InSort_Local_i) > CGSortLibArr(InSort_Local_j) THEN
125.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
126.                     DO WHILE InSort_Local_j + 1 > start
127.                         IF (InSort_Local_ArrayTemp > CGSortLibArr(InSort_Local_j)) THEN
128.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
129.                             InSort_Local_j = InSort_Local_j - 1
130.                         ELSE
131.                             EXIT DO
132.                         END IF
133.                     LOOP
134.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
135.                 END IF
136.             NEXT
137.     END SELECT
138. END SUB
139.  
140. SUB HeapSort (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, order AS INTEGER)
141.     DIM i AS _UNSIGNED LONG
142.     DIM j AS _UNSIGNED LONG
143.     FOR i = start + 1 TO finish
144.         PercolateUp CGSortLibArr(), start, i, order
145.     NEXT i
146.  
147.     FOR i = finish TO start + 1 STEP -1
148.         SWAP CGSortLibArr(start), CGSortLibArr(i)
149.         PercolateDown CGSortLibArr(), start, i - 1, order
150.     NEXT i
151. END SUB
152.  
153. SUB PercolateDown (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, MaxLevel AS _UNSIGNED LONG, order AS INTEGER)
154.     DIM i AS _UNSIGNED LONG
155.     DIM child AS _UNSIGNED LONG
156.     DIM ax AS _UNSIGNED LONG
157.     i = start
158.     '* Move the value in GetPixel!!!(start) down the heap until it has
159.     '* reached its proper node (that is, until it is less than its parent
160.     '* node or until it has reached MaxLevel!!!, the bottom of the current heap):
161.     DO
162.         child = 2 * (i - start) + start ' Get the subscript for the Child node.
163.         '* Reached the bottom of the heap, so exit this procedure:
164.         IF child > MaxLevel THEN EXIT DO
165.         SELECT CASE order
166.             CASE 1
167.                 '* If there are two Child nodes, find out which one is bigger:
168.                 ax = child + 1
169.                 IF ax <= MaxLevel THEN
170.                     IF CGSortLibArr(ax) > CGSortLibArr(child) THEN
171.                         child = ax
172.                     END IF
173.                 END IF
174.  
175.                 '* Move the value down if it is still not bigger than either one of
176.                 '* its Child!!!ren:
177.                 IF CGSortLibArr(i) < CGSortLibArr(child) THEN
178.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
179.                     i = child
180.                 ELSE
181.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
182.                     '* so exit:
183.                     EXIT DO
184.                 END IF
185.             CASE ELSE
186.                 '* If there are two Child nodes, find out which one is smaller:
187.                 ax = child + 1
188.                 IF ax <= MaxLevel THEN
189.                     IF CGSortLibArr(ax) < CGSortLibArr(child) THEN
190.                         child = ax
191.                     END IF
192.                 END IF
193.                 '* Move the value down if it is still not smaller than either one of
194.                 '* its Child!!!ren:
195.                 IF CGSortLibArr(i) > CGSortLibArr(child) THEN
196.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
197.                     i = child
198.                 ELSE
199.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
200.                     '* so exit:
201.                     EXIT DO
202.                 END IF
203.         END SELECT
204.     LOOP
205. END SUB
206.  
207. SUB PercolateUp (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, MaxLevel AS _UNSIGNED LONG, order AS INTEGER)
208.     DIM parent AS _UNSIGNED LONG
209.     DIM i AS _UNSIGNED LONG
210.     SELECT CASE order
211.         CASE 1
212.             i = MaxLevel
213.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
214.             '* reached its proper node (that is, until it is greater than either
215.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
216.             DO UNTIL i = start
217.                 '* Get the subscript for the parent node.
218.                 parent = start + (i - start) \ 2
219.                 '* The value at the current node is still bigger than the value at
220.                 '* its parent node, so swap these two array elements:
221.                 IF CGSortLibArr(i) > CGSortLibArr(parent) THEN
222.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
223.                     i = parent
224.                 ELSE
225.                     '* Otherwise, the element has reached its proper place in the heap,
226.                     '* so exit this procedure:
227.                     EXIT DO
228.                 END IF
229.             LOOP
230.         CASE ELSE
231.             i = MaxLevel
232.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
233.             '* reached its proper node (that is, until it is greater than either
234.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
235.             DO UNTIL i = start
236.                 '* Get the subscript for the parent node.
237.                 parent = start + (i - start) \ 2
238.                 '* The value at the current node is still smaller than the value at
239.                 '* its parent node, so swap these two array elements:
240.                 IF CGSortLibArr(i) < CGSortLibArr(parent) THEN
241.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
242.                     i = parent
243.                 ELSE
244.                     '* Otherwise, the element has reached its proper place in the heap,
245.                     '* so exit this procedure:
246.                     EXIT DO
247.                 END IF
248.             LOOP
249.     END SELECT
250. END SUB
251.  

InsertionSort was not very friendly to _UNSIGNED until modified this way:

Code: QB64: [Select]

1. WIDTH 80
2. DIM testn AS _UNSIGNED LONG
3. testn = 0
4. _CLIPBOARD$ = ""
5. DO
6.     testn = testn + 1
7.     REDIM a(0 TO testn) AS DOUBLE '* 65s
8.     DIM u AS _UNSIGNED LONG
9.     FOR u = LBOUND(a) TO UBOUND(a)
10.         a(u) = RND
11.     NEXT
12.     s! = TIMER(.001)
13.     QuickSortIntrospective a(), LBOUND(a), UBOUND(a), 1
14.     f! = TIMER(.001)
15.     'd$ = "." + STRING$(15, "#")
16.     DIM lp AS _UNSIGNED LONG
17.     lp = LBOUND(a)
18.     FOR u = LBOUND(a) TO UBOUND(a)
19.         IF a(u) < a(lp) THEN STOP
20.         'PRINT USING d$; a(u);
21.         lp = u
22.     NEXT
23.     _CLIPBOARD$ = _CLIPBOARD$ + STR$(testn) + STR$(1000 * (f! - s!)) + CHR$(13) + CHR$(10)
24.     testn = testn * 2
25. LOOP
26.  
27.  
28. '****************************************
29. '* The IntroSort() algorithm extended to QBxx because there is no qbxx-compatible code
30. '* The IntroSort algorithm extended to qb64 because i could find no pure qbxx code
31. '* 03Jun2017, by CodeGuy -- further mods for use in sorting library 03 Aug 2017
32. '* Introspective Sort (IntroSort) falls back to MergeSort after so many levels of
33. '* recursion and is good for highly redundant data (aka few unique)
34. '* for very short runs, it falls back to InsertionSort.
35.  
36. SUB QuickSortIntrospective (CGSortLibArr() AS DOUBLE, IntroSort_start AS _UNSIGNED LONG, IntroSort_finish AS _UNSIGNED LONG, order AS INTEGER)
37.     DIM IntroSort_i AS _UNSIGNED LONG
38.     DIM IntroSort_J AS _UNSIGNED LONG
39.     STATIC IntroSort_level AS INTEGER
40.     STATIC IntroSort_MaxRecurseLevel AS INTEGER
41.     IntroSort_MaxRecurseLevel = 15
42.     IF IntroSort_start < IntroSort_finish THEN
43.         IF IntroSort_finish - IntroSort_start > 31 THEN
44.             IF IntroSort_level > IntroSort_MaxRecurseLevel THEN
45.                 HeapSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
46.             ELSE
47.                 IntroSort_level = IntroSort_level + 1
48.                 QuickSortIJ CGSortLibArr(), IntroSort_start, IntroSort_finish, IntroSort_i, IntroSort_J, order
49.                 QuickSortIntrospective CGSortLibArr(), IntroSort_start, IntroSort_J, order
50.                 QuickSortIntrospective CGSortLibArr(), IntroSort_i, IntroSort_finish, order
51.                 IntroSort_level = IntroSort_level - 1
52.             END IF
53.         ELSE
54.             InsertionSort CGSortLibArr(), IntroSort_start, IntroSort_finish, order
55.         END IF
56.     END IF
57. END SUB
58.  
59. SUB QuickSortIJ (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, i AS _UNSIGNED LONG, j AS _UNSIGNED LONG, order AS INTEGER)
60.     DIM Compare AS DOUBLE '* MUST be the same type as CGSortLibArr()
61.     i = start
62.     j = finish
63.     Compare = CGSortLibArr(i + (j - i) \ 2)
64.     SELECT CASE order
65.         CASE 1
66.             DO
67.                 DO WHILE CGSortLibArr(i) < Compare
68.                     i = i + 1
69.                 LOOP
70.                 DO WHILE CGSortLibArr(j) > Compare
71.                     j = j - 1
72.                 LOOP
73.                 IF i <= j THEN
74.                     IF i <> j THEN
75.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
76.                     END IF
77.                     i = i + 1
78.                     j = j - 1
79.                 END IF
80.             LOOP UNTIL i > j
81.         CASE ELSE
82.             DO
83.                 DO WHILE CGSortLibArr(i) > Compare
84.                     i = i + 1
85.                 LOOP
86.                 DO WHILE CGSortLibArr(j) < Compare
87.                     j = j - 1
88.                 LOOP
89.                 IF i <= j THEN
90.                     IF i <> j THEN
91.                         SWAP CGSortLibArr(i), CGSortLibArr(j)
92.                     END IF
93.                     i = i + 1
94.                     j = j - 1
95.                 END IF
96.             LOOP UNTIL i > j
97.     END SELECT
98. END SUB
99.  
100. SUB InsertionSort (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, order AS INTEGER)
101.     DIM InSort_Local_ArrayTemp AS DOUBLE
102.     DIM InSort_Local_i AS _UNSIGNED LONG
103.     DIM InSort_Local_j AS _UNSIGNED LONG
104.     SELECT CASE order
105.         CASE 1
106.             FOR InSort_Local_i = start + 1 TO finish
107.                 InSort_Local_j = InSort_Local_i - 1
108.                 IF CGSortLibArr(InSort_Local_i) < CGSortLibArr(InSort_Local_j) THEN
109.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
110.                     DO WHILE InSort_Local_j + 1 > start
111.                         IF (InSort_Local_ArrayTemp < CGSortLibArr(InSort_Local_j)) THEN
112.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
113.                             InSort_Local_j = InSort_Local_j - 1
114.                         ELSE
115.                             EXIT DO
116.                         END IF
117.                     LOOP
118.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
119.                 END IF
120.             NEXT
121.         CASE ELSE
122.             FOR InSort_Local_i = start + 1 TO finish
123.                 InSort_Local_j = InSort_Local_i - 1
124.                 IF CGSortLibArr(InSort_Local_i) > CGSortLibArr(InSort_Local_j) THEN
125.                     InSort_Local_ArrayTemp = CGSortLibArr(InSort_Local_i)
126.                     DO WHILE InSort_Local_j + 1 > start
127.                         IF (InSort_Local_ArrayTemp > CGSortLibArr(InSort_Local_j)) THEN
128.                             CGSortLibArr(InSort_Local_j + 1) = CGSortLibArr(InSort_Local_j)
129.                             InSort_Local_j = InSort_Local_j - 1
130.                         ELSE
131.                             EXIT DO
132.                         END IF
133.                     LOOP
134.                     CGSortLibArr(InSort_Local_j + 1) = InSort_Local_ArrayTemp
135.                 END IF
136.             NEXT
137.     END SELECT
138. END SUB
139.  
140. SUB HeapSort (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, finish AS _UNSIGNED LONG, order AS INTEGER)
141.     DIM i AS _UNSIGNED LONG
142.     DIM j AS _UNSIGNED LONG
143.     FOR i = start + 1 TO finish
144.         PercolateUp CGSortLibArr(), start, i, order
145.     NEXT i
146.  
147.     FOR i = finish TO start + 1 STEP -1
148.         SWAP CGSortLibArr(start), CGSortLibArr(i)
149.         PercolateDown CGSortLibArr(), start, i - 1, order
150.     NEXT i
151. END SUB
152.  
153. SUB PercolateDown (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, MaxLevel AS _UNSIGNED LONG, order AS INTEGER)
154.     DIM i AS _UNSIGNED LONG
155.     DIM child AS _UNSIGNED LONG
156.     DIM ax AS _UNSIGNED LONG
157.     i = start
158.     '* Move the value in GetPixel!!!(start) down the heap until it has
159.     '* reached its proper node (that is, until it is less than its parent
160.     '* node or until it has reached MaxLevel!!!, the bottom of the current heap):
161.     DO
162.         child = 2 * (i - start) + start ' Get the subscript for the Child node.
163.         '* Reached the bottom of the heap, so exit this procedure:
164.         IF child > MaxLevel THEN EXIT DO
165.         SELECT CASE order
166.             CASE 1
167.                 '* If there are two Child nodes, find out which one is bigger:
168.                 ax = child + 1
169.                 IF ax <= MaxLevel THEN
170.                     IF CGSortLibArr(ax) > CGSortLibArr(child) THEN
171.                         child = ax
172.                     END IF
173.                 END IF
174.  
175.                 '* Move the value down if it is still not bigger than either one of
176.                 '* its Child!!!ren:
177.                 IF CGSortLibArr(i) < CGSortLibArr(child) THEN
178.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
179.                     i = child
180.                 ELSE
181.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
182.                     '* so exit:
183.                     EXIT DO
184.                 END IF
185.             CASE ELSE
186.                 '* If there are two Child nodes, find out which one is smaller:
187.                 ax = child + 1
188.                 IF ax <= MaxLevel THEN
189.                     IF CGSortLibArr(ax) < CGSortLibArr(child) THEN
190.                         child = ax
191.                     END IF
192.                 END IF
193.                 '* Move the value down if it is still not smaller than either one of
194.                 '* its Child!!!ren:
195.                 IF CGSortLibArr(i) > CGSortLibArr(child) THEN
196.                     SWAP CGSortLibArr(i), CGSortLibArr(child)
197.                     i = child
198.                 ELSE
199.                     '* Otherwise, CGSortLibArr() has been restored to a heap from start to MaxLevel!!!,
200.                     '* so exit:
201.                     EXIT DO
202.                 END IF
203.         END SELECT
204.     LOOP
205. END SUB
206.  
207. SUB PercolateUp (CGSortLibArr() AS DOUBLE, start AS _UNSIGNED LONG, MaxLevel AS _UNSIGNED LONG, order AS INTEGER)
208.     DIM parent AS _UNSIGNED LONG
209.     DIM i AS _UNSIGNED LONG
210.     SELECT CASE order
211.         CASE 1
212.             i = MaxLevel
213.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
214.             '* reached its proper node (that is, until it is greater than either
215.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
216.             DO UNTIL i = start
217.                 '* Get the subscript for the parent node.
218.                 parent = start + (i - start) \ 2
219.                 '* The value at the current node is still bigger than the value at
220.                 '* its parent node, so swap these two array elements:
221.                 IF CGSortLibArr(i) > CGSortLibArr(parent) THEN
222.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
223.                     i = parent
224.                 ELSE
225.                     '* Otherwise, the element has reached its proper place in the heap,
226.                     '* so exit this procedure:
227.                     EXIT DO
228.                 END IF
229.             LOOP
230.         CASE ELSE
231.             i = MaxLevel
232.             '* Move the value in CGSortLibArr(MaxLevel!!!) up the heap until it has
233.             '* reached its proper node (that is, until it is greater than either
234.             '* of its Child!!! nodes, or until it has reached 1, the top of the heap):
235.             DO UNTIL i = start
236.                 '* Get the subscript for the parent node.
237.                 parent = start + (i - start) \ 2
238.                 '* The value at the current node is still smaller than the value at
239.                 '* its parent node, so swap these two array elements:
240.                 IF CGSortLibArr(i) < CGSortLibArr(parent) THEN
241.                     SWAP CGSortLibArr(parent), CGSortLibArr(i)
242.                     i = parent
243.                 ELSE
244.                     '* Otherwise, the element has reached its proper place in the heap,
245.                     '* so exit this procedure:
246.                     EXIT DO
247.                 END IF
248.             LOOP
249.     END SELECT
250. END SUB
251.  

[codeguy]

There really is no point changing from long because long before you overflow the range of long numbers, you'll run out of heap space anyway, even storing _BYTE arrays. at the most, 1, MAYBE 2 GB will be in memory while the other 5 or 4 is untouched, awaiting processing. My suggestion? split whatever it is you're sorting into no more than 1 GB files and sort each individually. Then merge those files sequentially. Even optimistically, I wouldn't expect anything greater than (1/2 million BYTE-size elements/second for each GHz of CPU speed) for a generalized comparison sort. You MIGHT be lucky and get 1.5 GB/GHz this way. Yes, there are specialized sorts that can handle FAR better hourly volume, but the information you give us makes determination of a truly suitable algorithm pretty much impossible. Believe me, I know. I am among the most viewed and upvoted in Sorting algorithms on Quora, as well as a Top Writer for 2018. I don't know everything, but I am very well versed in what I do know. Please feel free to add more specifics and clarify what you really need so we can give a more satisfactory answer. I have only discussed POSSIBLE solutions to your problem as described as that is all the information you've given allows.

[soniaa]

The numbers I have,
is in thes style;

ARRAY     ( DIMensioned  _INTEGER64 )       -         (NO strigs)  message modificated
q1
q2
q3
....
last is q31

NO q(1) etccc

The value in those ARRAY  are in the range (1 - 8.589.934.590)

In the program these numbers they arrive not in sequence !!!  ....and I do not need to sort.

Every time in the moment I have acquire a number, I need to know if that number has already been processed;
q1 .... q31
 - IF Already processed  THEN  howmanytimesthisnumberalreadyprocessed = howmanytimesthisnumberalreadyprocessed +1
   (howmanytimesthisnumberalreadyprocessed  is in the range  0 - 255  (_UNSIGNED _BYTE)

 - IF NO Already processed  THEN  record this because is an new number
   (IF NO Already processed in this case to increase speed, it is not necessary also assign 1 at howmanytimesthisnumberalreadyprocessed)

[SMcNeill]

Easiest way in this case is a BINARY file:

DIM number AS _INTEGER64
DIM TimesProcessed AS _UNSIGNED _BYTE
OPEN "RecordCount.bin" FOR BINARY AS #1

DO
    INPUT number
    GET #1, number, TimesProcessed
    TimesProcessed = TimesProcessed + 1
    PUT #1, number, TimesProcessed
LOOP UNTIL number = -1 'or some other exit code

The above gets a number, puts it on the hard drive in a file which will be 8,589,934,590 bytes in size, and each byte will tell you how many times that number has "been processed".  (Up to a maximum of 255 times).

***********************************

Now, this method is assuming you have 8 billion records to work with.  If you have a limited dataset (the q31 almost seems to indicate there's only 31 records with values from 0 to 8.5B??), then I'd build an index, store the value and count, and keep it all in memory for speed and efficiency.

But, since it seems like you're going to process billions of records (2 years to run), saving the results in a file seems to me to be the best way to do this.
   

[soniaa]

the strategies I tried are the following:

strategy1;
create file.txt  for any number that the program create
into this .txt file write howmanytimesthisnumberalreadyprocessed
To do this I do;
 - IF _FILEEXISTS  (if 0 is an new number , if -1 no new number)
 - OPEN FOR APPEND  (if no exist this procedure create the file)
 - WRITE  1  (append new line in .txt file contain "1"   -  it can also be good in this way)
 - CLOSE

strategy2;
DIM Array(1 to 8589934590) AS _UNSIGNED _BYTE
 - IF Array(mynuber) = 0  THEN  GOTO ......
 - IF Array(mynuber) = >0  THEN  Array(mynuber)  =  Array(mynuber)  +1

strategy3;
OPEN "c.dat" FOR BINARY AS #1
GET #1  ,   mynumber  ,   howmanytimesthisnumberalreadyprocessed

 - IF   howmanytimesthisnumberalreadyprocessed  >  0  THEN     PUT #1  ,  mynumber  ,  howmanytimesthisnumberalreadyprocessed  + 1 :GOTO...

 - PUT #1  ,  mynumber  ,  1

[SMcNeill]

Strategy 3 doesn't even require an IF; just an increment since 0 + 1 = 1

Get #1, number, TimesProcessed
TimesProcessed = TimesProcessed + 1
Put #1, number, TimesProcessed

Logically, if the value is 0, it's going to increment to 1 when you do the math.

[TempodiBasic]

Hi guys /Ciao ragazzi
Hi Soniaa/Ciao Soniaa
welcome into the bilingual post /benvenuta nel post bilingue

1. it seems that you must calculate frequency of a number in a gigasize array of data ranging as you post
/1. sembra che tu debba calcolare la frequenza di un numero in un array delle dimensioni di GIGA di dati con un range di valori che hai messaggiato

The numbers I have,
is in thes style;

ARRAY  ( DIMensioned  _INTEGER64 )         -         (NO strigs)  message modificated
q1
q2
q3
....
last is q31

NO q(1) etccc

The value in those ARRAY  are in the range (1 - 8.589.934.590)  ( _INTEGER64 )

my question;
in the program I'm making, I estimated that the processing process is 2 years.
I have to adopt more strategies to get the maximum speed.

In some phases of the program, I have numbers in the range (1 to 8.589.934.591) (33bit)
NOT all numbers in the range, ONLY 20%.

I have to check if the number I'm processing has already been processed and how many times.

2.about https://www.qb64.org/forum/index.php?topic=705.msg5867#msg5867
 if you are not able to speak ItalianEnglish please help yourself with Google Translator, it is better than nothing! Moreover you can break the language barrier and you can get more from help of great coders like those are answering to you (except me I am coder as hobby)
/2. riguardo a https://www.qb64.org/forum/index.php?topic=705.msg5867#msg5867
se non sai parlare l'IngleseItalianizzato, prego aiutati con Google Translator, è meglio di niente! Inoltre puoi infrangere la barriera del linguaggio e puoi ottenere di più dall'aiuto di grandi programmatori come quelli che ti stanno rispondendo (eccetto me che sono programmatore per hobby)

3. about this

(howmanytimesthisnumberalreadyprocessed  is in the range  0 - 255  (_UNSIGNED _BYTE)

my questions to understand better (you are talking about processing for at least 2 years, an error should waste much time!):
  3.1 how can you say surely that the frequency cannot be more than 255?
  3.2 must  the numbers that are in the range (1 - 8.589.934.590) and that are not acquired,  be registered as 0 frequency?
/3. circa questo 

(howmanytimesthisnumberalreadyprocessed  is in the range  0 - 255  (_UNSIGNED _BYTE)

le mie domande per capire meglio (stai parlado di processare per almeno 2 anni, un errore sprecherebbe molto tempo!):
  3.1 come puoi dire sicuramente che la frequenza non può essere maggiore di 255?
  3.2 i numeri che sono nel range  (1 - 8.589.934.590) e che non sono acquisiti devono essere registrati con frequenza 0?

4. about ARRAY

ARRAY     ( DIMensioned  _INTEGER64 )       -         (NO strigs)  message modificated
q1
q2
q3
....
last is q31

NO q(1) etccc

Every time in the moment I have acquire a number, I need to know if that number has already been processed;
q1 .... q31
 - IF Already processed  THEN  howmanytimesthisnumberalreadyprocessed = howmanytimesthisnumberalreadyprocessed +1
   (howmanytimesthisnumberalreadyprocessed  is in the range  0 - 255  (_UNSIGNED _BYTE)

 - IF NO Already processed  THEN  record this because is an new number
   (IF NO Already processed in this case to increase speed, it is not necessary also assign 1 at howmanytimesthisnumberalreadyprocessed)

are you sure that this is an array? You talk of array q1 q2 q3  until q31 and not q(1) q(2).... It seems to me that this is a packed field data to manage by UDT
4.1 How can you distinguish among q1 q2 q3 ..q31 of the array in the acquiring phase of data? Or do you acquire a single number of large range?
4.2 How do you know that you can have only q31 number to process and to count the frequency?

/4. riguardo al tuo ARRAY
sei sicura che questo sia un array?  lo definisci composto da q31 elementi da q1 a q31 ma non tipo q(1) q(2)...q(31)
mi sembra che questo sia più un gruppo di dati compressi da gestire tramite UDT.
 4.1 Come puoi distinguere tra q1 q2 q3...q31 dell'array nella fase di acquisizione dei dati? Oppure tu acquisci un singolo numero di ampio range?
4.2 Come fai a sapere che tu puoi avere solo q31 numeri da processare e di cui contare la frequenza?

5. can you be clearer using a pseudocode with large chunks? i.e 

acquiring a large number ranging from 1 to 8.......  -> record it in a list of processed number -> count how many times it has been processed

/5. puoi essere più chiara usando pseudocodice a grandi blocchi_operazioni? per esempio

acquisire un grande numero nel range da 1 to 8...... -> registrare il numero in una lista di numeri processati -> contare quante volte esso sia stato processato

Thanks to read
/Grazie per la lettura

[soniaa]

Thanks for all reply;
I do not care about ordering the numbers.

in reply to;

SMcNeill;
the IF is necessary fom my because;
 - if GET acquisition >1  THEN  put value +1   AND  goto  inaditection
 - else   PUT  value  1  AND  goto otherdirection

 TempodiBasic;
3.1 -  its max 255
3.2 -  it is not necessary
4.1 -  I have write a program in mode for no use q(1) because using this have lowww performance,  q1 is moooore fasttt
4.2 -  the program loop in 31 step  forward and back billions of times  (brute force)
5.0 -  ?????

[soniaa]

The numbers generated by the array   q1   q2  .... q31    they can be  stored together in an singe  registry,
but in some way they must be associated with  howmanytimesalreadyprocessed (range 1 - 255 )

the registry  it must not have  references  of  the  number  has arrived by q1 or q2...

[SMcNeill]

SMcNeill;
the IF is necessary fom my because;
 - if GET acquisition >1  THEN  put value +1   AND  goto  inaditection
 - else   PUT  value  1  AND  goto otherdirection

The IF action is independent of the GET/ PUT action.

Get #1, number, TimesProcessed
TimesProcessed = TimesProcessed + 1
Put #1, number, TimesProcessed
IF TimesProcessed = 1 THEN GOTO inaditection ELSE GOTO otherdirection

[soniaa]

SMcNeill;
the IF is necessary fom my because;
 - if GET acquisition >1  THEN  put value +1   AND  goto  inaditection
 - else   PUT  value  1  AND  goto otherdirection

The IF action is independent of the GET/ PUT action.

Get #1, number, TimesProcessed
TimesProcessed = TimesProcessed + 1
Put #1, number, TimesProcessed
IF TimesProcessed = 1 THEN GOTO inaditection ELSE GOTO otherdirection

****what you wrote  is exactly the same as what I wrote !!??...
...or no?

[SMcNeill]

Here's a real world implementation of how I'd handle this problem:

Code: QB64: [Select]

1. DIM q AS _INTEGER64
2. DIM TimesProcessed AS _UNSIGNED _BYTE
3.  
4. RANDOMIZE TIMER
5.  
6. PRINT "Clearing and Opening Multiple files.  This will take a few seconds."
7. FOR i = 0 TO 8589 'multiple files to hold our values, since we have such a large range for output
8.     file$ = "FileCounter" + LTRIM$(RTRIM$(STR$(i))) + ".bin"
9.     OPEN file$ FOR OUTPUT AS #i + 1: CLOSE #i + 1 'blank the file if it exists
10.     OPEN file$ FOR BINARY AS #i + 1 'open a new file to track values
11. NEXT
12.  
13. Limit = 100 'The number of values we're going to process (times 31, since you have values from q1 to q33)
14.  
15.  
16. StartTime## = TIMER
17. FOR i = 1 TO Limit
18.     FOR j = 1 TO 31 '31 times since the values are for q1 to q31
19.         q = INT(RND * 8589934590)
20.         FileNumber = q \ 1000000
21.         ValueStored = q MOD 1000000
22.         GET #FileNumber + 1, ValueStored, TimesProcessed
23.         TimesProcessed = TimesProcessed + 1
24.         PUT #FileNumber + 1, ValueStored, TimesProcessed
25.         IF TimesProcessed = 1 THEN PRINT "New Entry", ELSE PRINT "Processed"; TimesProcessed; " already",
26.     NEXT
27. NEXT
28. CLOSE 'close all files
29. PRINT
30. FinishTime## = TIMER - StartTime##
31.  
32. PRINT USING "#####.##### seconds to process 31 numbers, ### times."; FinishTime##, Limit
33.  
34. PRINT
35. PRINT
36. PRINT "Clean Up the Disk?  (Y/N)"
37. DO
38.     _LIMIT 30
39.     i$ = UCASE$(INKEY$)
40. LOOP UNTIL i$ = "Y" OR i$ = "N"
41.  
42. IF i$ = "Y" THEN
43.     PRINT
44.     PRINT "Cleaning disk... This too may take several seconds."
45.     FOR i = 0 TO 8589 'multiple files to hold our values, since we have such a large range for output
46.         file$ = "FileCounter" + LTRIM$(RTRIM$(STR$(i))) + ".bin"
47.         KILL file$
48.     NEXT
49. END IF
50. SYSTEM
51.  

Now, a few things to note:

1) Notice that I've broken my data down to 1MB files?  This is because it's much faster for the drive to reserve space for a new file that's 1MB in size, than it is to do the same for one that's 8GB in size.  In fact, it's a lot faster to create almost 9000 1MB files, than it is for my drive to create and reserve space for a single 8GB one.  Play around with the values if you want and see how the speed is affected...

2) It still takes me about 40 seconds to process 100 sets of numbers, using this method -- but that's the hit you're going to get for having and using so much file access.  Times will probably be much better on your SSD than it is on my old one here, but it's still doing to be a lot slower than running some sort of counter in memory.

3) You've never told us what the MAXIMUM AMOUNT OF DATA NEEDS TO BE PROCESSED.  If there's less than a million total records, I'd use an index to see what values have appeared, increment them, and keep the whole process in memory.  You've told us that there's 31 values, ranging from 0 to 8.5B, but you haven't mentioned how many times you're going to repeat this process.  If there's 31 total values, there's absolutely no reason to use file access to track number of times a value is processed.  I'd only go the file route, like above, if it was a process which I had to repeat billions of times for those q1 to q31 numbers.  (And how can you be certain that they're only going to occur less than 255 times total, if there's billions of times of them being processed?)

From what you've said, the above is the best way I can think of the deal with the problem you've presented: tracking a counter of a limitless number of passes, of 31 values, which range from 0 to 8GB...  If what you need ISN'T for a limitless number of passes, then give us an idea of the max number of passes which are used with your data.  There's MUCH better ways to deal with the issue, with smaller datasets.

[soniaa]

I repeat;
The number I want stored for compare are in the range 0  to 33bit.
No all number in the range the program create, only approximately 20 -30 %.
The program create these number billion of time.
Every when a program create an number I have to know if that number is already processed, then store how many times.
thats is all,
no other.

I think the solutions OPEN c.dat for binary is for the moment the best I try.
If you have other solution muck speed write to me.

[TempodiBasic]

@soniaa

I can't imagine how to structure a program to do what you are talking about!
so I read again your requests in this thread:

the first:

I have 8.000.000.000 of items,
the value of any ia is max 100
I want create:
Dim q(8000000000) as _byte
BUT THES Produce error

in my TOSHIBA i3 8GB di ram it gives me Out of memory error on compiling

the second:

I have a goog idea;
Many of my data is value 0
i can no create array for this,
in thes mode the array I want to DIM are approximately 3.000.000.000
Now BIG Problem;
I want put my data into the arrays one by one,
example:
visitornumber1000000000 = 5
visitornumber2000000000 = 7
I do;
DIM a(1000000000 to 1000000000) as _BYTE
a(1000000000) = 5

but why do you create an array made by one single element with index 1000000000?

the third:

I have test this;
1  REM $DYNAMIC 
2  DIM a(1000000000 to 1000000000) as _BYTE
3  a(1000000000) = 5
4  REDIM _PRESERVE a(2000000000 to 2000000000)
But receive error

I cannot agree.
If I copy and paste this your code in QB64 ide I get compiling no error!
But we must observe that there is a logic error...the array a() as _BYTE on linecode 2 and the array a () on linecode 4 are not the same array, the first is of type _BYTE while the second is of type SINGLE....
moreover also if I add as _BYTE at the end of linecode 4 it runs ok in QB64.

the fourth

In some phases of the program, I have numbers in the range (1 to 8.589.934.591) (33bit)
NOT all numbers in the range, ONLY 20%.

I have to check if the number I'm processing has already been processed and how many times.

How many numbers? the only 20% of how many? We must process only 20% of numbers because only they are in the range.
We must record what number and how many times has been precessed. But the 20% of infinite is infinite! :-)
How can you be specific about number of number to process?

the fifth

The numbers I have,
is in thes style;

ARRAY  ( DIMensioned  _INTEGER64 )         -         (NO strigs)  message modificated
q1
q2
q3
....
last is q31

NO q(1) etccc

The value in those ARRAY  are in the range (1 - 8.589.934.590)  ( _INTEGER64 )

Here you decide to use 31 variables _INTEGER64. Why you do not say!

the sixth:

In the program these numbers they arrive not in sequence !!!  ....and I do not need to sort.

Every time in the moment I have acquire a number, I need to know if that number has already been processed;
q1 .... q31

Again how many numbers we do not know! Why do you use a cluster of 31 variable of _INTEGER64?

the seventh

strategy1;
create file.txt  for any number that the program create
into this .txt file write howmanytimesthisnumberalreadyprocessed
To do this I do;
 - IF _FILEEXISTS  (if 0 is an new number , if -1 no new number)
 - OPEN FOR APPEND  (if no exist this procedure create the file)
 - WRITE  1  (append new line in .txt file contain "1"   -  it can also be good in this way)
 - CLOSE

IMHO file/disk access is slower than RAM access... also if you can optimize this strategy above showed

the eighth

strategy2;
DIM Array(1 to 8589934590) AS _UNSIGNED _BYTE
 - IF Array(mynuber) = 0  THEN  GOTO ......
 - IF Array(mynuber) = >0  THEN  Array(mynuber)  =  Array(mynuber)  +1

this strategy can work if you have enough RAM but so you have already solved the issue

the nineth

strategy3;
OPEN "c.dat" FOR BINARY AS #1
GET #1  ,   mynumber  ,   howmanytimesthisnumberalreadyprocessed

 - IF   howmanytimesthisnumberalreadyprocessed  >  0  THEN     PUT #1  ,  mynumber  ,  howmanytimesthisnumberalreadyprocessed  + 1 :GOTO...

 - PUT #1  ,  mynumber  ,  1

IMHO an access to file/disk in bynary mode should be faster than to txt files but again slower to RAM access.

the tenth

the program loop in 31 step  forward and back billions of times  (brute force)

Here I ask "Why a loop in 31 steps and not 31 times a loop of a single step as all 31 variable are _INTEGER64?

the eleventh

The numbers generated by the array   q1   q2  .... q31    they can be  stored together in an singe  registry,
but in some way they must be associated with  howmanytimesalreadyprocessed (range 1 - 255 )

a simple UDT  can do this:

Code: QB64: [Select]

1. TYPE q31
2.     HowMany AS _UNSIGNED _BYTE
3.     q AS _INTEGER64
4. END TYPE

each variable of this type uses 9 byte of RAM (8 for _INTEGER64 and 1 for _BYTE) using this structure you can save/load from file/disk each variable with one access and the first byte is byself loaded in howmany and the last 8 bytes in q that record the value of number.

the twelveth

The number I want stored for compare are in the range 0  to 33bit.
No all number in the range the program create, only approximately 20 -30 %.
The program create these number billion of time.
Every when a program create an number I have to know if that number is already processed, then store how many times.
thats is all,

the other 80-70% of numbers generated by program are <1 and > 8.589.934.590
you process only numbers in the range 1--8.589.934.590 and you rate the frequency....
well the 31 variables _INTEGER64 seems only an your choice in projecting the program...
now I can create a right generator of numbers to emulate your issue and show how is my solution!

Perchè non ti aiuti con il traduttore di Google o Reverso, non è il massimo ma almeno costruisci la frase in inglese più correttamente.
Non tutti i membri di questo forum sono inglesi o americani.

Good Coding