Programming: Space-Time Relation

ขอเริ่มต้น post ของวันนี้ด้วยการขอโทษก่อนละกัน วันนี้ (จริง ๆ เมื่อวานด้วย) ไม่ได้ไปเยี่ยมบัณฑิตจุฬา ฯ ที่ไปซ้อมรับปริญญา เพราะมีเหตุการณ์สำคัญเกิดขึ้นที่บ้าน ที่คนทั่ว ๆ ไปคงเรียกว่าปัญหาครอบครัวหนะ

แล้วก็ ... เตือนกันอีกครั้งนะ ... ถ้าจะดู post เก่า ๆ ให้มันเป็นลำดับดี ๆ ไปดูที่นี่

Tunoblog Summarized

มันจะมี link มาที่หน้าของแต่ละ post ใน Tunoblog อันนี้

โปรโมตเสร็จ ก็ขอเข้าเรื่องละกัน คราวนี้จะพูดถึงความสัมพันธ์ระหว่าง ความเร็วของ algorithm กับเนื้อที่ memory ที่จะต้องใช้

สำหรับปัญหาปัญหานึง เราอาจจะมีวิธีแก้หลาย ๆ แบบ ซึ่งสำหรับนักเขียนโปรแกรมเนี่ย เค้ามักถามกันว่า "บิ๊กโอ (Big-O = O ใหญ่น่ะแหละ) เท่าไหร่?"

ใครที่ยังไม่รู้จัก O ตัวนี้ ก็ขอพูดคร่าว ๆ ละกัน

O(g) = { f | f(x) เพิ่มไม่เร็วกว่า g(x) เมื่อ x มีค่ามาก ๆ }

จริง ๆ นิยามแบบชัด ๆ มันก็มีอยู่อะนะ แต่ขี้เกียจยกมา ไปดูเอาเองจาก Wikipedia ละกัน :P

มาต่อกันเรื่องหลัก คราวนี้มาสนใจเรื่อง Space-Time ดีกว่า ...

ทฤษฎีสัมพัทธภาพ

ม่ายช่ายและ :P ... จะพูดถึง Big-O ของเวลา กับ เนื้อที่ memory ที่ algorithm ใช้ตะหาก

Sorting Algorithm

ปัญหาการเรียงข้อมูลเนี่ย เป็นปัญหาสุดคลาสสิก ที่น่าเอามาพูดถึงที่สุด วิธีการเรียงที่นิยมสอนกัน มักจะมีอยู่เท่านี้ (ขาดเกินบ้างนิดหน่อย)

• Selection Sort - ใช้เวลา O(n²) เมื่อมีข้อมูล n ตัว
• Bubble Sort - ใช้เวลา O(n²)
• Insertion Sort - ใช้เวลา O(n²)
• Shell Sort - ใช้เวลา O(n^1.5) (จริง ๆ มี O(n log²n) นะ ดูที่นี่)
• Merge Sort - ใช้เวลา O(n log n)
• Quick Sort - ใช้เวลา O(n log n) (เฉลี่ย)
• Heap Sort - ใช้เวลา O(n log n)
• Bucket Sort - ใช้เวลา O(m + n)
• Radix Sort - ใช้เวลา O(n log m)

เมื่อ n คือจำนวนข้อมูล และ m คือขนาดของ domain ของข้อมูล จะเห็นว่า 7 วิธีแรก ทำงานเร็วกว่า 2 วิธีสุดท้ายในกรณีที่ m มากกว่า n มาก ๆ

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

• Selection Sort - ใช้เนื้อที่เพิ่ม O(1)
• Bubble Sort - ใช้เนื้อที่เพิ่ม O(1)
• Insertion Sort - ใช้เนื้อที่เพิ่ม O(1)
• Shell Sort - ใช้เนื้อที่เพิ่ม O(1)
• Merge Sort - ใช้เนื้อที่เพิ่ม O(n)
• Quick Sort - ใช้เนื้อที่เพิ่ม O(log n) (เฉลี่ย)
  
• Heap Sort - ใช้เนื้อที่เพิ่ม O(1)
• Bucket Sort - ใช้เนื้อที่เพิ่ม O(m)
• Radix Sort - ใช้เนื้อที่เพิ่ม O(1)

ดู ๆ ไปเหมือน Heap Sort น่าจะดีที่สุด แต่จริง ๆ แล้ว มันมีอะไรมากกว่านี้นิดนึง มาลองดูละเอียดดีกว่า ว่าแต่ละวิธี ต้องการสิ่งอะไรที่ต่าง ๆ กัน (แบบคร่าว ๆ)

