Число Takeuchi в Clojure (производительность)

Question

При вычислении Takeuchi numbers нам нужно выяснить, сколько раз функция вызывает себя. Я быстро придумал:

(def number (atom 0)) 

(defn tak [x y z] 
    (if (<= x y) 
    y 
    (do 
     (dosync (swap! number inc)) 
     (tak (tak (dec x) y z) 
      (tak (dec y) z x) 
      (tak (dec z) x y))))) 

(defn takeuchi_number [n] 
    (dosync (reset! number 0)) 
    (tak n 0 (inc n)) 
    @number) 

(time (takeuchi_number 10)) 
; 1029803 
; "Elapsed time: 11155.012266 msecs" 

Но производительность очень плохая. Как сделать это невероятно быстро в Clojure?

Answer 1

Как говорит кто-то, удаление dosync, кажется, улучшает ситуацию в 10 раз, но это не вся история. Как только JVM имеет hotspotted ваш код, он получает еще один фактор на 10 быстрее. Вот почему вы должны использовать критериум или подобный, чтобы проверить реальную скорость ...

(def number (atom 0)) 

(defn tak [x y z] 
    (if (<= x y) 
    y 
    (do 
     (swap! number inc) 
     (tak (tak (dec x) y z) 
      (tak (dec y) z x) 
      (tak (dec z) x y))))) 

(defn takeuchi_number [n] 
    (reset! number 0) 
    (tak n 0 (inc n)) 
    @number) 

;=> (time (takeuchi_number 10)) 
; "Elapsed time: 450.028 msecs" 
; 1029803 
;=> (time (takeuchi_number 10)) 
; "Elapsed time: 42.008 msecs" 
; 1029803 

Оригинала с dosync был около 5 секунд на моей машине, поэтому мы два порядка основания 10 магнитуды уже! Это лучшее, что мы можем сделать? Давайте реорганизуем чистые функции и убежим от счетчика.

(defn tak [c x y z] 
    (if (<= x y) 
    [c y] 
    (let [[a- x-] (tak 0 (dec x) y z) 
      [b- y-] (tak 0 (dec y) z x) 
      [c- z-] (tak 0 (dec z) x y)] 
     (recur (+' 1 a- b- c- c) x- y- z-)))) 

(defn takeuchi_number [n] 
    (tak 0 n 0 (inc n))) 

;=> (time (takeuchi_number 10)) 
; "Elapsed time: 330.741 msecs" 
; [1029803 11] 
;=> (time (takeuchi_number 10)) 
; "Elapsed time: 137.829 msecs" 
; [1029803 11] 
;=> (time (takeuchi_number 10)) 
; "Elapsed time: 136.866 msecs" 
; [1029803 11] 

Не так хорошо. Стоимость хранения состояния в векторе и его передачи, вероятно, является накладными расходами. Однако теперь мы переработали чистоту, давайте воспользуемся нашим хорошим поведением!

=> (def tak (memoize tak)) 
#'euler.tak/tak 
=> (time (takeuchi_number 10)) 
"Elapsed time: 1.401 msecs" 
[1029803 11] 

Здоровые 3000 или около того раз быстрее. Работает на меня.

Answer 2

Чисто функциональный способ реализации это будет для вашей tak функции возвращает пару [result count], где result является фактическим результатом tak вычислений и count является числом раз функция рекурсивно называют себя. Но в этом случае я думаю, что это вызовет всевозможные болезненные искажения в теле функции и не будет стоить того.

Использование atom здесь, в то время как идиоматический Clojure, налагает ненужные накладные расходы; он действительно нацелен на синхронизацию независимых обновлений с общим состоянием между потоками. В основном то, что вы хотите, - это изменяемый объект, который вы можете передать для рекурсивных вызовов функций в том же потоке, без необходимости синхронизации. Массив должен быть достаточным для этой цели:

(defn tak [x y z ^longs counter] 
    (if (<= x y) 
    y 
    (do 
     (aset counter 0 (inc (aget counter 0))) 
     (tak (tak (dec x) y z counter) 
      (tak (dec y) z x counter) 
      (tak (dec z) x y counter) 
      counter)))) 

(defn takeuchi_number [n] 
    (let [counter (long-array [0])] 
    (tak n 0 (inc n) counter) 
    (aget counter 0))) 

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