小贝子编程

为什么在这种情况下，"all(itr) do"块比 for 循环慢？



我的代码做什么

目标是建立一个函数，用julia检查给定字符串中所有括号的打开和关闭是否正确。所以，

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

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

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

应返回false。

问题

我有两个版本的函数为什么版本I快了大约10%

版本I

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

版本II

在这里，我将for循环替换为do块：

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

编辑

我混淆了Trialjudication的顺序，所以版本I更快，正如François Févotte所建议的那样。我的问题仍然是：为什么？

现在judge的错误已经解决，答案可能是常见的警告：函数调用(在本例中是由传递给all的闭包产生的(经过了充分优化，但不是免费的。

为了获得真正的改进，我建议，除了使堆栈类型稳定(这在这里没什么大不了的(之外，通过在values和keys上调用in来消除隐含的迭代。只做一次就足够了，没有字典：

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

我在我的机器上没有观察到相同的情况：在我的测试中，版本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

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium