Performance e escalabilidade – Hash Map – Parte 2

Introdução

No post anterior, vimos um exemplo básico de uso de Hash Map em AdvPL, com foco em um programa comparativo de desempenho, usando um array pequeno como referência, e realizando um número muito elevado de buscas  neste array para tornar visível a diferença de desempenho. Porém, o exemplo em si era meramente didático, não necessariamente refletia um algoritmo que usamos diariamente em nossos programas.

Neste post, vamos ver um exemplo prático de uso do Hash Map, criado “vazio”, onde o caso de uso utilizado é relativamente comum de processamento com dados em array, e através deste exemplo conseguimos determinar e visualizar a partir de que momento o Hash Map faz efetivamente toda a diferença.

Hash Map “from scratch“

Um objeto de Hash Map pode ser criado a partir dos dados de um array multi-dimensional já existente, o que o torna muito prático para ser implementado em partes específicas de programas já desenvolvidos que fazem muitas buscas neste Array, ou o objeto Hash Map pode ser criado vazio e populado diretamente, sem a necessidade de usarmos um array já montado como base.

Para criarmos o objeto Hash Map vazio, usamos a função HMNew(). Após criado o objeto, podemos acrescentar as chaves e respectivos valores associados neste Hash Map usando a função HMAdd(). O elemento acrescentado deve ser um array. É possível acrescentar mais de um elemento de array na mesma chave. Quando pesquisamos por uma chave usando HMGet(), caso a chave seja encontrada, o valor retornado por referência no 3o parâmetro é um array, contendo todos os elementos acrescentados naquela chave.

É possível trocar um elemento da chave usando HMSet(), e isto substitui o array de todos os valores referenciados por aquela chave, sem que isso mude o nome da chave de busca. É importante ressaltar que o tipo de dado usado para a troca deve ser um array, seguindo o mesmo formato dos demais. Você pode eliminar a qualquer momento uma chave do Hash Map usando a função HMDel(). E, ainda existe a possibilidade de usar chaves compostas no Hash Map, usando mais de uma coluna do array, onde podemos usar uma função auxiliar chamada HMKey() para garantir que a chave de busca está sendo montada da forma correta.

No caso de uso deste post, usamos apenas as três primeiras funções : HMNew() , HMAdd() e HMGet()

Caso de uso: Array sem elementos repetidos

Normalmente, quando você popula um array vazio, onde uma ou mais colunas são usadas como chave, e não pode haver chaves repetidas, para cada dado a ser inserido no array você faz uma busca com ASCAN() para ver se um dado com aquela chave já não foi inserido, para somente fazer a inserção caso a chave não exista. Usando esta abordagem , o tempo de busca tende a crescer (e muito) conforme o crescimento da quantidade de elementos neste array.

Você pode criar e usar um Hash Map para implementara este algoritmo, ao invés de usar o ASCAN(). Para ilustrar a diferença de desempenho entre ambos, eu escrevi um fonte de testes que usa o aScan() e usa Hash Map, medindo o tempo de ambos. O mesmo teste é executado com um número crescente de chaves não repetidas (pior cenário), iniciando com 2 elementos, e dobrando a quantidade de elementos a cada iteração, até 8292 elementos, e mostrando o desempenho por teste. Segue o fonte abaixo:

User Function TSTDup()
Local aDados := {}
Local aCheck := {}
Local nI
Local nKey
Local aValues
Local nTotal1,nTotal2
Local nElements
Local oHash

nElements := 2

// Testa de 2 a 8192 elementos, dobrando a quantidade de elementos 
// a cada teste ( 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192 )

conout("Resultado ( Elementos / Tempo com Ascan() / Tempo com Hash")

