Ruby - Array.join versus Concatenación de cadenas (Eficiencia)

Question

Recuerdo haber recibido un regaño por concatenar cadenas en Python, una vez. Me dijeron que es más eficiente crear una lista de cadenas en Python y unirlas más tarde. Llevé esta práctica a JavaScript y Ruby, aunque no estoy seguro si esto tiene el mismo beneficio en este último.

¿Alguien me puede decir si es más eficiente (recursos y ejecución) unirse a una matriz de cadenas y llamar: únete a ellas o concatenar una cadena según sea necesario en el lenguaje de programación Ruby?

Gracias.

Answer 1

Pruebe usted mismo con la clase Benchmark.

require "benchmark" 

n = 1000000 
Benchmark.bmbm do |x| 
    x.report("concatenation") do 
    foo = "" 
    n.times do 
     foo << "foobar" 
    end 
    end 

    x.report("using lists") do 
    foo = [] 
    n.times do 
     foo << "foobar" 
    end 
    string = foo.join 
    end 
end 

Esto produce el siguiente resultado:

Rehearsal ------------------------------------------------- 
concatenation 0.300000 0.010000 0.310000 ( 0.317457) 
using lists  0.380000 0.050000 0.430000 ( 0.442691) 
---------------------------------------- total: 0.740000sec 

        user  system  total  real 
concatenation 0.260000 0.010000 0.270000 ( 0.309520) 
using lists  0.310000 0.020000 0.330000 ( 0.363102) 

Así que parece que la concatenación es un poco más rápido en este caso. Benchmark en su sistema para su caso de uso.

Answer 2

Sí, es el mismo principio. Recuerdo un rompecabezas de ProjectEuler donde lo intenté en ambos sentidos, llamar a join es mucho más rápido.

Si retira la fuente de Ruby, unión se llevaron a cabo todas en C, que va a ser mucho más rápido que la concatenación de cadenas (sin la creación de objetos intermedia, sin recolección de basura):

/* 
* call-seq: 
*  array.join(sep=$,) -> str 
* 
* Returns a string created by converting each element of the array to 
* a string, separated by <i>sep</i>. 
*  
*  [ "a", "b", "c" ].join  #=> "abc" 
*  [ "a", "b", "c" ].join("-") #=> "a-b-c" 
*/ 

static VALUE 
rb_ary_join_m(argc, argv, ary) 
    int argc; 
    VALUE *argv; 
    VALUE ary; 
{ 
    VALUE sep; 

    rb_scan_args(argc, argv, "01", &sep); 
    if (NIL_P(sep)) sep = rb_output_fs; 

    return rb_ary_join(ary, sep); 
} 

donde rb_ary_join es :

VALUE rb_ary_join(ary, sep) 
    VALUE ary, sep; 
{ 
    long len = 1, i; 
    int taint = Qfalse; 
    VALUE result, tmp; 

    if (RARRAY(ary)->len == 0) return rb_str_new(0, 0); 
    if (OBJ_TAINTED(ary) || OBJ_TAINTED(sep)) taint = Qtrue; 

    for (i=0; i<RARRAY(ary)->len; i++) { 
    tmp = rb_check_string_type(RARRAY(ary)->ptr[i]); 
    len += NIL_P(tmp) ? 10 : RSTRING(tmp)->len; 
    } 
    if (!NIL_P(sep)) { 
    StringValue(sep); 
    len += RSTRING(sep)->len * (RARRAY(ary)->len - 1); 
    } 
    result = rb_str_buf_new(len); 
    for (i=0; i<RARRAY(ary)->len; i++) { 
    tmp = RARRAY(ary)->ptr[i]; 
    switch (TYPE(tmp)) { 
     case T_STRING: 
     break; 
     case T_ARRAY: 
     if (tmp == ary || rb_inspecting_p(tmp)) { 
     tmp = rb_str_new2("[...]"); 
     } 
     else { 
     VALUE args[2]; 

     args[0] = tmp; 
     args[1] = sep; 
     tmp = rb_protect_inspect(inspect_join, ary, (VALUE)args); 
     } 
     break; 
     default: 
     tmp = rb_obj_as_string(tmp); 
    } 
    if (i > 0 && !NIL_P(sep)) 
     rb_str_buf_append(result, sep); 
    rb_str_buf_append(result, tmp); 
    if (OBJ_TAINTED(tmp)) taint = Qtrue; 
    } 

    if (taint) OBJ_TAINT(result); 
    return result; 
} 

Answer 3

divertido, la evaluación comparativa da resultados sorprendentes (a menos que yo estoy haciendo algo mal):

require 'benchmark' 

N = 1_000_000 
Benchmark.bm(20) do |rep| 

    rep.report('+') do 
    N.times do 
     res = 'foo' + 'bar' + 'baz' 
    end 
    end 

    rep.report('join') do 
    N.times do 
     res = ['foo', 'bar', 'baz'].join 
    end 
    end 

    rep.report('<<') do 
    N.times do 
     res = 'foo' << 'bar' << 'baz' 
    end 
    end 
end 

da

jablan@poneti:~/dev/rb$ ruby concat.rb 
          user  system  total  real 
+      1.760000 0.000000 1.760000 ( 1.791334) 
join     2.410000 0.000000 2.410000 ( 2.412974) 
<<     1.380000 0.000000 1.380000 ( 1.376663) 

join resulta ser el más lento. Puede tener que ver con la creación de la matriz, pero eso es lo que tendría que hacer de todos modos.

Oh cierto,

jablan@poneti:~/dev/rb$ ruby -v 
ruby 1.9.1p378 (2010-01-10 revision 26273) [i486-linux] 

Answer 4

Estaba leyendo sobre esto. Attahced es un enlace que habla de eso.

Building-a-String-from-Parts

Por lo que entiendo, en las cadenas de Python y Java son objetos inmutables a diferencia de las matrices, mientras que en Ruby ambas cadenas y matrices son tan mutable como los demás. Puede haber una diferencia mínima en la velocidad entre el uso de un método String.concat o < < para formar una cadena frente a Array.join, pero no parece ser un gran problema.

Creo que el enlace explicará esto mucho mejor que yo.

Gracias,

Martin

Answer 5

" El problema es el montón de datos en su conjunto.En su primera situación, tenía dos tipos de almacenamiento de datos: (1) una cadena temporal para cada fila en su archivo CSV, con citas fijas y esas cosas, y (2) la cadena gigante que contiene todo. Si cada cadena es 1k y hay 5.000 filas ...

Escenario uno: construir una gran cadena de pequeñas cadenas

cadenas temporales: 5 megas (5.000K) cadena masiva: 5 megas (5.000K) TOTAL: 10 megas (10,000k) La secuencia de comandos mejorada de Dave cambió la cadena masiva por una matriz. Mantuvo las cadenas temporales, pero las almacenó en una matriz. La matriz solo costará 5000 * sizeof (VALOR) en lugar del tamaño completo de cada cadena. Y, en general, un VALOR es de cuatro bytes.

Escenario dos: el almacenamiento de cadenas en una matriz

cuerdas: 5 megas (5.000K) arsenal masivo: 20k

Entonces, cuando tenemos que hacer una gran cadena, que llamamos unirse. Ahora tenemos hasta 10 megas y de repente todas esas cuerdas se convierten en cuerdas temporales y todas pueden ser liberadas a la vez. Es un gran costo al final, pero es mucho más eficiente que un crescendo gradual que consume recursos todo el tiempo. "

http://viewsourcecode.org/why/hacking/theFullyUpturnedBin.html

^En realidad es mejor que en el desempeño para la recolección de la memoria/basura para retrasar la operación hasta el final al igual que me enseñaron en Python. La razón comienzan que se obtiene una gran parte de asignación hacia el final y una liberación instantánea de objetos