Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Some experiments for memoization functions on Fibonacci sequence. */
- /* This uses the SpiderMonkey JS Shell functions print and dateNow for its output. */
- let
- fix=
- f=>(
- (f=>f(f))
- (g=>f((...a)=>g(g)(...a)))),
- memo=
- f=>(
- (map=>a=>(
- map.has(a)
- ?map.get(a)
- :map.set(a,f(a)).get(a)))
- (new Map)),
- fixmemo =
- f=>(
- (map=>fix(
- z=>a=>(
- map.has(a)
- ?map.get(a)
- :map.set(a,f(b=>z(b))(a)).get(a))))
- (new Map)),
- memocurried=
- ((m=>fix(
- z=>f=>l=>(
- m((0<l?z(f)(l-1):f)))))
- (memo)),
- time=
- f=>(
- (n=>[f(),dateNow()-n])
- (dateNow())),
- memfib=
- memo(
- n=>(
- n===0
- ?0
- :n===1
- ?1
- :memfib(n-1)+memfib(n-2))),
- memofib=(
- memocurried(
- n=>(
- n===0
- ?0
- :n===1
- ?1
- :(memofib(n-1)+memofib(n-2))))
- (1)),
- fmfib=
- fixmemo(
- fib=>n=>(
- n===0
- ?0
- :n===1
- ?1
- :fib(n-1)+fib(n-2))),
- Fibonacci=
- fix(
- fib=>n=>(
- n===0
- ?0
- :n===1
- ?1
- :fib(n-1)+fib(n-2))),
- recfromcorec=(
- (f,...a) => fix(
- z => n => (
- a.length > n
- ? a[n]
- : (a[a.length]=f(),z(n))))),
- cofibs=
- (m=0,n=1,o)=>(
- ()=>(
- [m,n,o]=[n,m+n,m],
- o)),
- fibco=recfromcorec(cofibs()),
- fdfib=(
- (f=>n=>(
- n<0
- ?(()=>{throw 'Fibonacci takes a positive integral argument.'})()
- :f(n)[0]))
- (fix(
- z=>n=>(
- n===0
- ?[0,1]
- :(
- (([a,b])=>(
- ((c,d)=>(
- n%2===0
- ?[c,d]
- :[d,c+d]))
- (a*(b*2-a),a*a+b*b)))
- (z(Math.floor(n/2))))))))
- ;
- print(
- 'Unmemoized: fib(0x20):\n\t',
- time(()=>Fibonacci(0x20)),'\n\t',
- time(()=>Fibonacci(0x20)));
- print(
- 'Memoized: fib(0x20):\n\t',
- time(()=>memfib(0x20)),'\n\t',
- time(()=>memfib(0x20)));
- print(
- 'Curry memoized: fib(0x20):\n\t',
- time(()=>memofib(0x20)),'\n\t',
- time(()=>memofib(0x20)));
- print(
- 'Fixmemoized: fib(0x20):\n\t',
- time(()=>fmfib(0x20)),'\n\t',
- time(()=>fmfib(0x20)));
- print(
- 'Corecursion: fib(0x20):\n\t',
- time(()=>fibco(0x20)),'\n\t',
- time(()=>fibco(0x20)));
- print(
- 'Fast Doubling Fibbonacci algorithm: fib(0x20):\n\t',
- time(()=>fdfib(0x20)),'\n\t',
- time(()=>fdfib(0x20)));
- print(
- 'Memoized: fib(0x40):\n\t',
- time(()=>memfib(0x40)),'\n\t',
- time(()=>memfib(0x40)));
- print(
- 'Curry memoized: fib(0x40):\n\t',
- time(()=>memofib(0x40)),'\n\t',
- time(()=>memofib(0x40)));
- print(
- 'Fixmemoized: fib(0x40):\n\t',
- time(()=>fmfib(0x40)),'\n\t',
- time(()=>fmfib(0x40)));
- print(
- 'Corecursion: fib(0x40):\n\t',
- time(()=>fibco(0x40)),'\n\t',
- time(()=>fibco(0x40)));
- print(
- 'Fast Doubling Fibbonacci algorithm: fib(0x40):\n\t',
- time(()=>fdfib(0x40)),'\n\t',
- time(()=>fdfib(0x40)));
- print(
- 'Memoized: fib(0x400):\n\t',
- time(()=>memfib(0x400)),'\n\t',
- time(()=>memfib(0x400)));
- print(
- 'Curry memoized: fib(0x400):\n\t',
- time(()=>memofib(0x400)),'\n\t',
- time(()=>memofib(0x400)));
- print(
- 'Fixmemoized: fib(0x400):\n\t',
- time(()=>fmfib(0x400)),'\n\t',
- time(()=>fmfib(0x400)));
- print(
- 'Corecursion: fib(0x400):\n\t',
- time(()=>fibco(0x400)),'\n\t',
- time(()=>fibco(0x400)));
- print(
- 'Fast Doubling Fibbonacci algorithm: fib(0x400):\n\t',
- time(()=>fdfib(0x400)),'\n\t',
- time(()=>fdfib(0x400)));
- print(
- 'Memoized: fib(0x800):\n\t',
- time(()=>memfib(0x800)),'\n\t',
- time(()=>memfib(0x800)));
- print(
- 'Curry memoized: fib(0x800):\n\t',
- time(()=>memofib(0x800)),'\n\t',
- time(()=>memofib(0x800)));
- print(
- 'Fixmemoized: fib(0x800):\n\t',
- time(()=>fmfib(0x800)),'\n\t',
- time(()=>fmfib(0x800)));
- print(
- 'Corecursion: fib(0x800):\n\t',
- time(()=>fibco(0x800)),'\n\t',
- time(()=>fibco(0x800)));
- print(
- 'Fast Doubling Fibbonacci algorithm: fib(0x800):\n\t',
- time(()=>fdfib(0x800)),'\n\t',
- time(()=>fdfib(0x800)));
- print(
- 'Memoized: fib(0x1000):\n\t',
- time(()=>memfib(0x1000)),'\n\t',
- time(()=>memfib(0x1000)));
- print(
- 'Curry memoized: fib(0x1000):\n\t',
- time(()=>memofib(0x1000)),'\n\t',
- time(()=>memofib(0x1000)))
- print(
- 'Fixmemoized: fib(0x1000):\n\t',
- time(()=>fmfib(0x1000)),'\n\t',
- time(()=>fmfib(0x1000)));
- print(
- 'Corecursion: fib(0x1000):\n\t',
- time(()=>fibco(0x1000)),'\n\t',
- time(()=>fibco(0x1000)));
- print(
- 'Fast Doubling Fibbonacci algorithm: fib(0x1000):\n\t',
- time(()=>fdfib(0x1000)),'\n\t',
- time(()=>fdfib(0x1000)));
- /* RESULTS:
- Unmemoized: fib(0x20):
- 2178309,13702.607177734375
- 2178309,14864.7529296875
- Memoized: fib(0x20):
- 2178309,0.52783203125
- 2178309,0.008056640625
- Curry memoized: fib(0x20):
- 2178309,0.2958984375
- 2178309,0.0048828125
- Fixmemoized: fib(0x20):
- 2178309,36.14892578125
- 2178309,0.0048828125
- Corecursion: fib(0x20):
- 2178309,0.6240234375
- 2178309,0.0048828125
- Fast Doubling Fibbonacci algorithm: fib(0x20):
- 2178309,0.281982421875
- 2178309,0.575927734375
- Memoized: fib(0x40):
- 10610209857723,0.310791015625
- 10610209857723,0.005859375
- Curry memoized: fib(0x40):
- 10610209857723,0.154052734375
- 10610209857723,0.0048828125
- Fixmemoized: fib(0x40):
- 10610209857723,0.380126953125
- 10610209857723,0.076171875
- Corecursion: fib(0x40):
- 10610209857723,0.27685546875
- 10610209857723,0.006103515625
- Fast Doubling Fibbonacci algorithm: fib(0x40):
- 10610209857723,0.14306640625
- 10610209857723,0.078125
- Memoized: fib(0x400):
- 4.506699633677816e+213,2.569091796875
- 4.506699633677816e+213,0.015869140625
- Curry memoized: fib(0x400):
- 4.506699633677816e+213,0.67919921875
- 4.506699633677816e+213,0.008056640625
- Fixmemoized: fib(0x400):
- 4.506699633677816e+213,12.121826171875
- 4.506699633677816e+213,0.01611328125
- Corecursion: fib(0x400):
- 4.506699633677816e+213,12.364990234375
- 4.506699633677816e+213,0.010986328125
- Fast Doubling Fibbonacci algorithm: fib(0x400):
- 4.506699633677817e+213,0.1259765625
- 4.506699633677817e+213,0.136962890625
- Memoized: fib(0x800):
- Infinity,0.322998046875
- Infinity,0.00390625
- Curry memoized: fib(0x800):
- Infinity,0.906982421875
- Infinity,0.01318359375
- Fixmemoized: fib(0x800):
- Infinity,6.6689453125
- Infinity,0.011962890625
- Corecursion: fib(0x800):
- Infinity,1.593994140625
- Infinity,0.0068359375
- Fast Doubling Fibbonacci algorithm: fib(0x800):
- Infinity,0.0869140625
- Infinity,0.06689453125
- Memoized: fib(0x1000):
- Infinity,0.658935546875
- Infinity,0.006103515625
- Curry memoized: fib(0x1000):
- Infinity,1.137939453125
- Infinity,0.006103515625
- Fixmemoized: fib(0x1000):
- Infinity,11.991943359375
- Infinity,0.012939453125
- Corecursion: fib(0x1000):
- Infinity,3.60107421875
- Infinity,0.012939453125
- Fast Doubling Fibbonacci algorithm: fib(0x1000):
- NaN,0.10205078125
- NaN,0.0791015625
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement