sexta-feira, 31 de março de 2017

Algorítimos de ordenação - considerações importantes

Fala pessoal. A pouco tempo eu fiz uma postagem sobre algorítimos de ordenação, mas senti que faltaram algumas considerações a serem feitas, então resolvi fazer um novo post ao invés de atualizar o anterior.
Antes de tudo, vamos lembrar de uma coisa: memórias (seja RAM, ROM, EEPROM, FLASH ou outra) não duram para sempre! São componentes eletrônicos, possuem vida útil limitada, e a maioria delas tem sua vida definida por ciclos de leitura/escrita, ou seja, quanto mais você escrever e acessar sua memória, menos tempo ela durará! Dito isto, observe a imagem abaixo e creio que ficará bem claro onde quero chegar:


Esta é a saída de um programa que escrevi em C para ordenar o mesmo vetor usando Selection Sorting e Bubble Sorting. Antes de ficar pasmo com a diferença de tempo, vamos olhar para o número de operações no vetor. O segundo método "só" realizou 24.958 vezes mais operações do que o primeiro. Quase 2 bilhões e meio de operações. Isso para um vetor de 100k Bytes. Fica bem claro qual algorítimo irá garantir maior vida útil para a memória. A diferença de tempo (3,5x) é só uma decorrência do número de operações maior.
Agora imagine que isto foi feito em um computador, com uma CPU operando a 3,2GHz e memória RAM (que é onde ficam as variáveis do C) a 1333MHz. Imagine no meu PIC que opera a 48MHz e a memória I2C, por exemplo, a 400kHz no máximo e levando 5ms pra cada operação de escrita. Pois então. Com Bubble Sorting o PIC levou mais 3 horas pra organizar 8K Bytes de uma 24C64, enquanto o Selection, cerca de 45 minutos a uma hora (eu realmente me perdi na contagem do tempo de tanto que demorou, mas foi algo próximo disto). Vamos simular no PC pra ver a diferença no número de operações:

 
A diferença de tempo foi minúscula se pensarmos em segundos, e não em razão entre eles, mas o número de operações na memória continua bem significativo (2022 vezes mais operações no Bubble). Não acho que a memória I2C duraria muito tempo.
E se está achando que as memórias duram bastante, que isto é conversa fiada, veja o EEPROM Destroyer.
A intenção aqui foi chamar a atenção para o fato de que a simples escolha de um algorítimo pode não só impactar na performance de um equipamento, mas também na sua vida útil, mesmo sendo difícil de acreditar que um firmaware pode encurtar a vida de um componente eletrônico.]

Por fim, resolvi testar o limite máximo do meu PC, o que me deu um vetor de 259625 Bytes e uam longa espera.