Skip to content

Instantly share code, notes, and snippets.

@ParthBarot-BoTreeConsulting
Last active August 31, 2017 12:06
Show Gist options
  • Save ParthBarot-BoTreeConsulting/1d2a0a8b7ca073fb60e85d529f781725 to your computer and use it in GitHub Desktop.
Save ParthBarot-BoTreeConsulting/1d2a0a8b7ca073fb60e85d529f781725 to your computer and use it in GitHub Desktop.
Ruby Vs Python Vs Golang

Ruby version

#Recursive version which we will write mostly!
def fibonacciVal(n)
  if n == 0
    return 0
  elsif n == 1
    return 1
  else
    return fibonacciVal(n-1) + fibonacciVal(n-2)
  end
end

#Memoized version ... Just see the difference in execution
def fibonacciValNew(n)
  memo = [0] * (n+1)
  memo[0], memo[1] = 0, 1
  for i in (2..n+1)
    memo[i] = memo[i-1] + memo[i-2]
  end
  return memo[n]
end

t1 = Time.now
fibonacciVal(40)
puts "Time taken =====> #{(Time.now - t1) * 1000}"

t2 = Time.now
fibonacciValNew(40)
puts "Time taken =====> #{(Time.now - t2) * 1000}"

Python version

#Memoized version ... Just see the difference in execution
def fibonacciVal(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fibonacciVal(n-1) + fibonacciVal(n-2)
  

#Memoized version ... Just see the difference in execution
def fibonacciValNew(n):
  memo = [0] * (n+1)
  memo[0], memo[1] = 0, 1
  for i in range(2, n+1):
    memo[i] = memo[i-1] + memo[i-2]
  return memo[n]

t1 = time.time()
fibonacciVal(40)
print((time.time() - t1) * 1000)

t2 = time.time()
fibonacciValNew(40)
print((time.time() - t2) * 1000)

Golang version

package main

import (
      "fmt"
      "time"
)

func main() {
  t1 := time.Now()
  fmt.Println(fibonacciVal(40))
  fmt.Println("Time taken ==========> ", time.Since(t1))
  t2 := time.Now()
  fmt.Println(fibonacciValNew(40))
  fmt.Println("Time taken ==========> ", time.Since(t2))
}

// Recursive version which we will write mostly!
func fibonacciVal(n int) (int) {
  if n == 0 {
    return 0
  } else if n == 1 {
    return 1
  } else {
    return (fibonacciVal(n-1) + fibonacciVal(n-2))
  }
}

// Memoized version ... Just see the difference in execution
func fibonacciValNew(n int) (int) {
  
  rangeArr := make([]int, n+2)
  memo := make([]int, n+2)

  for i := 1; i < n+2; i++ {
    rangeArr[i] = i
  }
  
  memo[1] = 1
  for i := 2; i < n+2; i++ {
    memo[i] = (memo[i-1] + memo[i-2])
  }
  
  return memo[n]
}

Results

Time in ms Ruby Python 2.7 GoLang
Recursive Algo 25410.060878 33261.4440918 806.313542
Memoized Algo 1.715674 0.661849975586 0.007878

Ruby seems working fine in recursion, compared to python. But in datastructur-ed memoization, python works faster. And golang out performs both of them - 806 ms compared to 25.4 and 33.3 seconds!

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