Algorithms

Chercher une clé dans un dict Python contenant dix entrées prend le même temps que dans un dict qui en contient dix millions. Ce n’est pas un hasard lié à un langage rapide. Le dict de Python, le HashMap de Java et la Map de JavaScript sont tous des tables de hachage, et toute leur conception vise à faire tourner recherche, insertion et suppression en O(1) en moyenne. La notation Big O donne à cette recherche l’étiquette “temps constant”. Voici le mécanisme qui la justifie. ...

<.+> appliqué à <b>bold</b> and <i>italic</i> ne trouve pas <b>. Il trouve la chaîne entière, du premier < au tout dernier >. Rien n’est cassé. C’est exactement ce qu’un quantificateur greedy est censé faire, et c’est aussi le bug le plus courant de “mon regex matche trop”. Une fois que vous savez ce que fait le moteur pendant qu’il lit votre motif, ce bug et la plupart de ses cousins arrêtent d’être des mystères. ...

Une fonction qui s’appelle elle-même a une profondeur maximale, et elle est plus petite que ce que la plupart des gens imaginent : 1 000 appels dans CPython par défaut, à peu près 10 000 à 15 000 dans Node et dans les moteurs des navigateurs, selon ce que chaque frame contient. Dépasser cette limite ne ralentit pas le programme. Il plante. Python lève RecursionError: maximum recursion depth exceeded ; JavaScript lève RangeError: Maximum call stack size exceeded. ...

Exécutez 0.1 + 0.2 dans un shell Python et vous n’obtenez pas 0.3. Vous obtenez 0.30000000000000004. Essayez en JavaScript, Java, Go, C ou Rust et vous retrouvez la même traîne de dix-sept chiffres. Chacun de ces langages fait exactement ce que lui impose le matériel. Un nombre qui demanderait une infinité de chiffres binaires est compressé dans 64 bits, et quelque chose doit céder. Pourquoi 0.1 ne peut pas être stocké exactement en binaire Les ordinateurs stockent les nombres à virgule flottante en base 2. En base 2, la fraction 1/10 a un développement périodique, tout comme 1/3 se répète indéfiniment en base 10 (0.3333...). Développé en détail, 0.1 en binaire commence ainsi : ...

Une recherche dans un dictionnaire Python prend environ 100 nanosecondes, que le dictionnaire contienne 1 000 clés ou 1 000 000. Une double boucle qui cherche des doublons dans une liste prend une demi-milliseconde sur 200 éléments et 136 millisecondes sur 3 200. Seize fois l’entrée, presque 280 fois l’attente. Même machine, même Python. La notation Big O est le nom de cette différence. Ce que mesure la notation Big O Big O décrit comment le temps d’exécution (ou l’utilisation de la mémoire) d’un morceau de code croît quand l’entrée grandit. Ce n’est pas une mesure au chronomètre, et peu importe que votre ordinateur soit rapide ou lent. Ce qui compte, c’est la forme de la courbe de croissance : quand vous doublez l’entrée, le temps double-t-il, quadruple-t-il, ou bouge-t-il à peine ? ...