الگوریتم و ساختمان داده چیست؟

الگوریتم و ساختمان داده چیست؟

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

چنان که Donald Knuth در کتاب The Art of Computer Programming بیان می‌کند، Algorithm واژهٔ پیچیده‌ای است به نحوی که گویا دو واژهٔ Logarithm و Arithmetic به ترتیب به معنای «لوگاریتم» و «حساب» را با هم ترکیب کرده‌اند تا این واژه را بسازند اما وجه تسمیه‌ای که کاملاً روی آن اتفاق نظر وجود دارد این است که الگوریتم از واژهٔ «الخوارزمی» گرفته شده است (ابوجعفر محمد بن موسی خوارزمی، ریاضیدان و ستاره‌شناس نامی ایرانی است.)

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

الگوریتم چیست؟
همان‌طور که اشاره شد، واژهٔ الگوریتم برای توصیف یک فرآیند گام به گام (یا مرحله به مرحله) استفاده می‌شود که در هر مرحله تنها یک راه درست و مشخص برای انجام تَسکی خاص وجود دارد که برای آشنایی بیشتر با این مفهوم، یک مثال واقعی در ارتباط با دفترچه تلفن زده و کاربرد سه الگوریتم متفاوت را در آن مورد بررسی قرار خواهیم داد.

- الگوریتم جستجوی خطی (Linear Search): فرض کنید به چندین سال پیش و به زمانی برگشته‌ایم که دفترچه تلفن‌ هنوز کاربرد داشت. اگر به خاطر داشته باشید، این دفترچه‌ها یک ویژگی داشتند و آن هم اینکه نام‌ها بر اساس حرف الفبا نوشته می‌شدند. حال فرض کنید شماره تلفن فردی به نام «سپهر نیک‌مرام» از قبل در این دفترچه نوشته شده و اکنون می‌خواهید با وی تماس بگیرید. برای پیدا کردن این شماره تلفن، راه‌های مختلفی پیش‌ روی شما قرار دارد و ساده‌ترین راهی که به ذهن می‌رسد این است که تک‌تک نام‌هایی که با حرف «س» شروع می‌شوند را در دفترچه تلفن چک کنید تا به نام مورد نظر خود برسید. به عنوان مثال:

- سارا آزاد بخت، نَه این نیست.
- سعید امیری، این هم نیست.
- سولماز ایزدی، این هم نیست.

و به همین ترتیب ادامه دهید تا بعد از بررسی تعداد زیادی از نام‌ها به «سپهر نیک‌مرام» برسید. این روش که Linear Search (جستجوی خطی) نام دارد، روش ساده‌ای است که در طی آن تمام موارد موجود در یک لیست با اطلاعات مورد نظر مقایسه می‌شوند تا نتیجهٔ مورد انتظار حاصل شود و این روش هرچند که ساده است و در موارد بسیاری نیز استفاده از آن کاملاً منطقی به نظر می‌رسد، اما گاهی می‌تواند بسیار زمان‌بَر باشد و نیاز به توضیح نیست که در توسعهٔ نرم‌افزار زمان اِلِمان بسیار مهمی در اجرای یک تَسک است.

- الگوریتم جستجوی بخش به بخش (Chunking Search): حال فرض کنید که دفترچه تلفن شما فاقد زبانه‌های نشان‌دهندهٔ‌ حروف الفبا است و می‌خواهید نامی را در آن پیدا نمایید. در این شرایط شاید شما هم مانند اغلب آدم‌ها آن‌قدر صبر و شکیبایی نداشته باشید تا تمام نام‌ها را بررسی کنید و سرانجام به نام مورد نظر خود برسید و اینجا است که جستجوی خطی دیگر روش مناسبی نیست و باید برای یافتن نام مورد نظر به دنبال روش بهتری بود.

روش بهتر و کاربردی‌تری که ‌می‌توانید برای این منظور استفاده کنید، Chunking Search (جستجوی بخش به بخش) است به این صورت که برای یافتن یک نام خاص، به جای شروع از نخستین نام موجود در لیست، ابتدا محل تقریبی قرار گرفتن نام مورد نظر خود را مشخص نموده و مستقیم در این بخش به جستجوی آن می‌پردازید.

