Почему в этом случае блок all (itr) do работает медленнее, чем a для l oop? - PullRequest
Новая
       20

Почему в этом случае блок all (itr) do работает медленнее, чем a для l oop?

2 голосов
/ 24 февраля 2020

Что делает мой код

Цель состояла в том, чтобы создать функцию, которая проверяет, все ли скобки открываются и закрываются правильно в заданной строке с помощью 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

Здесь я заменяю на l oop с блоком 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

Время

Используя @benchmark BenchmarkTools для строк "{()()[()]()}" и "{()()[())]()}", я получаю замедление примерно на 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

Редактировать

Я перепутал порядок в Судебном процессе, поэтому Версия I работает быстрее, как предполагает Франсуа Февотт. Мой вопрос остается: почему?

Ответы [ 2 ]

4 голосов
/ 24 февраля 2020

Теперь, когда ошибка с judge устранена, ответ, вероятно, является обычным предупреждением: вызовы функций, как в этом случае в результате закрытия, переданного в all, довольно оптимизированы, но не бесплатно.

Чтобы добиться реального улучшения, я предлагаю, кроме обеспечения стабильности типа стека (что здесь не так уж и сложно), избавиться от итераций, которые вы неявно выполняете, вызывая in on 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

Еще немного времени можно выжать, развернув внутренний l oop поверх кортежа: 

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

Обновление: если вы вставите break s в первой версии, на действительно Избегайте ненужных циклов, время практически неразличимо, с хорошим кодом: 

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
2 голосов
/ 24 февраля 2020

Я не наблюдаю то же самое на моей машине: в моих тестах версия 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

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

Тем не менее, я бы посоветовал вам внимательнее присмотреться к переменной 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
...