Matrix shortest distance problem - Need suggestions to improve the performance

Specific Domains Optimization (Mathematical)
21

makes a copy of array_num. If you want index-based iteration, do

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

22

ok, thank you.

23

This is one of my favorite :slight_smile: 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> 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
24

  • 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…

1 Like
25

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.

1 Like
26

thank you.

27

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 :slight_smile:

28

Generally, it’s better to do

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

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

4 Likes