StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Two things can be optimized a lot with one little change in your code. These two things are:</p> <ul> <li><p>You compute each fibonacci number using two other fibonacci numbers, resulting in an exponential complexity (which explodes even if you'd only compute a single but high fibonacci number).</p></li> <li><p>You don't remember any previous computed fibonacci number to compute the next in your loop.</p></li> </ul> <p>Simply remember all computed fibonacci numbers as a private implementation detail in <code>Fibonacci</code> and you get rid of both performance problems. You can do this by using a simple dynamic array to which you add the result if it wasn't cached before.</p> <p>Pseudo-code (I don't speak Python but this can be easily implemented):</p> <pre><code>def Fibonacci(NthTerm): if (cache contains NthTerm) return cache[NthTerm] else FibValue = Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2) cache[NthTerm] = FibValue return FibValue </code></pre> <p>This will result in very restricted recurion, since you compute the N-th fibonacci number only if you already know (and cached) the (N-1)-th number.</p> <p>This optimization works even if you need <em>any</em> fibonacci number (for future problems), but in this particular case we know that we only need to remember the last two numbers since we're never going to ask for old numbers again. So you don't need a whole list of numbers but only two, which you "cycle through" for each step in your main loop. Something like</p> <pre><code>f1, f2 = f2, f1 + f2 </code></pre> <p>within the loop and an initialization like</p> <pre><code>f1, f2 = 1, 1 </code></pre> <p>will essentially replace your function <code>Fibonacci</code> and its performance problems, but it restricts you to this limited use case.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload