Julia: implement unique!

[StefanKarpinski]

We have a unique function that produces a new collection similar to its argument, but with each item only occurring once (in order of first appearance). There should be a corresponding unique! function that removes recurrences of items and returns this modified collection. Note that for performance, at least on dense arrays, resizing of the array should only occur at end when you know the final size to shrink the array to. Part of #20402.

[kvmanohar22]

I don't understand by ...removing recurrences of items... , what is the additional functionality that would be incorporated in unique! function, could you please provide a small example ?

[ararslan]

@kvmanohar22

julia> x = [2, 2, 3, 1, 2, 3, 1];

julia> unique(x) # Retrieves unique elements without modifying x
3-element Array{Int64,1}:
 2
 3
 1

julia> unique!(x) # Modifies x to only contain its unique elements in order of occurrence
3-element Array{Int64,1}:
 2
 3
 1

julia> x # Proof that x has been modified
3-element Array{Int64,1}:
 2
 3
 1

[kvmanohar22]

I would like to implement this.
Would this be a good approach ?

function unique!(itr)
a= _default_eltype(typeof(itr))[]

# check if `val` is present in `a` if not append it 
push!(a, val)

# finally
return a

[ararslan]

That's a start, but notice that itr has not been modified in place in your code. I recommend taking a look at how unique is implemented and basing your approach off of that. Do note though that while unique can accept any iterable, unique! can only accept mutable iterables, otherwise the input won't (or rather _can't_) be modified in place.

One possible approach (probably not the best) would be to locate the indices in the input which contain duplicated elements, then just call deleteat!.

[kvmanohar22]

How about we sort the given iterable in place and remove the duplicates ?
Something like this...

function unique!(itr)
# sort `itr`
sort!(itr)

# remove duplicates
for i=1:length(itr)-1
   if i<length(itr)
      if itr[i]==itr[i+1]
         deleteat!(itr, i)
      end
   end
end

return itr

[ararslan]

The problem with sorting is that you lose the order of occurrence. Notice in my example above that unique(x) == [2, 3, 1]; with your proposal, unique!(x) would turn x into [1, 2, 3].

A very naive way to do it, posting here solely for the sake of example, would be

function unique!(itr)
    seen = Set{eltype(itr)}()
    for (i, x) in enumerate(itr)
        if x in seen
            # If x has already been encountered in itr, remove it
            deleteat!(itr, i)
        else
            # Otherwise note that we've encountered it
            push!(seen, x)
        end
    end
    return itr
end

Does that approach make sense? This is somewhat similar to how unique is currently implemented. As I said, I recommend taking a look at the code for unique to get a feel for how to efficiently approach the problem.

[fredrikekre]

The implementation above will give BoundsError since the itr will be shortened inside the loop.

julia> A = [1, 2, 1];

julia> unique!(A)
ERROR: BoundsError: attempt to access 2-element Array{Int64,1} at index [4]
 in next at ./iterator.jl:48 [inlined]
 in unique!(::Array{Int64,1}) at ./REPL[23]:3

I think the indices of the duplicates should be stored somehow and then the itr should be resized only once after the loop. Ref original post:

resizing of the array should only occur at end when you know the final size to shrink the array to

[kvmanohar22]

@fredrikekre to avoid BoundsError, I have put the condition on index, the first if condition makes sure that there is no BoundsError

[fredrikekre]

Feel free to open a work in progress PR, then its easier for people to comment on your implementation :)