Skip to content

Instantly share code, notes, and snippets.

@XanderStrike

XanderStrike/fibs.rb

Last active August 29, 2015 14:23
Show Gist options
  • Save XanderStrike/9798d68e0dc7b2289c9c to your computer and use it in GitHub Desktop.
Save XanderStrike/9798d68e0dc7b2289c9c to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. XanderStrike revised this gist Jun 27, 2015. 1 changed file with 7 additions and 5 deletions.
    12 changes: 7 additions & 5 deletions fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -20,14 +20,16 @@ def linear_fib(n)

    # === gooder ===
    def linear_cached_fib(n)
    (2..n-1).each_with_object([1, 1]) do |i, arr|
    a = arr[0] + arr[1]
    arr = [arr[1], a]
    cache = [1, 1]
    (2..n-1).each do |i|
    a = cache[0] + cache[1]
    cache = [cache[1], a]
    end
    cache
    end

    puts Benchmark.measure { linear_cached_fib(7_500_000) }
    # 0.980000 0.270000 1.250000 ( 1.255176)
    puts Benchmark.measure { linear_cached_fib(200_000) }
    # 0.630000 0.430000 1.060000 ( 1.059694)

    # === stupid good ===
    def fast_double_fib(n)
  2. XanderStrike revised this gist Jun 27, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,7 @@ def linear_fib(n)
    puts Benchmark.measure { linear_fib(200_000) }
    # 0.760000 0.460000 1.220000 ( 1.222171)

    # === slightly gooder ===
    # === gooder ===
    def linear_cached_fib(n)
    (2..n-1).each_with_object([1, 1]) do |i, arr|
    a = arr[0] + arr[1]
  3. XanderStrike revised this gist Jun 27, 2015. 1 changed file with 13 additions and 2 deletions.
    15 changes: 13 additions & 2 deletions fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -15,9 +15,20 @@ def linear_fib(n)
    (2..n-1).each_with_object([1, 1]) { |i, arr| arr << arr[-1] + arr[-2] }.last
    end

    puts Benchmark.measure { linear_fib(200000) }
    puts Benchmark.measure { linear_fib(200_000) }
    # 0.760000 0.460000 1.220000 ( 1.222171)

    # === slightly gooder ===
    def linear_cached_fib(n)
    (2..n-1).each_with_object([1, 1]) do |i, arr|
    a = arr[0] + arr[1]
    arr = [arr[1], a]
    end
    end

    puts Benchmark.measure { linear_cached_fib(7_500_000) }
    # 0.980000 0.270000 1.250000 ( 1.255176)

    # === stupid good ===
    def fast_double_fib(n)
    if n == 0
    @@ -35,5 +46,5 @@ def fast_double_fib(n)
    end
    end

    puts Benchmark.measure { fast_double_fib(10000000) }
    puts Benchmark.measure { fast_double_fib(10_000_000) }
    # 1.870000 0.010000 1.880000 ( 1.887631)
  4. XanderStrike revised this gist Jun 27, 2015. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -2,23 +2,23 @@

    require 'benchmark'

    # stupid
    # === stupid ===
    def recursive_fib(n)
    n <= 1 ? n : recursive_fib(n-1) + recursive_fib(n-2);
    end

    puts Benchmark.measure { recursive_fib(35) }
    # 1.140000 0.000000 1.140000 ( 1.146576)

    # good
    # === good ===
    def linear_fib(n)
    (2..n-1).each_with_object([1, 1]) { |i, arr| arr << arr[-1] + arr[-2] }.last
    end

    puts Benchmark.measure { linear_fib(200000) }
    # 0.760000 0.460000 1.220000 ( 1.222171)

    # stupid good
    # === stupid good ===
    def fast_double_fib(n)
    if n == 0
    return 0, 1
  5. XanderStrike revised this gist Jun 27, 2015. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -3,11 +3,11 @@
    require 'benchmark'

    # stupid
    def fib(n)
    n <= 1 ? n : fib(n-1) + fib(n-2);
    def recursive_fib(n)
    n <= 1 ? n : recursive_fib(n-1) + recursive_fib(n-2);
    end

    puts Benchmark.measure { fib(35) }
    puts Benchmark.measure { recursive_fib(35) }
    # 1.140000 0.000000 1.140000 ( 1.146576)

    # good
  6. XanderStrike created this gist Jun 27, 2015.
    39 changes: 39 additions & 0 deletions fibs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,39 @@
    # ruby fibs

    require 'benchmark'

    # stupid
    def fib(n)
    n <= 1 ? n : fib(n-1) + fib(n-2);
    end

    puts Benchmark.measure { fib(35) }
    # 1.140000 0.000000 1.140000 ( 1.146576)

    # good
    def linear_fib(n)
    (2..n-1).each_with_object([1, 1]) { |i, arr| arr << arr[-1] + arr[-2] }.last
    end

    puts Benchmark.measure { linear_fib(200000) }
    # 0.760000 0.460000 1.220000 ( 1.222171)

    # stupid good
    def fast_double_fib(n)
    if n == 0
    return 0, 1
    else
    a, b = fast_double_fib(n / 2)
    c = a * (b * 2 - a)
    d = a * a + b * b
    d = a * a + b * b
    if n % 2 == 0
    return c, d
    else
    return d, c + d
    end
    end
    end

    puts Benchmark.measure { fast_double_fib(10000000) }
    # 1.870000 0.010000 1.880000 ( 1.887631)