"ความตั้งใจสร้างได้ทุกอย่าง ความไม่ตั้งใจทำลายได้ทุกสิ่ง"
Big-O Notation กับต้นทุนที่ต่างกัน
14 Oct 2013 03:52   [37796 views]

สมัยยังเยาว์ ตอนที่เริ่มศึกษาการเขียนโปรแกรมด้วยตัวเอง มีคำอยู่คำนึงที่ได้ยินมาโดยตลอด เห็นเค้าว่าสำคัญกัน แต่ก็ไม่ค่อยจะเข้าใจนัก มันคือคำว่า Big-O ... ใช่ครับ มันอยู่ห่างจาก Big C นิดหน่อย ...​ บ้า !

ซึ่งตอนมัธยมได้ยินคำนี้จากเพื่อนคอมพ์โอฯ (เราไม่ได้ไปสอบด้วย เลยทำได้แค่ได้ยิน) ได้ยินแบบว่า บ่อยมากอ่ะ จะพูดอะไรกันเยอะแยะ ! แต่ก็ยังคงไม่เข้าใจอยู่ดี


จนเริ่มมาเข้าใจความหมายทางทฤษฎีของมันก็ตอนเรียนวิชา Algorithm ตอนอยู่วิศวฯคอมพ์จุฬาฯ อ้อ นะ มันมี O(1) นะ มี O(n) นะ มี O(log n) นะ มีโน่นมีนี่นะ มีเพียบเลยนะ ทำไมมีเยอะจังนะ T_T


แต่ก็ยอมรับด้วยสำเนียงแหะๆว่า ตอนนั้นรู้ก็เพื่อไปสอบเท่านั้น เขียนโปรแกรมจริงก็ไม่ได้แคร์อะไรกับ Big-O นักหรอกช่วงนั้น เพราะงานส่วนใหญ่ที่ทำ ไม่ใช่งานสเกลใหญ่โตอะไร เขียนกากๆให้ใช้งานได้ก็จบละ เอาจริงๆคือ Anti เลยหละช่วงแรกๆ ประมาณว่าเขียนโปรแกรมแล้วจะต้องมาแคร์ Big-O ทำไม ไร้สาระชะมัด !


นี่ไม่อยากจะคุย สอบมิดเทอมได้อันดับสอง ...​ จากท้ายอ่ะ อาจารย์แนะนำว่าให้ถอน แต่ด้วยความไม่อยากถอน ก็เลยไม่ถอนและดิ้นรนต่อไป (เหตุผลใช้ได้มั้ย) สุดท้ายสอบไฟนอลเสร็จ ตัดเกรด ได้ B+ นะเฟร้ยยยย


... นี่แหละนะ ไม่อยากจะคุย แต่ก็คุยไปแล้ว ...


นั่นแหละ ที่คุยก็เพราะจะบอกว่าประสบการณ์มิดเทอมรั้งท้ายครั้งนั้น มันทำให้เราใส่ใจกับงาน Algorithm ขึ้นมากอย่างมีนัยสำคัญ รักมันขึ้น 8 ขีด และเริ่มลากเราเข้าสู่งานที่เราถนัดที่สุด(จนถึงตอนนี้)อย่างงาน Optimization


และหลังจากเรียนจบมา มีงานเขียนโปรแกรมผ่านมือมาเยอะจนจำไม่ได้ และจากประสบการณ์การทำงานเหล่านั้นเอง จึงได้สัมผัสกับโลกของ Big-O มากขึ้นเรื่อยๆ และตระหนักได้ในที่สุดว่า


Big-O มันโคดดดดดดดดสำคัญเลย


(Big พอมะ)


สำคัญระดับว่า ถ้าโปรแกรมเมอร์คนใดไม่รู้เรื่อง Big-O ก็ไม่อาจเรียกว่าเป็นโปรแกรมเมอร์ได้เต็มปากเลยทีเดียว เรียกว่าแค่ว่าคนเขียนโปรแกรมพอเป็น เป็นหนึ่งในกำแพงที่ขีดคั่นระหว่างโปรแกรมเมอร์ที่ "เขียนโปรแกรมได้" กับ "เขียนโปรแกรมเป็น" ออกจากกัน


