Entretien avec Fibonacci

Le calcul de la série de Fibonacci est une tâche algorithmique classique, car il est souvent donné lors des entretiens quand ils veulent vérifier que le candidat, en principe, est au moins en quelque sorte capable dans les algorithmes. Supposons que vous soyez le même candidat. On vous a confié la tâche: en JavaScript, écrivez une fonction fib(n) qui retourne le nième nombre de Fibonacci. Nous considérons que le nombre de Fibonacci nul est nul. La validation de l'argument n'est pas requise. Quelles options avez-vous?

1. Pour être plus facile et les gens vous contacteront.

La solution la plus simple est un cycle banal.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Une plaisanterie. Bien sûr, vous n'avez pas besoin d'écrire comme ça - à moins, bien sûr, que vous ne soyez pas interviewé pour le poste d'obscurcisseur à temps plein.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

Vous manquez de coupons variables? cypok

D'accord, d'accord, pour encore plus de lisibilité, écrivons ceci:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

Il s'agit d'une option classique, simple et élégante. Mais peut-être voulez-vous démontrer votre connaissance d'autres concepts? Par exemple ...

2. Pour comprendre la récursivité, vous devez comprendre la récursivité

Par exemple, oui, vous pouvez démontrer que vous pouvez effectuer une récursivité. Par exemple, comme ceci:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

N'oubliez pas cette option. Cela ne vaut pas la peine. Ça ne devrait pas l'être. C'est impossible. Jamais. C'est pire que de donner des coups de pied à des chiots et c'est comparable à un petit holocauste.

Vous pouvez demander pourquoi. Dans ce cas, exécutez simplement ce code et essayez de calculer, disons, le nombre de cinquante Fibonacci. Je pense que vous ressentirez un certain retard. Une plaisanterie. Je crois que si vous exécutez ce code non pas sur un supercalculateur, alors vous n'attendrez tout simplement pas le résultat. Malgré le fait que le code simple et non récursif des exemples précédents comptera le cinquantième membre de la séquence de Fibonacci plus rapidement que vous n'avez le temps de dire le mot «cinquante» ou n'importe quelle syllabe.

Exprimée dans le langage grossier de la notation O, une telle solution a une complexité temporelle de O (e ⁿ ). Autrement dit, le temps d'exécution de cette fonction croît de façon exponentielle avec l'augmentation de n. Autrement dit, lorsque n augmente de , le temps d'exécution augmente de. En gros, si fib(45) vous avez dû attendre une heure, alors fib(46) vous attendez deux heures, fib(47) - 4 heures, et ainsi de suite. Je mâche tellement de détails que chaque lecteur, même un typographe qui s'est d'abord essayé à l'écriture de scripts, pourrait réaliser l'horreur de la situation.

C'est correct, mais trop grossier. Vous pouvez obtenir une estimation plus précise du nombre d'appels de fonction ~ (1 + sqrt (5)) fib (n) et la belle remarque "Pour calculer le nombre de Fibonacci en utilisant une méthode récursive naïve, vous avez besoin de 3,2 fois plus d'appels de fonction que le nombre de Fibonacci lui-même." Taus

Et nous obtenons une autre méthode pour le calculer. Il vous suffit d'exécuter la méthode récursive naïve, de compter le nombre d'appels de fonction et de diviser par 3,2! Cerberuser

Si vous devez résoudre ce problème de manière récursive lors d'un entretien, il s'agit très probablement d'un piège. Une récursion «correcte» fonctionnant en temps linéaire pourrait ressembler, par exemple, à ceci:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Pour résumer: malgré le fait que les nombres de Fibonacci sont un exemple classique de récursion classique, ce n'est en réalité pas le cas le plus pratique pour appliquer la récursivité. Mais vous pouvez essayer de montrer plus de connaissances.

3. Fonction commémorative

Il existe un moyen magique qui transforme une solution monstrueusement inefficace du dernier paragraphe en une solution potentiellement très rapide (mais pas sans problèmes). Son nom est mémorisation. Et si vous parlez russe - nous nous souvenons simplement des résultats des appels précédents au lieu de les calculer à nouveau.