While nElements <= 8192
 
   // Zera os arrays para fazer cada teste
   aSize(aDados,0)
 
   // Cria um array de dados sem valores repetidos
   For nI := 1 to nElements
      aadd(aDados, { nI , "Teste "+cValToChar(nI) } )
   Next
 
    // método 1: Verificar por repetições com Ascan()
    aSize(aCheck,0)
    nTotal1 := seconds()
    For nI := 1 to nElements
       nKey := aDados[nI][1]
       // Busca usando ASCAN
       If ascan( aCheck , {|x| x[1] == nKey }) == 0
          // Nao achou, acrescenta o elemento
          // no array de elementos nao repetidos
          AADD(aCheck,aDados[nI])
       Endif
    Next
    nTotal1 := seconds() - nTotal1
 
    // método 2: Usando Hash Map
    aSize(aCheck,0)
    nTotal2 := seconds()
    oHash := HMNew() // Cria um hash map sem dados 
    For nI := 1 to nElements
       nKey := aDados[nI][1]
       // Busca no Hash Map ( usando chave numérica ) 
       If !hmGet(oHash,nKey,@aValues)
          // Nao achou, acrescenta o elemento no hash 
          // e no array de elementos nao repetidos
          HMAdd(oHash,aDados[nI])
          AADD(aCheck,aDados[nI])
       Endif
    Next
    nTotal2 := seconds() - nTotal2

   // Mostra o resutado deste teste ( elementos, tempo ascan, tempo hash
    conout(str(nElements,5)+" / "+str(nTotal1,6,3)+" s. / "+str(nTotal2,6,3)+" s.")
 
    // Dobra a quantidade de elementos para o próximo teste
    nElements := nElements * 2
 
Enddo

Return

Resultado do teste

No meu equipamento, obtive os resultados abaixo no log de console:

Resultado ( Elementos / Tempo com Ascan() / Tempo com Hash
 2    / 0.000 s. / 0.000 s.
 4    / 0.000 s. / 0.000 s.
 8    / 0.000 s. / 0.000 s.
 16   / 0.000 s. / 0.000 s.
 32   / 0.000 s. / 0.000 s.
 64   / 0.000 s. / 0.000 s.
 128  / 0.016 s. / 0.000 s.
 256  / 0.032 s. / 0.015 s.
 512  / 0.125 s. / 0.015 s.
 1024 / 0.530 s. / 0.032 s.
 2048 / 1.950 s. / 0.046 s.
 4096 / 8.268 s. / 0.078 s.
 8192 / 38.243 s. / 0.188 s.

Agora vamos analisar com calma os resultados acima. Reparem que todos os testes de 2 a 64 foram tão rápidos que não contabilizaram diferença de tempo. Vamos focar nos primeiros resultados, onde não há diferença de tempo: Nos casos com 64 elementos ou menos, o tempo com ASCAN ou com HASH foi menor que 1/100 de segundo.

Agora, a partir de 128 elementos, os tempos do ASCAN() começam a ficar maiores, e a cada vez que dobramos a quantidade de elementos, o tempo de busca cresce desproporcionalmente, aproximadamente 8 x mais lento a cada 2x mais elementos. Enquanto isso, vendo os tempos com o uso do Hash Map: O tempo de busca somente foi superior a 1/100 de segundo após 256 elementos, e quando comparamos este tempo com o tempo do teste de 8192 elementos (32 vezes mais elementos), o tempo do hash cresceu aproximadamente 12 vezes, enquanto o tempo do ASCAN() cresceu 1195 vezes.

Veja o seguinte: A primeira busca com ASCAN() é feita com o array vazio, na segunda busca o array já tem um elemento, na terceira ele tem dois elementos, na ducentésima primeira pesquisa, o array já tem duzentos elementos, e como a pesquisa é sequencial, e para cada elemento do array é feita uma comparação, são feitas 32896 comparações para fazer 256 buscas em um array que cresce um elemento a cada busca.

Se considerarmos tempos ou diferenças de tempo neste tipo de operação abaixo de 1/10 de segundo irrelevantes, somente começa a haver diferença perceptível e ganhos visíveis de uso do Hash após 256 elementos. Na prática, isto significa que, se a sua verificação por duplicidade na montagem de um array onde não serão usados mais de 256 elementos, não faz diferença usa Hash Map ou ASCAN(). Agora, de 512 pra cima, quanto maior o tamanho do array, mais visível é a perda de desempenho em relação a uso do Hash Map.

Conclusão

Estou fadado a escrever o óbvio, e repetir a conclusão do primeiro post … então, conclui-se que “quanto mais elementos tem um array, mais ineficaz é realizar uma busca sequencial neste array”. O que nós não imaginamos, é que existem pontos onde nós achamos que o número de operações internas do sistema possa crescer tanto com o aumento da massa de dados no algoritmo. Para ajudar na descoberta destes pontos, muitas linguagens de mercado e até softwares independentes dos fabricantes da linguagem oferecem uma instrumentação para gerar um “Profiler” da aplicação.

O AdvPL possui um recurso de geração de Profiler nativo muito, muito interessante … mas este assunto fica para um próximo post !!! Até o próximo post, pessoal 😉