# Can this code be made faster

**URL:** <https://discourse.julialang.org/t/can-this-code-be-made-faster/44122>\
**Category:** Performance\
**Created:** [August 2, 2020, 8:11am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122 "2020-08-02T08:11:36Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 2, 2020, 8:11am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/1 "2020-08-02T08:11:36Z")

</div>

I attempted the [Advent od Code 2015 day 9](https://adventofcode.com/2015/day/9) solution in julia and here is my code for the first part (for this input 9.txt file refer to the link to the problem):

```julia
using Combinatorics, BenchmarkTools

distances = readlines("9.txt")

cities = unique!(vcat(map(string,unique!([split(dist)[1] for dist in distances])),map(string,unique!([split(dist)[3] for dist in distances]))))

function find_distance(a::String,b::String)::Int64
    for dist in distances
        if (a == split(dist)[1] && b == split(dist)[3]) || (a == split(dist)[3] && b == split(dist)[1])
            return parse(Int64,last(split(dist)))
        end
    end
end

function find_tour_length(a)::Int64
    dist = 0
    for i in 1:(length(a) - 1)        
        dist += find_distance(a[i],a[i+1])        
    end
    return dist
end

all_tours = permutations(cities)

solve() = println(minimum([find_tour_length(tour) for tour in all_tours]))
@btime solve()

```

Running this code, it takes 7.232 secs.

Can this code be made any faster?  
Thank you in advance.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [August 2, 2020, 8:34am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/2 "2020-08-02T08:34:36Z")

</div>

There is much that can be done to make it faster but what really strikes the eye is the repeated looping, splitting, and parsing done in `find_distance`. You really don’t want to be doing all that over and over again. Parsing the distances once and storing the results in a dict should give you a huge improvement to get started with.

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 2, 2020, 8:37am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/3 "2020-08-02T08:37:40Z")

</div>

Thanks a lot. I will change the code right away.  
Also, can you please tell me more on how can this code me made more faster?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 2, 2020, 11:11am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/4 "2020-08-02T11:11:55Z")

</div>

You should read the performance tips section of the manual: [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1/manual/performance-tips/index.html)

Tip number one is to avoid global variables, in particular you are reading `distances` from a global variable inside the function `find_distance`. Instead, you should pass `distances` as an input to the function.

Also avoid unnecessarily redoing the same thing over and over and over and over, as @GunnarFarneback points out.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 2, 2020, 11:20am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/5 "2020-08-02T11:20:28Z")

</div>

If you would like more help on speeding up the code, you can provide a snippet from your input text file. That would make it possible to run your code and identify speedup options.

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 2, 2020, 11:28am UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/6 "2020-08-02T11:28:25Z")

</div>

Here you go,

Tristram to AlphaCentauri = 34  
Tristram to Snowdin = 100  
Tristram to Tambi = 63  
Tristram to Faerun = 108  
Tristram to Norrath = 111  
Tristram to Straylight = 89  
Tristram to Arbre = 132  
AlphaCentauri to Snowdin = 4  
AlphaCentauri to Tambi = 79  
AlphaCentauri to Faerun = 44  
AlphaCentauri to Norrath = 147  
AlphaCentauri to Straylight = 133  
AlphaCentauri to Arbre = 74  
Snowdin to Tambi = 105  
Snowdin to Faerun = 95  
Snowdin to Norrath = 48  
Snowdin to Straylight = 88  
Snowdin to Arbre = 7  
Tambi to Faerun = 68  
Tambi to Norrath = 134  
Tambi to Straylight = 107  
Tambi to Arbre = 40  
Faerun to Norrath = 11  
Faerun to Straylight = 66  
Faerun to Arbre = 144  
Norrath to Straylight = 115  
Norrath to Arbre = 135  
Straylight to Arbre = 127

This is the entire text file.

---

<div class="post-metadata">

**Author:** ![anon37204545](https://avatars.discourse-cdn.com/v4/letter/a/439d5e/32.png) [@anon37204545](https://discourse.julialang.org/u/anon37204545)\
**Post date:** [August 2, 2020, 12:24pm UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/7 "2020-08-02T12:24:10Z")

</div>

```julia
using Combinatorics, BenchmarkTools

const distances = split.(readlines("9.txt"))
const cities = unique(
    vcat(map(x -> getindex(x, [1, 3]), distances)...)
)

function find_distance(a::AbstractString, b::AbstractString)::Int64
    for dist in distances
        if (a == dist[1] && b == dist[3]) || (a == dist[3] && b == dist[1])
            return parse(Int64,last(dist))
        end
    end
end

function find_tour_length(a)::Int64
    dist = 0
    for i in 1:(length(a) - 1)
        dist += find_distance(a[i], a[i+1])
    end
    return dist
end

const all_tours = permutations(cities)

solve() = println(minimum(find_tour_length, all_tours))
@btime solve()

```

Before:

```julia
  8.306 s (145555211 allocations: 5.61 GiB)

```

After:

```julia
 60.115 ms (201607 allocations: 14.77 MiB)

```

I get the same result, i.e. 251. Are you satisfied with the answer? 😄

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 2, 2020, 1:45pm UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/8 "2020-08-02T13:45:51Z")

</div>

Wow!  
Thank you so much 😊😊.  
Also, was my code consuming 5.7GB of space earlier and now it is consuming 14MB?  
If yes, then why was it consuming so much memory?

---

<div class="post-metadata">

**Author:** ![anon37204545](https://avatars.discourse-cdn.com/v4/letter/a/439d5e/32.png) [@anon37204545](https://discourse.julialang.org/u/anon37204545)\
**Post date:** [August 2, 2020, 4:45pm UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/9 "2020-08-02T16:45:49Z")

</div>

1. The major thing to do is `split.` the `distances` on the beginning and use `dist` instead of `split(dist)` in every instance after. That way you avoid doing a costy operation of splitting a string repeatedly.  
Doing that gets the performance to `867.532 ms (22639690 allocations: 979.76 MiB)`.

2. Passing a function to run while finding a minimum, as in `minimum(find_tour_length, all_tours))` loops the array only once (to apply the function and compare the values at the same time), instead of twice, to apply the function, and then compare.

3. Some optimizations help to unclutter the loops in `cities`. You don’t need to `map(string, ...)` (i.e. convert to type `String`) because without it you get type `SubString`, which is basically just a string. The problem was that you set `find_distance`’s argument types to `String` instead of `AbstractString`, which would accept both `String` and `SubString`.

You can even drop `::Int64` for function’s return argument, since compiler deduces that automatically.

I don’t understand completely how the memory management works in Julia, so someone else probably can explain better why is my code so memory-efficient.

If I solved your issue, you can also mark my post as “Solution”, so other people with similar problem can find it more easily.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 2, 2020, 4:58pm UTC](https://discourse.julialang.org/t/can-this-code-be-made-faster/44122/10 "2020-08-02T16:58:45Z")

</div>

The reason for the difference in memory allocation is that prior to 1.5 (which will be out very soon) each `SubString` requires allocating an object. Each object is very small (probably around 24 bytes), but you were creating about 100 million of these objects.