# How can I make this more elegant/performant?

**URL:** <https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797>\
**Category:** General Usage\
**Tags:** performance\
**Created:** [December 30, 2019, 1:53pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797 "2019-12-30T13:53:02Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [December 30, 2019, 1:53pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/1 "2019-12-30T13:53:03Z")

</div>

Based on past experience, I have a feeling that I’ve horrendously over-engineered a solution to what seems like a simple problem. I have a vector of codes (numbers represented as strings) that I need to ‘collapse’ down. For example, given the following vector:

```julia
codes = ["11", "13", "112", "11213", "113", "213", "21345", "21376", "7567", "75679"]

```

The function should produce this result:

```julia
["11", "13", "213", "7567"]

```

Basically, it should find the shortest codes in the vector and then see if there are any other codes that start with the same and eliminate them. So “112”, “11213”, and “113” all fall under the “11” category and, as such, should be removed from the vector. “21345” and “21376” fall under the “213” category so they should be removed, and so on.

The Frankenstein recursive function that I’ve written to do this looks like this:

```julia
function collapsecodes(v::Vector{String}, minlength::Int = 0)
    m = minlength == 0 ? minimum(length.(v)) : minlength
    s = filter(x -> length(x) == m, v)
    diff = setdiff(v, s)
    c = vcat([filter(x -> length(x) >= m && x[1:m] == s[i], diff) for i in 1:length(s)]...)
    a = setdiff(v, c)
    return length(setdiff(v, a)) == 0 ? a : collapsecodes(a, m+1)
end

# REPL

julia> @time collapsecodes(codes)
  0.085379 seconds (167.69 k allocations: 7.989 MiB)
4-element Array{String,1}:
 "11"
 "13"
 "213"
 "7567"

```

I have a feeling one of you amazing Julians can put together a solution that is 10 times more elegant and 10 times more performant 😜

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 30, 2019, 2:32pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/2 "2019-12-30T14:32:41Z")

</div>

i don’t know if its faster but I’m sure is shorter:

```julia
codes = ["11", "13", "112", "11213", "113", "213", "21345", "21376", "7567", "75679"]
function collapsecodes2(codes::Vector{String}) #out of place,creates a new vector
    _codes = sort(codes)  
    min_len = minimum(length,_codes) #using first argument as a function
    return min_codes = unique(x->first(x,min_len),_codes)
end

function collapsecodes2!(codes::Vector{String}) #inplace, modifies the input, should be faster
    sort!(codes)
    min_len = minimum(length,codes)
    return min_codes = unique!(x->first(x,min_len),codes)
end

```

benchamarking:

```julia
using BenchmarkTools
julia> @benchmark collapsecodes($codes)
BenchmarkTools.Trial:
  memory estimate: 10.56 KiB
  allocs estimate: 134
  --------------
  minimum time: 9.900 μs (0.00% GC)
  median time: 11.499 μs (0.00% GC)
  mean time: 12.470 μs (0.00% GC)
  maximum time: 60.501 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

julia> @benchmark collapsecodes2($codes)
BenchmarkTools.Trial:
  memory estimate: 944 bytes
  allocs estimate: 17
  --------------
  minimum time: 938.095 ns (0.00% GC)
  median time: 1.014 μs (0.00% GC)
  mean time: 1.232 μs (10.85% GC)
  maximum time: 355.852 μs (99.19% GC)
  --------------
  samples: 10000
  evals/sample: 21

```

EDIT: added the presorting, as suggested by @jling

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [December 30, 2019, 2:56pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/3 "2019-12-30T14:56:35Z")

</div>

Here’s a simple faster version:

```julia
julia> function collapsecodes(codes)
           "" in codes && return [""] # use the empty string as a sentinel value below
           result = copy(codes)
           sort!(result, by=length)
           for i in eachindex(result)
               for j in i + 1 : lastindex(result)
                   if !isempty(result[i]) && startswith(result[j], result[i])
                       result[j] = ""
                   end
               end
           end
           filter!(!isempty, result)
           result
       end

collapsecodes (generic function with 1 method)

julia> @btime collapsecodes(codes)
  424.985 ns (2 allocations: 240 bytes)
4-element Array{String,1}:
 "11"
 "13"
 "213"
 "7567"

```

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [December 30, 2019, 8:05pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/4 "2019-12-30T20:05:46Z")

</div>

this won’t work, the `min_len` is 2 in this example, if you swap the order or `"213", "21345",`, you will get `"21345"` because you only looking at first 2 `chars` of each string. Pre-sorting by length should fix this.

---

<div class="post-metadata">

**Author:** ![jebej](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jebej/32/1784_2.png) [@jebej](https://discourse.julialang.org/u/jebej)\
**Post date:** [December 30, 2019, 9:34pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/5 "2019-12-30T21:34:22Z")

</div>

This won’t work if you need to compare prefixes of other lengths than the minimum, e.g. if you add 214, which AFAIU should have its own category (or maybe create the 21 category, this is not clear from the question).

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [December 31, 2019, 12:30am UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/6 "2019-12-31T00:30:04Z")

</div>

@tkluck this is awesome! I’m struggling a bit to understand exactly what’s going on here though, what is the purpose of the first line: `"" in codes && return [""]`? You added the comment that the empty string is used as a sentinel value but it seems as though this line is just a check to make sure that there are no empty strings in the array that’s passed to the function…??

> e.g. if you add 214, which AFAIU should have its own category (or maybe create the 21 category, this is not clear from the question).

Nope, shouldn’t create a new category. The function should just find the ‘parent’ category, which is basically the shortest-length code. So in this case, “214” would stand alone and should be returned in the result.

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [December 31, 2019, 12:33am UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/7 "2019-12-31T00:33:11Z")

</div>

Bravo, and thanks to all of you 👏 👏 This community never ceases to amaze me 🙂

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [December 31, 2019, 8:52am UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/8 "2019-12-31T08:52:52Z")

</div>

> [@mthelm85](#):
>
> I’m struggling a bit to understand exactly what’s going on here though, what is the purpose of the first line: `"" in codes && return [""]` ? You added the comment that the empty string is used as a sentinel value but it seems as though this line is just a check to make sure that there are no empty strings in the array that’s passed to the function…??

It’s faster to do

```julia
result[j] = <sentinel>
...
filter!(!equals(<sentinel>), result)

```

than to delete eagerly

```julia
deleteat!(result, j)

```

as it avoids moving the tail elements every time. Typically, you’d use something like `nothing` as a sentinel value. In your specific case, if _any_ string is empty, it is a prefix for all others(!) and so `[""]` is the correct result. That means we can short-circuit that case and use `""` as the sentinel in other cases. It doesn’t make a big difference; just avoids some type juggling to allow `result` to also contain `nothing`. The alternative would have been something like (untested):

```julia
function collapsecodes(codes)
    result = collect(Union{eltype(codes), Nothing}, codes)
    sort!(result, by=length)
    for i in eachindex(result)
        isnothing(result[i]) && continue
        for j in i + 1 : lastindex(result)
            if startswith(result[j], result[i])
                result[j] = nothing
            end
        end
    end
    filter!(!isnothing, result)
end

```

Makes sense?

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [December 31, 2019, 12:55pm UTC](https://discourse.julialang.org/t/how-can-i-make-this-more-elegant-performant/32797/9 "2019-12-31T12:55:08Z")

</div>

Yes, thanks!