PDA

View Full Version : عملیات بر روی ماتریسهای اسپارس



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

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

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

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

سعید قاسمی
جمعه 04 آذر 1384, 21:15 عصر
سلام عزیزم : اول اینکه فقط به ماتریسی که درایه صفر زیاد داشته باشه اسپارس یا خلوت نمی گن / هر ماتزیس که درایه های مشابه زیاد داشته باشه رو اسپارس می گن ...

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

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

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

gm.sara
یک شنبه 13 آذر 1384, 23:51 عصر
به ماترسی که تعداد عناصر غیر صفر ماتریس کمتر از 3/1 کل عناصر ماتریس باشد .
جمع بر روی ماتریس اسپارس را بلد هستم اگر بازم به دردت می خورد بگو تا برات بنویسم.
و در مورد چند جمله ای ها : هرگاه تعداد ضرایب غیر صفر چند جمله ای کمتر از نصف تعداد کل ضرایب چند جمله ای باشد آن گاه به این چند جمله ای چند جمله ای اسپارس گویند .

تازه_کار
شنبه 01 مهر 1385, 03:00 صبح
با سلام خدمت تمامی عزیزان
متذکر می شوم ماتریس اسپارس ماتریسی نیست که صرفا عناصر صفر آن فراوان باشد بلکه ماتریسی است که یکی از عناصر آن در ماتریس به کرات تکرار شده باشد
یادمون نره تنها صفر بودن اکثر عناصر ملاک نیست شاید ماتریسی باشد که تعداد یکهای آن زیاد باشد و صفرهایش کمتر آیا این ماتریس نمی تواند اسپارس باشد؟
مگر مقدار چه اهمیتی دارد تکرار اهمیت بیشتری دارد
ماتریس اسپارس را ماتریس خلوت هم نامگذاری کرده اند

molla652003
پنج شنبه 10 آبان 1386, 21:44 عصر
[/URL][url]http://itmashhad.com/acm-icpc-2000-vt1467.html#5064 (http://barnamenevis.org/forum/showthread.php?t=83009)

babila
چهارشنبه 05 تیر 1387, 09:22 صبح
ما در ذخیره سازی ماتریس اسپارس یه ماتریس با 3 ستون و Z+1 سطر در نظر میگیریم.در ستون های اول و دوم مختصات درایه غیر صفر (در ستون اول موقعیت x درایه غیر صفر و در ستون دوم موقعیت y) را ذخیری می کنیم و در ستون سوم مقدار اون رو. بنابر این به تعداد درایه های غیر صفر(Z) سطر داریم. در سطر اول هم ابعاد ماتریس و تعداد درایه های غیر صفر رو مشخص می کنیم.


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

rabie_bahar20
یک شنبه 15 آبان 1390, 14:11 عصر
براي كار با ماتريس هاي اسپارس، وقتي ميخوايد داده ي تكراري رو ذخيره كنيد ميتونيد از يه حافظه ي ديگه استفاده كنيد. يه متغير ساده از هر نوعي كه خواستيد ميتونيد براي اين كار تعريف كنيد. توي اكثر كتابها و سايتها، ميشه گفت همشون، داده ي تكراري رو صفر در نظر گرفتن كه خوب كار خودشونو از خيلي جهات راحت كردن و همينطور نيازي به ذخيره ي اون نيست چون همه جا ديگه ميدونيم كه داده ي تكراري صفر بوده. اما اگه بخوايم اصولي تر و كلي تر نگاه كنيم. ماتريس اسپارس براي ذخيره ي بهينه ي ماتريس هايي هست كه (به تناسبي كه دوستان گفتن) داراي تعداد داده هاي تكراري و يا قابل محاسبه هست كه نيازي به ذخيره ي اون داده ي تكراري و يا قابل محاسبه به تعداد زياد نيست و شما ميتونيد فقط داده هاي غير تكراري رو در قالبي كه به اون ماتريس اسپارس ميگن ذخيره كنيد، و داده ي تكراري رو هم در يك خافظه ي جدا ذخيره كنيد و در آخر سر هرجا كه نياز داشتيد از اون استفاده كنيد. :لبخندساده: