مینی پروژه دوم

یکی از مهم‌ترین مباحث موجود در علوم کامپیوتر و به خصوص یادگیری ماشینی، مبحث فشرده‌سازی و استفاده‌ی بهینه از فضاهای موجود است. هم‌چنین فشرده‌سازی به شکل مناسب، می‌تواند عملیات‌های پایه نظیر افزودن، حذف کردن، جست و جو و اصلاح یک عنصر را تسریع بخشد.

در علم یادگیری ماشینی، داده ساختار ماتریس، یکی از پرکاربردترین ساختمان‌‌های داده به شما می‌رود و از این روی، در این پروژه کوچک، قرار است به مبحث فشرده‌سازی و نمایش صحیح یک ماتریس در ابعاد بزرگ بپردازیم.

شما تا کنون با داده‌ ساختار‌های آرایه و لیست پیوندی آشنا شده و عملیات‌های مربوط به هر یک و پیچیدگی زمانی هرکدام را به خوبی فرا گرفته‌اید. در ادامه شما بایستی به کمک همین دو ساختار، یک ماتریس خلوت را به شکل مناسبی نمایش داده و با کاهش فضای ذخیره‌سازی، اقدامات خواسته شده را انجام دهید.

منظور از ماتریس خلوت، ماتریسی است که تعداد خانه‌های صفر آن بسیار زیاد بوده و نسبت خانه‌های غیرصفر به صفر در آن عدد کوچکی خواهد شد. به عنوان مثال در شکل زیر می‌توانید یک ماتریس خلوت را مشاهده کنید:

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

روش‌های متنوعی برای فشرده‌سازی داده‌های ماتریس خلوت وجود دارد که در این مینی پروژه قصد داریم یکی از روش‌های بهینه آن را پیاده‌سازی کنیم. صورت پروژه را از فایل Project.md می‌توانید مشاهده کنید.

برای اطلاعات بیشتر در مورد کاربرد های ماتریس خلوت (Sparse Matrix) تحقیق کنید.