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

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

Pequeno manual do ócio em terras alemãs

  Pequeno manual do ócio em terras alemãs Como Lei alemã favorece aproveitadoras (e alguns aproveitadores que nunca tive o desprazer de conhecer)   Há algumas vias pelas quais pessoas de países em desenvolvimento migram para países como a Alemanha.   Por exemplo, é sabido que países desenvolvidos sofrem de escassez de mão-de-obra qualificada. Por esse motivo, países como a Alemanha dispõe vistos "especiais" para profissionais em demanda. Esse é o conceito do Blaukart (Blue Card) que na Alemanha se destina a profissionais salário anual seja superior a 55 mil euros ou 43 mil no caso de profissionais de áreas em alta demanda. Não há como recrutar essa mão-de-obra sem que a família desses profissionais também possa ser relocada. Então esses profissionais e seus familiares são relocados.   Além de se qualificar para essas vagas em demanda, ou ser parte direta da família qualificada, outra via possível para a imigração para o território alemão é através do matrimôni

O argumento anti-álcool

A lógica contra a produção do álcool é mais ou menos a seguinte: Os produtores capitalistas, produtores do combustível de humanos e máquinas irão preferir vender combustível mais caro para os mais ricos do que comida barata para os mais pobres. Máquinas e homens irão competir por combustível... Mas enquanto os ricos terão dinheiro para comprar comida e combustível o que sobrará aos pobres!? Vale lembrar que não importa se a produção é de cana ou de milho, a competição é pela terra e não pelo grão. Ainda, mesmo que o país agrícola taxe o produtor de combustível de maneira diferenciada ao produtor de comida, o governo teria maiores dificuldades em repartir o "bolo", haja vista que os governos que temos não são as instituições mais eficientes e, além do que, a comida estará mais cara. Ora, esquecem os "amigos" comunistas que a venda de biocombustível dará aos países agrícolas uma oportunidade ímpar de participar da economia mundial como protagonistas, e não meros fi