在这种情况下，为什么 'all(itr) do' 块比 for 循环慢？
Why is 'all(itr) do' block slower than a for loop in this case?
我的代码做了什么
目标是构建一个函数，使用 julia 检查给定字符串中的所有括号是否正确打开和关闭。所以，
"{abc()([[def]])()}"
应该 return 正确，而
"{(bracket order mixed up here!})[and this bracket doesn't close!"
应该return假。
问题
我有两个版本的函数。 为什么版本 I 快了大约 10%？
第一版
function matching_brackets_old(s::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)
end
时间
对字符串 "{()()[()]()}" 和 "{()()[())]()}" 使用 BenchmarkTools 的 @benchmark，比较最短执行时间时，两个字符串的速度都降低了大约 10%。
附加信息
版本信息：
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
OS: macOS (x86_64-apple-darwin18.6.0)
CPU: Intel(R) Core(TM) i5-4260U CPU @ 1.40GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, haswell)
时间码：
using BenchmarkTools
benchmark_strings = ["{()()[()]()}", "{()()[())]()}"]
for s in benchmark_strings
b_old = @benchmark matching_brackets_old("$s") samples=100000 seconds=30
b_new = @benchmark matching_brackets("$s") samples=100000 seconds=30
println("For String=", s)
println(b_old)
println(b_new)
println(judge(minimum(b_new), minimum(b_old)))
println("Result: ", matching_brackets(s))
end
结果：
For String={()()[()]()}
Trial(8.177 μs)
Trial(9.197 μs)
TrialJudgement(+12.48% => regression)
Result: true
For String={()()[())]()}
Trial(8.197 μs)
Trial(9.202 μs)
TrialJudgement(+12.27% => regression)
Result: false
编辑
我混淆了 Trialjudgmentment 的顺序，所以版本 I 更快，正如 François Févotte 所建议的那样。我的问题仍然是：为什么？
我在我的机器上没有观察到同样的情况：在我的测试中，版本 I 对于两个字符串都更快：
julia> versioninfo()
Julia Version 1.3.0
Commit 46ce4d7933 (2019-11-26 06:09 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
Environment:
JULIA_PROJECT = @.
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
现在 judge 的错误已经解决，答案可能是通常的警告：函数调用，在本例中由传递给 all 的闭包产生，是非常优化的，但是不是免费的。
为了获得真正的改进，我建议，除了使堆栈类型稳定（这在这里没什么大不了的）之外，通过调用 in 来摆脱你隐式执行的迭代values 和 keys。只做一次就足够了，没有字典:
const MATCHING_PAIRS = ('{' => '}', '(' => ')', '[' => ']')
function matching_brackets(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
for (open, close) in MATCHING_PAIRS
if c == open
push!(stack, c)
elseif c == close
if isempty(stack) || (pop!(stack) != open)
return false
end
end
end
end
return isempty(stack)
end
通过在元组上展开内循环可以挤出更多时间：
function matching_brackets_unrolled(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
if (c == '(') || (c == '[') || (c == '{')
push!(stack, c)
elseif (c == ')')
if isempty(stack) || (pop!(stack) != '(')
return false
end
elseif (c == ']')
if isempty(stack) || (pop!(stack) != '[')
return false
end
elseif (c == '}')
if isempty(stack) || (pop!(stack) != '{')
return false
end
end
end
return isempty(stack)
end
虽然这有点难看，但肯定不能很好地扩展。我的基准测试（matching_brackets_new 是你的第二个版本，matching_brackets 我的第一个）：
julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i7 CPU 960 @ 3.20GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, nehalem)
# NOT MATCHING
julia> @benchmark matching_brackets_new("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 784 bytes
allocs estimate: 16
--------------
minimum time: 674.844 ns (0.00% GC)
median time: 736.200 ns (0.00% GC)
mean time: 800.935 ns (6.54% GC)
maximum time: 23.831 μs (96.16% GC)
--------------
samples: 10000
evals/sample: 160
julia> @benchmark matching_brackets_old("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 752 bytes
allocs estimate: 15
--------------
minimum time: 630.743 ns (0.00% GC)
median time: 681.725 ns (0.00% GC)
mean time: 753.937 ns (6.41% GC)
maximum time: 23.056 μs (94.19% GC)
--------------
samples: 10000
evals/sample: 171
julia> @benchmark matching_brackets("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 164.883 ns (0.00% GC)
median time: 172.900 ns (0.00% GC)
mean time: 186.523 ns (4.33% GC)
maximum time: 5.428 μs (96.54% GC)
--------------
samples: 10000
evals/sample: 759
julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 134.459 ns (0.00% GC)
median time: 140.292 ns (0.00% GC)
mean time: 150.067 ns (5.84% GC)
maximum time: 5.095 μs (96.56% GC)
--------------
samples: 10000
evals/sample: 878
# MATCHING
julia> @benchmark matching_brackets_old("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 800 bytes
allocs estimate: 18
--------------
minimum time: 786.358 ns (0.00% GC)
median time: 833.873 ns (0.00% GC)
mean time: 904.437 ns (5.43% GC)
maximum time: 29.355 μs (96.88% GC)
--------------
samples: 10000
evals/sample: 106
julia> @benchmark matching_brackets_new("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 832 bytes
allocs estimate: 19
--------------
minimum time: 823.597 ns (0.00% GC)
median time: 892.506 ns (0.00% GC)
mean time: 981.381 ns (5.98% GC)
maximum time: 47.308 μs (97.84% GC)
--------------
samples: 10000
evals/sample: 77
julia> @benchmark matching_brackets("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 206.062 ns (0.00% GC)
median time: 214.481 ns (0.00% GC)
mean time: 227.385 ns (3.38% GC)
maximum time: 6.890 μs (96.22% GC)
--------------
samples: 10000
evals/sample: 535
julia> @benchmark matching_brackets_unrolled("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 160.186 ns (0.00% GC)
median time: 164.752 ns (0.00% GC)
mean time: 180.794 ns (4.95% GC)
maximum time: 5.751 μs (97.03% GC)
--------------
samples: 10000
evals/sample: 800
更新：如果你在第一个版本中插入breaks，为了真正避免不必要的循环，时间几乎无法区分，代码很好：
function matching_brackets(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
for (open, close) in MATCHING_PAIRS
if c == open
push!(stack, c)
break
elseif c == close
if isempty(stack) || (pop!(stack) != open)
return false
end
break
end
end
end
return isempty(stack)
end
与
julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 137.574 ns (0.00% GC)
median time: 144.978 ns (0.00% GC)
mean time: 165.365 ns (10.44% GC)
maximum time: 9.344 μs (98.02% GC)
--------------
samples: 10000
evals/sample: 867
julia> @benchmark matching_brackets("{()()[())]()}") # with breaks
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 148.255 ns (0.00% GC)
median time: 155.231 ns (0.00% GC)
mean time: 175.245 ns (9.62% GC)
maximum time: 9.602 μs (98.31% GC)
--------------
samples: 10000
evals/sample: 839
我的代码做了什么
目标是构建一个函数，使用 julia 检查给定字符串中的所有括号是否正确打开和关闭。所以，
"{abc()([[def]])()}"
应该 return 正确，而
"{(bracket order mixed up here!})[and this bracket doesn't close!"
应该return假。
问题
我有两个版本的函数。 为什么版本 I 快了大约 10%？
第一版
function matching_brackets_old(s::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)
end
时间
对字符串 "{()()[()]()}" 和 "{()()[())]()}" 使用 BenchmarkTools 的 @benchmark，比较最短执行时间时，两个字符串的速度都降低了大约 10%。
附加信息
版本信息：
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
OS: macOS (x86_64-apple-darwin18.6.0)
CPU: Intel(R) Core(TM) i5-4260U CPU @ 1.40GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, haswell)
时间码：
using BenchmarkTools
benchmark_strings = ["{()()[()]()}", "{()()[())]()}"]
for s in benchmark_strings
b_old = @benchmark matching_brackets_old("$s") samples=100000 seconds=30
b_new = @benchmark matching_brackets("$s") samples=100000 seconds=30
println("For String=", s)
println(b_old)
println(b_new)
println(judge(minimum(b_new), minimum(b_old)))
println("Result: ", matching_brackets(s))
end
结果：
For String={()()[()]()}
Trial(8.177 μs)
Trial(9.197 μs)
TrialJudgement(+12.48% => regression)
Result: true
For String={()()[())]()}
Trial(8.197 μs)
Trial(9.202 μs)
TrialJudgement(+12.27% => regression)
Result: false
编辑
我混淆了 Trialjudgmentment 的顺序，所以版本 I 更快，正如 François Févotte 所建议的那样。我的问题仍然是：为什么？
我在我的机器上没有观察到同样的情况：在我的测试中，版本 I 对于两个字符串都更快：
julia> versioninfo()
Julia Version 1.3.0
Commit 46ce4d7933 (2019-11-26 06:09 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
Environment:
JULIA_PROJECT = @.
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
现在 judge 的错误已经解决，答案可能是通常的警告：函数调用，在本例中由传递给 all 的闭包产生，是非常优化的，但是不是免费的。
为了获得真正的改进，我建议，除了使堆栈类型稳定（这在这里没什么大不了的）之外，通过调用 in 来摆脱你隐式执行的迭代values 和 keys。只做一次就足够了，没有字典:
const MATCHING_PAIRS = ('{' => '}', '(' => ')', '[' => ']')
function matching_brackets(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
for (open, close) in MATCHING_PAIRS
if c == open
push!(stack, c)
elseif c == close
if isempty(stack) || (pop!(stack) != open)
return false
end
end
end
end
return isempty(stack)
end
通过在元组上展开内循环可以挤出更多时间：
function matching_brackets_unrolled(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
if (c == '(') || (c == '[') || (c == '{')
push!(stack, c)
elseif (c == ')')
if isempty(stack) || (pop!(stack) != '(')
return false
end
elseif (c == ']')
if isempty(stack) || (pop!(stack) != '[')
return false
end
elseif (c == '}')
if isempty(stack) || (pop!(stack) != '{')
return false
end
end
end
return isempty(stack)
end
虽然这有点难看，但肯定不能很好地扩展。我的基准测试（matching_brackets_new 是你的第二个版本，matching_brackets 我的第一个）：
julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i7 CPU 960 @ 3.20GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-6.0.1 (ORCJIT, nehalem)
# NOT MATCHING
julia> @benchmark matching_brackets_new("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 784 bytes
allocs estimate: 16
--------------
minimum time: 674.844 ns (0.00% GC)
median time: 736.200 ns (0.00% GC)
mean time: 800.935 ns (6.54% GC)
maximum time: 23.831 μs (96.16% GC)
--------------
samples: 10000
evals/sample: 160
julia> @benchmark matching_brackets_old("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 752 bytes
allocs estimate: 15
--------------
minimum time: 630.743 ns (0.00% GC)
median time: 681.725 ns (0.00% GC)
mean time: 753.937 ns (6.41% GC)
maximum time: 23.056 μs (94.19% GC)
--------------
samples: 10000
evals/sample: 171
julia> @benchmark matching_brackets("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 164.883 ns (0.00% GC)
median time: 172.900 ns (0.00% GC)
mean time: 186.523 ns (4.33% GC)
maximum time: 5.428 μs (96.54% GC)
--------------
samples: 10000
evals/sample: 759
julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 134.459 ns (0.00% GC)
median time: 140.292 ns (0.00% GC)
mean time: 150.067 ns (5.84% GC)
maximum time: 5.095 μs (96.56% GC)
--------------
samples: 10000
evals/sample: 878
# MATCHING
julia> @benchmark matching_brackets_old("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 800 bytes
allocs estimate: 18
--------------
minimum time: 786.358 ns (0.00% GC)
median time: 833.873 ns (0.00% GC)
mean time: 904.437 ns (5.43% GC)
maximum time: 29.355 μs (96.88% GC)
--------------
samples: 10000
evals/sample: 106
julia> @benchmark matching_brackets_new("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 832 bytes
allocs estimate: 19
--------------
minimum time: 823.597 ns (0.00% GC)
median time: 892.506 ns (0.00% GC)
mean time: 981.381 ns (5.98% GC)
maximum time: 47.308 μs (97.84% GC)
--------------
samples: 10000
evals/sample: 77
julia> @benchmark matching_brackets("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 206.062 ns (0.00% GC)
median time: 214.481 ns (0.00% GC)
mean time: 227.385 ns (3.38% GC)
maximum time: 6.890 μs (96.22% GC)
--------------
samples: 10000
evals/sample: 535
julia> @benchmark matching_brackets_unrolled("{()()[()]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 160.186 ns (0.00% GC)
median time: 164.752 ns (0.00% GC)
mean time: 180.794 ns (4.95% GC)
maximum time: 5.751 μs (97.03% GC)
--------------
samples: 10000
evals/sample: 800
更新：如果你在第一个版本中插入breaks，为了真正避免不必要的循环，时间几乎无法区分，代码很好：
function matching_brackets(s::AbstractString)
stack = Vector{eltype(s)}()
for c in s
for (open, close) in MATCHING_PAIRS
if c == open
push!(stack, c)
break
elseif c == close
if isempty(stack) || (pop!(stack) != open)
return false
end
break
end
end
end
return isempty(stack)
end
与
julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 137.574 ns (0.00% GC)
median time: 144.978 ns (0.00% GC)
mean time: 165.365 ns (10.44% GC)
maximum time: 9.344 μs (98.02% GC)
--------------
samples: 10000
evals/sample: 867
julia> @benchmark matching_brackets("{()()[())]()}") # with breaks
BenchmarkTools.Trial:
memory estimate: 112 bytes
allocs estimate: 2
--------------
minimum time: 148.255 ns (0.00% GC)
median time: 155.231 ns (0.00% GC)
mean time: 175.245 ns (9.62% GC)
maximum time: 9.602 μs (98.31% GC)
--------------
samples: 10000
evals/sample: 839