Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

start

This is JavaScript

How many students write out is the following code, honest to me stand out 😂

    const fibonacci = function(n) {
        if (n < 2) {
            return n
        }
        return fibonacci(n - 1) + fibonacci(n - 2)}Copy the code

There are two problems with this code, and let’s look at them

Let’s throw the code into the force button and see if it works

It can be found that the force button prompt exceeds the time limit

In fact, the code itself is not wrong, we can use caching to optimize the code

Let’s take a look at the pre-optimization and post-optimization code execution times.

Directly from 20s => 0.13ms

Resolve out of time limit

The idea is to create a Map that returns the cached value of n if n is already recorded

    const map = new Map(a)const fibonacci = function(n) {
        if (n < 2) {
            return n
        }
        if (map.get(n)) {
            // If there is a map, fetch it directly
            return map.get(n)
        }
        let result = fibonacci(n - 1) + fibonacci(n - 2)
        // Set to map
        map.set(n, result)
        return result
    }
Copy the code

The cache piece is generic and can be used in many places to improve performance

Good! Let’s just throw the code into the force button and see if we can commit this time

As you can see, the time limit exceeded has been resolved, this time prompt solution error

excuse me??? Logic should be ok ah, why should prompt answer error

Let’s look at the picture above. When n is 45, the expected result is 134903163, but ours is 1134903170

And we see in the problem, there’s this statement

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Why module 1000000007? because

  1. Large numbers add up out of range
  2. 1000000007 is a prime number (prime number), mod to prime number to avoid conflict to the greatest extent
  3. The maximum value of int64 bits is 2^63-1, and for 1000000007 its square will not overflow in INT64

The final code

    const map = new Map(a)const fibonacci = function(n) {
        if (n < 2) {
            return n
        }
        if (map.get(n)) {
            // If there is a map, fetch it directly
            return map.get(n)
        }
        let result = fibonacci(n - 1) + fibonacci(n - 2)
        // If the calculated result is greater than 1000000007, modulo it
        result >= 1000000007 && (result = result % 1000000007)
        // Set to map
        map.set(n, result)
        return result
    }
Copy the code

You can see that the buckle was successfully committed ~~

conclusion

Article content is very low, do not like spray. Any errors or comments can be pointed out in the comments section, mainly to show you the role of caching and the value range of small knowledge, thank you