จากหลักล้านสู่หลักหน่วย ด้วยความรู้ด้าน Data structure (ตอน 1)
ถ้าใครเคยสัมภาษณ์งานตำแหน่ง Software Engineer ในองค์กรเทคระดับโลก (เช่น Google, Amazon, Facebook, Apple, Netflix) จะรู้ว่าทุกบริษัทจะเช็คความรู้ด้าน Data structure หมด
สาเหตุเพราะนี่ความรู้ที่สำคัญมากในการทำงานเสกลใหญ่ๆ ที่มีจำนวนข้อมูล หรือผุ้ใช้หลักล้านขึ้นไป
สำคัญมากนี่คือแค่ไหน?
ในบทความนี้ ผมจะยกตัวอย่างโจทย์ง่ายๆ ที่เกิดขึ้นในเว็บบราวเซอร์ที่เราใช้ทุกวัน และแสดงให้เห็นว่า โปรแกรมสามารถทำงานเร็วต่างกัน ชนิดราวฟ้ากับเหว (จากคำนวนล้านครั้งเหลือแค่ไม่ถึงสิบครั้ง) ถ้าคนเขียนรู้จักใช้ Data structure ที่เหมาะสม
โจทย์
สมมติว่าคุณเป็นนักพัฒนาเว็บบราวเซอร์ และได้รับมอบหมายให้เขียนฟีเจอร์ตรวจเช็คว่า domain ที่ผู้ใช้ใส่เข้ามา อยู่ในรายชื่อของเว็บไซต์ที่อันตรายหรือไม่ (เช่นมี Malware หรือ เป็น Scam)
คุณมีรายชื่อของ domain ที่เป็นอันตรายอยู่แล้ว โดยรายชื่อมีอยู่ 1 ล้านโดเมน
คุณจะเขียนฟีเจอร์นี้ยังไงครับ?
วิธีที่ 1: เก็บล้านค่าแบบโง่ๆ ก็ต้องจ่ายค่าโง่ด้วยการตรวจล้านครั้ง
ถ้าเราไม่คิดมาก เราสามารถเอาเว็บไซต์พวกนี้ใส่เข้าไปใน Array ทุกครั้งที่มีการพิมพ์ URL คุณสามารถหยิบ domain ใน URL มาวน Loop เช็คทุกค่า
แต่ปัญหาคือ รายชื่อเว็บไซต์พวกนี้นั้นมีเยอะมาก มีเป็นล้านเว็บไซต์ การจะวน Loop เทียบ URLเป็นล้านครั้ง ทำให้ทุกครั้งที่กด Enter ใน URL เว็บบราวเซอร์จะกระตุกนิดนึง เพราะต้องรอวนลูบให้เสร็จ โดยเฉพาะในกรณีที่เว็บไซต์นั้นไม่อยู่ในรายชื่อ
วิธีที่ 2:จากหลักล้านสู่หลักสิบ โดยเรียงข้อมูลเป็น Sorted array
ทางเลือกที่ดีกว่าคือใช้ Data structure อันอื่นในการเก็บค่า เช่น Sorted array, Hashtable, Tries ซึ่งพวกนี้จะสามารถทำการค้นหาได้เร็วกว่า Array
ถามว่าเร็วกว่าเท่าไร เปรียบเทียบคร่าวๆว่าจากเดิมจะต้องเทียบล้านครั้ง เราสามารถเทียบแค่ประมาณ 20 ครั้งเท่านั้น!
ทำไมถึงเร็วขึ้นขนาดนั้น?
ผมขอยกตัวอย่างกรณี Sorted Array
ใน Sorted Array, ข้อมูล domain ทั้งหมดมีการเรียงไว้ก่อนแล้วแล้ว เช่น
a.com aa.com abc.com abc.org abcd.com b.com .. ไปเรื่อยจนจบที่ zzzz.com ทั้งหมด 1,000,000 ตัว
สมมติว่าเราต้องการเช็คว่า cat.com อยู่ในรายการนี้หรือไม่
แทนที่จะไล่ตั้งแต่ต้น เราสามารถเริ่มเทียบจากตัวตรงกลาง (ตำแหน่งที่ 500,001) สมมติให้ ค่านี้คือ middle.com
เราจะรู้ได้ทันทีว่าค่า cat.com ต้องมาก่อนต้องอยู่ใน 500,000 ตัวแรกแน่นอน
เพราะ cat.com มาก่อน middle.com
ดังนั้น domain ที่อยู่หลังตัวที่ 500,001 จะต้องไม่มี cat.com แน่นอน
จากค่าที่ต้องค้นตอนแรกทั้งหมด 1,000,000 ตัว ก็จะเหลือแค่ 500,000 ตัว จากการเทียบแค่ครั้งเดียว
หลังจากนั้น เราสามารถเช็ค cat.com เทียบกับค่าตำแหน่งที่ 250,001 และตัดรายการ domain ที่ต้องค้นหาออกทีละครึ่งไปเรื่อยๆ
ถ้าทำต่อไปเรื่อยๆ จำนวนข้อมูลที่ต้องเช็คจะลดลงไปแบบนี้
1,000,000 -> 500,000 -> 250,000 -> 125,000 ->..
ทำซ้ำแบบนี้ไป 20 ครั้ง เราจะเหลือตัวที่ต้องเช็คอยู่แค่เพียง 1 ตัว ทำให้เรารู้ได้ทีว่าเว็บไซต์ cat.com อยู่ในลิสต์ของเว็บไซต์อันตรายรึเปล่า
มหัศจรรย์ไหมครับ? จากล้านเหลือแค่ 20
เทคนิคนี้เรียกว่า Binary search ครับ
Big O Notation
ศัพท์ทาง Computer science เราจะแสดงค่าความเร็วด้วยสิ่งที่เรียกว่า Big O Notation
การเก็บค่าแบบโง่ๆที่ต้องเทียบล้านครั้ง ถูกเรียกว่า O(n) (บิ๊ก-โอ-เอ็น)
ความเร็ว Binary search เมื่อครู่ O(lg(n)) (บิ๊ก-โอ-ล็อค-เอ็น)
ถ้าเรามีค่า 1,000,000 ค่า เราจะต้องเปรียบเทียบ 1,000,000 ครั้งใน O(n)
แต่ถ้าเราใช้วิธีที่มีความเร็วแบบ O(lg(n)) เราจะเปรียบเทียบแค่ ประมาณ 20 ครั้ง (lg(1,000,000) ~= 20)
(lg = Log ฐาน 2)
แต่เดี๋ยวก่อน… มันยังเร็วและเล็กได้กว่านั้น
ถึงจุดนี้ เราคงเห็นแล้วแค่เปลี่ยนวิธีเก็บข้อมูลแค่นิดเดียว จะทำให้โปรแกรมของเราลดการทำงานไปได้มหาศาล
ในตอนหน้า เราจะมาคุยกันเกี่ยวกับเรื่อง Data structure อีกตัวหนึ่ง ซึ่งสามารถแก้ปัญหานี้ได้ด้วยความเร็ว O(1) ด้วย Hash table
O(1) หมายถึงเวลาการทำงานเป็นค่าคงที่ ไม่ว่าจะมีข้อมูลเยอะแค่ไหน ก็ใช้เวลาเท่ากัน (ลองนึกภาพข้อมูลระดับพันล้าน หมื่นล้าน ที่บริษัทใหญ่ๆต้องใช้กัน)
หลังจากนั้นเราจะหาวิธีลดจำนวนการเก็บข้อมูล แทนที่จะต้องเก็บข้อมูลล้านค่า ให้เหลือแค่เพียงไม่กี่ไบต์ ด้วยการเปลี่ยนไปใช้ Data structure ที่เรียกว่า Bloom filter แทน
---
ติดตามบทความสำหรับโปรแกรมเมอร์ทั้งด้านได้ที่ Facebook page Not about code หรือ Twitter @notaboutcode บทความของเพจจะเน้นเนื้อหาที่นำไปใช้ได้กับชีวิตจริง แต่ไม่ยึดติดกับเทคโนโลยีหรือภาษา เช่น System Design, Continuous Delivery, Testing, Career, etc.
สำหรับท่านที่อยากสนับสนุนผู้เขียน รบกวนช่วยแชร์โพสต์ในเฟสบุ้คให้กับเพื่อนๆที่น่าจะสนใจหัวข้อพวกนี้ด้วยครับ