Wall of Text #6: When O(1) doesn’t matter

ไม่แน่ใจว่าเปิดประเด็นนี้มาได้ยังไง

ตอนเรียนปีสองจะมีวิชา Data Structure ซึ่งเราจะได้เรียนว่า Data Structure ต่างๆ มี Time complexity เท่าไร ทวนให้อีกครั้งหนึ่งคือ

ArrayList (Vector) คือการสร้าง Array ขึ้นมาเก็บข้อมูล ดังนั้นการเข้าถึงสมาชิกใดๆ ใน Array เป็น O(1) แปลว่าไม่ว่าจะเข้าตัวไหนก็ใช้เวลาเท่ากันหมด

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

LinkedList เป็นการสร้างระเบียนข้อมูล 1 ชุด ในระเบียนจะเก็บข้อมูล, ที่อยู่ (Pointer) ของระเบียนถัดไป และถ้าเป็น Doubly Linked List จะมีที่อยู่ของระเบียนก่อนหน้าด้วย

การเข้าถึงสมาชิกใน LinkedList จึงต้องกระโดดจากระเบียนหนึ่งไปอีกระเบียนหนึ่ง ถ้าหากต้องการเข้าถึงระเบียนสุดท้ายก็ต้องใช้เวลา O(n) คือกระโดดผ่านทุกสมาชิก

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

แต่ถ้าต้องการเพิ่มสมาชิกเข้าไป เราเพียงแค่สร้างช่องใหม่และเพิ่มตัวชี้เข้าไปยังระเบียนสุดท้ายของเดิม เป็นอันเรียบร้อย แบบนี้จะเป็น O(1)

จากข้อสรุปนี้เราก็จะทราบว่า ถ้าข้อมูลที่ต้องการเพิ่มต่อท้ายบ่อยๆ ใช้ LinkedList จะเร็ว นอกเหนือจากนั้นแล้วใช้ ArrayList ดีกว่า


แต่ตอนปีสามผมได้ฟัง Talk ของ James Gosling ผู้สร้างภาษา Java (เสียดายที่หาไม่เจอแล้ว) เค้าบอกว่าคุณไม่ควรใช้ LinkedList เลย ให้ใช้ ArrayList เสมอ

เพราะอะไร? คำตอบสั้นๆ คือ CPU Cache

ตอนนั้นผมได้ยินแล้วรู้สึกตื่นเต้นมาก เพราะมันคือศึกระหว่างวิชา Data Structure กับวิชา Computer Architecture เลยทีเดียว

Benchmark

เว็บไซต์ DZone ได้ทดลองวัดผลดูแล้ว (แนะนำให้ดูกราฟจากต้นทาง) พบว่าการแทรกสมาชิกใหม่ที่เราทราบดีว่า LinkedList เป็น O(1) นั้นกลับช้ากว่า ArrayList!

สิ่งที่เกิดขึ้น เค้าอธิบายว่าเนื่องจากว่า RAM ทำงานได้ช้า CPU จึงจะนำข้อมูลบางส่วนใน RAM เข้ามาพักบน Memory ที่อยู่บน CPU หรือเรียกว่า CPU Cache

แล้วการเลือกข้อมูลที่จะมาพักทำอย่างไร? วิธีที่ CPU ทำคือเมื่อมีการเข้าถึงข้อมูลที่ไม่อยู่บน Cache แล้ว CPU จะดึงข้อมูลนั้นจากใน RAM เข้ามา และข้อมูลที่อยู่โดยรอบด้วย

ดังนั้น Array ซึ่งเก็บข้อมูลเป็นชุดติดกันจึงได้ประโยชน์จากกระบวนการนี้มาก เพราะเมื่อเราเข้าถึงสมาชิกตัวหนึ่งแล้ว CPU จะดึงตัวติดกันมาด้วย ถ้าเราวนไล่สมาชิก Array ก็จะทำงานได้เร็วมาก สมบัตินี้เรียกว่า Locality

ในขณะเดียวกัน ถึงแม้ว่าการหาสมาชิกตัวถัดไปของ LinkedList จะเป็น O(1) เช่นกัน แต่จะใช้เวลานานกว่ามาก เพราะแต่ละระเบียนไม่ได้อยู่ติดกัน CPU จะต้องดึงข้อมูลจาก RAM ใหม่ทุกครั้ง

