انتخاب ساختمان داده در عمل: آرایه، لیست، هش یا درخت؟
چهار ساختار پرکاربرد کنار هم، با جدول مقایسه‌ی پیچیدگی زمانی و یک روش ساده برای تصمیم‌گیری در پروژه‌های واقعی.
انتخاب ساختمان داده یکی از تصمیم‌هایی است که بیشترین اثر را روی سرعت برنامه دارد. در درس ساختمان داده‌ها این ساختارها را یکی‌یکی می‌خوانیم. اما در پروژه‌ی واقعی سؤال این است: برای این مسئله کدام را بردارم؟ این نوشته چهار انتخاب رایج را کنار هم می‌گذارد و یک روش ساده برای تصمیم پیشنهاد می‌کند.
اول بپرسید: بیشتر چه عملی انجام می‌دهید؟
هیچ ساختاری در همه‌چیز بهترین نیست. هر کدام چند عمل را سریع انجام می‌دهد و در عوض در کارهای دیگر کند است. پس قبل از انتخاب، فهرست کنید برنامه‌تان بیشتر چه می‌کند:
- دسترسی به عنصر iام با شماره‌اش.
- جست‌وجوی یک مقدار یا یک کلید.
- افزودن و حذف در ابتدا، انتها یا وسط.
- نگه داشتن داده به ترتیب، یا پیدا کردن کوچک‌ترین و بزرگ‌ترین.
بعد ببینید کدام عمل‌ها بیشتر تکرار می‌شوند. همان‌ها تعیین‌کننده‌اند.
آرایه‌ی پویا
آرایه عنصرها را پشت سر هم در حافظه نگه می‌دارد. برای همین دسترسی با اندیس در زمان ثابت انجام می‌شود. آرایه‌ی پویا، مثل list در پایتون یا vector در ++C، وقتی پر شود خودش را بزرگ‌تر می‌کند. به همین دلیل افزودن به انتهای آن به‌طور سرشکن O(1) است.
ضعف آرایه افزودن و حذف در ابتدا یا وسط است، چون باید بقیه‌ی عنصرها جابه‌جا شوند. جست‌وجو در آرایه‌ی نامرتب هم خطی است. اما اگر آرایه مرتب باشد، با جست‌وجوی دودویی در O(log n) به جواب می‌رسید.
یک مزیت کمتر دیده‌شده هم دارد. چون داده‌ها کنار هم‌اند، از حافظه‌ی نهان پردازنده خوب استفاده می‌کند. در عمل، آرایه گاهی از ساختارهایی که روی کاغذ سریع‌ترند جلو می‌زند.
لیست پیوندی
در لیست پیوندی هر عنصر یک گره است که به گره بعدی اشاره می‌کند. افزودن و حذف در ابتدای لیست O(1) است. اگر به گره‌ای اشاره‌گر داشته باشید، افزودن بعد از آن هم O(1) است. در لیست دوطرفه، حذف خود آن گره هم در زمان ثابت انجام می‌شود.
در عوض، برای رسیدن به عنصر iام باید از اول لیست راه بیفتید؛ پس دسترسی O(n) است. گره‌ها هم در حافظه پراکنده‌اند و هر کدام جای اضافه برای اشاره‌گر می‌خواهد. لیست پیوندی وقتی به کار می‌آید که مدام در جاهای مشخص اضافه و حذف کنید. نمونه‌ی معروفش حافظه‌ی نهان LRU است که لیست دوطرفه را کنار یک جدول درهم‌سازی به کار می‌برد.
جدول درهم‌سازی
جدول درهم‌سازی یا هش، هر کلید را با یک تابع درهم‌سازی به یک خانه می‌برد. جست‌وجو، افزودن و حذف به‌طور میانگین O(1) است. dict و set در پایتون و HashMap در جاوا از این نوع‌اند.
دو نکته را فراموش نکنید. اول، در بدترین حالت، وقتی برخوردها زیاد شوند، این عمل‌ها تا O(n) کند می‌شوند. دوم، جدول درهم‌سازی ترتیب ندارد. اگر کلیدها را مرتب بخواهید یا دنبال همه‌ی کلیدهای بین دو مقدار باشید، باید سراغ ساختار دیگری بروید.
درخت جست‌وجوی دودویی متوازن
درخت جست‌وجوی دودویی کلیدها را مرتب نگه می‌دارد. نسخه‌های متوازن، مثل درخت AVL یا درخت قرمز-سیاه، تضمین می‌کنند ارتفاع درخت O(log n) بماند. پس جست‌وجو، افزودن و حذف حتی در بدترین حالت O(log n) است. TreeMap در جاوا و std::map در ++C معمولاً با درخت قرمز-سیاه پیاده شده‌اند.
درخت نامتوازن را با این‌ها اشتباه نگیرید. اگر کلیدها به ترتیب وارد شوند، درخت ساده به یک زنجیره تبدیل می‌شود و همه‌ی عمل‌ها O(n) می‌شوند.
جدول مقایسه‌ی ساختمان داده‌ها
دو جدول زیر هزینه‌ی رایج‌ترین عمل‌ها را نشان می‌دهند. n تعداد عنصرهاست و «سرشکن» یعنی میانگین در یک دنباله‌ی طولانی از عمل‌ها.
| ساختار | دسترسی با اندیس | جست‌وجو | افزودن |
|---|---|---|---|
| آرایه‌ی پویا | O(1) | O(n)؛ مرتب: O(log n) | انتها: سرشکن O(1)؛ وسط: O(n) |
| لیست پیوندی | O(n) | O(n) | ابتدا یا بعد از گره معلوم: O(1) |
| جدول درهم‌سازی | ندارد | میانگین O(1)؛ بدترین O(n) | میانگین O(1)؛ بدترین O(n) |
| درخت متوازن | ندارد | O(log n) | O(log n) |
جدول دوم، حذف و کارهایی را نشان می‌دهد که به ترتیب داده‌ها مربوط‌اند.
| ساختار | حذف | کوچک‌ترین یا بزرگ‌ترین | پیمایش به ترتیب کلید |
|---|---|---|---|
| آرایه‌ی پویا | انتها: O(1)؛ وسط: O(n) | O(n)؛ مرتب: O(1) | O(n log n) با مرتب‌سازی |
| لیست پیوندی | ابتدا: O(1)؛ گره معلوم در لیست دوطرفه: O(1) | O(n) | O(n log n) با مرتب‌سازی |
| جدول درهم‌سازی | میانگین O(1)؛ بدترین O(n) | O(n) | O(n log n) با مرتب‌سازی |
| درخت متوازن | O(log n) | O(log n) | O(n) |
یک روش سریع برای تصمیم
- اگر بیشتر با شماره به عنصرها دسترسی دارید و به انتها اضافه می‌کنید، آرایه‌ی پویا.
- اگر مهم‌ترین کار پیدا کردن با کلید است و ترتیب اهمیتی ندارد، جدول درهم‌سازی.
- اگر هم جست‌وجوی سریع می‌خواهید و هم ترتیب، درخت متوازن.
- اگر مدام در جاهایی که اشاره‌گرشان را دارید اضافه و حذف می‌کنید، لیست پیوندی.
- اگر بارها فقط کوچک‌ترین عنصر را لازم دارید، به هیپ فکر کنید که برای همین کار ساخته شده است.
یادتان باشد که Big-O فقط رفتار را در n بزرگ نشان می‌دهد. برای داده‌ی کوچک، ضریب‌های ثابت و حافظه‌ی نهان مهم‌ترند. اگر شک دارید، هر دو گزینه را با داده‌ی واقعی بسنجید.
برای مرور هزینه‌ی عمل‌ها در پایتون، صفحه‌ی TimeComplexity در ویکی رسمی پایتون مرجع خوبی است. برای یک درس کامل، درس مقدمه‌ای بر الگوریتم‌ها در MIT OpenCourseWare را ببینید. جزوه و نمونه‌سؤال درس ساختمان داده‌ها هم در جزوه‌ها و نمونه‌سؤال‌های فایلامون هست.
جمع‌بندی
انتخاب ساختمان داده باید از روی عمل‌های پرتکرار برنامه انجام شود، نه از روی عادت. آرایه برای دسترسی سریع، هش برای پیدا کردن با کلید، درخت متوازن برای ترتیب و لیست پیوندی برای افزودن و حذف در جای معلوم. جدول‌های بالا را کنار دستتان نگه دارید و در هر پروژه یک بار از خودتان بپرسید: چرا این ساختار؟
نظرها
وارد شوید تا نظرتان را بنویسید.
هنوز نظری نوشته نشده است.
