[存疑in缓存]无限斐波那契数列

我手痒写了一个无限的 斐波那契数列,但是我不会操作

struct Fib end

function Base.iterate(fib::Fib) # -> next
    (1,(1,0))
end

function Base.iterate(fib::Fib,state::T) where T # -> next
    (a,b) = state
    (a+b,(a+b,a))
end

我好像只能这样用

f = Fib()
for i in f
    print(i) # loop forever
end

针对这个情况我想用collect(Iterator.take(fib,10)) 来解决,但是这个需要length(::Fib) 定义,我应该怎么做?


3.29 修改完毕

定义长度Base.length(f::Fib) = typemax(Int),可以正常使用

fib= Fib()
collect(Iterator.take(fib,10)) # 1,1,2,3,5,8,13,21,...

另外

function Base.iterate(fib::Fib) 
    (BigInt(1),(BigInt(1),BigInt(0))) #防止溢出
end

3.31 带缓存版本

module Fib
struct __Fib
    dict::Dict{Int,BigInt}
end
fib = __Fib(Dict{Int,BigInt}())

function Base.iterate(fib::__Fib) # -> next
    # (1,(1,0))
    res = BigInt(1),(BigInt(1),BigInt(0),2)
    fib.dict[1] = res[1]
    res
end

function Base.iterate(fib::__Fib,(a,b,n)::T) where T # -> next
    res = 0
    if n < length(fib.dict)
        res = fib.dict[n]
    else
        res = a+b
        fib.dict[n] = res
    end
    # (a+b,(a+b,a))
    res,(res,a,n+1)
end

Base.length(fib::__Fib) = typemax(Int)

export fib
end

4.11 文档补全

斐切那波数列 无缓存版本

n fib
1 1
2 1
3 2
4 3
5 5

1. Base.iterate(fib::__Fib) -> (n,state) # next

我们把n看作fib的值–fib(n),state看作为下一次迭代所需要的值,(fib(n),fib(n-1))

function Base.iterate(fib::__Fib)
	1,(1,0) # 特殊情况,在第一次迭代过程中state为(1,0)
	# 为了防止整数溢出,应该用
	BigInt(1),(BigInt(1),BigInt(0))
end

2. Base.iterate(fib::__Fib,state) -> (n,state) # next

经过第一次迭代后的state为(1,0),通过用Tuple(a,b)作为fib的进行函数结构,a+b可以得到本次fib的值

function Base.iterate(fib::__Fib,(a,b)::T) where T
	a+b,(a+b,a)
end

3. 定义fib的length

Base.length(fib::__Fib) = typemax(Int)

斐切那波数列 带缓存版本[存疑,不要用]

我们在__Fib结构里加上一个dict来做缓存

struct __Fib
	dict::Dict{Int,BigInt}
end
fib = __Fib(Dict{Int,BigInt}())

接下来修改state,假设当前fib值为fib(n),state为(fib(n),fib(n-1),n+1),其中n+1为缓存做准备(缓存体现在Iterator.take中)

function Base.iterate(fib::__Fib) # -> next
    # (1,(1,0))
    res = BigInt(1),(BigInt(1),BigInt(0),2)
    fib.dict[1] = res[1]
    res
end

function Base.iterate(fib::__Fib,(a,b,n)::T) where T # -> next
    res = 0
    if n < length(fib.dict)
        res = fib.dict[n]
    else
        res = a+b
        fib.dict[n] = res
    end
    # (a+b,(a+b,a))
    res,(res,a,n+1)
end

Base.length(fib::__Fib) = typemax(Int)

测试

# with dict
julia> @benchmark collect(Iterators.take(fib,100000))
BenchmarkTools.Trial: 
  memory estimate:  789.99 KiB
  allocs estimate:  11
  --------------
  minimum time:     4.160 ms (0.00% GC)
  median time:      11.374 ms (0.00% GC)
  mean time:        10.868 ms (0.06% GC)
  maximum time:     20.342 ms (0.00% GC)
  --------------
  samples:          459
  evals/sample:     1

# without dict
julia> @benchmark collect(Iterators.take(fib,100000))
BenchmarkTools.Trial: 
  memory estimate:  2.29 MiB
  allocs estimate:  99989
  --------------
  minimum time:     1.457 ms (0.00% GC)
  median time:      2.655 ms (0.00% GC)
  mean time:        2.716 ms (6.33% GC)
  maximum time:     10.372 ms (74.08% GC)
  --------------
  samples:          1816
  evals/sample:     1

