تعریف : ساختمان داده، کلاسی است که جهت سازماندهی داده ها مورد استفاده قرار می گیرد و از عملیات مختلف قابل اجرا بر روی این داده ها، پشتیبانی می نماید.
معمول ترین و آشنا ترین ساختمان داده، آرایه است که شامل مجموعه ای از داده ها است که پشت سر هم قرار گرفته اند و از طریق یک اندیس مشخص قابل دسترسی هستند.
قبل از شروع این قسمت، مطالب مورد بررسی در مجموعه شش قسمتی مربوط به ساختمان داده را مرور می کنیم تا هدف نهایی از این سری مطالب برای شما مشخص گردد.
در قسمت اول، نگاهی بر اهمیت ساختمان داده ها و چگونگی تاثیر آنها بر کارآیی یک الگوریتم خواهیم کرد. برای تعیین تاثیر کارآیی یک ساختمان داده بر روی یک الگوریتم، لازم است تا کلیه عملیات موجود در ساختمان داده به دفت مورد بررسی قرار گیرند. در ابتدا تمرکز خود را بر روی دو ساختمان داده آرایه و لیست جمع می کنیم، چراکه با این دوساختمان داده از قبل آشنایی داشته و می توانیم راحت تر به آنالیز انها بپردازیم. برای آنالیز کارآیی آنها، به بررسی عملیات موجود در هر یک از آنها و کارآیی هر یک از این عملیات خواهیم پرداخت.
در قسمت دوم ، به بررسی صف (Queue) و پشته (Stack) خواهیم پرداخت. همانند لیست ها، صف و پشته نیز مجموعه ای از داده ها هستند و این دو ساختمان داده در .Net Framework Base Class Library وجود دارند. بر خلاف لیست، که اعضای آن به هر ترتیبی قابل دسترسی هستند، دسترسی به اعضای صف و پشته تنها از طریق ترتیبی خاص قابل دسترسی است. سپس به بررسی چند برنامه و طریقه پیاده سازی صف و پشته خواهیم پرداخت و پس از آن Hashtable ها را مورد بررسی قرار می دهیم. Hashtable ها امکان دسترسی به عناصر را بصورت مستقیم فراهم می نمایند (همانند آرایه یا ArrayList ها) ولی اندیس مورد استفاده در آن کلیدهایی رشته ای هستند. (String Keys)
هر چند ساختمان داده هایی مانند آرایه و لیست، برای دسترسی مستقیم به داده ها در زمانیکه با حجم زیادی از داده ها سر و کار داریم بسیار مفید هستند، این ساختمان داده ها برای جستجو درون داده ها، از بهینگی کمتری برخوردارند. در قسمت سوم، به بررسی ساختمان داده درخت جستجوی دودویی (Binary Search Tree) می پردازیم که روشی مناسب و بهینه برای جستجوی داده های موجود در یک مجموعه است.
اگرچه استفاده از درخت جستجوی دودویی باعث کاهش زمان جستجو می شود، اما دارای نواقص و کاستی هایی نیز می باشد. در قسمت چهارم، به بررسی SkipList ها می پردازیم که ترکیبی از درختهای دودویی و لیست های پیوندی (Linked List) است.
در قسمت پنجم، به بررسی ساختمان داده هایی پرداخته می شوند که می توانند نشان دهنده گراف (Graph) باشند. یک گراف مجموعه ای از گره ها (Nodes) است که هر یک از آنها با لبه هایی (Edge) به گره های دیگر متصل شده اند. برای مثال، نقشه شهرها را میتوان با یک گراف پیاده سازی کرد که در آن شهرها همان گره ها و راه ها و اتوبانهای بین شهرها نشان دهنده Egde ها می باشند. بسیاری از مسایل دنیای واقعی با استفاده از مفهوم گرافها بطور انتزاعی قابل پیاده سازی هستند.
نهایتاً در قسمت ششم، به بررسی ساختمان داده هایی می پردازیم که نشان دهنده Sets و Disjoined Sets هستند. Set ، مجموعه ای است از داده ها که بدون هیچ گونه ترتیبی در کنار یکدیگر قرار گرفته اند. Disjoined Set ، مجموعه ای از Set هاست که هیچ عنصر مشترکی با یکدیگر ندارند. این دو مفهوم در پیاده سازی برنامه های امروزه کارآیی زیادی دارند و در قسمت ششم به بررسی و نحوه استفاده از آنها خواهیم پرداخت.
آنالیز کارآیی ساختمان های داده
هنگامیکه با یک مسئله برنامه نویسی مواجه می شویم، اغلب برنامه نویسان و طراحان نرم افزار به دنبال پیدا کردن و طراحی الگوریتمی هستند تا بتوانند بواسطه آن کارآیی برنامه خود را افزایش داده و نیازهای کاربر را به بهترین شکل ممکن برآورده نمایند. از دید یک کاربر نرم افزار نیز مفید بودن برنامه اهمیت دارد و کمتر کسی پیدا می شود که به الگوریتم پشت پرده مورد استفاده در برنامه اهمیت دهد. اما استفاده از یک الگوریتم قوی و کارآ در زمینه برنامه یا نرم افزاری که تولید می شود، می تواند نقش بسیار مهمی در افزایش کارآیی برنامه داشته باشد. بعنوان مثال، جستجو درون یک آرایه را در نظر بگیرید. با استفاده یک الگوریتم جستجوی ساده و عادی، به تعداد اعضای موجود در آرایه باید عمل جستجو انجام گیرد. با استفاده از درخت جستجوی دودویی یا SkipList ها، مدت زمان جستجو برای یک عنصر نسبتی لگاریتمی با تعداد اعضای موجود در آرایه پیدا می کند و باعث کاهش زمان جستجو می شود. زمانیکه در انبوهی از داده های بخواهیم به جستجو بپردازیم، نوع الگوریتم و ساختمان داده مورداستفاده بسیار می تواند در زمان انجام جستجو موثر باشد، بطوری که می توان اختلاف آنرا بر حسب ثانیه و حتی دقیقه حس نمود.
اگرچه ساختمان داده مورد استفاده در یک الگوریتم به شدت می تواند کارآیی آن را تحت تاثیر قرار دهد، اما روشهای دقیق و مناسبی نیز برای مقایسه و بدست آوردن این کارآیی باید وجو داشته باشند. مسئله ای که برای ما بعنوان یک طراح نرم افزار یا برنامه نویس می تواند اهمیت داشته باشد، کارآیی ساختمان های داده مختلف به هنگام افزایش حجم داده ها است. و این بدان معناست که برای هر عنصر جدیدی که وارد ساختمان داده ما می شود، زمان کار الگوریتم ما به ه شکلی تحت تاثیر قرار می گیرد.
به مثال زیر توجه کنید، فرض کنید باید برنامه ای بنویسید که آرایه ای از رشته ها را بعنوان ورودی دریافت نماید که این آرایه حاوی نام تعدادی فایل است. وظیفه برنامه شما اینست که درون این آرایه به دنبال فایلی با پسوند خاصی بگردد. نمونه ساده این برنامه می تواند بشک زیر باشد :
public bool DoesExtensionExist(string [] fileNames, string extension)
{
int i = 0;
for (i = 0; i < fileNames.Length; i++)
if (String.Compare(Path.GetExtension(fileNames[i]), extension, true) == 0)
return true;
return false; // If we reach here, we didn't find the extension
}
}
به نگاهی دقیق تر به این برنامه، متوجه می شوید که در بدترین حالت، یعنی زمانیکه فایل مورد نظر در آرایه وجود نداشته باشد و یا وجود داشته باشد اما در آخرین خانه آرایه جای داشته باشد، باید تمامی عناصر آرایه را یکبار مورد بررسی و جستجو قرار دهیم. برای آنالیز مسائل، بطور مثال برای آنالیز مرتب سازی عناصر آرایه (Sort)، به شکل زیر باید فکر کنیم : " فرص می کنم آرایه ای با n عنصر دارم، اگر عنصر دیگری به این آرایه اضافه کنم n+1 عنصر خواهم داشت، در این حالت زمان اجرای برنامه من چقدر خواهد شد؟ " . توجه نمایید که کلمه "زمان اجرا " یا Running Time عملا به معنا محاسبه دقیق زمان اجرا برنامه نیست، بلکه محاسبه تعداد مراحل و زمان اجرای این مراحل برای یک عمل خواسته شده است. برای مثال در مورد آرایه، تعداد مراحل به تعداد دفعات دسترسی به عناصر آرایه است. برای جستجو درون یک آرایه، در صورتیکه n+1 عنصر در آرایه داشته باشیم، باید n+1 بار مقدار مورد نظر خود را با عناصر آرایه مقایسه نماییم. از اینرو می گوئیم مدت زمان جستجو درون یک آرایه بطور خطی با تعداد عناصر موجود در آرایه رابطه مستقیم دارد.
این روش آنالیز که در اینجا مطرح گردید، به روش آنالیز آسیمپوتیک (Asymptotic Analyze) معروف است. روش علامتگذاری که در این روش آنالیز مورد استفاده قرار می گیرد، به روش نشانه گذاری O (Big-Oh Notation) معروف است. برای نشان دادن کارآیی جستجو در آرایه غیر مرتب با استفاده از این روش نشانه گذاری، بشکل زیر عمل می شود O(n) که نشان دهنده رابطه زمان با تعداد اعضا است. بدین ترتیب با استفاده از O(n) برای نشان دادن کارآیی یک ساختمان داده، این مفهوم بدست می آید که رابطه ای خطی و مستقیم بین افزایش تعداد اعضای از n به n+1 و زمان انجام عملیات وجود دارد. بدین ترتیب علامت O نشان دهنده روش نشانه گذاری و روش آنالیز کارآیی است و n نشان دهنده چگونگی افزایش مراحل پردازش عمل بسته به تعداد عناصری است که می خواهند مورد پردازش قرار گیرند.
برای محاسبه زمان اجرای یک قطعه کد با استفاده از O-Notation یا همان Asymptotic Analyze می توان از چند مرحله ساده زیر استفاده نمود :
1- بدست آوردن مراحلی که زمان اجرای یک الگوریتم را شکل می دهند. همانطور که قبلاً ذکر شد، این مراحل برای یک آرایه، خواندن و نوشتن یا همان دسترسی به عناصر آرایه است و این مراحل برای ساختمان های داده ای دیگر متفاوت خواهد بود. باید توجه داشته باشید که برای آنالیز کارآیی یک ساختمان داده، تنها به مراحلی که توسط خود ساختمان داده ی مورد نظر انجام می شود توجه می گردد و عملیات ساده ای که توسط کامپیوتر انجام می شوند را در این محاسبه به حساب نمی آوریم. برای مثال در کد بالا، برای محاسبه کارآیی تنها به تعداد دفعات لازم برای دسترسی به عناصر آرایه توجه کرده و به زمان های لازم جهت ایجاد متغیرها و با زمان محاسبه تساوی دو رشته اهمیت نداده ایم.
2- خطهایی از برنامه که در الگوریتم شما تاثیر دارند و می خواهید کارآیی را برای آنها محاسبه کنید را پیدا کرده و در کنار آنها عدد 1 قرار دهید.
3- اگر این خطوط که آنها را با عدد 1 مشخص کرده اید خود یک حلقه تکرار هستند، بجای عدد 1 در کنار آنها عدد معادل بیشترین تعداد تکرار حلقه را قرار دهید. اگر در جایی حلقه تو در تو دارید، باید از ضرب بیشترین تعداد دفعات تکرار حلقه ها استفاده کنید.
4- بزگترین عدد نوشته شده را پیدا کنید. این عدد زمان اجراست.