我手痒写了一个无限的 斐波那契数列，但是我不会操作
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: 这个内存分配到底怎么看，
