بتل کد Battle Codeدارد باز می‌شود…

الگوریتم

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

مقایسه: more … than و ‎-er

درباره‌ی الگوریتم‌ها همیشه مقایسه می‌کنیم. صفت‌های کوتاه ‎-er می‌گیرند: faster، slower، smaller. صفت‌های بلند با more می‌آیند: more efficient، more complex. بعد از هر دو than می‌آید: Binary search is faster than brute force.

هشت کلمه‌ی این درس

algorithm (اَلگُریتِم): الگوریتم؛ روش قدم‌به‌قدم حل یک مسئله

algorithm یعنی دستور کاری قدم‌به‌قدم و روشن برای حل یک مسئله، مثل دستور پخت یک غذا: اول این، بعد آن، تا وقتی که آماده شود. مرتب کردن یک فهرست، پیدا کردن کوتاه‌ترین راه روی نقشه و پیشنهاد ویدیوی بعدی همه با الگوریتم انجام می‌شوند. الگوریتم فکرِ پشت کد است؛ همان الگوریتم را می‌شود با هر زبانی نوشت.

This algorithm sorts a list of numbers from small to large.

این الگوریتم فهرستی از عددها را از کوچک به بزرگ مرتب می‌کند.

complexity (کامپلِکسیتی): پیچیدگی؛ این‌که با بزرگ شدن داده کار چقدر بیشتر می‌شود

complex یعنی پیچیده و complexity یعنی پیچیدگی. درباره‌ی الگوریتم‌ها معنی دقیقی دارد: وقتی داده بزرگ‌تر می‌شود، زمان (time complexity) یا حافظه‌ی لازم (space complexity) چقدر بیشتر می‌شود. آن را با نماد O می‌نویسند: O(n) یعنی اگر داده دو برابر شود کار هم دو برابر می‌شود، و O(n²) یعنی چهار برابر. به پیچیده بودن خود کد هم همین کلمه را می‌گویند.

The time complexity of binary search is O(log n).

پیچیدگی زمانی جست‌وجوی دودویی O(log n) است.

recursion (ریکِرژِن): بازگشت؛ تابعی که خودش را صدا می‌زند

recur یعنی دوباره پیش آمدن. recursion یعنی یک تابع برای حل مسئله خودش را روی تکه‌ی کوچک‌تری از همان مسئله صدا بزند، تا به ساده‌ترین حالت برسد و بایستد (base case). مثل عروسک‌های تودرتوی روسی: هر کدام را باز می‌کنی یکی کوچک‌تر درونش است، تا به آخری برسی. برای گشتن در درخت‌ها و پوشه‌های تودرتو خیلی به کار می‌آید.

This function uses recursion to visit every folder.

این تابع برای سر زدن به همه‌ی پوشه‌ها از بازگشت استفاده می‌کند.

iteration (ایتِرِیشِن): تکرار؛ یک دور از حلقه

iterate یعنی کاری را پشت سر هم تکرار کردن. iteration دو چیز را می‌گوید: هم خود کار تکرار با حلقه (در برابر recursion)، هم یک دور از حلقه؛ حلقه‌ای که ده بار می‌چرخد ده iteration دارد. در کار تیمی هم می‌شنوی: هر نسخه‌ی تازه و بهترشده‌ی یک طرح یک iteration است.

The loop stops after ten iterations.

حلقه بعد از ده دور می‌ایستد.

binary search (باینِری سِرچ): جست‌وجوی دودویی؛ هر بار نصف کردن

binary یعنی «دوتایی» و search یعنی جست‌وجو. binary search روشی برای پیدا کردن چیزی در یک فهرست مرتب است: وسط را نگاه می‌کنی؛ اگر چیزی که می‌خواهی کوچک‌تر بود نیمه‌ی راست را دور می‌ریزی، وگرنه نیمه‌ی چپ را، و همین را تکرار می‌کنی. مثل بازی حدس عدد با «بیشتر» و «کمتر». در یک میلیون عضو، با حدود بیست قدم به جواب می‌رسی.

Binary search only works if the list is sorted.

جست‌وجوی دودویی فقط وقتی کار می‌کند که فهرست مرتب باشد.

brute force (بروت فُرس): زور خام؛ امتحان کردن همه‌ی حالت‌ها

brute یعنی خشن و بی‌فکر و force یعنی زور؛ brute force یعنی «با زور خالی». در الگوریتم به ساده‌ترین راه می‌گویند: همه‌ی حالت‌های ممکن را یکی‌یکی امتحان کن تا جواب پیدا شود. همیشه جواب می‌دهد، ولی برای داده‌ی بزرگ خیلی کند است. در امنیت هم به حمله‌ای می‌گویند که همه‌ی رمزهای ممکن را امتحان می‌کند؛ برای همین سایت‌ها بعد از چند رمز غلط جلوی تو را می‌گیرند.

The brute force solution is too slow for large inputs.

راه‌حل زور خام برای ورودی‌های بزرگ خیلی کند است.

efficient (ایفیشِنت): بهینه؛ کارآمد و بدون هدر دادن

efficient یعنی کاری را با کمترین هدر رفتن زمان، انرژی یا پول انجام دادن. کد efficient همان نتیجه را با زمان یا حافظه‌ی کمتر می‌دهد. خودروی کم‌مصرف را هم fuel-efficient می‌گویند. مخالفش inefficient است و اسمش efficiency.

A dictionary is more efficient than a list for lookups.

برای پیدا کردن مقدار، دیکشنری از لیست بهینه‌تر است.

optimize (آپتیمایز): بهینه کردن؛ سریع‌تر یا سبک‌تر کردن

optimize یعنی چیزی را تا جای ممکن بهتر کردن؛ هم‌ریشه با optimal (بهترین حالت). در برنامه‌نویسی یعنی کدی را که درست کار می‌کند عوض کنی تا سریع‌تر شود، حافظه‌ی کمتری بگیرد یا حجمش کم شود. قانون باتجربه‌ها: اول کد را درست کن، بعد اگر واقعاً کند بود بهینه‌اش کن. اسمش optimization است.

We optimized the query and now it runs ten times faster.

کوئری را بهینه کردیم و حالا ده برابر سریع‌تر اجرا می‌شود.

بازبینی یک کد

Sara: Your algorithm works, but it is a brute force solution. It checks every item one by one.
Ali: Is that a problem? The list is sorted.
Sara: Then use binary search. It is much more efficient: about 20 steps for a million items.
Ali: Should I write it with recursion?
Sara: You can, but a simple loop is easier to read. Each iteration cuts the list in half.
Ali: OK, I will optimize it today.

سارا: الگوریتم تو کار می‌کند، ولی یک راه‌حل زور خام است. همه‌ی آیتم‌ها را یکی‌یکی بررسی می‌کند.
علی: این مشکلی دارد؟ فهرست مرتب است.
سارا: پس جست‌وجوی دودویی را به کار ببر. خیلی بهینه‌تر است: حدود ۲۰ قدم برای یک میلیون آیتم.
علی: آن را با بازگشت بنویسم؟
سارا: می‌توانی، ولی خواندن یک حلقه‌ی ساده آسان‌تر است. هر دور، فهرست را نصف می‌کند.
علی: باشد، امروز بهینه‌اش می‌کنم.