เมทริกซ์กระจัดกระจายในโครงสร้างข้อมูล

ในส่วนนี้เราจะมาดูกันว่าเมทริกซ์กระจัดกระจายคืออะไรและเราจะแสดงเมทริกซ์เหล่านี้ในหน่วยความจำได้อย่างไร ดังนั้นเมทริกซ์จะเป็นเมทริกซ์เบาบางถ้าองค์ประกอบส่วนใหญ่เป็น 0 อีกคำจำกัดความหนึ่งคือเมทริกซ์ที่มีองค์ประกอบที่ไม่ใช่ศูนย์สูงสุด 1/3 (ประมาณ 30% ของ m x n) เรียกว่าเมทริกซ์เบาบาง

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

สมมติว่าเรามีเมทริกซ์กระจัดกระจายดังนี้ -

ดังที่เราเห็นได้ว่ามีองค์ประกอบที่ไม่เป็นศูนย์ 8 องค์ประกอบและมีค่าเป็นศูนย์ 28 รายการ เมทริกซ์นี้ใช้พื้นที่หน่วยความจำ 6*6 =36 ช่อง หากขนาดของเมทริกซ์ใหญ่ขึ้น การสูญเสียพื้นที่จะเพิ่มขึ้น

เราสามารถเก็บข้อมูลเกี่ยวกับเมทริกซ์กระจัดกระจายโดยใช้โครงสร้างตาราง สมมติว่าเราจะสร้างตารางชื่อ X ดังด้านล่าง -

ที่นี่คอลัมน์แรกถือหมายเลขแถว และคอลัมน์ที่สองถือหมายเลขคอลัมน์ อันที่สามกำลังเก็บข้อมูลอยู่ที่ M[row, col] แต่ละแถวของตารางนี้เรียกว่า triplets เนื่องจากมีสามพารามิเตอร์ แฝดสามตัวแรกกำลังเก็บข้อมูลขนาดของเมทริกซ์ Row =6 และ Column =6 แสดงว่าเมทริกซ์ M คือเมทริกซ์ขนาด 6 x 6 ฟิลด์ค่าแสดงถึงจำนวนขององค์ประกอบที่ไม่ใช่ศูนย์ที่มีอยู่ในอาร์เรย์

ตารางนี้ใช้พื้นที่ 9 * 3 =36 ด้วยดังนั้นกำไรอยู่ที่ไหน? ถ้าขนาดเมทริกซ์คือ 8*8 =64 แต่มีเพียง 8 องค์ประกอบเท่านั้น ตาราง X จะใช้พื้นที่ 36 หน่วยด้วย เราจะเห็นว่ามี 3 คอลัมน์คงที่ จำนวนแถวแตกต่างกันไปตามจำนวนองค์ประกอบที่ไม่ใช่ศูนย์ ดังนั้นหากมีองค์ประกอบที่ไม่เป็นศูนย์จำนวน T ความซับซ้อนของช่องว่างจะเป็น O(3*T) =O(T) สำหรับเมทริกซ์จะเป็น O(m x n)