Pular para o conteúdo principal

Hash vs OrderedHash

Seria o OrderedHash menos eficiente que o Hash?


Contextualizando: Algumas vezes queremos que um dicionário (ou tabela de símbolos) tenha não apenas uma relação de chave e objeto como também uma ordem (a palavra dicionário aliás remete bem a ideia de chaves ordenadas, cada qual com uma definição relacionada).  O ActiveSupport do Rails oferece uma classe chamada OrderedHash para honrar a especificação do YAML que exige a implementação de um mapa ordenado (omap). Quais os riscos de usar o ActiveSupport::OrderedHash em outros contextos?

Para responder a questão vou utilizar de dois recursos. Um simples teste de performance e o código-fonte do OrderedHash.


require 'benchmark'
require 'active_support'

TIMES= 100000
a = []
Benchmark.bm do  |bm|
  bm.report("Hash") do
    TIMES.times { |i|
      a = {}
      a[:a] = 1
      a[:b] = 2
    }
  end

  bm.report("Ordered Hash") do
    TIMES.times { |i|
      a = ActiveSupport::OrderedHash.new
      a[:a] = 1
      a[:b] = 2
    }
  end
end

Resultado:
      user     system      total        real
Hash  1.430000   0.070000   1.500000 (  1.655311)
Ordered Hash  1.770000   0.130000   1.900000 (  2.235623)

Duas perguntas... Por que? e Qual impacto disso?

Por que?

A desvantagem do Ordered Hash frente ao Hash é linear. Por maior que seja a coleção de objetos, o tempo de execução do ordered hash é proporcional ao tempo do próprio hash. Porém a diferença não era para ser tão grande. O Ordered Hash deveria ter uma lista com a ordem das chaves (o impacto deveria ser mínimo).

Isso não ocorre devido a implementação da funções hash nativas do Ruby. Nas palavras do rails:

In MRI the Hash class is core and written in C. In particular, methods are programmed with explicit C function calls and polymorphism is not honored.

For example, []= is crucial in this implementation to maintain the @keys array but hash.c invokes rb_hash_aset() originally. This prevents method reuse through inheritance and forces us to reimplement stuff.

For instance, we cannot use the inherited #merge! because albeit the algorithm itself would work, our []= is not being called at all by the C code.

Então o ActiveSupport reimplementa algumas funções que não seriam necessárias em outras ocasições.

Qual impacto disso?

Repetindo, a diferença do custo computacional do Ordered Hash para o Hash é linear. Dito isso, vale lembrar que para um hash com poucos elementos a diferença entre os algoritmos é quase desprezível. O custo de ordenar, inverter, embaralhar, zaralhar, um vetor com mais ou menos 10 elementos é por si desprezível. Dê uma olhada no código acima... mude a variável TIMES para 10. Qual a diferença entre os tempos!? No caso de aplicações em Rails, por exemplo, o processamento da pilha do framework é tão grande que a escolha acima não terá impacto prático no tempo de cada requisição.

Comentários

Postagens mais visitadas deste blog

Expressões, preconceito e racismo

Expressões preconceituosas e racistas Antes de alguma outra frase, primeiro peço licença para falar de mais um assunto do qual não domino. Falo por acreditar que um leigo presta serviço maior ao debater assunto com base em fontes (ainda que seja uma Wikipedia) e no pensamento lógico do que simplesmente se manter mudo a questões do cotidiano. Em voga agora está em falar quais são ou eram as expressões preconceituosas e racistas que até a pouco eram toleradas em muitos meios.
Como é covarde dizer que em boca fechada não entra racismo. O racismo não é perpetrado apenas por quem profere mas por quem se cala à agressão perpetrada a outrem. Mas veremos que a questão é muito mais complexa que os cães raivosos do politicamente correto querem dizer.
Tomo aqui a palavra racista, como sendo algo usado para impor a dominação de uma “raça” sobre outra. Portanto, a acusação de racismo vai muito além da mera acusação de preconceito. Não tenho o menor apreso por vitimismo barato, onde expressões que…

Um texto pós-moderno - better man

Espere olhando para as horas... são 4 horas. Tem que parar. Nesse tom melancólico, começa a modesta música "better man", uma balada pop composta por Eddie Vedder ainda na adolescência. A música é a ilustração perfeita da ironia. O próprio título é irônico, uma vez que em momento algum na música aparece um better man.

She lies and says she's in love with him, can't find a better man...

Irônico, não!? Para começar, com a personagem central da história, a mulher que aguarda tarde da noite seu esposo... Ela chega a treinar com o espelho o fim do relacionamento. E o que faz? Diz a negação do que queria dizer.

Vedder escreve músicas sobre sentimentos fortes. Sua relação com a mãe foi bastante complicada pelo o que descreve em suas canções. Na trilogia Mommy, Vedder descreve um homem perturbado com o relacionamento materno; a mãe mente para o filho sobre a identidade do pai, revela a verdade para o garoto na puberdade dizendo a ele como se parece com o verdadeiro pai e o leva …

Filme: Obrigado Por Fumar

Obrigado Por Fumar (Thank you for Smoking) - 2006Filme escrito e dirigido por Jason Reitman, produzido por David Sacks e baseado na novela de Christopher Buckley. Duração de 92 minutos.
"Obrigado Por Fumar" é um aclamado filme, vencedor do globo de ouro 2006 e sucesso em bilheterias (com faturamento superior a 39 milhões de dólares). O filme conta a história de Nick Naylor (Aaron Eckhart), vice-presidente da empresa Academia do Estudo do Tabaco, um lobby da indústria tabagista, e como ele usa suas habilidades de persuação para defender os interesses de seus superiores.
Direção muito interessante: ao contrário do que se pode esperar, o filme não mostra um quadro contaminado por fumaça em que o próprio telespectador tenha dificuldades em respirar. Aliás, o filme não mostra nehuma pessoa fumando. Também não faz uma crítica raivosa à indústria do cigarro. Seus argumentos são sutis, inteligentes e bem-humorados. Mas, a mensagem não passa despercebida pelo público, apenas não o agri…