在这种情况下，为什么'all（itr）do'的阻塞速度比for循环快？

Question

我的代码做什么

目标是构建一个函数，该函数使用julia在给定的字符串中检查所有方括号是否正确打开和关闭。因此，

"{abc()([[def]])()}"

应该返回true，而类似的东西

"{(bracket order mixed up here!})[and this bracket doesn't close!"

应该返回false。

问题

我有该功能的两个版本。 为什么II版的速度要快10％？

版本I

function matching_brackets_old(AbstractString)
    close_open_map = Dict('}' => '{', ')' => '(', ']' => '[')
    order_arr = []
    for char in s
        if char in values(close_open_map)
            push!(order_arr, char)
        elseif (char in keys(close_open_map)) &&
            (isempty(order_arr) || (close_open_map[char] != pop!(order_arr)))
            return false
        end
    end
    return isempty(order_arr)
end

第二版

这里我用一个do块替换了for循环：

function matching_brackets(s::AbstractString)
    close_open_map = Dict('}' => '{', ')' => '(', ']' => '[')
    order_arr = []
    all_correct = all(s) do char
        if char in values(close_open_map)
            push!(order_arr, char)
        elseif (char in keys(close_open_map)) &&
            (isempty(order_arr) || (close_open_map[char] != pop!(order_arr)))
            return false
        end
        return true
    end
    return all_correct && isempty(order_arr)

时间

使用BenchmarkTools的@benchmark作为字符串"{()()[()]()}"和"{()()[())]()}"，在比较最短执行时间时，两个字符串的速度都提高了大约10％。

Answer 1

我在机器上没有看到相同的东西：在我的测试中，两个字符串的版本我都更快：

julia> @btime matching_brackets_old("{()()[()]()}")
  716.443 ns (18 allocations: 800 bytes)
true

julia> @btime matching_brackets("{()()[()]()}")
  761.434 ns (19 allocations: 832 bytes)
true

julia> @btime matching_brackets_old("{()()[())]()}")
  574.847 ns (15 allocations: 752 bytes)
false

julia> @btime matching_brackets("{()()[())]()}")
  612.793 ns (16 allocations: 784 bytes)
false

我认为（但这是一个疯狂的猜测），当字符串大小增加时，for循环与高阶函数之间的差异将变得越来越不重要。

但是，我鼓励您更仔细地研究order_arr变量：目前编写的变量是Vector{Any}类型，它像任何抽象类型的值的容器一样，都会影响性能。通过具体键入order_arr的元素，以下版本的性能更好：

function matching_brackets_new(s::AbstractString)
    close_open_map = Dict('}' => '{', ')' => '(', ']' => '[')

    # Make sure the compiler knows about the type of elements in order_arr
    order_arr = eltype(s)[]  # or order_arr = Char[]

    for char in s
        if char in values(close_open_map)
            push!(order_arr, char)
        elseif (char in keys(close_open_map)) &&
            (isempty(order_arr) || (close_open_map[char] != pop!(order_arr)))
            return false
        end
    end
    return isempty(order_arr)
end

收益：

julia> @btime matching_brackets_new("{()()[()]()}")
  570.641 ns (18 allocations: 784 bytes)
true

julia> @btime matching_brackets_new("{()()[())]()}")
  447.758 ns (15 allocations: 736 bytes)
false