Не должна ли хвостовая рекурсивная функция быть быстрее

Question

У меня есть следующий код Clojure для вычисления числа с определенным «факториальным» свойством. (что именно код делает вторичным).

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

Теперь я в TCO и понимаю, что Clojure может обеспечить хвостовую рекурсию только в том случае, если это явно указано, используя ключевое слово recur. Поэтому я переписал код для этого (замена фактора-9 на recur - единственное отличие):

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (recur (quot n 10))))))

Насколько мне известно, ТШО имеет двойную выгоду. Первый состоит в том, что он не использует стек так сильно, как нерекурсивный вызов, и, следовательно, не использует его при больших рекурсиях. Во-вторых, я думаю, что, следовательно, он быстрее, поскольку его можно преобразовать в цикл.

Итак, я сделал очень грубый тест и не видел никакой разницы между этими двумя реализациями. Я ошибаюсь во втором предположении, или это как-то связано с работой на JVM (у которой нет автоматической TCO) и recur с использованием трюка для достижения этой цели?

Спасибо.

Answer 1

Использование recur ускоряет процесс, но только на 3 наносекунды (действительно) по сравнению с рекурсивным вызовом. Когда вещи становятся такими маленькими, они могут быть скрыты в шуме остальной части теста. Я написал четыре теста (ссылка ниже), которые могут проиллюстрировать разницу в производительности.

Я бы также предложил использовать что-то вроде критерия при тестировании. (Переполнение стека не позволяет мне публиковать более 1 ссылки, так как у меня нет репутации, о которой я могу говорить, поэтому вам придется поискать ее в Google, может быть, «критерий Clojure»)

По причинам форматирования я поместил тесты и результаты в эту гист .

Вкратце, для сравнения, если рекурсивный тест равен 1, то тест циклический составляет около 0,45, а тест TCO - около 0,87, а абсолютная разница между тестами рекурсивный и TCO - около 3 нс

Конечно, все применяются предостережения относительно бенчмаркинга.

Answer 2

При оптимизации любого кода полезно начинать с потенциальных или реальных узких мест и сначала оптимизировать их.

Мне кажется, что этот конкретный фрагмент кода потребляет большую часть вашего процессорного времени:

 (map (fn [x] ,(Integer. (apply str x))) (permutations digits))

И это никак не зависит от TCO - оно выполняется таким же образом. Таким образом, хвостовой вызов в этом конкретном примере позволит вам не использовать весь стек, но для достижения лучшей производительности попробуйте оптимизировать это.

Answer 3

просто языческое напоминание, что у clojure нет TCO

Answer 4

После оценки factor-9 (quot n 10) необходимо проверить and и or, прежде чем функция сможет вернуться.Таким образом, это не хвостовая рекурсия.