Fondamentalement, nous ne pouvons même pas changer quoi que ce soit à l'intérieur de cette solution - il suffit d'ajouter une fonction d'emballage de memoize . Ici, pour plus de clarté, j'utilise sa version simplifiée pour une fonction avec un seul argument.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Maintenant, la fonction fib a accès à l'objet cache via la fermeture. S'il est appelé avec un argument qui n'a pas été rencontré auparavant, la valeur calculée est stockée dans le cache . Avec de nouveaux appels de fonction avec le même argument, la valeur n'a pas besoin d'être recalculée, elle sera simplement extraite du cache. Le principal problème de la «mauvaise» ancienne fonction fib était que les mêmes valeurs étaient recalculées plusieurs fois. Par exemple, pour calculer fib(45) il a été nécessaire de calculer f(44) une fois, deux fois f(43) , trois fois f(42) , cinq fois f(41) , etc.


Ainsi, les valeurs précédentes seront désormais calculées une fois, et lorsqu'elles seront à nouveau demandées - simplement extraites du cache. Pouvez-vous imaginer à quel point nous pouvons maintenant calculer plus rapidement le quarante-cinquième nombre de Fibonacci? Sérieusement, à quelle heure pensez-vous?

En fait - un peu plus lent. J'ai délibérément fait une erreur classique, souvent commise lors de la mémorisation de fonctions récursives. Lorsque fib(45) appelé «sous le capot», oldFib(45) est appelé, ce qui appelle oldFib(44) et oldFib(43) pour ses besoins ... Sentez-vous le piège? Ci-après, il existe déjà des appels à une fonction régulière non mémorisée. Bien sûr, lorsque vous appelez à nouveau fib(45) , nous obtenons instantanément le résultat du cache - cependant, le premier appel n'a pas accéléré du tout. Pour résoudre ce problème, vous devez toujours obtenir oldFib sous le fond de la clé:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Super! Maintenant, le premier appel à fib(45) fonctionnera à une vitesse comparable à la version avec boucle. Et les autres défis fonctionneront généralement en temps constant ... Oups! Encore une fois trompé. L'obtention de la valeur de la propriété d'un objet par clé est une opération rapide, mais O (1) n'est toujours qu'en moyenne, dans le pire des cas, il peut se dégrader en O (n). Pour le rendre très bon, dans notre cas, nous pouvons changer le type de cache d'un objet à un tableau.

Bien sûr, il ne faut pas oublier que la mémorisation nécessite de la mémoire. Et tandis que nous réduisons la complexité temporelle, la complexité de la mémoire passe de O (1) à O (n).

Comment montrer autrement? Par exemple, démontrer votre connaissance approfondie des mathématiques

4. M. Binet

Il existe une science merveilleuse et spéciale sur la façon de transformer les relations de récurrence en formules explicites. Ici, nous n'entrerons pas dans ses détails. Nous dirons seulement que pour les nombres de Fibonacci, en utilisant des arguments assez simples, nous pouvons dériver la formule suivante, connue sous le nom de formule de Binet:

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5}$$

Cependant, c'est un langage assez mathématique, nous l'écrivons en JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Conduisons sur les premiers chiffres. Génial, tout semble fonctionner. Voici 13, voici 21, voici 34, voici ... 54.9999999999999999?

Oui, bien sûr, un tel résultat est logique. La formule de Binet est mathématiquement précise, mais l'ordinateur fonctionne avec des fractions de précision finie, et une erreur peut s'accumuler pendant les opérations avec eux, ce qui s'est produit dans ce cas. Cependant, nous pouvons y remédier. Sachant que le soustrait dans le numérateur sera toujours de faible amplitude, nous pouvons simplifier la formule à l'état suivant:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

Ici, les crochets étranges inachevés signifient l'entier le plus proche, c'est-à-dire l'arrondi. Réécrivez notre code:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Oui, c’est beaucoup mieux. Nous pouvons voir à la fois 55 et 89, et même mon numéro de Fibonacci préféré est 144 (que j'aime parce qu'il équivaut à douze carrés). Tout ira bien jusqu'au nombre 76. Ce qui devrait être égal à 3416454622906707, et notre fonction calculera 3416454622906706. Parce que le problème de la précision limitée des nombres fractionnaires n'a pas disparu, nous l'avons juste poussé plus profondément et espéré qu'il ne reviendrait pas. Comme le montre cet exemple, ils espéraient en vain.

