1

我在 Julia Studio（Julia 0.2.0，OSX 10.8.2）中编写了一个非常基本的算法，用于计算炉石中给定法力曲线每回合剩余的平均法力值。完成算法后，我向所有变量添加了类型声明，认为这将有助于提高整体速度。惊喜！添加的类型声明使代码运行速度慢了 4 倍以上（从 ~7s 到 ~28s）。是什么导致了这种奇怪的行为，我该如何解决？感觉添加类型应该有助于编译器生成更快的代码，或者至少没有任何区别。

这是没有类型声明的代码（运行时间 6.76s）：

function all_combinations(n)
    result = Array{Int64}[]
    for x in [1:n]
        append!(result, collect(combinations(1:n,x)))
    end
    return result
end

curve = [2, 3, 4, 5, 5, 4, 3, 2, 1, 1]

games = Array{Int64}[]

function execute()
    for game_n in [1:5000]

        deck = mapreduce(
            (x) -> fill(x[1], x[2]),
            append!,
            enumerate(curve))

        function drawcard()
            card = splice!(deck, rand(1:length(deck)))
        end

        hand = [drawcard() for n in [1:3]]

        turn_leftovers = Int64[]

        for mana in [1:10]

            push!(hand, drawcard())

            possible_plays = all_combinations(length(hand))
            map!(
                play -> map(i -> hand[i], play),
                possible_plays)
            filter!(x -> sum(x) <= mana, possible_plays)

            if  !isempty(possible_plays)

                play = reduce(
                    (a, b) -> sum(a) > sum(b) ? a : b,
                    possible_plays)
                for card in play
                    splice!(hand, findfirst(hand, card))
                end
                push!(turn_leftovers, mana - sum(play))
            else
                push!(turn_leftovers, mana)
            end

        end

        push!(games, turn_leftovers)

    end
end

println(@elapsed execute())

println("Averaging over $(length(games)) games")
for turn in [1:length(games[1])]
    avrg = mean(map(game -> game[turn], games))
    println("Left on turn $turn: $avrg")
end
println("Average mana leftover: $(mean(reduce(vcat, games)))")
println("Done")

这是带有类型声明的代码（运行时间 28.48 秒）：

function all_combinations(n)
    result = Array{Int64}[]
    for x in [1:n]
        append!(result, collect(combinations(1:n,x)))
    end
    return result
end

curve::Array{Int64} = [2, 3, 4, 5, 5, 4, 3, 2, 1, 1]

games = Array{Int64}[]

function execute()
    for game_n::Int64 in [1:5000]

        deck::Array{Int64}
        deck = mapreduce(
            (x) -> fill(x[1], x[2]),
            append!,
            enumerate(curve))

        function drawcard()
            card::Int64 = splice!(deck, rand(1:length(deck)))
        end

        hand::Array{Int64}
        hand = [drawcard() for n in [1:3]]

        turn_leftovers::Array{Int64}
        turn_leftovers = Int64[]

        for mana::Int64 in [1:10]

            push!(hand, drawcard())

            possible_plays::Array{Array{Int64}} = all_combinations(length(hand))
            map!(
                play -> map(i::Int64 -> hand[i], play),
                possible_plays)
            filter!(x::Array{Int64} -> sum(x) <= mana, possible_plays)

            if  !isempty(possible_plays)

                play::Array{Int64} = reduce(
                    (a::Array{Int64}, b::Array{Int64}) -> sum(a) > sum(b) ? a : b,
                    possible_plays)
                for card::Int64 in play
                    splice!(hand, findfirst(hand, card))
                end
                push!(turn_leftovers, mana - sum(play))
            else
                push!(turn_leftovers, mana)
            end

        end

        push!(games, turn_leftovers)

    end
end

println(@elapsed execute())

println("Averaging over $(length(games)) games")
for turn in [1:length(games[1])]
    avrg = mean(map(game -> game[turn], games))
    println("Left on turn $turn: $avrg")
end
println("Average mana leftover: $(mean(reduce(vcat, games)))")
println("Done")

值得注意的是，即使是最快的版本也比用 JavaScript 编写的等效代码要慢一些。不过，这可能只是因为糟糕的实现。我毫不怀疑，一个更好的算法会在一周中的任何一天胜过 JS。

4

1 回答 1

1

减速的一个来源：您正在使用大量匿名函数和高阶函数，例如，

map!( play -> map(i::Int64 -> hand[i], play), possible_plays ) filter!(x::Array{Int64} -> sum(x) <= mana, possible_plays)

在当前的 Julia 中，这两种结构都不容易被编译器优化。将它们替换为列表推导或 for 循环之类的东西会有所改善。

于 2014-03-03T14:46:46.560 回答