¿La asignación variable es realmente cara en Ruby, o optimiza los métodos de cadena encadenada?

Question

Tengo el siguiente método que escribí para Project Euler - Problem 36. Todo lo que hace es sumar todos los números menos de 1.000.000 que son palíndromos, tanto en la base 10 y la base 2.

def problem_36 
    (1...1_000_000).select do |n| 
    n.to_s == n.to_s.reverse && n.to_s(2) == n.to_s(2).reverse 
    end 
end 

Ahora, esto funciona y da el resultado correcto en poco más de 1 segundo. Quería que fuera menos de 1 segundo, así que decidí reducir la cantidad de veces que convertía números a cadenas. Así que hice los siguientes cambios:

def problem_36 
    (1...1_000_000).select do |n| 
    base10 = n.to_s 
    base2 = n.to_s(2) 
    base10 == base10.reverse && base2 == base2.reverse 
    end 
end 

El problema es que esta versión realmente ejecuta alrededor del 50% más lenta que el original. Entonces, la pregunta es: ¿es realmente tan lento asignar esas dos variables? ¿O está Ruby optimizando las llamadas al método encadenado?

Answer 1

En esta línea

n.to_s == n.to_s.reverse && n.to_s(2) == n.to_s(2).reverse 

la segunda parte no se ejecuta si la primera parte es false (&& operador cortocircuitos de Ruby, unlike its & counterpart). Eso ahorra muchas llamadas al to_s(2).

Answer 2

Interesante.

La regla de rendimiento de Ruby habitual es que si un programa utiliza las operaciones integradas, será rápido. Si no lo hace, será lento.

Aunque su segunda versión puede o no hacer menos conversiones, ejecuta tres líneas de Ruby contra una.

Una vez leí un archivo de registro de gran tamaño. En mi primera versión, mantuve una lista enlazada eficiente de las líneas usando el código de Ruby.

1. Complejidad del tiempo: O (1).

Luego lo cambié para simplemente usar << y virar cada nuevo nodo al final de una matriz.

2. complejidad Tiempo: O (N), o al menos O (N ^{1 + ε})

La segunda versión ⁽¹⁾ fue más rápido.

---

^{1. Es evidente que la aplicación fue la expansión de la matriz en trozos, por lo que no era totalmente cuadrática, pero todavía mucho más trabajo que una lista enlazada.}