• Selection Sort - ลูป 2 ชั้น และตัวแปรพักข้อมูลสำหรับการสลับ
  
• Bubble Sort - ลูป 2 ชั้น และตัวแปรพักข้อมูลสำหรับการสลับ
  
• Insertion Sort - ลูป 2 ชั้น และตัวแปรพักข้อมูลสำหรับการแทรก
• Shell Sort (กรณีเวลา O(n log²n)) - ลูป 3 ชั้น ตัวแปรสำหรับสร้างลำดับ 2 ตัว และตัวแปรพักข้อมูลสำหรับการสลับ หรือ แทรก
  
• Merge Sort - Recursive 2 ครั้ง ลูป 1 ชั้นที่มีตัวนับ 2 ตัว กับ array พักข้อมูลความยาว n และลูปคัดลอกค่าจาก array พักข้อมูล
  
• Quick Sort - ลูป 1 ชั้นที่มีตัวนับ 2 ตัว ตัวแปรพักข้อมูลสำหรับการสลับ และ Recursive 2 ครั้ง
  
• Heap Sort - ลูป 2 ชั้น 2 ลูป และตัวแปรพักข้อมูลสำหรับการแทรก
  
• Bucket Sort - ลูปกำหนดค่าเริ่มต้น (ใช้เวลา O(m)) ลูปรับ input และลูปแสดง output (ใช้เวลา O(n))
  
• Radix Sort (ฐาน 2) - ลูป 2 ชั้น ชั้นนอกทำซ้ำ log₂m ครั้ง ชั้นในมีตัวนับ 2 ตัว
  

ถ้าคิดความซับซ้อนของโปรแกรม เป็นเนื้อที่อีกประเภท เราก็พอจะคิดได้ว่า ถ้าใช้เนื้อที่มาก มันก็ทำงานเร็วนะ

Dynamic Programming - Fibonacci Function

อันนี้ คิดว่า หลาย ๆ คนคงคุ้นเคยและรู้อยู่แล้ว หน้าตามันก็ประมาณนี้ (ภาษา C ละกัน)

int fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }

จะเห็นว่า code สั้นมาก ดังนั้น จากหลักของเรา พอจะเดาได้ว่า น่าจะมีวิธีทำให้มันทำงานเร็วกว่านี้ แต่ code ยาวกว่านี้ หรือมีตัวแปรเพิ่ม

ลองดูก่อน ว่า เขียนโปรแกรมแบบนี้ ใช้เวลาทำงานเท่าไหร่ ... คำตอบค่อนข้างง่ายนะ เวลาก็คือ O(fib(n)) น่ะแหละ (ว่าไปก็คือ O(αⁿ) เมื่อ α = golden ratio น่ะแหละ)

มันกินเวลาน่าดูเลยนะเนี่ย ลองพยายามทำให้มันเร็วขึ้นสิ ... วิธีง่าย ๆ ก็คือ กำหนดตัวแปรเพิ่มเป็น array ความยาว n แล้วก็คิดค่าไล่ตั้งแต่ f(0) ถึง f(n) ไง หยั่งงี้ f(...) ตัวที่เคยคิดแล้ว ก็ไม่ต้องคิดซ้ำ

int fib(int n) { return a[n] > 0 ? a[n] : a[n] = fib(n - 1) + fib(n - 2); }

แล้วกำหนดค่าเริ่มต้นให้ a[0] = 1, a[1] = 1 และ a[อื่น ๆ] = -1

จริง ๆ มันประหยัดเนื้อที่ได้อีกนะ แต่คราวนี้โปรแกรมจะซับซ้อนละ ...

 int fib(int n)
 {
  int f, last1, last2;
  if (n <= 1) return 1;
  last1 = 1;
  last2 = 1;
  for (--n; n > 0; --n)
  {
   f = last1 + last2;
   last2 = last1;
   last1 = f;
  }
  return f;
 }

จะเห็นว่า เหลือตัวแปรแค่ 3 ตัว (คือ memory O(1)) แลกกับ code ที่ยาวขึ้นอีกนิดนึง

จริง ๆ ยังทำให้มันเร็วกว่านี้ได้อีกแหละ แต่คราวนี้ code จะยาวขึ้นเยอะเลย แล้วจะเร็วขึ้นเฉพาะเมื่อ n เยอะมาก ๆ ๆ ๆ ๆ เท่านั้น

เอาเป็นว่า หยุดแค่นี้ก่อนดีกว่า