และจากประสบการณ์การทำงานที่สเกลใหญ่ขึ้นเรื่อยๆ (โดยเฉพาะไอ่นกฮูกสีส้มตัวดี) ยิ่งงานบิ๊ก รับ Concurrent User เยอะ ก็ยิ่งเห็นว่า Big-O มันสำคัญเพียงใด และกระทบต่อค่าใช้จ่ายได้รุนแรงขนาดไหน วันนี้เลยขอมาเขียนเรื่อง Big-O Notation กับต้นทุนที่ต่างกัน (ที่เขียนไปข้างบนเป็นแค่การเกริ่น ...​ ยาวมั้ยหละ)


สำหรับคนที่ยังไม่เข้าใจว่า Big-O คืออะไร สั้นๆก็คือ เป็นคำศัพท์ที่ใช้ในการวัดประสิทธิภาพ Algorithm ตัวอย่างเบสิคสุดเลยคือการ "ค้นหาข้อมูล" มีหนังสือการ์ตูนวางอยู่ 100 เล่ม จะหาเล่มที่ต้องการได้ยังไง?


นายเอบอกว่า เดี๋ยวหาทีละเล่ม เดี๋ยวก็เจอ อ่า อันนี้ O(n)


นายบีบอกว่า มันเป็นวิธีที่โง่เอามากๆเลยนะนายเอ เวลาเก็บการ์ตูนก็รู้จักเรียงหน่อยเซ่ แล้วก็จิ้มไล่หาแบบ Binary Search ไป โอเค้ อันนี้ O(log n)


นายซีบอกว่า เรามีพลังจิต เราฝึกฝนตัวเองมายี่สิบปี เราเป็นผู้รอบรู้ ไม่ต้องหาให้เสียเวลา เล่มนั้นไง ...​ อันนี้ O(1)


(หลังจากจบเหตุการณ์ นายซีก็โดนนายเอและนายบีกระทืบตายด้วยความหมั่นไส้)


สังเกตดูว่าสามคนนี้มีวิธีหาที่ต่างกัน ทำให้เวลาที่ใช้ในการหาการ์ตูนเล่มนั้นก็ต่างกันไป ถามว่าใครใช้เวลาน้อยสุด? ก็นายซีไง เจือกมีพลังจิต และใครใช้เวลามากสุด ...​ โดยเฉลี่ยแล้วก็นายเอที่นั่งหาทีละเล่มนั่นเอง ส่วนนายบีถ้าโชคดีก็ใช้เวลาเท่ากับนายซี จิ้มเล่มแรกเจอเลย ถ้าโชคร้ายก็เล่มที่ log n


ก็จะเห็นแล้วว่าผลลัพธ์ที่ได้มันก็เหมือนกัน สุดท้ายก็หาการ์ตูนเจอเหมือนกันหนิ แต่วิธีการมันต่างกัน นั่นหมายถึง "ต้นทุนที่ต่างกัน" ด้วย


แต่เผอิญหนังสือการ์ตูนมันมีแค่ 100 เล่มไง นายเอกับนายซีเลยอาจจะใช้เวลาต่างกันไม่มาก อาจจะแค่ 1 นาที


เอาใหม่ ถ้าโจทย์คือมีหนังสือกองรวมกันอยู่ 100,000,000 เล่ม ช่วยหาหนังสือเรื่องเจาะเวลาหาหลินปิงให้ที คราวนี้นายเออาจจะต้องใช้เวลาสิบปีในการหา ในขณะที่นายซีใช้ 1 วินาทีก็ตามหาหลินปิงเจอแล้ว


จบหลักสูตร Intensive ว่าด้วยเรื่องความหมายของ Big-O ...


จะเห็นว่าการจะได้มาซึ่งผลลัพธ์ของโจทย์ที่ตั้งไว้ ต้นทุนจะมีอยู่สองส่วนด้วยกัน


ต้นทุนการพัฒนา - แน่นอนว่ายิ่ง Algorithm ดีกว่าที่มนุษย์ทั่วไปทำได้เท่าไหร่ เวลาที่ใช้ในการพัฒนาก็จะยิ่งนานกว่า และยิ่ง Algo ซับซ้อนมากขึ้นเท่าใด จำนวนคนที่สามารถทำตรงนี้ได้ก็จะยิ่งน้อยลงเป็น Exponential

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

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


ต้นทุนการ Operate - อย่าคิดว่าจ่ายค่าพัฒนาแล้วจบ หลังจากพัฒนาระบบเสร็จแล้ว ระหว่างการใช้งานก็จะมีต้นทุนการรันระบบอยู่เช่นเดียวกัน และโดยปกติ ยิ่ง Algorithm ทำออกมาห่วย ก็จะทำให้การใช้งานยาก ต้นทุนการ Operate ก็จะสูงกว่า ในขณะที่ถ้าทำ Algorithm ออกมาดี ใช้งานง่าย ใช้เวลาน้อย ต้นทุนการ Operate ก็จะต่ำกว่า

