Category Archives: programming

คำนวณเลข Fibonacci ด้วย Python แบบไม่ช้านัก

ผมเห็นหัวข้อ 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

Understand Classical Mechanics Precisely, Very Precisely

The excellent Nerd Wisdom website steered me toward a most unusual book about understand classical mechanics (Lagrangian and friends, see contents for details) precisely enough that computers can manipulate the expressions involved. Not numerical values, expressions.

I remember that when I learned about all these stuffs back in college, I was a master of symbol manipulation and automatically assumed or ignored details as necessary to arrive at the final solutions. Many of my friends had more trouble doing this since they were more precise thinkers and never got used to hand-waving arguments involved. This book would be a great boon to them. There’s no ambiguity left in the symbols if computers can understand them.

Young physicists in training might find this useful too.