## Remove elements repeted

General FreeBASIC programming questions.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Remove elements repeted

Hi!

Code: Select all

`'lrcvs 01.11.17'Program to eliminate repeated elements in an array.'1) we sort the initial array, using quicksort.'2) we remove the repeated elements. '3) skipping the ones that are the same and reducing the time of "cleaning the repeated elements".DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)DIM AS INTEGER c,f,k,n,xCLSx = 3000000 '<<< elementsDIM s (x)AS INTEGERDIM t (x)AS INTEGERRANDOMIZE, 3FOR n = 1 TO x    s(n) = INT(RND * x) + 1NEXT nPRINT "Init array of "; x; " elements, some repeated"ordenar2 (s(),1,x)  '<<< quicksort'******************************************************************************'Here remove elements repetedf = 1c = 1WHILE f <= x    k = 0    IF s(f) = s(f + 1)  THEN        k = 1        f = f + 1    ELSE        t(c) = s(f)        f = f + 1        c = c + 1    END IFWEND'******************************************************************************PRINTPRINT "here are ";c-1;" unique elements"PRINTPRINT "end"SLEEPENDSUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)    'quick sort    DIM AS INTEGER i,j,y    i = inicio    j = final    y = s((INT(i + j) / 2))    WHILE i < j        WHILE s(i) < y            i = i + 1        WEND        WHILE s(j) > y            j = j - 1        WEND        IF i <= j THEN            SWAP s(i), s(j)            i = i + 1            j = j - 1        END IF    WEND    IF j > inicio THEN ordenar2(s(),inicio,j)    IF i < final THEN ordenar2(s(),i,final)    END SUB`

Regards
integer
Posts: 393
Joined: Feb 01, 2007 16:54
Location: usa

### Re: Remove elements repeted

This is not clear.
k is set & cleared but not used after exit.

Code: Select all

`'Here remove elements repetedf = 1c = 1WHILE f <= x    k = 0    IF s(f) = s(f + 1)  THEN        k = 1        f = f + 1    ELSE        t(c) = s(f)        f = f + 1        c = c + 1    END IFWEND`

IF the original array with the duplicates is no longer needed,
this what I would do AFTER the array is sorted in ascending order:

Code: Select all

`f = 1 for c = 2 to x   IF s(f) < s(c)  THEN f += 1 : s(f) = s(c)next c `
sancho3
Posts: 358
Joined: Sep 30, 2017 3:22

### Re: Remove elements repeted

@ircvs
There is an error in your code
Out of bounds array access on line 35.

when f = x the if statement checks s(f + 1) and f + 1 is beyond the upper boundary of s().

Code: Select all

`WHILE f <= x    k = 0          IF s(f) = s(f + 1)  THEN        k = 1        f = f + 1`
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi, all!

Thanks to both of you.
I change the lines of code that you indicate to me.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi

The program does not indicate an error.

Code: Select all

`'lrcvs 01.10.17'Program to eliminate repeated elements in an array.'1) we sort the initial array, using quicksort.'2) we remove the repeated elements, skipping the ones that are the same'and reducing the time of "cleaning the repeated elements".DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)DIM AS INTEGER c,f,k,n,xCLSx = 20 '<<< elements     'x = number of array elementsDIM s (x)AS INTEGER     '<<< This is the main arrayDIM t (x)AS INTEGER     ''<<< This is the auxiliary arrayRANDOMIZE, 3FOR n = 1 TO x    s(n) = INT(RND * x) + 1     'Here we write the values in the main array    print s(n);" ";                  'show elements of auxiliary arrayNEXT nprintPRINT "Init array of "; x; " elements, some repeated"printordenar2 (s(),1,x)            'sort the elements'******************************************************************************'Remove elements repetedf = 1       'f = counter for the main arrayc = 0       'c = counter for the auxiliary arrayWHILE f <= x    k = 0   'k = control flag       'Here we compare an element of the main array with the following of the main array 'comparing them, if they are equal, the counter (f) of the main array advances one step, and so on'else comparing them, if they are different, we add the element of the main array to the auxiliary array and increase "c" and 'advance the main counter (f)'the process is repeated until the end of the main array        IF s(f) = s(f + 1)  THEN        k = 1        f = f + 1    ELSE        c = c + 1                t(c) = s(f)        f = f + 1    END IFWEND'******************************************************************************'show elements of auxiliary arrayfor n = 1 to c    print t(n);" "; next nPRINTPRINT "There are ";c;" unique elements"PRINTPRINT "end"SLEEPEND'******************************************************************************SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)    'quick sort    DIM AS INTEGER i,j,y    i = inicio    j = final    y = s((INT(i + j) / 2))    WHILE i < j        WHILE s(i) < y            i = i + 1        WEND        WHILE s(j) > y            j = j - 1        WEND        IF i <= j THEN            SWAP s(i), s(j)            i = i + 1            j = j - 1        END IF    WEND    IF j > inicio THEN ordenar2(s(),inicio,j)    IF i < final THEN ordenar2(s(),i,final)    END SUB`
sancho3
Posts: 358
Joined: Sep 30, 2017 3:22

### Re: Remove elements repeted

