Algoritmos – Conversão Binária – Parte 03

Introdução

No post anterior sobre conversão binária, vimos algumas formas de converter um valor binário representado em uma string de volta a um valor decimal. O algoritmo mais rápido demorou 9,2 segundos para converter 2.560.000 valores. E se eu disser que dá para fazer isso QUATRO VEZES mais rápido, eu devo estar louco ???

Acelerando o AdvPL

No primeiro post sobre conversão binária, o algoritmo têm um desempenho incrível para converter valores de decimal para string binária, pois eu monto um cache com um array armazenando as strings  com o resultado das conversões dos valores de 0 a 255, e ao converter eu acesso diretamente o elemento pela sua posição, o tempo de busca é praticamente o mesmo para qualquer elemento.

Agora, será que é possível aplicar isso da forma inversa ? Usar um array em cache, com as strings binárias e o seu valor decimal correspondente, e buscar o valor desejado a partir da string informada ? Considerando uma string de 8 caracteres ‘0’ ou ‘1’ , com 256 possibilidades diferentes, é mais rápido calcular o número em decimal ou procurar na lista ? Veremos …

Peso do algoritmo de cálculo

Partindo da conversão de uma string binária de 8 caracteres, usando o algoritmo proposto no post anterior, podemos elencar o melhor e pior tempo da rotina, partindo das operações que ela precisa fazer para chegar ao resultado final. Vamos avaliar quantas operações de string, comparação e aritmética são necessárias para converter as strings “00000000” e “11111111” respectivamente:

User Function TST8()
Local nRet 
nRet := BitStoN("00000000")
nRet := BitStoN("11111111")
return

STATIC Function BitsToN(cBitStr)
Local nI, nT := len(cBitStr) 
Local nMult := 1
Local nResult := 0
For nI := nT to 1 STEP -1
    // a linha abaixo é executada 8 vezes, uma para 
    // identificar cada caractere da string binária
    // e compará-lo com '1'
    IF substr(cBitStr,nI,1) = '1'
        // A soma do multiplicador somente é executada para
        // cada caractere '1' encontrado na string. Ela 
        // nao é executada nenhuma vez para "00000000", mas é
        // feita 8 vezes para converter "11111111"
        nResult += nMult
    Endif
    // A Multiplicação abaixo é feita sempre 8 vezes
    nMult *= 2
Next
Return nResult

Passando na ponta do lápis, a busca mais “leve” de uma string binária fará 8 extrações de uma posição da string (substr), 8 comparações de string de 1 caractere e 8 multiplicações de nMult. Para cada dígito encontrado que tenha o  valor ‘1’ ainda será feita uma soma adicionando o valor de nMult no resultado. Logo, com “11111111”, temos mais oito operações aritméticas. Podemos concluir que, o número estimado de operações dessa rotina é de 24 a 32 operações de string e numéricas por conversão.

HASH MAP

Quem se lembra do artigo sobre Performance e Escalabilidade – HASH MAP em AdvPL ? Então, um Hash Map é uma forma otimizada de busca em vetores do tipo chave-valor, que monta internamente um acesso posicional. Se, internamente, a quantidade e peso das operações para fazer a busca usando um HASHMAP em uma lista pré-montada é menor do que calcular o resultado, o HASH vai ser mais rápido. Vamos ao teste:

User Function tststr()
Local cStrBit
Local nTimer
Local nNum, nI , nJ      
Local oHash

// Cria o cache de HASH para a busca ( 0 a 255 )            
oHash := BuildBitHash()

// Roda a carga de teste
nTimer := seconds()
For nJ := 0 to 255              
  // Cria uma string binária para conversão
  cStrBit := nToBit8(nJ)
  For nI := 1 to 10000 
    // Busca o valor no HashMap
    HMGET( oHash,cStrBit ,@nNum)
  Next
Next
// Mostra o tempo do teste
conout(str(seconds()-nTimer,12,3)+"s.")

// Limpa de destroi o HashMap
HMClean(oHash) 
FreeObj(oHash)

Return

// Monta o HashMap com os 256 bytes de cache
STATIC Function BuildBitHash()
Local oHash := HMNew()
For nI := 0 to 255
  // Seta uma tupla chave , valor 
  HMSet(oHash, NTOBIT8(nI) , nI )
Next
Return oHash

Desempenho

Usando a função BitSToN(), 2.560.000 conversões levaram em média de 8,5 a 9 segundos para serem realizadas. Usando o objeto de Hash Map, o mesmo processamento levou em média 2 segundos. Isso significa quase 1280000 conversões por segundo, contra no máximo 320.000 conversões por segundo da BitSToN()

Observações

O tempo obtido foi realmente impressionante, porém para chegar neste desempenho, dada a quantidade de iterações, o objeto de cache foi montado e armazenado em variável local, e as chamadas para a busca do HashMap foram feitas com a função HMGet(), sem encapsulamento em Static Function. Após implementar o encapsulamento do HMGET() por Static Function, o tempo foi para perto de 4 segundos, o que ainda é a metade do tempo do algoritmo anterior. 😀

Conclusão

Sempre dá pra “apertar” mais um pouco o desempenho, usando as técnicas e abordagem adequadas.

Agradeço a todos a audiência, e lhes desejo TERABYTES DE SUCESSO !!! 

Referências

TDN – HashMap

 

 

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s