Categoria: Ciência da Computação
Artigos sobre ciência da computação, algoritmos, estruturas de dados, linguagens de programação e fundamentos teóricos da computação.
Pilhas, Filas, Heaps e Contêineres Associativos: o Estado que Sobrevive à Pergunta Seguinte
Uma estrutura de dados é um acordo entre as atualizações e as perguntas. Este artigo abre o capítulo das estruturas com as que guardam candidatos, ordem ou hash. No MSVC,...
Treino T05: Intervalos com Orçamento
Cada problema deste treino pergunta algo sobre um trecho de um vetor, e nenhum deles pode pagar o preço de ler o trecho inteiro. Às vezes a resposta é prometer...
Hash de Prefixo, Seleção em Três Partes e o Algoritmo de Mo
Duas cadeias de 1024 letras, diferentes, têm o mesmo hash módulo 2^64 para qualquer base ímpar, e sortear a base não muda nada. Este artigo fecha o capítulo dos arrays...
Bits como Conjuntos: Máscaras, popcount e Bitsets de Muitas Palavras
Um inteiro de 64 bits é um conjunto de até 64 elementos, e uma instrução do processador faz a interseção de todos eles de uma vez. Este artigo usa bits...
Janelas que Deslizam: Deque Monotônico, Dois Ponteiros, Kadane e Sparse Table
Uma janela que anda uma posição perde um elemento e ganha outro, e quem recalcula a janela inteira paga k vezes mais do que precisa. Este artigo mantém o estado...
Somas de Prefixo e Arrays de Diferenças: Integrar e Derivar em Tempo Constante
Somar um intervalo de cem mil posições custa cem mil somas, a menos que alguém tenha somado antes. Prefixos respondem a qualquer soma de intervalo com uma subtração, diferenças aplicam...
Treino T04: Comprar Informação
Cada problema deste treino pergunta, de um jeito ou de outro, onde fica uma fronteira. Às vezes é a primeira pedra depois de um peregrino, às vezes é o menor...
Ordenar sem Comparar: Contagem, Radix e a Escolha da Ferramenta
Quando as chaves são inteiros de um universo pequeno, ordenar não exige comparar. No MSVC, a contagem ordenou dez milhões de inteiros entre 0 e 255 em 11 ms, contra...
Ordenar por Comparação: o Limite, a Biblioteca e a Seleção
Nenhum algoritmo que só compara elementos ordena um milhão de números com menos de 18,5 milhões de comparações. O std::sort do MSVC fez 31 milhões e levou 61 ms. Uma...
Busca Binária: Comprar Informação pela Metade
Cada comparação de uma busca binária compra um bit de informação e descarta metade da incerteza. Vinte comparações bastam para um milhão de elementos. No MSVC, porém, a mesma busca...
Treino T03: Alimentando a Máquina
Vários problemas deste treino são aritmeticamente triviais de propósito. Quando a conta é silenciosa, o custo de mover bytes, a semântica da conversão de texto e a posse dos caracteres...
Entrada e Saída de Alto Desempenho
Um algoritmo O(n log n) pode perder para a leitura da própria entrada. No MSVC, ler um milhão de inteiros com std::cin custou 360 ms, e um leitor de vinte...
Treino T02: Pagar Uma Vez, Perguntar Sempre
Pagar um pré-processamento uma vez para responder muitas perguntas depressa é a primeira grande troca da série. Este treino cobra essa troca em sete problemas e, depois deles, aplica a...
Caixa de Ferramentas II: Vetores, Matrizes, Vistas e Algoritmos
Um vetor que cresce sozinho move cada elemento, em média, duas vezes no MSVC. Uma vista que filtra dez valores pode ler só sete. Uma tabela de contagem vence a...
Caixa de Ferramentas I: Tipos, Números e Trabalho em Tempo de Compilação
Toda solução tem duas vidas. Na primeira, escolhemos a ideia e provamos que ela funciona. Na segunda, digitamos a ideia em C++23 depressa e limpo o bastante para que o...
Treino T01: Contando Antes de Codificar
Saber um algoritmo e entregar um programa correto com o relógio correndo são habilidades diferentes. O primeiro treino da série cobra a segunda, com sete problemas cujos enunciados não dizem...
A Máquina por Baixo do Algoritmo: Tipos, Cache e Desvios
A notação Big O conta operações e trata todas como iguais. O processador discorda. Vamos abrir a máquina e medir o preço de escolher o tipo errado, de percorrer a...
Contar Antes de Programar: Complexidade, Restrições e Medição
Um programa correto que estoura o limite de tempo recebe o mesmo veredito de um programa errado. A série começa aprendendo a contar o trabalho antes de escrever a primeira...
Alto Desempenho, Regras que Sobrevivem à Medição
Um catálogo de regras de Cpp23 para código rápido, organizado por tema e temperado com a lição mais antiga da otimização, que é medir antes de acreditar.
Seu Programa Não Começa na main
Antes da main(), muita coisa já aconteceu: o sistema operacional carregou o processo, o loader resolveu bibliotecas e a runtime inicializou o ambiente.
Aprovação: O problema da média e o tratado de paz
A média de aprovação é realmente um indicativo de aprendizado? Discutimos as falhas na avaliação do ensino superior.
Fused Multiply-Add A Instrução que Dobra sua CPU
Descubra como a instrução Fused Multiply-Add (FMA) funciona nos bastidores para acelerar a computação numérica e melhorar o arredondamento em sua CPU.
Representação Numérica em Hardware Constrito
Guia prático para otimizar operações numéricas em hardware constrito como o Raspberry Pi usando formatos de ponto flutuante de menor precisão.
Maps Cache-Friendly em C++23 Localidade e Indexação Múltipla
Aprenda a otimizar a performance de suas estruturas associativas em C++23 usando std::flat_map e padrões cache-friendly.
A Falha do Cloudflare e o Haskell
Análise técnica do incidente da Cloudflare: entenda como uma mudança de permissões causou uma falha catastrófica em sistemas de alta performance.
Heaps na Standard Template Library do C++23
Explore as funcionalidades de heap no C++23 e otimize suas estruturas de dados de árvore binária.
Receitas da Família Alcantara
Aprenda a fazer receitas deliciosas e testadas no dia a dia da Família Alcantara.
