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 …

Curry with JS

Partial application and currying with Javascript In the strict way, currying is the technique of transforming a function that takes multiple arguments (a tuple of arguments) to one function that receive only one. In such way, currying techniques allow transform one multi-parameter function in a chain of functions, each one with a single argument. Looks complicated? Blah.. it is not true.
In this little article, we are actually more interesting in partial applications. Let’s take the Mozilla Example for replace function in String. As we know, we can use a “replacer” function as paramenter for replace method in String object.
Let’s say that we want to split a String defined by a non-numerical part, a numerical part and finally a non-alphanumeric part. Here is how:
function replacer(match, p1, p2, p3, offset, string){ // p1 is nondigits, p2 digits, and p3 non-alphanumerics return [p1, p2, p3].join(' - '); }; We can try it as usual…
var newString = "abc12345#$*%".r…