programming

JavaScript Closure

posted on 25 Mar 2009 00:37 by ipats
[เรื่องเขียนโปรแกรม มึนๆ น้อ]

พอดีวันนี้ลองเขียนเล่น แล้วติดปัญหาอยู่อย่างนึง.. ทำเอามึนไปนานโข พอแก้ได้แล้วเลยลองหาข้อมูลดู ปรากฏว่า เค้าก็เป็นกัน 555 (ดีใจ ที่ไม่ได้มึนไปคนเดียว)

ปัญหาที่ว่าเป็นอย่างไร ของดูโค้ดสั้นๆ ข้างล่างนี้เลย (เป็น JavaScript เน้อ)

var func = [];
for(var i=0; i<10; i++) {
    func[i] = function ()    {
        alert(i);
    };
}
func[5]();

คำถามคือ.. โค้ดนี้มันจะ alert ค่าอะไรออกมา?

ตอบอย่างรวดเร็ว 5 แน่ๆ

ผิด! ผ่างๆๆๆๆๆ

เหตุผลเพราะ function ที่สร้างขึ้นมาข้างในมันอ้าง i เป็นตัวเดียวกับใน loop ซึ่งมันอ้างแบบอิงตัวแปรเลย ไม่ได้เอาค่ามาใช้อย่างที่ผมคาดว่ามันจะทำ Y-Y

แต่มันไม่ใช่ที่ผมต้องการหน่ะซิ ง่ะ.. เลยต้องหาวิธีแก้ ก็ออกมาเป็นประมาณนี้ (กว่าจะได้.. รากเลือด)

function makefunc(i) {
    return function ()    {
        alert(i);
    };
}

var func = [];
for(var i=0; i<10; i++) {
    func[i] = makefunc(i);
}

func[5]();

ที่ทำแบบนี้ได้ เพราะเมื่อเรา call makefunc(i) มันจะ pass ค่า i ไปเข้าใน function ซึ่งในนั้นก็จะเป็นอีกสโคปนึง (ประมาณว่ามันจะก็อปค่าไป ไม่ได้อิงกับตัวเดิม)

ทำเสร็จก็ไปค้นๆ ดู เค้ามีอธิบายไว้ค่อนข้างละเอียด (เคสเดียวกันเลย เหอๆ)
Explaining JavaScript scope and closures (อันนี้เค้าใช้ self-invoking functions ไฮโซมาก)
More closure examples


ปล. รากเลือดนะ ไม่ใช่ลากเลือด "ราก" แปลว่าอ้วก (รู้จักครั้งแรกเมื่ออ่านขายหัวเราะ - ใครว่าอ่านการ์ตูนไร้สาระ :p ) เพราะฉะนั้น รากเลือดก็คือ อาการที่เหนื่อยสาหัสจนอ้วกเป็นเลือกนั้นเอง โฮะๆๆ

Fibonacci ภาค 2

posted on 04 Jun 2008 05:39 by ipats

สวัสดีครับ
จำเรื่องที่แล้วได้ไหม? ที่พูดถึงเลข fibonacci เอาไว้ และก็ทิ้งโค้ดไว้สามชุด

คราวนี้ เรามาดูกันดีกว่า ว่าโค้ดทั้งสามชุดนั้นมันเป็นยังไงกันบ้าง
ก่อนอ่าน ลองนึกๆ ดูเล่นๆ กันก่อนนะว่า อันไหนคำนวณยังไง ใช้หน่วยความจำอย่างไร

อ่ะ... อันแรก (เอาโค้ดมาเป็นรูป มีสีๆ ด้วย.. อยากได้เป็นข้อความไปดูในเอ็นทรีเก่านะครับ)


วิธีนี้ ใช้เทคนิคที่เรียกว่า recursive function หรือฟังก์ชันเรียกตัวเอง
การเขียนแบบนี้ ก็ตามนิยามของมันเลยครับ ซึ่งก็เป็นข้อดีของมัน คือ อ่านเข้าใจง่าย เขียนง่าย
แต่ มันก็มีข้อเสียครับ ลองดูรูปข้างล่างนี้ เป็นตัวอย่างการหาเลข F5



