ผมเห็นหัวข้อ blog post ว่า “Holy Shmoly, Ruby 1.9 smokes Python away!” ก็เลยกดเข้าไปดู ปรากฎว่าผู้เขียนได้จับเวลาการคำนวณเลข Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, 21, … ) หรือเลขตัวที่ n เท่ากับผลรวมของตัวที่ n-1 กับ n-2 และ Python ใช้เวลาประมาณ 30 วินาที ขณะที่ Ruby 1.9.0 ใช้ประมาณ 12 วินาที ในการคำนวณตัวเลข 35 ตัวแรก

โปรแกรมที่ใช้คำนวณหน้าตาแบบนี้:

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

for i in range(36):
    print "n=%d => %d" % (i, fib(i))

ผมลองรันโปรแกรมบนเครื่องผมก็ใช้เวลา 36 วินาที ผมรู้สึกประหลาดใจเนื่องจากไม่คิดว่าจะใช้เวลานานอย่างนี้เลยคิดถึงสาเหตุที่ทำให้ใช้เวลานาน สาเหตุที่ผมพบมีดังนี้:

1. ตัวแปรในภาษา Python เป็นตัวแปรที่มี run-time type information ที่ CPU ไม่สามารถทำการคำนวณโดยตรงได้เหมือนตัวแปรพวก int หรือ double ในภาษา C

เวลา Python interpreter ทำการคำนวณ จะต้องหาว่าตัวแปรเป็นประเภทอะไรก่อน จึงจะเลือกคำสั่ง CPU ที่ถูกมาใช้

2. จะเห็นได้ว่าฟังค์ชัน fib(n) เป็นฟังค์ชันที่เรียกตัวเอง (หรือ recursive function) คือการคำนวณ fib(n) จะเรียกใช้ fib(n-1) และ fib(n-2) และค่า fib(0), fib(1), …, fib(k) ก็ถูกคำนวณซ้ำซากอยู่บ่อยๆ

ผมก็เลยคิดถึงวิธีที่จะแก้ปัญหาสองข้อนี้ สำหรับสาเหตุข้อแรกเราสามารถใช้เครื่องมือที่เรียกว่า Psyco ซึ่งทำหน้าที่เหมือน JIT (Just-in-Time) compiler ที่แปลงโปรแกรม Python เป็นคำสั่งที่มีประสิทธิภาพสูงของ CPU โดยตรง พอผมเพิ่มสองบันทัด (สีแดง) เข้าไป:

import psyco
psyco.full()

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

for i in range(36):
    print "n=%d => %d" % (i, fib(i))

เวลาในการคำนวณก็ลดจาก 36 วินาทีเหลือ 2 วินาที

สำหรับสาเหตุที่สองเราแก้ได้โดยไม่คำนวณอะไรซ้ำๆ โดยเก็บค่าที่เคยคำนวณไว้ไม่ต้องทำใหม่ทุกๆครั้ง (เทคนิคประเภทนี้เรียกว่า Caching หรือ Memoization):

class cachedFib:
def __init__(self):
    self.f = {}
    self.f[0] = 0
    self.f[1] = 1

def fib(self,n):
    if n in self.f:
        return self.f[n]
    else:
        self.f[n] = self.f[n-1]+self.f[n-2]
        return self.f[n]

cf = cachedFib()
for i in range(36):
    print "n=%d => %d" % (i, cf.fib(i))

เวลาในการคำนวณก็ลดจาก 36 วินาทีเหลือ 0.08 วินาที

— – —- – —– ———
P.S.
1. โปรแกรมสำหรับการคำนวณแบบอื่น (โดยไม่ใช้ recursion และในภาษาอื่นๆ) ดูได้ที่นี่
2. ตาราง Fibonacci 300 ตัวแรก (แถมแยกตัวประกอบ)
3. Fibonacci ตัวที่ 10,000,000
4. สูตรน่าสนใจในการคำนวณเลข Fibonacci