مثلاً فرض کنید که به دنبال شمارهٔ فردی به نام «کیوان علی‌زاده» می‌گردید. برای پیدا کردن آن با روش Chunking Search، می‌توانید با توجه به اینکه حرف «ک» بیست‌و‌پنجمین حرف الفبای فارسی است، حدس بزنید که این نام در کجای دفترچه قرار دارد. فرض کنید که با حدس زدن به این نتیجه رسیدید که نام مورد نظر باید در صفحهٔ شمارهٔ ۵۰ دفترچه تلفن قرار داشته باشد اما پس از باز کردن صفحهٔ ۵۰ متوجه می‌شوید که اسامی موجود در این صفحه با حرف «ص» آغاز شده‌اند و از همین روی برای رسیدن به صفحهٔ حدودی محل قرارگیری نام مد نظر باید چندین صفحه جلوتر بروید. با این دیدگاه، صفحهٔ ۷۰ دفترچه را باز می کنید و می‌بینید که اسامی موجود در آن با حرف «م» آغاز شده‌اند و متوجه می‌شوید که باید کمی به عقب برگردید تا به حرف «ک» برسید و به این ترتیب کمی عقب‌تر می‌روید و با باز نمودن صفحهٔ‌ ۶۵ دفترچه، به حرف مذکور می‌رسید.

با این تفاسیر، دیگر لازم نیست برای یافتن نامی که با حرف «ک» شروع می‌شود دفترچه را از ابتدای آن صفحه به صفحه بررسی کنید زیرا می‌دانید که محل تقریبی نام مورد نظر شما جایی میان صفحه‌ ۶۵ تا انتهای صفحات حرف «ک» قرار دارد و نیاز به توضیح نیست که این روش نسبت به روش جستجوی خطی، رویکرد منطقی‌تری است اما در عین حال به قدر کافی بهینه نیست و همان‌طور که پیش از این اشاره کردیم،‌ وقتی پای پرفورمنس نرم‌افزار به میان می‌آید، باید تمام تلاش خود را به کار بندیم تا تَسک مذکور در کمترین زمان ممکن عملی گردد.

- الگوریتم جستجوی دودویی (Binary Search): بهترین روش برای یافتن یک نام در دفترچهٔ تلفن این است که دفترچه را از وسط به دو بخش تقسیم نموده و تعیین کنیم که نام مورد نظر در کدام نیمه قرار ندارد و در ادامه آن بخش را از جستجوی خود حذف نماییم.

فرض کنید دفترچه تلفن شما ۴۰۰ صفحه دارد و می‌خواهید شمارهٔ شخصی به نام «فریبا بختیاری» را در آن پیدا کنید (همچنین فرض کنید نام این شخص در صفحهٔ ۲۹۱ دفترچه قرار دارد اما شما این موضوع را نمی‌دانید.) حال با استفاده از روش باینری یا دودویی، می‌توانید نام این شخص را بیابید به این صورت که دفترچه را از وسط به دو بخش تقسیم می‌کنید و صفحهٔ‌ باز شده (یعنی صفحهٔ ۲۰۰) را نگاه می‌کنید. متوجه می‌شوید که نام‌هایی که با حرف «ش» و یا «ص» شروع می‌شوند در این صفحه قرار دارند و با توجه به اینکه حرف «ف» که حرف اول نام مد نظر است پس از حروف «ش» و «ص» قرار دارد، می‌توان با قاطعیت گفت که نام مورد نظر در نیمهٔ‌ اول دفترچه قرار ندارد و از همین روی نام «فریبا بختیاری» باید جایی میان صفحات ۲۰۰ تا ۴۰۰ باشد.

حال نیمهٔ باقیمانده را مجدداً از وسط به دو بخش تقسیم می‌کنیم. یعنی این بار باید صفحهٔ‌ ۳۰۰ را باز کنید. فرض کنید صفحهٔ ۳۰۰ دفترچه را باز نموده و نام‌هایی را مشاهده می‌کنید که با حرف «ق» آغاز می‌شوند و به عنوان یک فارسی‌زبان قطعاً می‌دانید که حرف «ف» دقیقاً قبل از حرف «ق» قرار دارد و با ورق زدن فقط چند صفحه، می‌توان آن را پیدا کرد اما برای ادامهٔ الگوریتم جستجوی باینری، فرض کنید که چنین چیزی را نمی‌دانید.

با دیدن حرف «ق» نتیجه می‌گیرید که نام مورد نظر در نیمهٔ دوم این بخش قرار ندارد و بنابراین نیمهٔ دوم را حذف می‌کنید که مسلماً نام مد نظر باید جایی میان صفحات ۲۰۰ تا ۳۰۰ باشد. اگر کمی دقت کنید، در می‌یابید که در ابتدا جستجوی خود را در میان ۴۰۰ صفحه آغاز کردید و اکنون پس از دو مرحله موفق شدید تعداد صفحات را به یک‌چهارم تعداد اولیه کاهش دهید! با ادامه دادن روش جستجوی باینری به صورت زیر، در نهایت به صفحه‌ای که نام مورد نظر در آن قرار دارد دست خواهید یافت:

[200-300] → [250-300] → [275-300] → [287-300] → [287-293] → [290-293] → [290-291] → 291

بدین ترتیب، فقط با چند بار مقایسه می‌توانید نام مورد نظر خود را در یک دفترچه تلفن ۴۰۰ صفحه‌ای پیدا کرد. در این روش، تعداد مقایسه‌های مورد نیاز به صورت (log2(n محاسبه می‌شود. در مثال فوق در بین ۴۰۰ صفحه، با ۹ بار مقایسه صفحهٔ مورد نظر مشخص شد:

Log2(400) = 8.64385618977

و این در حالی است که با روش جستجوی خطی برای یافتن این نام، که در صفحهٔ ۲۹۱ قرار داشت، باید صفحه به صفحه پیش می‌رفتیم تا به صفحهٔ مورد نظر برسیم و در همین مثال اگر دفترچه تلفن ۴۰۰۰۰۰۰ صفحه داشت، برای یافتن صفحه‌ای که نام «فریبا بختیاری» در آن قرار دارد به ۲۲ بار مقایسه نیاز می‌داشتید:

log2(4000000) = 21.9315685693

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

ساختمان داده چیست؟
در علوم کامپیوتر، اصطلاح Data Structure (ساختمان داده) به روش ساماندهی داده‌ها اطلاق می‌شود. به عبارت دقیق‌تر، دیتا استراکچر مجموعه‌ای از مقادیر دیتا، ارتباطات میان آن‌ها و اَعمالی که می‌توان بر روی داده‌ها انجام داد را در بر می‌گیرد.

وقتی مفاهیم الگوریتم و ساختمان داده در کنار هم قرار می‌گیرند، ممکن است کمی پیچیده به نظر برسند که در همین راستا و برای درک بهتر دیتا استراکچر، اجازه بدهید تا دیتا استراکچر Queue (صَف) را به عنوان یک مثال مورد بررسی قرار دهیم (نیاز به توضیح است که اگر با دیتا استراکچرها آشنایی نداشته باشید، مثل این است که یکی از ابزارهای جعبه‌‌ابزارتان را گم کرد‌ه‌اید و باید دیر یا زود منتظر رخ دادن مشکلاتی در اجرای الگوریتم‌های مختلف باشید!)

آشنایی با ساختمان دادهٔ صَف
ممکن است مثال خوبی از دیتا استراکچر Queue را در اغذیه‌فروشی‌ها یا بانک‌ها تجربه کرده باشید به این صورت که با ورود به آنجا، شماره‌ای را دریافت می‌کنید و منتظر می‌مانید تا شمارهٔ شما را صدا بزنند. هر کس قبل از شما وارد صف شده باشد، قبل از شما هم سفارش خود را دریافت خواهد کرد و هر کسی هم که پس از شما وارد شده باشد، مسلماً بعد از شما غذا میل خواهد کرد و بدین ترتیب اگر کسی باشید که بیش از سایر افرادی که در صَف هستند منتظر مانده باشید، یعنی در صَف کسی جلوی شما نباشد، اولین کسی که کارتان را انجام خواهند داد شما هستید.

به طور کلی، Queue دو ویژگی اصلی تحت عناوین Enqueue و Dequeue دارد که Enqueue به زمانی اطلاق می‌گردد که ورود به صَف انتظار رخ می‌دهد که معادل دریافت شماره در مثال فوق است و Dequeue به زمانی اطلاق می‌شود که انتظار تمام می‌شود که معادل زمانی است که شمارهٔ شما را صدا می‌زنند. ساختمان دادهٔ صف به طور خلاصه با عبارت FIFO که مخفف واژگان First-In-First-Out است توصیف می‌شود. به عبارت دیگر، هر آیتمی که اول وارد صَف شود، اول هم خارج خواهد شد.

منابع آموزشی مرتبط با الگوریتم و دیتا استراکچر
برای یادگیری این دو مقوله منابع مختلفی به صورت رایگان و غیررایگان در وب می‌توان یافت که در ادامه برخی از منابع رایگان را لیست کرده‌ایم:

- Khan Academy Algorithms Course
Introduction to Data Structures
- Geek for Geeks Data Structures
Data Structures & Algorithms in Python

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

شما تا چه حد با مفاهیم الگوریتم و ساختمان داده آشنایی دارید و به نظرتان آیا آشنایی و یا عدم آشنایی با این مفاهیم می‌تواند تأثیر منفی یا مثبتی بر موفقیت یک برنامه‌نویس داشته باشد؟ نظرات، دیدگاه‌ها و تجربیات خود را با سایر کاربران سکان آکادمی به اشتراک بگذارید.

منبع


رائفه خلیلی