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 ได้ และแน่นอนการจะเก็บข้อมูลนี้ไว้ในหน่วยความจำไม่ใช่เรื่องง่ายๆ


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