อย่างตัวอย่างด้านบน นายเอใช้เวลาสิบปีในการหาหนังสือเล่มเดียว ต้องมีค่าไฟ ค่าน้ำ ค่าสถานที่ ค่าเหนื่อยอันยืดเยื้อของนายเอ รวมถึงค่าเสียเวลารอของผู้ต้องการหาหนังสือ เป็นต้นทุนการ Operate

ในขณะที่นายซี วิเดียวจบ ไม่มีค่าไฟ ค่าน้ำ ค่าสถานที่ รวมถึงไม่ต้องรออีกด้วย


ไม่เอาละ เบื่อเรื่องหาหนังสือละ ยกตัวอย่างจริงให้ดูตัวอย่างนึงเลยละกัน


นกฮูกสีส้ม MOLOME ในส่วนของ Server ช่วงนึง มีการเขียนโค้ดแบบไม่ได้คำนึงเรื่อง Big-O เท่าไหร่นัก ปรากฎว่าประสิทธิภาพต่ำมาก รับโหลดได้แค่หลักร้อยต่อ Server เครื่องนึง บางส่วนดึงโหลด Server ไปจนหมด คนเรียกได้แค่ 10 Concurrents ก็ล่มแล้ว จนสุดท้ายต้องไปไล่ดูว่าส่วนไหนประสิทธิภาพต่ำ ก็ไล่แก้ให้หมด ปรับ O(n) ให้กลายเป็น O(1) จนหมด


ทั้งนี้ Big-O ไม่ได้จำกัดแค่โค้ดของเราเท่านั้น การ Index ในตาราง DBMS ก็ช่วยให้ DBMS ลด Big-O ลงได้อีกด้วย จาก O(n), O(n log n) หรือ Big-O สูงๆ ให้เหลือเพียง O(1) ไม่ก็ O(log n) ได้เลยในพริบตา และความจริงเป็นส่วนที่สำคัญมากๆๆๆๆเลยก็ว่าได้สำหรับงานด้าน Server Side Development


ผลสรุปสุดท้าย รับโหลดเพิ่มขึ้นเป็นหลักพัน คำนวณแล้วก็ราวๆ 8-10 เท่า ไม่มีส่วนไหนที่เป็นตัวถ่วงความเจริญของ Server อีกต่อไป


มันแปลว่าอะไรครับ?


ครับ แปลว่าผมเขียนโค้ดกาก ผมขอโทษคับ T_T


ไม่ใช่เรื่องนั้น ! ที่หมายถึงคือ Server ที่สเปคเท่าเดิม สามารถรับการใช้งานได้มากขึ้นถึง 8-10 เท่า ถ้ามีคนใช้งานเพิ่มขึ้นอีก 5 เท่าเราก็ไม่หวั่น ปล่อยมันทำงานของมันไป แต่ถ้าไม่ได้ Optimize ในครั้งนั้น เราจะต้องเปิด Server เพิ่มขึ้นอีก 4 เครื่อง จ่ายเงินเพิ่มขึ้นเป็น 5 เท่าเลยทีเดียว (จาก 100 บาทเป็น 500 บาท) หรือถ้ามองอีกมุมนึง เราลด Spec เครื่องลง 5 เท่าได้ทันที เพื่อรับโหลดเท่าเดิม จ่ายเงินน้อยลงจาก 100 บาทเหลือ 20 บาททันที เย้ ! (เยอะนะ)


เป็นการลดต้นทุนการ Operate ที่ดีมาก แต่ต้องยอมรับว่ากว่าจะแก้ Server เสร็จก็แทบรากเลือดหละครับ ต้นทุนการพัฒนาสูงลิบ แต่ระยะยาวแล้วคุ้มกว่ามากๆๆๆๆๆๆๆ (ยาวแบบไม่ต้องยาวมาก แค่สามเดือนก็คุ้มละ)


อย่างไรก็ตาม หากย้อนกลับไปที่ตัวอย่างการหาหนังสือ หากมีหนังสือแค่ 100 เล่ม ถามว่าคุ้มมั้ยที่จะไปควานหาตัวนายซี แล้วจ้างด้วยค่าจ้างแพงๆ ทั้งๆที่สามารถใช้ใครก็ได้ช่วยหา แป๊บเดียวก็หาเจอแล้ว


ตอบให้ก็ได้ครับว่า "ไม่คุ้มเลย" ใช้นายเอไปสิ !


บทสรุปของเรื่องนี้คือ เราจำเป็นต้อง Balance ให้ดีระหว่างต้นทุนการพัฒนาและต้นทุนการ Operate ต้อง Balance ให้ดีระหว่างประสิทธิภาพและความจำเป็นที่ต้องทำถึงขนาดนั้น ถ้าไม่จำเป็นและสุดท้ายผลที่ออกมาก็ไม่ได้ต่างกันมาก แต่ต้นทุนต่างกันลิบ ก็จงเขียนกากๆแล้วเอาเงิน/เวลาไปทำอย่างอื่นซะเถอะ


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


บางทีโจทย์อาจจะแค่ว่า "มีข้อมูลอยู่ล้านชุดในไฟล์ เอาไปทำโน่นทำนี่ทำนั่นให้หน่อย ใช้งานครั้งเดียว แล้วก็ทิ้งเลย" หากประเมินว่าใช้เวลาพัฒนา 5 นาทีด้วย Algorithm กากๆ และปล่อยให้มันรันอีก 6 ชั่วโมง ก็จะได้ผลลัพธ์ออกมา มันก็ยังเป็นทางเลือกที่ดีกว่า พัฒนา Algorithm สุดล้ำ ใช้เวลารันเพียง 5 วินาที แต่ใช้เวลาพัฒนา 7 วัน แต่ใช้ครั้งเดียวทิ้ง เป็นต้น ...


โปรแกรมเมอร์ที่ดีเยี่ยมต้องสามารถประเมินตรงนี้ได้ด้วย จงจำไว้ว่าโปรแกรมเมอร์คือ "นักแก้ปัญหาที่แก้โจทย์ด้วยวิธีที่เหมาะสม"


คนที่จะจ้างโปรแกรมเมอร์ก็จำเป็นต้องรู้เรื่องนี้ อาจจะไม่ต้องลงลึกถึง Big-O แต่ก็ต้องเข้าใจว่าการจะได้มาซึ่งผลลัพธ์นั้น มีต้นทุนแฝงอยู่มาก หากคุณอยู่ดีๆอยากลอก Twitter ขึ้นมา อาจจะมีนักพัฒนาทำให้คุณได้ในราคาสัก 100,000 บาท แต่ผลคือใช้งานได้ก็จริง แต่ Server รับโหลดได้แค่เครื่องละ 300 คน อยากมีผู้ใช้สักล้านคน ก็ตั้ง Server สัก 3,333 เครื่องก็พอ


ในขณะที่ถ้าลงทุนมากกว่านั้น อาจจะสัก 1,000,000 บาท อาจจะได้โปรแกรมเมอร์ที่เก่งขึ้น หรือโปรแกรมเมอร์อาจจะคนเดิมแหละ แต่มีเงินที่จะทำให้ Algorithm ดีขึ้น Optimize ได้มากขึ้น Server อาจจะรับโหลดได้เพิ่มเป็น 10,000 ก็ได้ ผู้ใช้ล้านคน ก็ตั้งแค่ 100 เครื่องเป็นอันจบ


จะจ้างใครคิดไว้ด้วยว่ามันมีหลายวิธีที่ได้ซึ่งผลลัพธ์ที่คุณต้องการ แต่ไม่ใช่ทุกวิธีที่เหมาะสม บางวิธีก็แค่ทำได้ พอตบตาคุณได้ แต่พอใช้งานจริง ...​ เจ๊ง และโทษใครไม่ได้ด้วย เพราะคุณภาพก็ตามงบประมาณหละ (แต่ถ้าให้เงินเยอะแล้วห่วยอีก ตบ!)


Keep in mind ไว้เสมอว่า

จะ O(1), O(n), O(log n), O(n2) หรือ O อะไรก็ตาม

ถึงผลลัพธ์จะออกมาเหมือนกัน

แต่ต้นทุนไม่เท่ากันนะจ๊ะ


ตอนแรกว่าจะเขียนสั้นๆ แต่ ...


เอาน่า พิมพ์เพลินไปนิด T_T


จบจ้า

บทความที่เกี่ยวข้อง

Sep 1, 2013, 21:44
22317 views
ทำไม Facebook Login ถึงจำเป็นบนระบบ Login ของแอพฯ
Mar 21, 2014, 12:08
6146 views
ทำความรู้จัก Android Wear หน้าต่างที่ไร้หัวใจ ...
0 Comment(s)
Loading