Remove elements repeted

[lrcvs]

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,x

CLS
x = 3000000 '<<< elements
DIM s (x)AS INTEGER
DIM t (x)AS INTEGER

RANDOMIZE, 3
FOR n = 1 TO x
    s(n) = INT(RND * x) + 1
NEXT n

PRINT "Init array of "; x; " elements, some repeated"

ordenar2 (s(),1,x)  '<<< quicksort

'******************************************************************************
'Here remove elements repeted

f = 1
c = 1
WHILE 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 IF
WEND

'******************************************************************************

PRINT
PRINT "here are ";c-1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

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


Regards

[integer]

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

Code: Select all

'Here remove elements repeted
f = 1
c = 1
WHILE 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 IF
WEND


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]

@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]

Hi, all!

Thanks to both of you.
I change the lines of code that you indicate to me.

[lrcvs]

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,x

CLS
x = 20 '<<< elements     'x = number of array elements
DIM s (x)AS INTEGER     '<<< This is the main array
DIM t (x)AS INTEGER     ''<<< This is the auxiliary array

RANDOMIZE, 3
FOR 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 array
NEXT n

print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),1,x)            'sort the elements

'******************************************************************************
'Remove elements repeted

f = 1       'f = counter for the main array
c = 0       'c = counter for the auxiliary array

WHILE 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 IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 1 to c
    print t(n);" ";
next n


PRINT
PRINT "There are ";c;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
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]

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]

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

Yes, at least during the debugging phase.

[lrcvs]

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]

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.

[lrcvs]

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]

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]

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]

Hi


Editor Fb:


FB IDE See 0.4.6, February 19, 2006, wxwidgets 2.2.2

[fxm]

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:

https://www.freebasic.net/forum/viewtopic.php?p=121731#p121731, at paragraph: "Leaving the command line window open when the program finishes"

[SARG]

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 ;-)