จะเห็นว่า มันมีการเรียกฟังก์ชันอย่างซ้ำซ้อน และเยอะแยะมาก ทำให้คำนวณผลลัพธ์ออกมาช้ามาก
โดยเวลาที่ใช้ในวิธีนี้จะเติบโตแบบ exponential หรือ O(2n)
ซึ่งก็หมายความว่า ยิ่งหาตัวเลขทีอันดับมากๆ ยิ่งใช้เวลาเป็นเท่าตัว (เช่น F5 ใช้เวลา X เท่าของ F4)

ส่วนเรื่องหน่วยความจำที่ใช้ ดูเผินๆ จะใช้น้อย เพราะไม่มีตัวแปรในฟังก์ชันเลย
แต่จริงๆ n ก็เป็นตัวแปรนะ และการเรียกฟังก์ชันซ้ำแต่ละครั้ง
ก็ต้องใช้หน่วยความจำในการเก็บสถานะของการเรียกอีกด้วย ซึ่งถ้าสังเกตดู จะเห็นว่าจำนวนชั้นที่ลึกที่สุดของการเรียกฟังก์ชัน จะแปรตาม n แบบเชิงเส้น หรือ O(n)
ซึ่งก็คือ n ยิ่งมาก ก็ต้องใช้หน่วยความจำมากขึ้น เพื่อจัดเก็บสถานะในการเรียกฟังก์ชัน

วิธีการคิดแบบนี้นี้ มีชื่อเรียกเฉพาะว่า Tree Recursion

ถัดมา อันที่สอง


วิธีนี้ ใช้สิ่งที่เรียกว่า Lookup table (คือหาผลลัพธ์ใช้ตารางที่เก็บผลลัพธ์ที่คำนวณไว้เรียบร้อยแล้ว)
ซึ่งจะเห็นว่า การคำนวณจะถูกทำครั้งแรกที่ฟังก์ชันถูกเรียกเพียงครั้งเดียว (ถือเป็น initialization)
หลังจากนั้น ก็เอาค่าที่คำนวณไว้แล้ว มาตอบเลย


[ ภาพ: วิธีการคำนวณเพื่อทำตาราง โดยคำนวณเชิงเส้นไปเรื่อยๆ ]

ด้วยเทคนิคนี้ จึงทำให้วิธีนี้ ใช้เวลาในการคำนวณคำตอบคงที่ตลอด (ไม่นับขั้นเริ่มต้น)
นั่นก็คือ O(1) นั่นเองซึ่งก็ถือว่าเป็น order ที่เร็วที่สุด
แต่นั่น ก็ต้องแลกด้วยการใช้หน่วยความจำในการเก็บตาราง ซึ่งก็ใช้เป็น O(n)

สุดท้าย


วิธีนี้ คำนวณโดยใช้ Circular buffer เข้ามาช่วย ทำให้ใช้หน่วยความจำน้อยมาก และเป็นค่าคงที่
ซึ่งก็คือ ใช้หน่วยความจำเป็น O(1)

แต่ทุกๆ ครั้งของการเรียกฟังก์ชัน ก็ยังต้องมีการคำนวณผลใหม่ทุกครั้ง จึงทำให้การใช้เวลายังคงเป็น O(n) อยู่


ภาพ: circular buffer ที่ใช้ในตัวอย่างนี้ จะเห็นว่า ตำแหน่งที่เก็บจะวนไปเรื่อยๆ
ถ้าดูในโค้ด ก็จะเห็นว่า ผมใช้วิธีการบวก แทนลบ คือ X + 1 แทนที่จะเป็น X - 2
เพื่อหลีกเลี่ยงปัญหาเลขติดลบ ซึ่งอาจเกิดปัญหาในการ mod ขึ้นได้

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

