# Matrix shortest distance problem - Need suggestions to improve the performance

**URL:** <https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175>\
**Category:** Optimization (Mathematical)\
**Tags:** array\
**Created:** [March 15, 2021, 7:35am UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175 "2021-03-15T07:35:11Z")\
**Posts on this page:** 8\
**Page:** 2

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [March 15, 2021, 3:49pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/21 "2021-03-15T15:49:47Z")

</div>

> [@shanmukhan](#):
>
> `array_num[1:end]`

makes a copy of array\_num. If you want index-based iteration, do

```julia
for i=1:length(array_num)
  a=array_num[i]
  ...
end

```

if you want to iterate over an arbitrary subset of array\_num, create a view [Arrays · The Julia Language](https://docs.julialang.org/en/v1/base/arrays/#Views-(SubArrays-and-other-view-types))

---

<div class="post-metadata">

**Author:** ![shanmukhan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/shanmukhan/32/22928_2.png) [@shanmukhan](https://discourse.julialang.org/u/shanmukhan)\
**Post date:** [March 15, 2021, 3:52pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/22 "2021-03-15T15:52:19Z")

</div>

ok, thank you.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 15, 2021, 4:06pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/23 "2021-03-15T16:06:09Z")

</div>

This is one of my favorite 🙂 Slicing in python is not the same as in Julia. When you do `x[1:2]` in python you create a special object, which can go over the subset of elements of the original `x` without copying. But in Julia, slicing is a copying operation, so you spend a lot of time allocating and copying the content of the original vector.

In Julia, you can use `view` or `@views` to achieve the same effect but in this case it’s better to iterate over indices.

Or if you need something simple, like split the head off the collection, you can use `Iteratos.peel`

```julia
julia> x = 1:10
julia> a, rest = Iterators.peel(x)
julia> [l for l in rest]
9-element Vector{Int64}:
  2
  3
  4
  5
  6
  7
  8
  9
 10

```

---

<div class="post-metadata">

**Author:** ![czylabsonasa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/czylabsonasa/32/8663_2.png) [@czylabsonasa](https://discourse.julialang.org/u/czylabsonasa)\
**Post date:** [March 15, 2021, 4:48pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/24 "2021-03-15T16:48:55Z")

</div>

- I think that the complexity is not O(n^2), but O(\text{num of bikes\*num of persons}) which is \approx O(n^4) in the worst case. (That is why the high exec times…)

- After a successful lang level optimization turn to the algo level.  
One possible approach: start a BFS from the bike nodes…

---

<div class="post-metadata">

**Author:** ![shanmukhan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/shanmukhan/32/22928_2.png) [@shanmukhan](https://discourse.julialang.org/u/shanmukhan)\
**Post date:** [March 16, 2021, 11:14am UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/25 "2021-03-16T11:14:18Z")

</div>

I don’t think it is O(n^4), it is 2 times of O(n^2) which is O(n^2).

Agree that I should start with BFS approach.

---

<div class="post-metadata">

**Author:** ![shanmukhan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/shanmukhan/32/22928_2.png) [@shanmukhan](https://discourse.julialang.org/u/shanmukhan)\
**Post date:** [March 16, 2021, 11:16am UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/26 "2021-03-16T11:16:45Z")

</div>

thank you.

---

<div class="post-metadata">

**Author:** ![czylabsonasa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/czylabsonasa/32/8663_2.png) [@czylabsonasa](https://discourse.julialang.org/u/czylabsonasa)\
**Post date:** [March 16, 2021, 2:52pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/27 "2021-03-16T14:52:36Z")

</div>

If the original 0-1 matrix is of size n\times n, then  
we have 2 nested loops, both of them can have \frac{n^2}{2} steps (in the worst case)…  
Anyway, it is your algo and your complexity 🙂

---

<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:** [March 16, 2021, 3:25pm UTC](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175/28 "2021-03-16T15:25:55Z")

</div>

> [@Jeff\_Emanuel](#):
>
> makes a copy of array\_num. If you want index-based iteration, do
> 
> ```julia
> for i=1:length(array_num)
> a=array_num[i]
> ...
> end
> 
> ```

Generally, it’s better to do

```julia
for i in eachindex(array_num)
  a=array_num[i]
  ...
end

```

That will avoid bugs when the array isn’t 1-based wrt indexing.

[Previous page](https://discourse.julialang.org/t/matrix-shortest-distance-problem-need-suggestions-to-improve-the-performance/57175.md?page=1)