عملیات بر روی ماتریسهای اسپارس

[google]

میدونیم ماتریسهای اسپارس ماتریسهایی هستند که بیشتر درایه های آن صفر است
دو تا سوال دارم:
1-یعنی چه نسبتی از درایه های ماتریس صفر باشد؟آیا درصد خاصی وجود داره؟
2-بهترین الگوریتم برای ضرب و جمع ماتریسهای کدومه؟هر کی بلده لطفا آدرسی یا کدی به من بده.
با تشکر.((google))
****************************************
هیچ چیز شیرین تر از حقیقت نیست اگر چه همه می گویند حقیقت تلخ است.
((ناشناس))

[رضا جاسبی]

تا جایی که می دونم درصد صفر ها زیاده ! یعنی فکر کنم حداکثر 3/1 یا 4/1 و شاید کمتر عناصر می توانند مقدار داشته باشند تا این روش مقرون به صرفه باشد. درصد مشخصی رو جایی ندیدم.
در مورد پیاده سازی آن هم باید یک Structure داشت که حاوی یک عنصر برای مقدار این درایه و دو اشاره گر سطری و ستونی برای عناصر بعدی باشد.
برای جمع و تفریق باید هر عضوی که هر یک از دو آرایه دارند در آرایه جواب کپی شود و عناصری را که هر دو دارند با هم جمع شوند. برای ضرب الگوریتم کمی پیچیده تر است و باید سطر اولی با ستون دومی برابر باشد.
متاسفانه من وقت کافی ندارم وگرنه کد این الگوریتم رو می نوشتم. :sorry:

[pcseven]

ماتریس اسپارس ماتریسی هست که تعداد درایه های صفر اون خیلی زیاد باشه. حالا چقدر ؟ توضیح می دم :
ببینید. ما در ذخیره سازی ماتریس اسپارس یه ماتریس با 3 ستون و Z+1 سطر در نظر میگیریم.در ستون های اول و دوم مختصات درایه غیر صفر (در ستون اول موقعیت x درایه غیر صفر و در ستون دوم موقعیت y) را ذخیری می کنیم و در ستون سوم مقدار اون رو. بنابر این به تعداد درایه های غیر صفر(Z) سطر داریم. در سطر اول هم ابعاد ماتریس و تعداد درایه های غیر صفر رو مشخص می کنیم.
با این تعریف از روش کلی ذخیره سازی ماتریس اسپارس، ماتریسی رو اسپارس میگیم که اگه به روش دوم ذخیره بشه فضای کمتری رو اشغال می کنه.
فضای مورد نیاز برای ذخیره سازی یک ماتریس m*n برابر m*n بایت(یا اندازه نوع ماتریس)
فضای مورد نیاز برای ذهیره سازی ماتریس اسپارس : 3*(Z+1) بایت(یا اندازه نوع ماتریس)

[h_shirazee]

البته ... ماتریس های اسپارسی که حالت های خاصی دارند مثلا بالا قطری یا ایین قطری و یا شکل های خاصی دارند رو می تونید توی یک آرایه یک بعدی ذخیره کنید بعد با استفاده از به فرمول که از روی شکل ماتریس تون بدست میارین و یه تابع که سطر و ستون های ماتریس رو می گیره ، جای اون رو توی خونه ماتریس یه بعدی پیدا کنین ولی راه حل کلی همین شکلی هست که دوستانمون هم بهش اشاره کردند !

[سعید قاسمی]

سلام عزیزم : اول اینکه فقط به ماتریسی که درایه صفر زیاد داشته باشه اسپارس یا خلوت نمی گن / هر ماتزیس که درایه های مشابه زیاد داشته باشه رو اسپارس می گن ...

جواب سوال اول : یک روش برای ذخیره کردن این ماتریس ها هست / در این روش ما تنها مکان و مقدار عناصر غیر متشابه رو ذخیره می کنیم / که با یک محاسبه ساذه می توان گفت که این روش برای این ماتریس مناسب است یا نه

جواب سوال دوم : همون طور که یگانه گفت میشه با لیست پیوندی یا آرایه پیاذه سازی بشه

* توضیح بیشتر : کتاب ساختمان داده ها در ++C / مهندس جعفرنژاد فمی

[gm.sara]

به ماترسی که تعداد عناصر غیر صفر ماتریس کمتر از 3/1 کل عناصر ماتریس باشد .
جمع بر روی ماتریس اسپارس را بلد هستم اگر بازم به دردت می خورد بگو تا برات بنویسم.
و در مورد چند جمله ای ها : هرگاه تعداد ضرایب غیر صفر چند جمله ای کمتر از نصف تعداد کل ضرایب چند جمله ای باشد آن گاه به این چند جمله ای چند جمله ای اسپارس گویند .

[تازه_کار]

با سلام خدمت تمامی عزیزان
متذکر می شوم ماتریس اسپارس ماتریسی نیست که صرفا عناصر صفر آن فراوان باشد بلکه ماتریسی است که یکی از عناصر آن در ماتریس به کرات تکرار شده باشد
یادمون نره تنها صفر بودن اکثر عناصر ملاک نیست شاید ماتریسی باشد که تعداد یکهای آن زیاد باشد و صفرهایش کمتر آیا این ماتریس نمی تواند اسپارس باشد؟
مگر مقدار چه اهمیتی دارد تکرار اهمیت بیشتری دارد
ماتریس اسپارس را ماتریس خلوت هم نامگذاری کرده اند

[molla652003]

http://itmashhad.com/acm-icpc-2000-vt1467.html#5064

[babila]

ما در ذخیره سازی ماتریس اسپارس یه ماتریس با 3 ستون و Z+1 سطر در نظر میگیریم.در ستون های اول و دوم مختصات درایه غیر صفر (در ستون اول موقعیت x درایه غیر صفر و در ستون دوم موقعیت y) را ذخیری می کنیم و در ستون سوم مقدار اون رو. بنابر این به تعداد درایه های غیر صفر(Z) سطر داریم. در سطر اول هم ابعاد ماتریس و تعداد درایه های غیر صفر رو مشخص می کنیم.

در این حالت عنصر تکراری رو کجا ذخیره می کنیم؟

[rabie_bahar20]

براي كار با ماتريس هاي اسپارس، وقتي ميخوايد داده ي تكراري رو ذخيره كنيد ميتونيد از يه حافظه ي ديگه استفاده كنيد. يه متغير ساده از هر نوعي كه خواستيد ميتونيد براي اين كار تعريف كنيد. توي اكثر كتابها و سايتها، ميشه گفت همشون، داده ي تكراري رو صفر در نظر گرفتن كه خوب كار خودشونو از خيلي جهات راحت كردن و همينطور نيازي به ذخيره ي اون نيست چون همه جا ديگه ميدونيم كه داده ي تكراري صفر بوده. اما اگه بخوايم اصولي تر و كلي تر نگاه كنيم. ماتريس اسپارس براي ذخيره ي بهينه ي ماتريس هايي هست كه (به تناسبي كه دوستان گفتن) داراي تعداد داده هاي تكراري و يا قابل محاسبه هست كه نيازي به ذخيره ي اون داده ي تكراري و يا قابل محاسبه به تعداد زياد نيست و شما ميتونيد فقط داده هاي غير تكراري رو در قالبي كه به اون ماتريس اسپارس ميگن ذخيره كنيد، و داده ي تكراري رو هم در يك خافظه ي جدا ذخيره كنيد و در آخر سر هرجا كه نياز داشتيد از اون استفاده كنيد.