That is why FXM always maintains that you compile with -exx.
Yes it does report an error. Out of bounds.
And it is an obvious one. s() is an array with upper bound of x. You loop until f is less than or equal to x. When f = x you then check in the if statement f+1 which will be 30000001. That is out of bounds.

In the latest code, the error is now on line 45.

Perhaps you can try

Code: Select all

`WHILE f < x`

If you don't compile with -exx FB does not do bounds checking.
So test it like this and you will see that without -exx it still reports no errors despite being obviously out of bounds

Code: Select all

`WHILE f < x + 9`

or even this to make it more obvious

Code: Select all

`print s(ubound(s) + 1)`
fxm
Posts: 10258
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Remove elements repeted

sancho3 wrote:That is why FXM always maintains that you compile with -exx.

Yes, at least during the debugging phase.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi,

Sorry for the delay in responding.

Well, I work with this:
FB IDE See 0.4.6, February 19, 2006, wxwidgets 2.2.2

And with this editor, the program does not indicate error.

Here you have a sample:

13 10 18 18 16 3 20 7 3 17 13 14 16 8 19 14 8 13 8 13
Init array of 20 elements, some repeated

3 7 8 10 13 14 16 17 18 19 20
There are 11 unique elements

end

*******************************************************************
Other:

105 9 40 146 189 159 24 188 116 56 200 73 114 168 184 169 179 167 109 123 132 121 80 174 144 158 1
86 174 95 118 30 151 196 156 41 87 39 169 111 75 77 40 81 23 39 48 157 80 192 152 40 118 109 150
20 47 77 77 123 198 194 104 165 161 76 40 20 171 130 68 165 143 134 70 79 14 128 98 122 156 199 11
131 49 49 136 137 196 18 168 183 124 12 87 198 91 114 183 138 72 72 60 127 199 97 101 55 138 149
16 10 188 149 107 178 192 26 107 193 18 119 163 175 6 122 91 53 18 198 124 24 88 141 128 185 186
129 96 27 2 103 64 195 160 52 6 87 124 67 36 61 39 160 169 25 80 199 180 114 81 99 156 43 138 9
38 125 178 15 143 70 39 105 12 128 159 180 196 158 98 88 16 30 100 169 147 193 75 62 166 200 121 1
53 10 20 190 181 146 188 76
Init array of 200 elements, some repeated

2 6 9 10 11 12 14 15 16 18 20 23 24 25 26 27 30 36 38 39 40 41 43 47 48 49 52 53 55 56 60 61
62 64 67 68 70 72 73 75 76 77 79 80 81 87 88 91 95 96 97 98 99 100 101 103 104 105 107 109 111
114 116 118 119 121 122 123 124 125 127 128 129 130 131 132 134 136 137 138 141 143 144 146 147 149
150 151 152 153 156 157 158 159 160 161 163 165 166 167 168 169 171 174 175 178 179 180 181 183 184
185 186 188 189 190 192 193 194 195 196 198 199 200
There are 124 unique elements

end

"The program work very well"

(Also for 3 million of numbers)

Regards
sancho3
Posts: 358
Joined: Sep 30, 2017 3:22

### Re: Remove elements repeted

snip...
Compile from the command line using

Code: Select all

`fbc -exx "nameofprogram.bas"`

Then run it from the command line and see.

But really. Just debug your code and you can see that there is an error there.
Again, when f gets to 20 it comes down to the if statement and in that if statement is "s(f + 1)". f + 1 is 21 and that is out of bounds.
Last edited by sancho3 on Nov 04, 2017 1:44, edited 1 time in total.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi, sancho3:

You're right!

I have never tried "fbc -exx" xxx.bas "

and yes, it indicates the same error as you.

... but with the editor, there is no error.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi, sancho3:

... but with the editor, there is no error... and... is a good idea!

... 3.000.000 of elements <= 1 second!

Init array of 3000000 elements, some repeated

There are 1896773 unique elements

end

Regards
fxm
Posts: 10258
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Remove elements repeted

lrcvs wrote:Hi, sancho3:

You're right!

I have never tried "fbc -exx" xxx.bas "

and yes, it indicates the same error as you.

... but with the editor, there is no error.

What editor are you using?
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

### Re: Remove elements repeted

Hi

Editor Fb:

FB IDE See 0.4.6, February 19, 2006, wxwidgets 2.2.2
fxm
Posts: 10258
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Remove elements repeted

In addition to compile with the '-exx' option, and in order to can visualize the run-time error messages when running code from FBIde "Run/Quick run" command, you must configure in the "View/Settings/FreeBASIC" menu the "Run command" field as specified at:
SARG
Posts: 1240
Joined: May 27, 2005 7:15
Location: FRANCE

### Re: Remove elements repeted

To show the bug (I guess it would be hard to find as it occurs randomly)

Just add this line after the ordenar2(...) instruction : s(21)=s(20).
The last value will be lost.....

If by chance the ubound+1 value is equal to the greatest value of the array this value is removed.
In this example seems to be 0 (but could be any value)
So removing elements in an array containing values <=0 the risk is to loose the zero.

Hope it's enough clear ;-)