Skip to content

Instantly share code, notes, and snippets.

@BetterProgramming
Created September 24, 2020 19:19
Show Gist options
  • Save BetterProgramming/d23d2f140a3f09720e1913fff424f065 to your computer and use it in GitHub Desktop.
Save BetterProgramming/d23d2f140a3f09720e1913fff424f065 to your computer and use it in GitHub Desktop.
package main
import (
"log"
"time"
)
func main(){
input := 50
//Recursion
start := time.Now()
result := expensiveFib(input)
defer trackTime(start, result, "Recursion")
//Loop
fibByLoop(input)
//Memoization
memoize(input)
}
/* function for measuring the execution the */
func trackTime(start time.Time, result int, name string) {
elapsed := time.Since(start)
log.Printf("---> %s solution | result: %v | took: %s", name, result, elapsed)
}
/* Recursion solution */
func expensiveFib(n int) int {
if n < 2 {
return n
}
result := expensiveFib(n-1) + expensiveFib(n-2)
return result
}
/* using loop */
func fibByLoop(n int) int {
fibBox := []int{0, 1}
for i := int(0); i < n; i++ {
v := fibBox[i] + fibBox[i+1]
fibBox = append(fibBox, v)
}
result := int(fibBox[n])
defer trackTime(time.Now(), result, "Loop")
return result
}
/* Memoization solution */
// using memoization
func refinedExpensiveFib(n int, cache map[int]int) int {
if n < 2 {
cache[n] = n // n is either 0 or 1
return n
}
// check cache before calling the function recursively
if _, ok := cache[n-1]; !ok {
// we haven't come across n-1 before
cache[n-1] = refinedExpensiveFib(n-1, cache)
}
// At this point, n-1 is in the cache. You could log n-1
if _, ok := cache[n-2]; !ok {
// we haven't come across n-2 before
cache[n-2] = refinedExpensiveFib(n-2, cache)
}
// At this point, n-2 is in the cache. You could log n-2
// returns the summed up cache
return cache[n-1] + cache[n-2]
}
func memoize(n int) int {
cache := make(map[int]int)
bucket := make([]int, n)
for i := 1; i <= n; i++{
bucket[i-1] = refinedExpensiveFib(i, cache)
}
result := bucket[n-1]
defer trackTime(time.Now(), result, "Memoization")
return result
}
@D-sense
Copy link

D-sense commented Aug 28, 2022

Hi. I notice bugs here. Please could you update the code to the one pasted below? Thanks

package main

import (
	"log"
	"time"
)

func main() {
	input := 50

	//Recursion
	start := time.Now()
	result := expensiveFib(input)
	defer trackTime(start, result, "Recursion")

	//Loop
	fibByLoop(input)

	//Memoization
	memoize(input)
}

/* function for measuring the execution the */
func trackTime(start time.Time, result int, name string) {
	elapsed := time.Since(start)
	log.Printf("---> %s solution | result: %v | took: %s", name, result, elapsed)
}

/* Recursion solution */
func expensiveFib(n int) int {
	if n < 2 {
		return n
	}

	result := expensiveFib(n-1) + expensiveFib(n-2)

	return result
}

/* using loop */
func fibByLoop(n int) int {
	startTime := time.Now()
	fibBox := []int{0, 1}

	for i := int(0); i < n; i++ {
		v := fibBox[i] + fibBox[i+1]
		fibBox = append(fibBox, v)
	}

	result := int(fibBox[n])
	defer trackTime(startTime, result, "Loop")

	return result
}

/* Memoization solution */
// using memoization
func refinedExpensiveFib(n int, cache map[int]int) int {
	if n < 2 {
		cache[n] = n // n is either 0 or 1
		return n
	}

	// check cache before calling the function recursively
	if _, ok := cache[n-1]; !ok {
		// we haven't come across n-1 before
		cache[n-1] = refinedExpensiveFib(n-1, cache)
	}
	// At this point, n-1 is in the cache. You could log n-1

	if _, ok := cache[n-2]; !ok {
		// we haven't come across n-2 before
		cache[n-2] = refinedExpensiveFib(n-2, cache)
	}
	// At this point, n-2 is in the cache. You could log n-2

	// returns the summed up cache
	return cache[n-1] + cache[n-2]
}

func memoize(n int) int {
	startTime := time.Now()
	cache := make(map[int]int)
	bucket := make([]int, n)

	for i := 1; i <= n; i++ {
		bucket[i-1] = refinedExpensiveFib(i, cache)
	}

	result := bucket[n-1]
	defer trackTime(startTime, result, "Memoization")
	return result
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment