ปวดหัวเล่นๆ กับ Data Structure

เรื่องของเรื่องก็คือ เมื่อวานนี้ผมได้มีโอกาส Discuss (อ่านออกเสียงว่า "เถียง") กับเพือนร่วมงานเรื่องการใช้ฟังก์ชั่น TrimExcess ของ List ครับ เป้าหมายของเราคือการที่จะลดปริมาณการใช้ Memory ให้น้อยที่สุด ซึ่งชื่อของ TrimExcess ก็ดูเข้าท่าดี แต่สิ่งที่มันทำนั่นไม่ค่อยเข้าท่าอย่างชื่อเลย (เดี๋ยวอ่านไปแล้วจะเฉลยว่ามันทำยังไง) ทำให้ผมคิดขึ้นมาได้ว่า เอ้อ เรื่อง Data Structure นี้ก็สำคัญเหมือนกัน โดยเฉพาะอย่างยิ่ง กับการ Develop บน Device ซึ่งมีขนาดแรมที่จำกัด แค่ 64MB (ซึ่งมักจะมีใช้จริงแค่ 20-30MB) หรืออาจจะตกต่ำถึงขั้น 32MB ในบางรุ่น แถมยังมีโปรเซสเซอร์ที่ความเร็วไม่สูงนัก ดังนั้นการมีไอเดียเกี่ยวกับ Data Structure ก็น่าจะเป็นประโยชน์มาก ๆ ในการพัฒนาแอพพลิแคชั่นบน Device ให้มีประสิทธิภาพสูงสุดนะครับ ผมเลยอยากเอาความรู้ Com Sci ที่ติดๆ มาบ้างตอนเรียน มาแบ่งปันครับ

Data Structure นี่มันอะไรนะ?

อ๊ะ ๆ อย่าเพิ่ง Flame ผมนะครับ ผมเชื่อว่ามีหลายคนเหมือนกัน ที่ไม่ได้เรียน Com Sci มาโดยตรง แล้วเข้ามาเขียนโปรแกรม ซึ่งก็ไม่ผิดใช่ไหมล่ะครับ ผมไม่ค่อยแน่ใจเหมือนกันว่า ในสาขาอื่น ๆ ที่มีสอนโปรแกรมมิ่งนี่ เขาพูดถึงเรื่อง Data Structure ไว้บ้างหรือเปล่า ผมเลยอยากจะเกริ่นนำให้ฟังสักนิดนึงก่อนนะครับ จะได้ชัวร์ว่าเรากะลังเข้าใจเรื่องเดียวกันอยู่ ถ้ารู้เรื่องอยู่แล้ว ก้อไม่ต้องอ่านก้อได้นะคับ เดี๋ยวเจอผมเขียนผิด เหอ ๆ

