# Unique! and sorted collections

**URL:** <https://discourse.julialang.org/t/unique-and-sorted-collections/16352>\
**Category:** General Usage\
**Created:** [October 15, 2018, 4:31pm UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352 "2018-10-15T16:31:35Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [October 15, 2018, 4:31pm UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/1 "2018-10-15T16:31:36Z")

</div>

Consider

```julia
a = rand(1:10_000_000, 100_000_000)
b = sort(a)
c = copy(a)

```

`unique!(c)` takes 6.79s.  
`unique!(b)` takes 0.35s.

However, it seems to me that `unique!` does an `issorted` first. If we call `_groupedunique!` first, we save the O(n) (worst case, which is what happens when you’re checking a sorted list) check of `issorted()` and get 0.28s.

Is there a reason that there isn’t an exported `uniquesorted!()` (or equivalent) function that bypasses the `issorted()` check when we know that the vector is already sorted?

---

<div class="post-metadata">

**Author:** ![adamslc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adamslc/32/3452_2.png) [@adamslc](https://discourse.julialang.org/u/adamslc)\
**Post date:** [October 15, 2018, 5:52pm UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/2 "2018-10-15T17:52:06Z")

</div>

I can’t imagine why adding the keyword argument `sorted` to `unique!` in 1.1 would be objectionable…

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [October 16, 2018, 12:48am UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/3 "2018-10-16T00:48:27Z")

</div>

Also it would be good to allow metadata to stored with the vector. Eg. Sorted

---

<div class="post-metadata">

**Author:** ![adamslc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adamslc/32/3452_2.png) [@adamslc](https://discourse.julialang.org/u/adamslc)\
**Post date:** [October 16, 2018, 5:29am UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/4 "2018-10-16T05:29:39Z")

</div>

The issue with that approach is that the metadata would probably be encoded as a type. For example, a `SortedVector{Int64}`, which would allow `unique!` and friends to dispatch on this extra information and reap the performance benefits.  
However, if some function overly restricted its input type, for instance `Vector{T} where T <: Number`, then the `SortedVector` wouldn’t work at all!  
For a real life example of this, look at the Linear Algebra code in Base. There has been a huge proliferation of new types to describe different properties of matrices. When this information is used to dispatch to optimized methods, there is a huge performance payoff, but if a method is missing, then the calculations resort to slow fallback methods. Adding all of the appropriate methods continues to be a big challenge.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [October 16, 2018, 5:50am UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/5 "2018-10-16T05:50:48Z")

</div>

This is where traits can help.

---

<div class="post-metadata">

**Author:** ![laborg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laborg/32/5474_2.png) [@laborg](https://discourse.julialang.org/u/laborg)\
**Post date:** [October 16, 2018, 6:12am UTC](https://discourse.julialang.org/t/unique-and-sorted-collections/16352/6 "2018-10-16T06:12:48Z")

</div>

It would only be not objectionable if `sorted` would be a keyword hint to skip the `issorted` check, but not to let it choose if the sorting check is done at all, because this would introduce regressions. I’m undecided if the use case is there in real life (e.g. the `unique` versions that take a function as argument have bugs and nobody has noticed them yet, where i feel, that it’s just not used that often).

In my PR: [RFC: Implement unique consistently by laborg · Pull Request #29038 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/29038) where I tried to improve the performance of all `unique[!]([f])` functions I’ve already added a issorted argument to the internal implementation, that could easily be made a key word argument for the external function.