Re: [Gambas-user] I need a hint on how to deleted duplicate items in a array

[Tobias B. <ta...@gm...>]

On Fri, 30 Jun 2017, Gianluigi wrote:
> What was wrong in my example which meant this?
> 
> Public Sub Main()
> 
>   Dim sSort As String[] = ["A", "B", "B", "B", "C", "D", "D", "E", "E",
> "E", "E", "F"]
>   Dim s As String
> 
>   For Each s In ReturnArrays(sSort, 0)
>     Print s
>   Next
>   For Each s In ReturnArrays(sSort, -1)
>     Print s
>   Next
> 
> End
> 
> Private Function ReturnArrays(SortedArray As String[], withNumber As
> Boolean) As String[]
> 
>   Dim sSingle, sWithNumber As New String[]
>   Dim i, n As Integer
> 
>   For i = 0 To SortedArray.Max
>     ' You can avoid with Tobias's trick (For i = 1 To ...)
>     If i < SortedArray.Max Then
>       If SortedArray[i] = SortedArray[i + 1] Then
>         Inc n
>       Else
>         Inc n
>         sSingle.Push(SortedArray[i])
>         sWithNumber.Push(n & SortedArray[i])
>         n = 0
>       Endif
>     Endif
>   Next
>   Inc n
>   sSingle.Push(SortedArray[SortedArray.Max])
>   sWithNumber.Push(n & SortedArray[SortedArray.Max])
>   If withNumber Then
>     Return sWithNumber
>   Else
>     Return sSingle
>   Endif
> 
> End
> 

I wouldn't say there is anything *wrong* with it, but it also has quadratic
worst-case running time. You use String[].Push() which is just another name
for String[].Add(). Adding an element to an array (the straightforward way)
is done by extending the space of that array by one further element and
storing the value there. But extending the space of an array could potentially
require you to copy the whole array somewhere else (where you have enough
free memory at the end of the array to enlarge it). Doing worst-case analysis,
we have to assume that this bad case always occurs.

If you fill an array with n values, e.g.

  Dim a As New Integer[]
  For i = 1 To n
    a.Add(i)
  Next

then you loop n times and in the i-th iteration there will be already
i-many elements in your array. Adding one further element to it will,
in the worst case, require i copy operations to be performed. 9-year-old
C.F. Gauss will tell you that the amount of store operations is about n^2.

And your function does two jobs simultaneously but only returns the result
of one of the jobs. The output you get is only worth half the time you spent.

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk