زمان جاری: 07-31-2014, 07:55 PM
خوش آمدید مهمان گرامی! (ورودعضویت)

ارسال پاسخ 
 
رتبه موضوع:
  • 0 رای - 0 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5
ماتريس اسپارس
01-11-2011, 11:40 AM
ارسال: #1
ماتريس اسپارس
ماتريس اسپارس ماتريسيه كه داده هاي معتبر (داده معتبر همون 1 است) در اون قرار ميگيرن

اما سئوال:

اساسا اين ماتريس بدرد چي ميخوره ؟
براي پاسخ به اين سئوال اول اين سئوال رو بايد جواب دادكه:
مگه كلا از يه ماتريس براي چه كارهايي استفاده ميكردن؟خوب معلومه براي ذخيره موقتي يه سري داده ها


داده هايي كه ازش صحبت ميكنيد چه داده هايي هستن؟
هر مجموعه داده كه قراره مورد پردازش قرار بگيرن ميتونه منظور ما باشه ولي قطعا بايد تعداد داده هاي غير معتبرش خيلي بيشتر از داده هاي معتبرش باشن تا اجازه ورود به ماتريس اسپارس رو داشته باشن.

براي اينكه مطلب بهتر جا بيفته يك مثال ميزنم :

فرض كنيد از شما بخوان اطلاعات يه برگه a4 رو كه تنها يه خط كوچيك توش كشيده شده رو وارد رايانه كنيد
قطعا شما براي اينكار از ساختمان داده ماتريس دو بعدي براي قرار دادن و ذخيره كردن اطلاعات برگه استفاده ميكنيدكه اون ماتريس بايد ماتريس اسپارس باشه

(منظور از دادههاي برگه اينه كه اگه ما صفحه برگه رو يه ماتريس دو بعدي فرض كنيم داده هاي معتبر اون نقاطي هستن كه با قلم شما سياه شدن و تشكيل به خط تو اون صفحه دادن.پس هر نقطه يه داده معتبره تو اون صفحس كه در كنار بيشمار داده غير معتبر قرار گرفته (نقاط سفيد دست نخورده)(كه تو رايانه داده معتبر 1 وداده غير معتبر0 معرفي ميشه))


اما چرا از ماتريس دو بعدي معمولي براي ذخيره سازي داده ها استفاده نميكنيم؟

چون ماتريس دو بعدي معمولي توش هم داده معتبر و هم داده غير معتبر قرار ميگيره (اگه برگرديم به همون مثالي كه زدم داده هاي بيشمار غير معتبر 0 و دادههاي اندك 1 مال برگه آ4 تو اين ماتريس قرار خواهند گرفت)كه همان طور كه ميدانيم داده هاي غير معتبر رو دليلي نداره تو پردازش هايي كه قراره بعدا با دادهاي ماتريس داريم شركت بديم(به دليل اتلاف وقت و حافظه اي كه اين داده هاي غيرمعتبر تو پردازش هامون دارن)

پس از اون جاييكه روز به روز الگوريتم هاي بهينه(الگوريتم هايي كه سريعتر اجرا ميشن و كمتر فضا اشغال ميكنن)جاي الگوريتم هاي قبلي رو ميگيرن پس به جاي نگه داري داده ها از ماتريس اسپارس به جاي ماتريس دو بعدي معمولي استفاده ميكنيم

تكرار ميكنم كه :
از اين ماتريس زماني استفاده ميشه كه داده هاي غير معتبرت خيلي بيشتر از داده هاي معتبرت باشن يعني اگه از ما سئوال كردن از چه ساختمان داده اي براي نگه داري داده هاي يه عكس(كه بسيار داده معتبر داره) استفاده بايد كرد ؟

ميگيم ماتريس دو بعدي نه ماتريس اسپارس چرا كه داده هاي غير معتبر يه عكس خيلي بيشتر از داده هاي معتبرش نيست كه بياييم از ماتريس اسپارس استفاده كنيم.

اما اين سئوال پيش مياد كه ساز وكار ماتريس اسپارس چيه؟
جواب:اين ماتريس مياد جاي اون داده معتبر رو پيدا ميكنه (سطر وستون داده هاي معتبر رو)به همراه مقدار داده (كه ميتونه 1 باشه يا هر عددي باشه)و سطر و ستون ومقدار اون داده رو تو خودش قرار ميده

نكته:
اين ماتريس سه ستون داره و به تعداد داده هاي معتبر سطر داره .

باز براي روشنتر شدن مطلب به مثال خودمان بر ميگرديم
براي قرار دادن داده هاي برگه آ4 ماتريس اسپارس مياد سطر و ستون داده معتبر رو پيدا ميكنه و به همراه خود داده مياد و اون ها رو به ترتيب داخل سطر اول ستون اول و سطر اول و ستون دوم و سطر اول ستون سوم خودش قرار ميدهدو باز براي داده بعدي سطر و ستون و خود داده بعدي رو به ترتيب تو سطر دوم ستون اول و سطر دوم ستون دوم و سطر دوم ستون سوم قرار ميدهد وبراي داده هاي بعدي هم همين كار ها رو انجام ميدهد تا كليه داده ها وارد رايانه شوند


اما پياده سازي الگوريتم ماتريس اسپارس:

كافيست حلقه اي در برنامه مان قرار داده وتو اون هر بار يه داده رو از ماتريس دو بعدي اي كه قبلا از كاربر گرفته شده بگيريم وسطر وستون و خود داده رو تو ماتريس اسپارسي كه از قبل به تعداد سه ستون و به تعداد مورد نظر داده ها سطردار براي سيستم تعريف كرده ايم قرار دهيم و اين حلقه رو تا زماني تكرار كنيم كه ديگر داده اي در ماتريس از قبل پر شده نداشته باشيم

اما اين سئوال پيش مياد كه اون ماتريسي اسپارسي كه قراره وسط برنامه تعداد سطراش مشخص بشه چطور اول برنامه تعداد سطراشو براي سيستم معرفي كنيم؟(نميشه بگيم ماتريسمون يه سطر يا دو و يا فلان مقدار سطر داره چرا كه برنامه مان بايد جامع باشه (نه فقط براي حالات خاص اجرا بشه) ونيز نميتونيم بگيم ماتريسمون n تا سطر داره چرا كه وقتي كامپايلر(مفسر) به n رسيد ميگه n ديگه چيه؟(چون هميشه جاي مقدار سطر عدد قرار ميگيره نه متغير))
پس براي رفع اين مشكل چه كار بايد كرد؟

كافيست از تابع malloc براي اينكار استفاده كنيد تا مشكل حل بشوديعني بنويسيم:

((new= (int*)malloc(sizeof(int* (البته در زبان c)

كه خود اين تابع مياد به تعداد سطر هاي مورد نياز برنامه از سيستم حافطه ميگيره و مشكل مشخص نبودن تعداد سطرهاي ماتريس اسپارس رو برامون حل ميكنه


انشاءالله از مطالبي كه براتون نوشتم راضي بوده باشيد.

You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : clapton
01-11-2011, 11:41 AM
ارسال: #2
RE: ماتريس اسپارس
ماتريس اسپارس

ماتریسی است که اکثریت عناصر ان مقدار ثابت و غیر قابل محاسبه ( معمولا صفر) می باشد و تنها تعداد کمی از خانه های ان داده ها به درد بخور می باشند بنابراین فضای بسیار زیادی از حافظه اصلی را برای ذخیره کردن این تعداد کم داده ها تلف می کنیم .


مثال :

0 0 0 2 0
0 0 3 0 1
0 0 0 0 0
0 18 0 0 0

به عنوان مثال در ماتریس فوق برای ذخیره کردن چهار عنصر غیر صفر یک ماتریس ( 5 * 4 ) و 20 خانه از حافظه را تلف کرده ایم روشی که برای ذخیرهء بهینهء این نوع ماتریسها استفاده می شود بدین صورت است که یک ماتریس در نظر می گیریم که همیشه 3 ستون خواهد داشت و به تعداد عناصر غیر صفر سطر خواهد داشت که در هر سطر در ستون اول شمارهء سطر مربوط به عنصر غیر صفر ودر ستون دوم شمارء مربوط به ستون عنصر غیر صفر ودر ستون سوم مقدار عنصر غیر صفر را ذخیره خواهیم کرد
که کاهش قابل توجهی در میزان حافظه مصرفی خواهیم داشت.
نقل قول: کد:

i j value
2 2 1
1 1 2
3 3 2
18 4 4

You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : behnaz clapton
01-11-2011, 11:46 AM (آخرین تغییر در این ارسال: 01-11-2011 11:52 AM توسط مهرداد عباسی.)
ارسال: #3
RE: ماتريس اسپارس
در کد زیر مراحل ذکر شده در پایین به ترتیب انجام می شود:

۱ : خواندن ماتریس اسپارس و چاپ آن
۲ : چاپ ماتریس واقعی
۳ : جمع و تفریق و ضرب با ماتریسی دیگر


سورس کد ضمیمه شد


فایل‌های ضمیمه
.txt  Aspars Matrix.txt (اندازه: 9.28 KB / دانلودها: 320)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : behnaz clapton tahmina
01-11-2011, 11:48 AM
ارسال: #4
RE: ماتريس اسپارس
چند لینک مفید در باره روش های ذخیره سازی

You are not allowed to view links. Register or Login to view.

You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
01-11-2011, 11:56 AM
ارسال: #5
RE: ماتريس اسپارس
ضمیمه شد

You are not allowed to view links. Register or Login to view.


فایل‌های ضمیمه
.txt  Aspars Matrix linked list.txt (اندازه: 3.69 KB / دانلودها: 126)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : behnaz MN32 naserqw
ارسال پاسخ 


پرش در انجمن: