Matrix shortest distance problem - Need suggestions to improve the performance

Specific Domains Optimization (Mathematical)
5

In addition to the above, maybe use

import Dates
import StatsBase.sample
import StatsBase.ProbabilityWeights

struct Position
    x::Int32
    y::Int32
    val::Int8
end

matrix = sample([0,1], ProbabilityWeights([1/6, 5/6]), (100, 100))
matrix_test = sample([0,1], ProbabilityWeights([1/6, 5/6]), (10, 10))

function prepare_persons_bikes(matrix)
    rows, cols = size(matrix)

    persons = Position[]
    bikes = Position[]
    for x in 1:rows
        for y in 1:cols
            pos = Position(x, y, matrix[x, y])
            if pos.val == 1
                push!(persons, pos)
            else
                push!(bikes, pos)
            end
        end
    end
    println("Size of persons=$(length(persons)), bikes=$(length(bikes))")
    return (persons, bikes)
end

my_metric(p1::Position, p2::Position) = abs(p1.x - p2.x) + abs(p1.y - p2.y)

find_nearest(p1::Position, p2::Vector{Position}) = findmin(my_metric(p1,p2))

function build_distance_matrix!(D::AbstractMatrix, persons::Vector{Position}, bikes::Vector{Position})
    for p in persons
        D[p.x, p.y] = find_nearest(p, bikes)[1]
    end
end

function find_nearest_(p1::Position, p2::Vector{Position})
    dist = zero(Int32)
    best = Int32(1000000)
    for p in p2
        dist = my_metric(p1, p)
        dist < best ? (best = dist) : nothing
    end
    return best
end


function build_distance_matrix_!(D::AbstractMatrix, persons::Vector{Position}, bikes::Vector{Position})
    for p in persons
        D[p.x, p.y] = find_nearest_(p, bikes)
    end
end

function find_distance(matrix, persons, bikes)
    for (idx, person) in enumerate(persons)
        nearest_distance = abs(person.x-bikes[1].x) + abs(person.y-bikes[1].y)

        for bike in bikes[2:end]
            dist = abs(person.x-bike.x) + abs(person.y-bike.y)
            if dist < nearest_distance
                nearest_distance = dist
            end

            if nearest_distance == 1
                break
            end
        end

        matrix[person.x, person.y] = nearest_distance

    end
end

find(matrix_test)
find(matrix)
using BenchmarkTools
matrix = sample([0,1], ProbabilityWeights([1/6, 5/6]), (100, 100))
m1 = deepcopy(matrix)
m2 = deepcopy(matrix)
m3 = deepcopy(matrix)
persons, bikes = prepare_persons_bikes(matrix)
@btime find_distance(m1, persons, bikes)
@btime build_distance_matrix!(m2, persons, bikes)
@btime build_distance_matrix_!(m3, persons, bikes)

With the output

34.528 ms (16768 allocations: 155.69 MiB)
27.975 ms (8384 allocations: 52.71 MiB)
15.156 ms (0 allocations: 0 bytes)

From julia 1.6rc1 :wink:

5 Likes