Recursion แบบเร็วขึ้นแต่ออกแรงนิดเดียว

19 มีนาคม 2562

สมัยที่เรียนหนังสือเขามักจะเอา Fibonacci number มาเป็นตัวอย่างกัน function ก็เป็นงี้ครับ

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) สำหรับ n มากกว่า 1

ซึ่งเอามาแปลงเป็น Clojure ได้แบบตรงไปตรงมาเลย

(def fib
  (fn [n]
    (if (<= n 1) n
        (+ (fib (- n 1)) (fib (- n 2))))))

ผมลองรันบนเครื่องผมใช้เวลา 4.324 วินาที ซึ่งมันช้าเพราะไปเรียก fib ซ้ำไปซ้ำมา ดูง่าย ๆ fib(4) ก็ไปเรียก fib(3), fib(2) แล้ว fib(3) ก็ไปเรียก fib(2) อีกซ้ำ พอเลขมากก็ซ้ำไปเรื่อย ๆ

จริง ๆ มันมีวิธีหล่อ ๆ เยอะแยะที่จะแก้ปัญหานี้ให้เร็วขึ้น แต่ถ้าเราไม่ต้องหล่อมาแก้แบบดอกเดียวเสร็จก็ใช้ memoize เขียนแบบนี้

(def fib
  (memoize
   (fn [n]
     (if (<= n 1) n
         (+ (fib (- n 1))
            (fib (- n 2)))))))
(println (time (fib 42)))

แก้นิดเดียวเอา memoize มาครอบ function ไว้ มันจะจำ function ที่เคยเรียกไว้แล้วส่งผลกลับมาเลยโดยไม่ต้องไล่ยาว ผลคือโปรแกรมใช้เวลารันเหลือ 0.820 วินาที

จริง ๆ มันจบแล้วล่ะ แต่เขียนให้ดูอีก function แบบใช้ loop

(defn fib [n]
  (loop [i 1 acc0 0 acc1 1]
    (if (< i n)
      (recur (inc i) acc1 (+ acc0 acc1))
      acc1)))      
(println (time (fib 42)))

อันนี้ใช้เวลาแค่ 0.0976 วินาที แต่ก็จะเห็นได้ว่าโปรแกรมเปลี่ยนไปเยอะ เปลี่ยนวิธีคิดเยอะ memoize นี่มันแทบไม่ต้องคิดต้องเขียนอะไรมากเลย ใส่ไปแล้วได้ผลเลย

ขอบคุณ visibletrap@twitter.com ที่แนะนำ function time มาครับ