En fait, nous pouvons faire autre chose pour enregistrer cette méthode. Mais plus à ce sujet ci-dessous. En attendant - blagues à part. Parlons de la méthode dure, hardcore et brutale.

5. Suivez le lapin blanc.

Ils disent que si vous avez un problème et que l'idée vous est venue de le résoudre avec des expressions régulières, vous avez maintenant deux problèmes. Les matrices sont au contraire des expressions régulières. De nombreux problèmes, s'ils sont reformulés dans le langage des matrices, sont résolus simplement par eux-mêmes.

Quant aux nombres de Fibonacci, pour eux en langage matriciel vous pouvez écrire cette identité évidente:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

Autrement dit, si nous prenons une paire de nombres de Fibonacci consécutifs et les multiplions par une matrice aussi simple, nous obtenons la paire suivante. Et la conclusion logique en découle: si nous prenons une paire de zéro et de premiers nombres de Fibonacci, c'est-à-dire zéro et un, et les multiplions par cette matrice à une nième puissance, nous obtenons une paire de nième et en plus le premier Fibonacci. C'est-à-dire, parler humainement:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

Vous pouvez simplifier cela un peu plus en abandonnant les vecteurs. En fait, toutes les valeurs nécessaires sont contenues dans la matrice elle-même:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} & F_ {n + 1 } \ end {pmatrix}$$

Super, non? Reste à comprendre, quoi pour l'harmonie du cul, s'il n'est pas philharmonique. Je veux dire - pourquoi ces difficultés sont-elles sur le bleu. Et la réponse est simple: une exponentiation rapide.

Combien de multiplications élémentaires faut-il pour calculer, disons, 2 ¹⁰ ? Une personne normale dira neuf. Deux fois - quatre. Deux à quatre - huit. Deux fois huit seize. Et ainsi de suite. Une personne rusée dira que quatre.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

Le programmeur dira. qu'il se souvient de ce nombre par cœur, et rien n'a besoin d'être multiplié. Cependant, nous avons discuté des problèmes de mémorisation ci-dessus.

Ainsi, une exponentiation rapide est également applicable aux matrices, et nous permet ainsi de réduire la complexité temporelle asymptotique de notre fonction de O (n) à O (log n). Et c'est très cool - à moins, bien sûr, que cette complexité ne soit vraiment si importante pour nous. Écrivons le code:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

Nous avons donc obtenu l'algorithme le plus rapide du Far West. Et cela, contrairement à la plupart des précédents, peut être démontré de manière non ironique lors d'une interview. Et dans certains endroits mathématiques, on attendra de vous.

PS

J'ai promis une remarque sur la façon de sauvegarder une méthode basée sur la formule de Binet. La réponse réside dans mon article. Là, pour les besoins de l'économie nationale, j'ai écrit une classe spéciale, la racine de cinq nombres rationnels, qui, sans perte de précision, peut stocker les résultats des opérations arithmétiques sur des entiers et une racine de cinq. Vous pouvez prendre ce cours, le compléter avec la méthode d'arrondi et l'utiliser pour rechercher des nombres de Fibonacci en utilisant la formule de Binet. Et puis injectez de l'oxyde nitreux en appliquant une exponentiation rapide.

Et ce qui est le plus intéressant: si vous regardez attentivement quels nombres seront obtenus dans le processus, quelles opérations seront effectuées, il deviendra clair que cette méthode est la même multiplication matricielle, uniquement sous une façade différente. La seule différence est de savoir si nous stockons des nombres dans des tableaux à deux dimensions ou dans les champs d'un objet d'une classe spéciale.

C’est tout. Si vous pensez que j'ai raté d'autres façons intéressantes de trouver des chiffres dont personne n'a besoin, assurez-vous d'écrire à ce sujet dans les commentaires.

Il existe également une méthode telle que le doublement rapide . Il fonctionne comme la multiplication matricielle en O (log), mais avec une constante plus petite en asymptotique (et en pratique). En bref, deux formules y sont utilisées, en se basant sur lesquelles on peut rapidement revenir à des indices deux fois inférieurs de manière récursive:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

La mise en œuvre, soit dit en passant, est assez compacte.

Comparaison de la vitesse des différentes méthodes

just_maksim