ผมเห็นหัวข้อ 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
Thank you Aj. Ko. 🙂
I have never tried psyco before (I surprise that 2 lines of code can save a lot of seconds.).
When I have to work with a lot of number manipulations, I use only numpy. This also save a computing time too.
Yep, if you are doing numerically intensive calculation in Python, you should use numpy and/or psyco.
The key to make Python fast enough is to delegate as much work as possible to library functions since they are highly optimized. Of course, this assumes that we already choose an appropriate algorithm for our work.
On the other hand, a lazy+quick way is to enable psyco and see if anything improve!
😀
def fib(n):
a, b = 0, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(1000)