จากการทดสอบแล้วก็จะพบว่า overhead ตรงนี้ของ LinkedList แค่จะเปิดหาตัวสุดท้ายมาเพิ่มระเบียนใหม่ก็ช้ากว่า Copy Array แล้ว

ทั้งนี้ถ้า Array มีข้อมูลใหญ่มากๆ ก็ยังอาจจะแพ้ LinkedList อยู่ดีเพราะประสิทธิภาพของ LinkedList ไม่ได้ขึ้นอยู่กับขนาดของข้อมูลเลย ขึ้นอยู่กับจำนวนข้อมูลเท่านั้น

Don’t Premature Optimize

คำแนะนำหนึ่งที่ผมชอบคือ “Premature optimization is the root of all evil” อย่ามัวพะวงว่าโปรแกรมเราช้าเพราะเรื่องเล็กๆ แบบนี้ เพราะบางทีเรา optimize ตรงนี้เป็นอย่างดีแล้วอาจจะเร็วขึ้นแค่ 3% ก็ได้แต่เสียเวลาทำไปหลายวัน

ถ้าอยากจะ optimize ควรจะต้องวัดผลจากการใช้งานจริงให้รู้แน่เสียก่อนว่าตรงไหนช้า ถึงจะ optimize ได้ถูกจุด

Wall of Text #1: Dict vs. List

มีน้องสนใจจะย้ายสายมาทำ Computer Science กำลังหัดเขียนโปรแกรม เลยถามอะไรเราเยอะหน่อย

ทีนี้ด้วยความเป็นเพื่อนที่ดีก็เลยจะชอบตอบอะไรยาวๆ เลยจากที่เค้าถามไปเยอะ

ไม่รู้เค้าอ่านรู้เรื่องหรือเปล่านะ

แล้วก็เริ่มนึกออกว่าจริงๆ เอามาเล่าเป็น Blog ก็สนุกดี


คำถามวันนี้ น้องต้องการเก็บข้อมูล แน่นอนว่าวิธีที่ดีที่สุดคือใช้ Database แต่เค้ายังใช้ไม่เป็น เลยจะลองเขียน Datastore ง่ายๆ ขึ้นมา น้องถามว่าถ้าต้องการหาข้อมูลอย่างหนึ่ง การ index ด้วย Dict จะทำให้มันง่ายขึ้นใช่มั้ย?

คำตอบคือ

  • Dictionary Index เป็นกระบวนการ O(1) แปลว่ามันจะเสร็จในทีเดียว
  • Array จะต้องวนหา ดังนั้นคือ O(n) แปลว่ามันอาจจะต้องวนซ้ำไป n ครั้งจึงจะหาค่าที่ต้องการเจอ

Note: ในความเป็นจริง O ของคนละ algorithm เปรียบเทียบกันไม่ได้ต้อง Benchmark เช่น Dictionary เป็น O(1) แต่ถ้าใช้ hash function เป็น argon2 มันอาจจะช้ากว่า runtime ของการวน array ก็ได้ แต่เรื่องนี้ไม่ใช่ประเด็นวันนี้

ถามว่าแล้ว Array ไม่มีข้อดีเลยหรอ?

คำตอบคือ ข้อเสียของ Dict คือมันกิน Memory มาก และ Array index นั้นเร็วกว่า Dict index อีกถ้าเราพยายามทำให้ปัญหา Solve ได้ด้วย Dict index

ปัญหาการใช้ Memory นี้จะเห็นได้ชัดในกรณี Matrix เพราะถ้าเรามี Matrix ทั่วๆ ไป เช่น

1 2 3
4 5 6
7 8 9

Matrix แบบนี้ใช้ 2D Array เก็บดีที่สุด เพราะสามารถ index เอาข้อมูลได้ทันที และใช้ Memory น้อย

แต่ถ้าเรามีเมทริกซ์มากเลขศูนย์ (Sparse Matrix) แบบนี้

0 0 1 0 0
0 2 0 0 1
3 0 0 2 0
0 0 3 0 4
0 4 0 5 0
5 0 6 0 0

แบบนี้เราจะเสียหน่วยความจำในการเก็บเลข 0 เป็นจำนวนมาก ดังนั้นเราอาจจะใช้ Dict เก็บก็จะใช้หน่วยความจำน้อยกว่า (แต่ก็ช้ากว่า) หรือจะเก็บเป็น Array ของ Tuple (col, row, value) ก็ได้

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


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