Buscar uma chave em um dict Python com dez entradas leva o mesmo tempo que buscar em um com dez milhões. Isso não é acidente de uma linguagem rápida. O dict do Python, o HashMap do Java e o Map do JavaScript são todos tabelas hash, e todo o design existe para que busca, inserção e remoção rodem em O(1) na média. A notação Big O dá a essa busca o rótulo “tempo constante”. Este é o mecanismo que justifica isso. ...
<.+> contra <b>bold</b> and <i>italic</i> não encontra <b>. Encontra a string inteira, do primeiro < ao último >. Nada está quebrado. É exatamente isso que um quantificador greedy deve fazer, e também é o bug mais comum de “o regex está casando demais”. Depois que você entende o que o motor faz enquanto lê o seu padrão, esse bug e a maioria dos parentes dele deixam de ser mistério. Como um Motor de Regex Lê o Seu Padrão Um motor de regex não compara o seu padrão com a string como você compara duas strings por igualdade. Os motores que você usa no dia a dia (re do Python, RegExp do JavaScript, PCRE, .NET, Java) são regex-directed: eles percorrem o padrão da esquerda para a direita, token por token, e para cada token tentam consumir caracteres da string na posição atual. Quando um token casa, o motor avança tanto o ponteiro do padrão quanto o da string. Quando um token falha, o motor faz backtracking: volta ao último ponto em que tinha uma escolha, como um quantificador que poderia ter casado com menos caracteres ou um ramo de alternância ainda não tentado, e tenta a outra opção. ...
Uma função que chama a si mesma tem uma profundidade máxima, e ela é menor do que a maioria imagina: 1.000 chamadas no CPython por padrão, algo entre 10.000 e 15.000 no Node e nos motores de navegador, dependendo de quanto cada frame ocupa. Passar desse limite não deixa o programa mais lento. Ele trava. O Python lança RecursionError: maximum recursion depth exceeded; o JavaScript lança RangeError: Maximum call stack size exceeded. ...
Execute 0.1 + 0.2 em um shell Python e você não recebe 0.3. Recebe 0.30000000000000004. Tente em JavaScript, Java, Go, C ou Rust e aparece a mesma cauda de dezesseis dígitos. Cada uma dessas linguagens faz exatamente o que o padrão de hardware determina. Um número que precisaria de infinitos dígitos binários é comprimido em 64 bits, e algo precisa ser descartado. Por que 0.1 não pode ser guardado de forma exata em binário Computadores guardam números de ponto flutuante na base 2. Na base 2, a fração 1/10 tem uma expansão periódica, do mesmo jeito que 1/3 se repete para sempre na base 10 (0.3333...). Escrito por completo, 0.1 em binário começa assim: ...
Uma busca em um dicionário Python leva cerca de 100 nanossegundos, não importa se o dicionário tem 1.000 ou 1.000.000 de chaves. Um laço duplo que procura duplicatas em uma lista leva meio milissegundo com 200 itens e 136 milissegundos com 3.200. Dezesseis vezes a entrada, quase 280 vezes a espera. Mesma máquina, mesmo Python. A notação Big O é o nome dessa diferença. O que a notação Big O mede Big O descreve como o tempo de execução (ou o uso de memória) de um trecho de código cresce conforme a entrada aumenta. Não é uma leitura de cronômetro, e não importa se o seu notebook é rápido ou lento. O que importa é a forma da curva de crescimento: ao dobrar a entrada, o tempo dobra, quadruplica ou quase não muda? ...