Is variable allocation really expensive in Ruby, or does it optimize chained string methods?

I have the following method that I wrote for Project Euler - Problem 36. All it does is add up all the numbers less than 1,000,000 that are palindromes in both base 10 and 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

Now, this works and gives the correct result in just over 1 second. I wanted to get it under 1 second, so I decided I would reduce the number of times I was converting numbers to strings. So I made the following changes:

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

The trouble is, this version actually runs about 50% slower than the original. So the question is this: is it really that slow to allocate those two va开发者_如何学Criables? Or is Ruby optimizing the chained method calls?

---

In this line

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

the second part is not executed if the first part is false (Ruby's && operator short-circuits, unlike its & counterpart). That saves a lot of calls to to_s(2).

---

Interesting.

The usual Ruby performance rule is that if a program uses the built-in operations, it will be fast. If it doesn't, it will be slow.

Even though your second version may or may not do less converting, it executes three Ruby lines vs one.

I once read a large logfile. In my first version, I kept an efficient linked list of the lines using Ruby code.

1. Time complexity: O(1).

I then changed it to just use << and tack each new node onto the end of an Array.

2. Time complexity: O(N²), or at least O(N^{1 + ε})

The second version⁽¹⁾ was faster.

---

^{1. Obviously the implementation was expanding the array in chunks, so it wasn't fully quadratic, but still a lot more work than a linked list.}