manejo - interpolar en ruby

¿Por qué el conteo de letras es más rápido usando el conteo de Cadena#que usando caracteres de cadena#en Ruby?

Question

Usando el siguiente punto de referencia:

def create_genome
  "gattaca" * 100
end

def count_frequency_using_chars(sequence)
  100000.times do
    sequence.chars.group_by{|x| x}.map{|letter, array| [letter, array.count]}
  end
end

def count_frequency_using_count(sequence)
  100000.times do
    ["a", "c", "g", "t"].map{|letter| sequence.count(letter)}
  end
end

sequence = create_genome
count_frequency_using_chars(sequence)
count_frequency_using_count(sequence)

Descubrí que, en Ruby basado en C para 1.8 y 1.9.2, el uso del String#count(letter) es aproximadamente 50 veces más rápido que ordenarlos y contarlos usando Enumerable#group_by y Array#count . Me sorprendió un poco, porque el método de String#count lee la cadena cuatro veces en cada iteración, mientras que el último solo lo lee una vez.

Traté de ejecutar el código en ruby-prof y perftools.rb, y ambos meramente indicaron que String#chars tomó el 90% del tiempo, sin desglosar dónde pasó el 90% del tiempo.

Si tuviera que adivinar por qué hay una diferencia, diría que la creación de 70 millones de cadenas de un solo carácter sería costosa, pero ¿cómo podría saberlo? ( Actualización : String#chars no fue el culpable - vea el punto de referencia para mainly_execute_a_trivial_block )

Edición: puntos de referencia actuales usando 1.9.2 patchlevel 180:

require ''pp''
require ''benchmark''

def create_genome
  "gattaca" * 100
end

ZILLION = 100000

def count_frequency_using_count(sequence)
  ZILLION.times do
    ["a", "c", "g", "t"].map{|letter| sequence.count(letter)}
  end
end

def count_frequency_using_chars(sequence)
  ZILLION.times do
    sequence.chars.group_by{|x| x}.map{|letter, array| [letter, array.count]}
  end
end

def count_frequency_using_inject_hash(sequence)
  ZILLION.times do
     sequence.chars.inject(Hash.new(0)) { |h, e| h[e] += 1 ; h }
  end
end

def count_frequency_using_each_with_object(sequence)
  ZILLION.times do
     sequence.chars.each_with_object(Hash.new(0)) { |char, hash| hash[char] += 1}
  end
end


def just_group_by(sequence)
  ZILLION.times do
    sequence.chars.group_by{|x| x}
  end
end

def just_chars_and_trivial_block(sequence)
  ZILLION.times do
    sequence.chars() {}
  end
end

def mainly_execute_a_trivial_block(sequence)
  ZILLION.times do
    sequence.length.times() {}
  end
end

def execute_an_empty_loop_instead(sequence)
  ZILLION.times do
    i = 0
    max = sequence.length
    until i == max
      i += 1
    end
  end
end

sequence = create_genome

puts RUBY_VERSION

Benchmark.bm do |benchmark|
  benchmark.report do
    count_frequency_using_count(sequence)
  end
  benchmark.report do
    count_frequency_using_chars(sequence)
  end
  benchmark.report do
    count_frequency_using_inject_hash(sequence)
  end
  benchmark.report do
    count_frequency_using_each_with_object(sequence)
  end
  benchmark.report do
    just_group_by(sequence)
  end
  benchmark.report do
    just_chars_and_trivial_block(sequence)
  end
  benchmark.report do
    mainly_execute_a_trivial_block(sequence)
  end
  benchmark.report do
    execute_an_empty_for_loop_instead(sequence)
  end
end

Resultados:

     user     system      total        real
 0.510000   0.000000   0.510000 (  0.508499) # count_frequency_using_count
23.470000   0.030000  23.500000 ( 23.575487) # count_frequency_using_chars
32.770000   0.050000  32.820000 ( 32.874634) # count_frequency_using_inject_hash
31.880000   0.040000  31.920000 ( 31.942437) # count_frequency_using_each_with_object
22.950000   0.030000  22.980000 ( 22.970500) # just_group_by
13.300000   0.020000  13.320000 ( 13.314466) # just_chars_and_trivial_block
 5.660000   0.000000   5.660000 (  5.661516) # mainly_execute_a_trivial_block
 1.930000   0.010000   1.940000 (  1.934861) # execute_an_empty_loop_instead

Answer 1

Lo que es lento es group_by. Efectivamente, aunque necesita hacer 4 pases para el método de conteo, el método group_by es mucho más lento porque está haciendo mucho trabajo para hacer ese group_by.

Rompiendo el código un poco para tener un método que solo haga el grupo:

def create_genome
  "gattaca" * 100
end

def count_frequency_using_chars(sequence)
  100000.times do
    sequence.chars.group_by{|x| x}.map{|letter, array| [letter, array.count]}
  end
end

def count_frequency_using_count(sequence)
  100000.times do
    ["a", "c", "g", "t"].map{|letter| sequence.count(letter)}
  end
end

def just_group_by(sequence)
  100000.times do
    sequence.chars.group_by{|x| x}
  end
end

sequence = create_genome

...

ruby-1.9.2-p180 :068 > puts Time.now()
2011-06-17 11:17:36 -0400

ruby-1.9.2-p180 :069 > count_frequency_using_chars(sequence)
 => 100000 
ruby-1.9.2-p180 :070 > puts Time.now()
2011-06-17 11:18:07 -0400

ruby-1.9.2-p180 :071 > count_frequency_using_count(sequence)
 => 100000 
ruby-1.9.2-p180 :072 > puts Time.now()
2011-06-17 11:18:08 -0400

ruby-1.9.2-p180 :073 > just_group_by(sequence)
 => 100000 
ruby-1.9.2-p180 :074 > puts Time.now()
2011-06-17 11:18:37 -0400

Puedes ver

• usar group_by tomó 31 segundos
• usar el conteo tomó 1 segundo
• solo haciendo group_by tomó 29 segundos

Si bien usar group_by para obtener la información que necesita es bueno conceptualmente, está haciendo un trabajo adicional que no necesita hacer.

Answer 2

Una manera más rápida y más lenta sería pasar la matriz solo una vez.

hash = sequence.chars.inject(Hash.new(0)) { |h, e| h[e] += 1 ; h }
=> {"g"=>100, "a"=>300, "t"=>200, "c"=>100}

pero en realidad NO es más rápido

Esto fue un fracaso total de copiar y pegar.

De todas formas, dejo la respuesta ya que muestra cómo se usa Benchmark en la biblioteca estándar.

require ''pp''
require ''benchmark''

def count_frequency_using_inject_hash(sequence)
  100000.times do
     sequence.chars.inject(Hash.new(0)) { |h, e| h[e] += 1 ; h }
  end
end

sequence = create_genome

Benchmark.bm do |benchmark|
  benchmark.report do
    pp count_frequency_using_chars(sequence)
  end
  benchmark.report do
    pp count_frequency_using_count(sequence)
  end
  benchmark.report do
    pp count_frequency_using_inject_hash(sequence)
  end
end

user system total real 41.500000 0.000000 41.500000 ( 42.484375) 1.312000 0.000000 1.312000 ( 1.406250) 49.265000 0.000000 49.265000 ( 49.348633)

Answer 3

No tiene nada que ver con el rubí interno. Estás comparando manzanas con naranjas.

en su primer ejemplo, está agrupando 700 cadenas de caracteres 100000 veces y buscando el recuento. Entonces es un problema en tu lógica. no en contar. En el segundo enfoque solo estás contando,

Y en ambos enfoques, solo estás usando recuento

solo cambia el primer ejemplo como este

def count_frequency_using_chars(sequence)
  grouped = sequence.chars.group_by{|x| x}
  100000.times do
    grouped.map{|letter, array| [letter, array.count]}
  end
end

Y es tan rápido como tu segundo

Editar

Este enfoque es 3 veces más rápido que count_frequency_using_count , verifica los puntos de referencia

  def count_frequency_using_chars_with_single_group(sequence)
    grouped = sequence.chars.group_by{|x| x}
      100000.times do
        grouped.map{|letter, array| [letter, array.count]}
      end
    end

    def count_frequency_using_count(sequence)
      100000.times do
        ["a", "c", "g", "t"].map{|letter| sequence.count(letter)}
      end
    end

Benchmark.bm do |benchmark|
  benchmark.report do
    pp count_frequency_using_chars_with_single_group(sequence)
  end
  benchmark.report do
    pp count_frequency_using_count(sequence)
  end
end


    user     system      total        real
  0.410000   0.000000   0.410000 (  0.419100)
  1.330000   0.000000   1.330000 (  1.324431)

Andrew a tus comentarios,

measuring the character composition of 100000 sequences once each, not the character composition of one sequence 100000 times , aún así su enfoque de recuento es demasiado lento que el enfoque de group_by. Acabo de comparar las grandes cadenas como dijiste

seq = "gattaca" * 10000
#seq length is 70000

arr_seq = (1..10).map {|x| seq}
#10 seq items

y cambió los métodos para manejar las múltiples secuencias

def count_frequency_using_chars_with_single_group(sequences)
  sequences.each do |sequence|
    grouped = sequence.chars.group_by{|x| x}
    100000.times do
      grouped.map{|letter, array| [letter, array.count]}
    end
  end
end

def count_frequency_using_count(sequence)
  sequences.each do |sequence|
    100000.times do
      ["a", "c", "g", "t"].map{|letter| sequence.count(letter)}
    end
  end
end


Benchmark.bm do |benchmark|
  benchmark.report do
    pp count_frequency_using_chars_with_single_group(arr_seq)
  end
  benchmark.report do
    pp count_frequency_using_count(arr_seq)
  end
end

Para procesar 100000 veces, 10 secuencias cada una con 70000 de longitud

  user        system      total        real
 3.710000     0.040000    3.750000     ( 23.452889)   #modified group_by approach
 1039.180000  6.920000    1046.100000  (1071.374730) #simple char count approach

Su enfoque simple de recuento de caracteres es un 47% más lento que el enfoque group_by modificado para las cadenas de alto volumen. Ejecuté el punto de referencia anterior para solo 10 secuencias cada una con 70000 de longitud. Supongamos esto para 100 o 1000 secuencias, el conteo simple nunca sería una opción. ¿derecho?

Answer 4

Puede ver mejor lo que está sucediendo al crear un perfil de la máquina virtual.

Un bloqueo que se produce un número excesivo de veces es el culpable aquí. Si usa el perfilador de Perftools para la máquina virtual, siga las instrucciones enumeradas en "Creación de perfiles de las extensiones de Ruby VM y C" en https://github.com/tmm1/perftools.rb (nota: esto es más o menos perftools vainilla, no perftools.rb)

Removing _init from all stack traces.
Total: 3883 samples
    1321  34.0%  34.0%     3883 100.0% rb_yield_0
     273   7.0%  41.1%      274   7.1% _IO_str_pbackfail
     191   4.9%  46.0%      191   4.9% __i686.get_pc_thunk.bx
     171   4.4%  50.4%      171   4.4% _init
     131   3.4%  53.7%     3880  99.9% rb_eval
     122   3.1%  56.9%      347   8.9% st_lookup
     105   2.7%  59.6%      423  10.9% new_dvar
      93   2.4%  62.0%      326   8.4% rb_newobj
      89   2.3%  64.3%       89   2.3% _setjmp
      77   2.0%  66.3%      400  10.3% str_new
      67   1.7%  68.0%      357   9.2% dvar_asgn_internal
      63   1.6%  69.6%      204   5.3% malloc
      62   1.6%  71.2%     3820  98.4% rb_str_each_char
      58   1.5%  72.7%      187   4.8% rb_ary_store
      55   1.4%  74.1%       55   1.4% rb_memcmp
      55   1.4%  75.5%     3883 100.0% rb_yield
# rest snipped for brevity

Como puede ver, rb_yield_0 representa más de un tercio de la actividad, por lo que incluso si pudiera optimizar todo lo demás, aún sería más lento que si estuviera usando String#count .

También puede confirmar esto haciendo un punto de referencia donde solo está creando un bloque que no hace nada.

require ''pp''
require ''benchmark''

def create_genome
  "gattaca" * 100
end

ZILLION = 100000

def mainly_execute_a_trivial_block(sequence)
  ZILLION.times do
    sequence.length.times() {}
  end
end

def execute_an_empty_loop_instead(sequence)
  ZILLION.times do
    i = 0
    max = sequence.length
    until i == max
      i += 1
    end
  end
end

sequence = create_genome

puts RUBY_VERSION

Benchmark.bm do |benchmark|
  benchmark.report do
    pp mainly_execute_a_trivial_block(sequence)
  end
  benchmark.report do
    pp execute_an_empty_loop_instead(sequence)
  end
end

da

      user     system      total        real
  5.700000   0.000000   5.700000 (  5.727715) # mainly_execute_a_trivial_block
  1.920000   0.000000   1.920000 (  1.942096) # execute_an_empty_loop_instead