נושא: חידה - ביעילות של איחסון מטריצות

נשלח בתאריך: 18 January 2005 בשעה 11:48 | IP רשוּם

שלום לכולם

.אני מעוניין לאחסן מטריצות בזיכרון, המטריצות מורכבות מרצפים של אפסים, ומספרים

באיזה מבנה נתונים כדאי לי לאחסן את המטריצות ושמבנה זה יאפשר לי לעשות חיבור וכפל

?בין מטריצות

.כמובן להתחשב בחיסכון בזיכרון ובזמן

נשלח בתאריך: 18 January 2005 בשעה 12:29 | IP רשוּם

רציתי להסביר שוב

המטריצות נראות כך:

0 0 0 0 0 0 0 0 57 0 0 64

0 0 76 0 0 0 7 0 0 0 0 0

0 10 9 9 0 0 0 0 0 0 0 0

......

נשלח בתאריך: 18 January 2005 בשעה 19:37 | IP רשוּם

.תודה רבה על העזרה, ודרך אגב יש לך אחלה אתר

רק לא מוסבר שם איך בדיוק יעבוד כפל עם מטריצות בצורת איחסון זו, יש לי רעיון אבל מעניין

...אותי איך אתה חושב שזה יתבצע

נשלח בתאריך: 18 January 2005 בשעה 19:53 | IP רשוּם

האם מישהו חושב על דרכים נוספות ומבנה נתונים מתאים, לביצוע המשימות??

נשלח בתאריך: 18 January 2005 בשעה 22:03 | IP רשוּם

ברור שאתה רוצה לנצל את העובדה שהמטריצה מלאה אפסים,
רשימה של הקוארדינטות של האיברים השונים מאפס הכי יעילה מבחינת מקום אבל לא נוחה מבחינת חישובים,
עדיף, לפי דעתי, להרחיב טיפה את המבנה לרשימה של שורות, שכל אלמנט הוא רשימה של ערכים באותה שורה. כאשר שתי הרשימות נשמרות ממויינות.

היתרון במבנה כזה לעומת המבנה הקודם הוא בכפל מטריצות, בעיקר במטריצה דלילה שבה יש שורות של אפסים, יתקבלו מספר רב של איברים שאין צורך לחשב אותם.
אם גם גודל המטריצה ידוע מראש, תוכל להשתמש במערך שכל איבר בו הוא רשימה של עמודות, ואז הגישה לכל איבר תשתפר מ (O(N*M  ל (O(1*M.