Распределение переменных действительно дорого в Ruby или оптимизирует цепочечные методы?

Question

У меня есть следующий метод, который я написал для Project Euler - задача 36 . Все, что он делает, это складывает все числа менее 1 000 000, которые являются палиндромами как в базе 10, так и в базе 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

Теперь это работает и дает правильный результат всего за 1 секунду. Я хотел получить его менее чем за 1 секунду, поэтому я решил сократить количество раз, когда я преобразовывал числа в строки. Поэтому я внес следующие изменения:

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

Проблема в том, что эта версия работает примерно на 50% медленнее , чем оригинал. Таким образом, вопрос заключается в следующем: действительно ли медленно, чтобы выделить эти две переменные? Или Ruby оптимизирует цепочечные вызовы методов?

Answer 1

В этой строке

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

вторая часть не выполняется, если первая часть false (операторы Ruby's &&, короткое замыкание оператора в отличие от & аналога ).Это экономит много звонков на to_s(2).

Answer 2

Интересно.

Обычное правило производительности Ruby: если программа использует встроенные операции, она будет быстрой. Если этого не произойдет, это будет медленно.

Даже если ваша вторая версия может выполнять или не выполнять меньшее преобразование, она выполняет три строки Ruby против одной.

Однажды я прочитал большой лог-файл. В моей первой версии я держал эффективный связанный список строк, используя код Ruby.

1. Сложность времени: O (1).

Затем я изменил его, чтобы использовать << и прикрепить каждый новый узел к концу массива.

2. Сложность времени: O (N ² ) или не менее O (N ^{1 + ε} )

Вторая версия ⁽¹⁾ была быстрее.

---

^{1. Очевидно, что реализация расширяла массив порциями, поэтому он не был полностью квадратичным, но все же выполнял намного больше работы, чем связанный список.}