เมทริกซ์กระจัดกระจายคืออะไร
เมทริกซ์จะถูกเรียกว่า "เมทริกซ์กระจัดกระจาย" (Sparse Matrix) เมื่อส่วนใหญ่ขององค์ประกอบเป็นศูนย์ (0) นิยามอีกประการหนึ่งคือ เมทริกซ์ที่มีองค์ประกอบที่ไม่ใช่ศูนย์สูงสุด 1/3 (ประมาณ 30% ของ m × n) จะถูกจัดว่าเป็นเมทริกซ์กระจัดกระจาย
ปัญหาการจัดเก็บแบบปกติ
การใช้เมทริกซ์ในหน่วยความจำคอมพิวเตอร์ช่วยให้ดำเนินการได้อย่างมีประสิทธิภาพ แต่ถ้าเมทริกซ์เป็นแบบกระจัดกระจาย จะทำให้พื้นที่หน่วยความจำถูกใช้ไปมากโดยไม่จำเป็น เนื่องจากต้องจัดเก็บค่าศูนย์จำนวนมาก
ตัวอย่างเมทริกซ์ 6×6
เมทริกซ์นี้มีองค์ประกอบที่ไม่ใช่ศูนย์ 8 ค่า และค่าศูนย์ 28 ค่า ใช้พื้นที่ 36 ช่อง หากขนาดเมทริกซ์ใหญ่ขึ้น การสูญเสียพื้นที่จะเพิ่มขึ้นตามสัดส่วน
การจัดเก็บด้วยโครงสร้างตาราง (Triplet Representation)
เราสามารถจัดเก็บข้อมูลเมทริกซ์กระจัดกระจายโดยใช้ตารางที่มี 3 คอลัมน์:
- คอลัมน์ที่ 1: หมายเลขแถว (Row)
- คอลัมน์ที่ 2: หมายเลขคอลัมน์ (Column)
- คอลัมน์ที่ 3: ค่าข้อมูลที่ M[row, col]
แต่ละแถวของตารางนี้เรียกว่า "ทริปเล็ต" (Triplet) เพราะมี 3 พารามิเตอร์
การวิเคราะห์พื้นที่จัดเก็บ
ทริปเล็ตแรกเก็บข้อมูลขนาดเมทริกซ์: Row = 6, Column = 6 แสดงว่าเป็นเมทริกซ์ 6×6 ค่า Value field บอกจำนวนองค์ประกอบที่ไม่ใช่ศูนย์
ตารางนี้ใช้พื้นที่ 9 × 3 = 36 หน่วย เท่ากับเมทริกซ์เดิม แต่ประโยชน์จะชัดเจนเมื่อเมทริกซ์มีขนาดใหญ่ เช่น 8×8 = 64 ช่อง แต่มีองค์ประกอบไม่ใช่ศูนย์เพียง 8 ค่า ตารางทริปเล็ตยังใช้พื้นที่ 36 หน่วยเท่าเดิม
ซับซ้อนיותพื้นที่ (Space Complexity): O(3×T) = O(T) โดย T = จำนวนองค์ประกอบที่ไม่ใช่ศูนย์ ในขณะที่เมทริกซ์ทั่วไปเป็น O(m×n)