不知道为什么带缓存的版本有点慢,可能是查询引起的,不过内存分配明显减少了
本来我想测试1000000个fib数的,但是电脑内存不够用,julia-repl崩溃了,有时间的小伙伴请帮忙测试一下


从Slack问到了一个答案 我只是加了个length定义,得出的fib是(1 2 3 5 …),作者说的是HasLength这个函数

mutable struct Fibs
    value::Int
    rest::Fibs
    Fibs(v) = new(v)
    Fibs(v, r) = new(v, r)
end

fibs = Fibs(0, Fibs(1))

function Base.iterate(fibs::Fibs, (a,b)=(fibs, fibs.rest))
    value = a.value + b.value
    if !isdefined(b, :rest)
        b.rest = Fibs(value)
    end
    return value, (b, b.rest)
end

Base.length(fibs::Fibs) = typemax(Int)

测试

julia> @benchmark collect(Iterators.take(fibs,1000000))
BenchmarkTools.Trial: 
  memory estimate:  22.89 MiB
  allocs estimate:  999990
  --------------
  minimum time:     9.076 ms (0.00% GC)
  median time:      12.147 ms (0.00% GC)
  mean time:        14.792 ms (26.59% GC)
  maximum time:     45.646 ms (65.09% GC)
  --------------
  samples:          339
  evals/sample:     1

ps: 这个内存分配到底怎么看,

2赞

带缓存的版本

测试1000000 个fib 数消耗了我28.8G内存。

julia> @benchmark collect(Iterators.take(fib,100000))
BenchmarkTools.Trial: 
  memory estimate:  789.99 KiB
  allocs estimate:  11
  --------------
  minimum time:     2.986 ms (0.00% GC)
  median time:      3.313 ms (0.00% GC)
  mean time:        3.399 ms (0.25% GC)
  maximum time:     6.525 ms (42.50% GC)
  --------------
  samples:          1466
  evals/sample:     1
julia> @benchmark collect(Iterators.take(fib,1000000))
BenchmarkTools.Trial: 
  memory estimate:  7.71 MiB
  allocs estimate:  11
  --------------
  minimum time:     51.677 ms (0.00% GC)
  median time:      52.031 ms (0.00% GC)
  mean time:        55.230 ms (5.07% GC)
  maximum time:     75.032 ms (25.73% GC)
  --------------
  samples:          91
  evals/sample:     1

不带缓存的版本

测试1000000 个fib 数消耗了我大概300M内存。

julia> @benchmark collect(Iterators.take(fib,100000))
BenchmarkTools.Trial: 
  memory estimate:  2.29 MiB
  allocs estimate:  99989
  --------------
  minimum time:     626.132 μs (0.00% GC)
  median time:      660.006 μs (0.00% GC)
  mean time:        747.380 μs (8.61% GC)
  maximum time:     3.666 ms (75.19% GC)
  --------------
  samples:          6603
  evals/sample:     1
julia> @benchmark collect(Iterators.take(fib,1000000))
BenchmarkTools.Trial: 
  memory estimate:  22.89 MiB
  allocs estimate:  999989
  --------------
  minimum time:     6.449 ms (0.00% GC)
  median time:      7.836 ms (4.22% GC)
  mean time:        8.382 ms (10.72% GC)
  maximum time:     81.850 ms (87.63% GC)
  --------------
  samples:          596
  evals/sample:     1

从Slack问到了一个答案的版本

julia>  @benchmark collect(Iterators.take(fibs,1000000))
BenchmarkTools.Trial: 
  memory estimate:  22.89 MiB
  allocs estimate:  999990
  --------------
  minimum time:     7.795 ms (0.00% GC)
  median time:      9.232 ms (0.00% GC)
  mean time:        9.549 ms (10.07% GC)
  maximum time:     105.615 ms (87.36% GC)
  --------------
  samples:          523
  evals/sample:     1

配上我的versioninfo

julia> versioninfo()
Julia Version 1.4.0
Commit b8e9a9ecc6 (2020-03-21 16:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: AMD Ryzen 7 4800H with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, znver1)
Environment:
  JULIA_NUM_THREADS = 16
  JULIA_PKG_SERVER = https://kr.pkg.julialang.org

你能测试无缓存版本来对比吗?

我现在感觉我写的缓存有点不对,得去改改

又整了一个,不过你的内存分配是怎么得出来的 :yum:

我是去跑了一遍那个带缓存的版本,然后发现电脑非常卡顿,就看了下,发现内存快占用满了,从任务管理器看到julia 占用了28.8G内存。

京ICP备17009874号-2