แล้ว B มันเร็วกว่า C เสมอมั๊ย? ก็ไม่อีกนั่นแหละ
ลองคิดดูว่า ถ้าเราเรียกครั้งเดียว หา F5 ถ้าแบบ B มันต้องคำนวณไปถึง F40 ก่อน
แต่ถ้า เราเรียกซักร้อยรอบล่ะ อันนี้แบบ B ก็ควรจะเร็วกว่าแน่ๆ
ก็เหมือนกับ ระบบแคช ที่ต้องดู hit rate และผลของมัน ว่าคุ้มค่าแค่ไหน

ส่วนแบบ A นั่น ก็ใช่ว่ามันจะไม่มีประโยชน์ อย่างน้อยมันก็เข้าใจได้ง่ายหล่ะน่า
นอกจากนี้ เรายังสามารถทำอะไรคล้ายๆ กันนี้ แต่ไม่จำเป็นต้องทำการเรียกตัวเองได้ด้วย
ลองไปดูตัวอย่างโค้ด directory traversal ใน เอ็นทรีี้นี้ดูนะครับ
จะเห็นว่ามันเป็นวิธีการท่องไปตามต้นไม้แบบ DFS นั่นเอง ซึ่งสามารถเขียนแบบเรียกตัวเองได้อย่างง่ายๆ
และก็สามารถเลี่ยงโดยใช้ list/stack เข้ามาแทน (ลองดูในโค้ดผม หรือในวิกิก็ได้)


สุดท้าย.. ของแถม



ปล. มีคนตั้งข้อสังเกตเรื่องการยกตัวอย่างการหา fac ...
เรื่องของเรื่องที่ผมใช้ fibo ก็เพราะมันเห็นความแตกต่างชัดหน่อยครับ เพราะ มันไปเรียกซ้ำสองรอบแหนะ ;)

ปล2. มีอะไรผิดก็ติติงได้นะครับ ไม่ได้ใช้พวกนี้มานาน นานๆ เอามารื้อฝื้นหน่อย กันลืม

Fibonacci

posted on 02 Jun 2008 22:55 by ipats
สวัสดีครับ
ก่อนอื่น ก็ขอขอบคุณทุกๆ คน ที่อวยพรวันเกิด exteen ให้นะครับ
ตอนแรกว่าจะเขียนบล็อกถึงเหมือนกัน แต่ด้วยตัวแปรบางอย่าง เลยขอติดไว้ก่อนนะครับ ;)

พอดีว่าช่วงนี้เพิงได้ดูซีรีย์ Numb3rs มาครับ สนุกดีอ่ะ
แล้วบวกกับวันนี้คุยกับอ. มะนาวนิดหน่อย ว่าอาจารย์กำลังสอนเด็กอยู่
วิชา practicum สอน python ซะด้วยอ่ะ.. สมัยนี้เขา พัต-ตะ-นา แล้วววว
(หมายเหตุ: วิชานี้ เป็นวิชาแนวๆ เตรียมความพร้อมเด็กปีสอง สอบพื้นฐานหลายอย่างมาก)

มันก็เลยเกิดการคิดถึงสมัยเรียน (แก่แล้วเนาะ)
แถมวันนี้ได้มีบทสนทนาเกี่ยวกับแนวคิดการเขียนโปรแกรมนิดหน่อย
เลยมีไอเดียเขียนบล็อกขึ้นมาซะงั้น ;)

วันนี้ จะมาเขียนถึงเรื่อง การแก้ปัญหา, เขียนโปรแกรม โดยใช้กรณีเลข Fibonacci ครับ

ก่อนอื่น ก็คงต้องว่ากันก่อนว่า ไอ้เลขนี้คืออะไร
เลข Fibonacci เป็นชุดตัวเลข ที่เลขตัวใดๆ ในชุด จะมาจากผมรวมของเลขสองตัวหน้ามัน
โดยกำหนดเริ่มต้นให้ เลขสองตัวแรก (คือตัวที่ 0 และตัวที่ 1) คือ 0 กับ 1 ตามลำดับ

