Cerca una chiave in un dict Python con dieci elementi e ci metti lo stesso tempo che cercarla in un dict con dieci milioni. Non è un caso dovuto a un linguaggio veloce. Il dict di Python, la HashMap di Java e la Map di JavaScript sono tutte hash table, e l’intero design esiste per far girare lookup, inserimento e cancellazione in O(1) in media. La notazione Big O chiama questa lookup “tempo costante”. Ecco il meccanismo che se lo merita. ...
<.+> contro <b>bold</b> and <i>italic</i> non trova <b>. Trova l’intera stringa, dal primo < all’ultimo >. Non c’è nessun bug. È esattamente quello che un quantificatore greedy deve fare, ed è anche il bug più comune in assoluto quando “il regex matcha troppo”. Una volta capito cosa fa il motore mentre legge il pattern, questo bug e i suoi parenti smettono di essere misteriosi. Come un Motore Regex Legge il Pattern Un motore regex non confronta il pattern con la stringa come si confrontano due stringhe per uguaglianza. I motori che usi ogni giorno (re di Python, RegExp di JavaScript, PCRE, .NET, Java) sono regex-directed: scorrono il pattern da sinistra a destra, token per token, e per ogni token provano a consumare caratteri dalla stringa nella posizione attuale. Quando un token trova corrispondenza, il motore avanza sia il puntatore del pattern che quello della stringa. Quando un token fallisce, il motore fa backtracking: torna all’ultimo punto in cui aveva una scelta, come un quantificatore che poteva fermarsi prima o un ramo di un’alternanza non ancora provato, e prova l’altra opzione. ...
Una funzione che richiama se stessa ha una profondità massima, ed è più piccola di quanto la maggior parte delle persone si aspetti: 1.000 chiamate in CPython di default, circa 10.000-15.000 in Node e nei motori dei browser, a seconda di quanto pesa ogni frame. Superarla non significa che il programma rallenta: crasha. Python solleva RecursionError: maximum recursion depth exceeded; JavaScript solleva RangeError: Maximum call stack size exceeded. Entrambi gli errori hanno la stessa causa, e una volta vista capisci subito quando la ricorsione è lo strumento giusto e quando diventa un rischio. ...
Esegui 0.1 + 0.2 in una shell Python e non ottieni 0.3. Ottieni 0.30000000000000004. Prova in JavaScript, Java, Go, C o Rust e trovi la stessa coda di sedici cifre. Ognuno di questi linguaggi fa esattamente quello che impone lo standard hardware. Un numero che richiederebbe infinite cifre binarie viene compresso in 64 bit, e qualcosa deve cedere. Perché 0.1 non si può memorizzare esattamente in binario I computer memorizzano i numeri in virgola mobile in base 2. In base 2, la frazione 1/10 ha uno sviluppo periodico, proprio come 1/3 si ripete all’infinito in base 10 (0.3333...). Scritto per intero, 0.1 in binario inizia così: ...
Una lookup su un dizionario Python impiega circa 100 nanosecondi, che il dizionario contenga 1.000 chiavi o 1.000.000. Un doppio ciclo che cerca duplicati in una lista impiega mezzo millisecondo su 200 elementi e 136 millisecondi su 3.200. Sedici volte l’input, quasi 280 volte l’attesa. Stessa macchina, stesso Python. La notazione Big O è il nome di quella differenza. Cosa misura la notazione Big O Big O descrive come cresce il tempo di esecuzione (o l’uso di memoria) di un pezzo di codice all’aumentare dell’input. Non è una lettura al cronometro e non le importa se il tuo portatile è veloce o lento. Le interessa la forma della curva di crescita: raddoppiando l’input, il tempo raddoppia, quadruplica, o si muove appena? ...