จะว่าไปแล้ว คำว่า Data Structure นี่ผมก็จำ Definition มันไม่ได้หรอกครับ (แหะๆ อ๋า ผมผิดไปแล้ว 'จาน อย่าโบยผม โอ๊ย ๆ) แต่ผมเข้าใจว่า Data Structure เนี่ย ก็คือวิธีการ(อันแสนแปลกประหลาด) ที่เราจะเก็บข้อมูล ในเมมโมรี่ของคอมพิวเตอร์ครับ เน้นว่า แรม นะครับ เพราะถ้าในดิสก์เนี่ย มันยังมีอีกวิชา แยกไปเลย คือวิชา File Structure ซึ่งวิชาโน้นเนี่ย ผมจำ Concept ได้อย่างแม่นยำทีเดียวว่า: "Reduce Efficientcy Increase Seek Time" เอ๊ะ หรือ "Improve Efficiency, Reduce seek Time" เนี่ยแหละ เข้าเรื่องๆ ซึ่งใน Data Structure นี้เราไม่ต้องกังวลเรื่อง Seek Time ครับ เพราะว่าเราทำงานอยู่บนแรม ที่เป็น Direct Access อยู่แล้ว แต่สิ่งที่ Data Structure สนใจ คือ ความเร็วในการเรียกใช้ข้อมูล และความสะดวกในการเปลี่ยนแปลง และจัดเรียงข้อมูลครับ หรือ Efficiency อย่างเดียวเลย

ความเร็วในการเรียกใช้...แล้ววัดได้ด้วยอะไร?

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

ลองสมมุติว่าผมมีโค๊ดเผาซีพียูเล่นๆ แบบนี้ 1 พันล้านครั้งกว่าๆ

ในเครื่องผม ที่ใช้พิมพ์อยู่นี้ ทำได้ในเวลา 3.5 วินาทีครับ ( 3500ms ) ผมก็สรุปเอาว่าโค๊ดเผาซีพียูเล่นของผมนี้ สามารถบวกเลข 1 พันล้านครั้ง ได้ในเวลาเพียง 3.5 วินาที เร็วไหมล่ะ

ปัญหาก็คือ เครื่องที่ผมใช้อยู่นี้ เป็นเครื่อง P4 3.0GHz HT ครับ ทีนี้ ลองทดสอบรันกับเครื่องคุณดูสิครับ ว่าได้เท่าไหร่? แน่นอนว่า ผลลัพท์ ย่อมได้ไม่เท่ากับเครื่องผมอย่างแน่นอน มันก็แน่นอนอยู่แล้วครับ ถ้าคุณใช้ AthlonFX 4000+ เวลาที่ใช้ก็ย่อมน้อยกว่าเครื่องผมชัวร์ๆ และในทางกลับกัน ถ้าคุณเอา Code ชุดนี้ไปรันใน PocketPC พรุ่งนี้ก็ยังไม่น่าจะเสร็จครับ (จริงๆ คงแค่หลายสิบวินาที...)

เรื่องวุ่นวายยังไม่จบแค่นั้นครับ ถ้าเกิดว่าผมเปลี่ยน Code ใหม่ จาก 1024*1024*1024 เป็น 1024 เฉยๆ

ไม่ต้องบอกคุณก็คงทราบใช่ไหมล่ะครับ ว่า Code ชุดนี้ ทำงานไม่ถึง 1ms ก็คงเสร็จแล้ว ไม่ว่าจะอยู่ในเครื่องผม, AthlonFX 4000+ หรือว่า PocketPC ก็ตาม อ้าว ทีเมื่อกี้ ความเร็วยังต่างกันอยู่เลย ทำไมตอนนี้เท่ากันแล้วล่ะ???

คุณคงมองเห็นปัญหาของการวัดด้วยเวลาแล้วใช่ไหมครับ? นั่นก็คือ

• ความเร็ว CPU ไม่เท่ากัน ก็ได้ผลลัพทธ์ ต่างกัน แน่นอนอยู่แล้วว่า เครื่องเร็วกว่า มันก็ย่อมเร็วกว่า
• จำนวนข้อมูลต่างกัน ผลลัทธ์ก็ต่างกันเหมือนกัน ก็แน่นอนเหมือนกันว่า ข้อมูลน้อย มันก็ย่อมเร็วกว่า แม้โค๊ดที่ทำงานจะเหมือน ๆ กัน

โอ๊ย เห็นไหมครับว่า เราใช้เวลามาวัดความเร็วของ Code ไม่ได้เลย แล้ววัดยังไงดีละทีนี้

Big-O Notation

เพื่อแก้ปัญหานี้ เราเลยขอยืมแนวคิดของเลขเขามาใช้ครับ เรียกว่า บิ๊กโอ๊โนเทชั่น (Big-Oh Notation) ถ้าเกิดว่านึกครึ้ม ๆ อยากลองรื้อฟื้นความรู้เก่าขึ้นมา ก็ลองไปอ่านในวิกิพีเดียได้ครับ ผมคนนึงละที่ไม่เอาดีกว่า เอาเป็นว่า ผมขอสรุปง่ายๆ เลยว่า เจ้า Big-O นี่ก็คือ จำนวนสัดส่วนของ Operation ที่จะเกิดขึ้นภายใน Code เมื่อมี Input หรือ "ปัญหา" จำนวน n ตัวครับ โดย Big-O นี่คือ Limit สูงสุด (Upper Bound) ของเจ้าสัดส่วนของ Opeartion นี่แหละครับ (ผิดพลาด ก็ช่วยมาแก้ไขด้วยนะครับ ผมก็อธิบายตามที่เข้าใจ ) ซึ่งหน้าตาของมัน จะมีลักษณะคล้าย ๆ แบนี้ครับ: O(n) หรือ O(n log n) โดยตรงใส้ของ Big-O จะใช้ในการเปรียบเทียบว่าฟังก์ชั่นไหน มีความซับซ้อน (Complexity) มากกว่ากัน ถ้าตัวไหนมีกำลังสูงกว่า ก็คือซับซ้อนกว่าครับ

ตัวอย่างเช่น เมธอดนี้มี Complexity เป็น Constant Time ครับ หรือ O(1) ซึ่งถ้าโค๊ดใครทำได้แบบนี้ (แล้วมีประโยชน์) ถือว่าสุดยอดแล้วครับ

int[] CreateNewArray(int n) { return new int[ n ]; }  

นั่นก็เพราะว่า ไม่ว่า n จะเป็นจำนวนเท่าใดก็ตาม สิ่งที่ Function นี้ทำ ก็คือการสั่งจองแรม ขนาด n แถวครับ ซึ่งก็เหมือนกับการ Call ไปยัง Kernel ครั้งเดียว เพื่อขอจอง Memory จำนวน n x 4 Byte เท่านั้นเอง n จึงไม่มีผลกับเมธอดนี้ครับ

แต่เมธอดนี้ กลับมี Complexity เป็น Linear Time ครับ หรือ O(n)

int[] InitializeNewArray(int n, int initialValue) { int[] toInit = new int[ n ]; for ( int i = 0; i < n; i++ ) { toInit[ i ] = initialValue; } return toInit; }

นั่นก็เพราะว่า ถ้าหากเรายิ่งกำหนดขนาดของ Array มากขึ้น จำนวนลูปก็ยิ่งเพิ่มขึ้นตามไปด้วย เพราะว่า InitializeNewArray จะต้องวนลูปจำนวน n ครั้ง เพื่อไล่ Assign ค่าให้กับ Array จนครบทุกช่อง เลยได้ออกมาเป็น O(n) ครับ

แล้วถ้าเป็นแบบนี้ล่ะครับ?

int[] InitializeNewArray(int n, int initialValue) { int[] toInit = new int[ n ]; for ( int i = 0; i < n; i++ ) { toInit[ i ] = initialValue; } return toInit; } int[][] InitializeSquareArray(int n, int initialValue) { int[][] toInit = new int[ n ][]; for ( int i = 0; i < n; i++ ) { toInit[ i ] = InitializeNewArray(n, initialValue); } return toInit; }

คุณว่า Method InitializeSquareArray นั้น จะมี Big-O เท่าไหร่ O(n) เหมือนกันหรือเปล่า?

ปรากฏเมธอดนี้ยิ่งซับซ้อนหนักหว่า InitializeNewArray เยอะเลยครับ เพราะว่า การทำงาน 1 ครั้ง ใน InitializeSquareArray มีการไปเรียก InitializeNewArray ซึ่งจะทำงานอีก n ครั้ง ก็แสดงว่า Complexity ของ InitializeSquareArray นี่เพิ่มเป็นทวีคูณเลยนะครับ ถ้าเกิดว่า n เป็น 5 เจ้าเมธอด InitializeSquareArray นั้นต้องทำงานถึง 25 ครั้งเลยทีเดียว สรุปได้ว่า InitializeSquareArray มี Complexity เป็น O(N²) ครับ เป็นรูปแบบของสมการ Quadratic นั่นเอง

และนอกจากแบบ Constant, Linear และ Quadratic แล้ว ยังมีอีกหลายรูปแบบนะครับ ตามแต่ละแบบของลักษณะสมการนั่นแหละ อย่างเช่น ลอการิธึมก็มี (O(log n)) เอ็กซ์โปเนนเชียลก็มี (O(cⁿ)) แต่ส่วนใหญ่แล้ว เรามักจะพบแค่ 3 แบบแรก และแบบลอการิธึมครับ อ่านดูผมใช้ศัพท์แล้ว ดูเทพไหมล่ะ จริงๆแล้วผมน่ะ ไม่ค่อยจะได้เกรดหรอก วิชาเลขน่ะ หึ ๆ รู้แต่ขื่อ

แต่แค่ O(xxx) ก้อไม่พอหรอก

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

อ้างอิงจาก บทความนี้ ผมเห็นเขาใช้การเปรียบเทียบตาม Best, Worst และ Average ครับ ถ้ายกตัวอย่างกรณีของการ Add ข้อมูลเข้า List ก็จะได้ว่า:

• Best ตอนที่ List เพิ่งสร้างมาใหม่ ๆ และมีที่ว่างครับ แค่ O(1) เท่านั้น
• Average ปกติแล้ว List คงไม่ค่อยเต็มครับ Add ได้ทันที O(1) เหมือนกัน
• Worst จะเกิดตอน List เต็มครับ เราต้องขยาย List ให้ยาวขึ้น โดยการสร้าง List ใหม่แล้วก็อปปี้ข้อมูลเดิมไปใส่ ซึ่งการก็อปปี้แบบนี้ O(n) ครับ ต้องอ่านที่ละตัว แล้ว Copy ไปใส่

นั่นคือ เราต้องมองให้ครบทุกกรณี ก่อนจะตัดสิน ว่าอัลกอริธึมไหน ดีกว่านั่นเองครับ

ทำไมมีแค่ N? ทำไมไม่มี N + 10, N * 10

จริง ๆ แล้ว ถ้าเราลองนึงถึง Worst Case ของ การ Add ข้อมูลเข้า List จะพบว่า มันไม่ใช่ แค่ O(n) ครับ แต่ว่า น่าจะเป็น O(n + 1) มากกว่า เพราะเกิดจาก...

1. เราต้องขยาย List ให้ยาวขึ้น โดยการสร้าง List ใหม่แล้วก็อปปี้ข้อมูลเดิมไปใส่ คือ O(n)
2. นำข้อมูลที่จะ Add มาใส่ลงใน List ซึ่งก็คือ 1 Operation ก็ O(1)

ก็น่าจะต้อง + 1 เข้าไปด้วยสิ?

แต่ว่าไม่ต้องครับ เพราะว่าบวกเพิ่มเข้าไป 1 นั้น มันไม่ทำให้สัดส่วนของ Operation ต่อจำนวนปัญหานั้นเปลี่ยนไปครับ แค่ขยับไป + 1 ในทางแกน Y เท่านั้นเอง เพราะเราสนใจสัดส่วนครับ เราไม่ได้สนใจเวลาที่ใช้จริงๆ เราจึงมักจะตัดพวกตัวไร้กำลังทิ้งไปครับ ดังนั้น อัลกอริธึมที่ทำได้ N² กับ 10 * N² + N จึงเป็น O(n²) เหมือนกัน เพราะเวลานำมา Plot แล้วลักษณะของกราฟก็เพิ่มขึ้นเหมือนกัน แต่ะจะโดนพวก 10 กับ N มาขยับให้มันสูงขึ้นไป

แต่ยังไงเสีย ถ้าเราจะสนใจว่า ใครเร็วกว่าใครจริงๆ N² ก็ต้องเร็วกว่า 10 * N² + N อยู่แล้วครับ แต่ถ้า N มีจำนวนมาก ๆ แล้ว ก็พวกไร้กำลังนี้ก็อาจทำให้ผลต่างไปไม่มากนัก แน่นอนว่า ผมยังอ้างอิงจาก บทความนี้ นะครับ

ส่งท้าย...แต่ไม่ท่ายสุด

คราวนี้คุณก็เห็นแล้วใช่ไหมครับว่า O(...) พวกนี้ ที่อยู่ตาม Help ของฟังก์ชั่นต่างๆ นี่มันคืออะไร พวกคลาสที่เป็น Data Structure ใน .NET จะมีพวก Big-O นี้เขียนกำกับไว้แทบทุกฟังก์ชั่น ที่เกี่ยวข้องกับการเรียกใช้ หรือว่าเปลี่ยนแปลงตัว Data Structure ครับ ลองดูตัวอย่างจากเมธอด List.TrimExcess ดูได้ครับ จะมีเขียนไว้ว่า

This method is an O(n) operation, where n is Count.

นั่นก็คือ เมธอดนี้ จะต้องทำงาน n ครั้ง สำหรับ List ขนาด n ครับ ลองมาเปรียบเทียบ Array.BinarySearch กับ Array.IndexOf ก็ได้ครับ จะเห็นว่า BinarySearch นั้น ทำงานที่ O( log n ) ในขณะที่ IndexOf นั้น ต้องใช้ถึง O(n) หรือ BinarySearch นั้น เร็วกว่าถึง 10 เท่าทีเดียว (ถ้า Array คุณ Sort อยู่แล้วนะ) ใน Post ถัด ๆ ไป ผมจะทยอยพูดถึง Data Structure แต่ละแบบให้ฟังครับ ตอนนี้ลองไปอ่าน Help ของคลาสที่อยู่ใน System.Collections.Generics เรียกน้ำย่อยดูก่อนได้ครับ จะเจอพวก Big-O เยอะเลย