Category Archives: ภาษาไทย

คำนวณเลข 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

ข่าวน่าชื่นใจ

เด็กออสเตรเลียอายุ 14 ปี (เป็นนักดนตรีพังค์ร็อคด้วย) เสี่ยงชีวิตเข้าช่วยชายอายุ 54 ปีที่เป็นลมตกลงไปในรางรถไฟ

เขาเรียนรู้เรื่องแรงลมดูดจากการเคลื่อนที่ของรถไฟจากรายการ Myth Buster ด้วย!

ฝูงปลาโลมาเข้าช่วยคนที่ถูกฉลามขาวกัด โดยว่ายน้ำล้อมรอบคนไม่ให้ฉลามเข้าใกล้

คุณสงสัยไหมว่าทำไมสิ่งมีชีวิตถึงช่วยเหลือกัน ถ้าสงสัยอาจจะอยากอ่านหนังสือที่ผมเคยแนะนำเรื่อง The Evolution of Cooperation

ศาสนาเป็นผลจากจริยธรรมที่มีอยู่แล้วในตัวคน(และสัตว์)ที่เกิดขึ้นมาตามธรรมชาติ ไม่ใช่เหตุ (ดังนั้นควรระวังเวลาศาสนากลายพันธ์ุและเป็นโทษกับมนุษยชาติด้วย จงเชื่ออะไรอย่างมีเหตุผล ไม่งมงาย)

ทำไมการดูชะตาชีวิตด้วยวันเดือนปีเกิดจึงไม่น่าจะทำได้

สมมุติว่าหมอดูสามารถดูชะตาชีวิตด้วยวันเดือนปีเกิดได้ แสดงว่าหมอดูสามารถใช้ฟังค์ชัน f(d) ที่รับค่าวันเดือนปีเกิด d เข้าไป แล้วให้คำทำนายชะตาชีวิต p ที่ถูกต้อง

หรือแสดงว่า มี f ที่ f(d) = p

ถ้า f มีจริง คุณสมบัติของ f จะเป็นอย่างไร?

เราสามารถรู้ว่าคุณสมบัติของ f เป็นอย่างไรได้โดยการดูชะตาชีวิตของฝาแฝด เราพบว่าฝาแฝดที่เกิดที่เวลาต่างกันนิดเดียว(เป็นหลักนาที) มีชะตาชีวิตที่ต่างกันได้มากมาย (เช่นตายไม่พร้อมกัน นิสัยต่างกัน ป่วยต่างกัน ฯลฯ) แสดงว่า f ขึ้นอยู่กับวันเดือนปีเกิด d แบบอ่อนไหวมาก คือ ถ้าค่า d เปลี่ยนไปนิดเดียวจะสามารถทำให้ f(d) เปลี่ยนไปเยอะมาก

คุณสมบัตินี้แปลว่าอะไร มันแปลว่าถ้าเราไม่สามารถให้ข้อมูลวันเดือนปีเกิดที่ละเอียดและถูกต้องมากๆ คำทำนายชีวิตที่ได้ก็จะคลาดเคลื่อนไปมากจนไม่เหมือนชีวิตเรา เช่นถ้าคลาดเคลื่อนไปสองสามนาที จะทำให้คำทำนายออกทะเลไปเลย ด้วยคุณสมบัติของ f ดังที่กล่าวมา

โดยส่วนตัวผมไม่คิดว่าฟังค์ชัน f จะมีตัวตนอยู่แล้ว แต่ถึงแม้ว่า f จะมีตัวตน คุณสมบัติที่ f ขึ้นอยู่กับวันเดือนปีเกิด d แบบอ่อนไหวมาก ก็ทำให้ไม่สามารถใช้ทำนายได้อยู่ดี
— – —- – —– ———
ป.ล.
1. ถ้าอ่านหรือฟังภาษาอังกฤษได้ ลองค้นคว้าดูว่าหมอดู(และผู้วิเศษทั้งหลาย)หลอกชาวบ้านอย่างไร ด้วยการค้นหาด้วย keywords เช่น “cold reading” ผมมีตัวอย่าง links ให้สามอัน: 1, 2, 3

2. ลองหา video clips ของ Derren Brown ดูที่ YouTube เพื่อดูเทคนิคการทำให้คนคล้อยตาม และคิดว่าเราเป็นผู้วิเศษ

3. ถ้ารู้เรื่อง probability บ้าง ปรากฎการณ์แปลกๆ ก็อาจจะไม่แปลกนัก

4. ถ้าคุณเป็นหมอดูที่เก่งจริง หรือรู้จักหมอดูที่เก่งจริง คุณอาจจะได้รางวัล $1,000,000 มาใช้ก็ได้!

5. ภาพประกอบไม่เกี่ยวกับบทความเลย ผมแค่อยากโชว์ท่าแปลงร่างของลูกผมเท่านั้น