julia - 使用 Julia 实现递归函数返回的问题

Question

我已经实现了下一个代码，用于在网格中向下和向右移动，我正在尝试实现某种计数，如 return +1 但我不能，如果我被迫使用全局，它会使运行时相当长(如 8 次，尽管它随迭代次数而变化)。请告知如何使用这种语言正确编码。

我也想过像在 C 中那样使用指针，但很难实现它

function numOfPaths(NominalSize,x,y)
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
    (x >= NominalSize && y>=NominalSize) && global count+=1;
end
count = 0;
t1 = @elapsed numOfPaths(16,0,0)

使用 Ref 而不是使用全局的第二个版本，性能几乎相同。

function numOfPaths(NominalSize,x,y)
   (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
   (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
   ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
end
count = 0;
ref = Ref(count)
t1 = @elapsed anse = numOfPaths(15,0,0)

Answer 1

对于 Julia 编译器的当前状态，我认为您有两个选择(假设您不更改代码的逻辑)。

第一个是让代码保持原样，但将 count 更改为全局 const。然而，当你想改变它时，你必须引入一些包装器，一个自然的包装器是 Ref。所以你可以使用类似的东西:

const count = Ref(0)
function numOfPaths(NominalSize,x,y)
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
    (x >= NominalSize && y>=NominalSize) && global (count[] +=1)
end
count[] = 0
@time numOfPaths(16,0,0)
count[]

现在你可以像这样传递 count:

function numOfPaths(NominalSize,x,y, count=Ref(0))
    (x < NominalSize) && numOfPaths(NominalSize,x+1,y, count)
    (y < NominalSize) && numOfPaths(NominalSize,x,y+1, count)
    (x >= NominalSize && y>=NominalSize) && (count[] +=1)
    return count[]
end

作为参数，但是会慢一点。

最后(这是一个比第一个快一点的选项，推荐)你可以执行 count 的累加而不将它作为参数传递(这次它只是一个整数):

function numOfPaths(NominalSize,x,y)
    count = 0
    x < NominalSize && (count += numOfPaths(NominalSize,x+1,y))
    y < NominalSize && (count += numOfPaths(NominalSize,x,y+1))
    x >= NominalSize && y>=NominalSize && (count+=1)
    return count
end

---

编辑:

另外让我评论一下不起作用的地方。自然地，您会想像这样重写您的函数:

function numOfPaths(NominalSize,x,y)
    function f(x, y)
        x < NominalSize && f(x+1,y)
        y < NominalSize && f(x,y+1)
        x >= NominalSize && y>=NominalSize && (count+=1)
    end

    count = 0
    f(x, y)
    return count
end

不幸的是，目前这样的代码很慢，因为 Julia 正在装箱 count:

julia> @code_warntype numOfPaths(16, 0, 0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64
  f@_5::Core.Box
  count@_6::Core.Box
  f@_7::Union{}
  f@_8::Union{}
  count@_9::Union{}

Body::Any
1 ─       (f@_5 = Core.Box())
│         (count@_6 = Core.Box())
│   %3  = Main.:(var"#f#3")::Core.Compiler.Const(var"#f#3", false)
│   %4  = Core.typeof(NominalSize)::Core.Compiler.Const(Int64, false)
│   %5  = Core.apply_type(%3, %4)::Core.Compiler.Const(var"#f#3"{Int64}, false)
│   %6  = f@_5::Core.Box
│   %7  = %new(%5, NominalSize, %6, count@_6)::var"#f#3"{Int64}
│         Core.setfield!(f@_5, :contents, %7)
│         Core.setfield!(count@_6, :contents, 0)
│   %10 = Core.isdefined(f@_5, :contents)::Bool
└──       goto #3 if not %10
2 ─       goto #4
3 ─       Core.NewvarNode(:(f@_8))
└──       f@_8
4 ┄ %15 = Core.getfield(f@_5, :contents)::Any
│         (%15)(x, y)
│   %17 = Core.isdefined(count@_6, :contents)::Bool
└──       goto #6 if not %17
5 ─       goto #7
6 ─       Core.NewvarNode(:(count@_9))
└──       count@_9
7 ┄ %22 = Core.getfield(count@_6, :contents)::Any
└──       return %22

希望将来这会得到解决(这是一个已知问题)。

---

编辑 2

如果您想使这段代码运行得更快，首先让我评论一下该怎么做。在这种情况下，可以使用动态编程代替递归，例如:

function numOfPaths(NominalSize, x, y)
    y, x = minmax(x, y)
    a = ones(BigInt, NominalSize + 1 - y)
    for i in 2:NominalSize - x + 1
        i > length(a) || (a[i] = 2 * a[i])
        for j in i+1:length(a)
            a[j] += a[j-1]
        end
    end
    return a[end]
end

(请注意，我在这里使用的是 BigInt，因为使用这段代码，您可以测试比 Int64 类型的范围大得多的值；如果您想要甚至更快只需在代码中将 BigInt 切换为 Int，但是对于大于 33 的 NominalSize 你会得到溢出)

---

现在，转到@Alex Zh 为什么第二个代码运行缓慢的问题。您可以在其上运行 @code_warntype 以了解以下内容:

julia> function numOfPaths(NominalSize,x,y)
          (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
          (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
          ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
       end
numOfPaths (generic function with 1 method)

julia> count = 0;

julia> ref = Ref(count)
Base.RefValue{Int64}(0)

julia> @code_warntype numOfPaths(15,0,0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64

Body::Any
1 ─ %1  = (x < NominalSize)::Bool
└──       goto #3 if not %1
2 ─ %3  = (x + 1)::Int64
│         Main.numOfPaths(NominalSize, %3, y)
└──       goto #3
3 ┄ %6  = (y < NominalSize)::Bool
└──       goto #5 if not %6
4 ─ %8  = (y + 1)::Int64
│         Main.numOfPaths(NominalSize, x, %8)
└──       goto #5
5 ┄ %11 = (y >= NominalSize)::Bool
└──       goto #9 if not %11
6 ─ %13 = (x >= NominalSize)::Bool
└──       goto #8 if not %13
7 ─ %15 = Base.getindex(Main.ref)::Any
│   %16 = (%15 + 1)::Any
│         Base.setindex!(Main.ref, %16)
└──       return %16
8 ─       return false
9 ─       return false

现在在行中:

%15 = Base.getindex(Main.ref)::Any

你看到，当 Julia 从 Main 获取 ref 时，它不知道它的类型是什么，因为它是一个全局变量，而不是常量。因此，编译器无法生成高效的机器码，因为 ref 的类型必须在运行时(而非编译时)解析。

现在考虑以下更改(您需要重新启动 Julia 来测试它):

ulia> function numOfPaths(NominalSize,x,y)
          (x < NominalSize) && numOfPaths(NominalSize,x+1,y)
          (y < NominalSize) && numOfPaths(NominalSize,x,y+1)
          ((y >= NominalSize) && (x >= NominalSize)) && (ref[] += 1 ;)
       end
numOfPaths (generic function with 1 method)

julia> count = 0;

julia> const ref = Ref(count)
Base.RefValue{Int64}(0)

julia> @code_warntype numOfPaths(15,0,0)
Variables
  #self#::Core.Compiler.Const(numOfPaths, false)
  NominalSize::Int64
  x::Int64
  y::Int64

Body::Union{Bool, Int64}
1 ─ %1  = (x < NominalSize)::Bool
└──       goto #3 if not %1
2 ─ %3  = (x + 1)::Int64
│         Main.numOfPaths(NominalSize, %3, y)
└──       goto #3
3 ┄ %6  = (y < NominalSize)::Bool
└──       goto #5 if not %6
4 ─ %8  = (y + 1)::Int64
│         Main.numOfPaths(NominalSize, x, %8)
└──       goto #5
5 ┄ %11 = (y >= NominalSize)::Bool
└──       goto #9 if not %11
6 ─ %13 = (x >= NominalSize)::Bool
└──       goto #8 if not %13
7 ─ %15 = Base.getindex(Main.ref)::Int64
│   %16 = (%15 + 1)::Int64
│         Base.setindex!(Main.ref, %16)
└──       return %16
8 ─       return false
9 ─       return false

现在我已将 ref 设为全局 const。这告诉编译器 ref 保证不会改变它的类型。因此你有:

7 ─ %15 = Base.getindex(Main.ref)::Int64

因为这一次编译器拥有它需要的所有类型信息，所以可以生成更高效的机器码。