ลองมาดูนิยามทางคณิตศาสตร์ และตัวเลขสิบเอ็ดตัวแรกกันครับ (จากวิกิ)



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

เพราะงั้น ผมก็เลย.. ขอเขียนมันซะหน่อย โดยใช้ภาษาซี และจำกัดให้หาได้ถึงแค่ F(40)
ซึ่งลองเขียนมาสามแบบดังนี้ครับ

แบบแรก
long int fibo1(int n){
if ((n < 0) || (n > 40)) {
return -1;
} else if (n < 2) {
return n;
} else {
return fibo1(n - 1) + fibo1(n - 2);
}
}

แบบที่สอง
int fibocal = 0;
long int fibotab[41];

long int fibo2(int n){
int i;
if (!fibocal) {
fibotab[0] = 0;
fibotab[1] = 1;
for(i=2;i<=40;i++){
fibotab[i] = fibotab[i - 1] + fibotab[i - 2];
}
fibocal = 1;
}

return ((n<=40) && (n>=0))?fibotab[n]:-1;
}

แบบที่สาม
long int fibo3(int n){
long int clist[3];
int i;
if ((n < 0) || (n > 40)) {
return -1;
} else if (n < 2) {
return n;
} else {
clist[0] = 0;
clist[1] = 1;
for(i=2;i<=n;i++) {
clist[i % 3] = clist[(i + 2) % 3] + clist[(i + 1) % 3];
}
return clist[(i - 1) % 3];
}
}


ถ้าใครอ่านโค้ดเข้าใจ ลองอ่านดูนะครับ
แล้วคิดหน่อยว่า... สามแบบนี้ มันต่างกันยังไง ข้อดีข้อเสียแต่ะแบบเป็นยังไง
แล้วคราวหน้า ผมจะมาลองเล่าให้ฟัง (อุ๊บไว้ก่อน อิอิ)

ทิ้งท้าย เฉลยโค้ดเก่าหน่อย (เหลือบไปเห็นมีคนมาตอบพอดี 555)
เริ่มจาก
ybtb ng uhaqerq qvi guerr cyhf sbhe.cv naq n dhnegre bs sbhe fvk guerr qbhoyr h

อันนี้มีคนบอกว่า แค่เห็นก็รู้แล้วว่าแปลงกลับยังไง ซึ่งมันก็ได้เป็น
logo at hundred div three plus four.pi and a quarter of four six three double u

ขั้นตอนนี้ใช้ ROT13 ครับ เป็นการเข้ารหัสแบบง่ายๆ โดยการแทนที่ด้วยตัวอักษรสิบสามตัวถัดไป
ในภาษาอังกฤษมันมี 26 ตัว ก็คือครึ่งนึงพอดี เวลาจะเข้ารหัส หรือถอดรหัส ก็เลยใช้วิธีเดียวกัน

ทีนี้ จากประโยคนั้น มันก็ได้เป็น
logo ที่ 100 / 3 + 4.31416 และ 1/4 * 463 W
logo ที่ 37.64749 และ 115.75 W

เห็นเลขสองตัว พร้อมคำว่า ที่ (at) ก็ควรจะนึกถึงพิกัดอะไรซักอย่างเนาะ
แถมมีตัว W ห้อยท้าย... พิกัดไรน้อ มี W ด้วย...

ติ๊ก ต๊อก ติ๊ก ต็อก

มันคือ lat/long นั่นเอง เอ๊า.. จิ้มไปโลด
(W = West ใน Google Map ก็แทนด้วยค่าติดลบนั่นเอง)

ปล. เลขไฟโบ มีชื่อเล่น (ที่ตั้งเอง) ว่า.. "เลขกระต่ายเอากัน" :p
(อยากรู้ทำไม ไปดูในวิกิ หาคำว่า rabbit ในหน้านั่นอ่ะ)