Эффективное внедрение цепей Маркова в Юлии

Question

Я хочу максимально эффективно имитировать движение случайного бродяги в сети. Ниже я показываю игрушечную модель с тремя подходами, которые я пробовал до сих пор. Я должен отметить, что в моей исходной задаче ребра сети фиксированы, однако веса ребер могут быть обновлены (то есть список соседей такой же, но веса могут измениться).

using QuantEcon
using LightGraphs
using Distributions
using StatsBase

n = 700 #number of nodes
#setting an arbitrary network and its transition matrix
G_erdos = erdos_renyi(n, 15/n)
A_erdos = adjacency_matrix(G_erdos) + eye(n, n);
A_transition = A_erdos ./ sum(A_erdos, 2);

##Method 1
#using QuantEcon library
function QE_markov_draw(i::Int, A::Array{Float64,2})
    d = DiscreteRV(A[i, :]);
    return rand(d, 1)   
end

##Method 2
#using a simple random draw
function matrix_draw(i::Int, A::Array{Float64,2}, choices::Array{Int64,1})
    return sample(choices, Weights(A[i, :]))
end

##Method 3
# The matrix may be sparse. Therefore I obtain first list of neighbors and weights
#for each node. Then run sample using the list of neighbors and weights.
function neighbor_weight_list(A::Array{Float64,2}, i::Int)
    n = size(A)[1]
    neighbor_list = Int[]
    weight_list = Float64[]
    for i = 1:n
        for j = 1:n
            if A[i, j] > 0
                push!(neighbor_list, j)
                push!(weight_list, A[i, j])
            end
        end
    end
    return neighbor_list, weight_list
end
#Using sample on the reduced list.
function neigh_weights_draw(i::Int, neighs::Array{Int,1}, weigh::Array{Float64,1})
    return sample(neighs, Weights(weigh))
end

neighbor_list, weight_list = neighbor_weight_list(A_transition, 1)
states = [i for i = 1:n];

println("Method 1")
@time for t = 1:100000
    QE_markov_draw(3, A_transition)
end

println("Method 2")
@time for t = 1:100000
    matrix_draw(3, A_transition, states)
end

println("Method 3")
@time for t = 1:100000
    neigh_weights_draw(3, neighbor_list, weight_list)
end

Общие результаты показывают (после первой итерации), что метод 2 самый быстрый. Метод 3 использует наименьшее количество памяти, за которым следует метод 2, однако это может быть связано с тем, что они «питаются» на neighbor_list и states.

Method 1
  0.327805 seconds (500.00 k allocations: 1.086 GiB, 14.70% gc time)
Method 2
  0.227060 seconds (329.47 k allocations: 554.344 MiB, 11.24% gc time)
Method 3
  1.224682 seconds (128.19 k allocations: 3.482 MiB)

Мне было интересно, какая реализация будет наиболее эффективной и есть ли способ ее улучшить.

Answer 1

Вот несколько рекомендаций, которые я могу дать:

В варианте 2 вместо этого используйте представление и работайте над транспонированием матрицы (поэтому вы работаете со столбцами, а не строками):

# here A should be a transpose of your original A
function matrix_draw(i::Int, A::Array{Float64,2}, choices::Array{Int64,1})
    return sample(choices, Weights(view(A, i, :)))
end

Это дает почти 7-кратное ускорение в моих тестах.

Но в целом метод 3 должен быть самым быстрым, но, похоже, он реализован неправильно. Вот фиксированный подход

function neighbor_weight_list(A::Array{Float64,2})
    n = size(A)[1]
    neighbor_list = Vector{Int}[]
    weight_list = Vector{Float64}[]
    for i = 1:n
        push!(neighbor_list, Int[])
        push!(weight_list, Float64[])
        for j = 1:n
            if A[i, j] > 0
                push!(neighbor_list[end], j)
                push!(weight_list[end], A[i, j])
            end
        end
    end
    return neighbor_list, weight_list
end

function neigh_weights_draw(i::Int, neighs::Vector{Vector{Int}}, weigh::Vector{Vector{Float64}})
    return sample(neighs[i], Weights(weigh[i]))
end

neighbor_list, weight_list = neighbor_weight_list(A_transition)

Когда я запускаю этот код, он в 4 раза быстрее, чем фиксированный метод 2. Также обратите внимание, что вы можете использовать метод 3 без создания матрицы смежности вообще, но напрямую работать с использованием функции neighbors из LightGraphs.