آموزش الگوریتم‌هامبانی برنامه‌نویسی · پیچیدگی زمانی، مرتب‌سازی، جست‌وجو و ۲ مورد دیگر

۰۱ بهای نصف کردن، و کسی که می‌پردازدش

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

مرتب‌سازی پایتون بر پایه مقایسه است، و مرتب‌سازی مقایسه‌ای از n log n بهتر نمی‌شود. این یک اثبات است نه یک محدودیت مهندسی: هر مقایسه به یک پرسش بله یا خیر جواب می‌دهد، و تعداد ترتیب‌های ممکن از چیزی که آن تعداد جواب می‌تواند از هم جدا کند بیشتر است. پس sorted() همان n log n است و تا وقتی دارد مقایسه می‌کند هیچ کتابخانه‌ای بهتر از این به شما نمی‌دهد.

دو خاصیت آن هر روز به کار می‌آید. sorted(radifha, key=lambda r: r[1]) با یک کلید محاسبه‌شده مرتب می‌کند، پس مرتب کردن پرونده‌ها بر اساس مبلغ خسارت اصلاً تابع مقایسه نمی‌خواهد. و sorted() پایدار است، پس کلیدهای مساوی ترتیب ورودشان را نگه می‌دارند: بلبرینگ و تسمه و لنت و لامپ که بر اساس تعداد مرتب شوند، تسمه و لامپ اول می‌آیند و به همان ترتیبی که در فهرست بودند. پایداری همان چیزی است که مرتب کردن دوباره را ممکن می‌کند، و مرتب کردن بر اساس دو ستون در عمل یعنی دو بار مرتب کردن. این‌ها موضوع همان چند روش، و اینکه چرا زبان شما یکی را از قبل انتخاب کرده و خطی، دودویی، و آنچه مرتب بودن می‌خرد هستند.

۰۲ حرکت نام‌دار دوم: دوباره حساب نکردن

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

• GHESTHA = (50_000, 100_000, 200_000, 500_000)
• def rah(baghi, k=0):
• if baghi == 0: return 1
• if baghi < 0 or k == len(GHESTHA): return 0
• return rah(baghi - GHESTHA[k], k) + rah(baghi, k + 1)

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

جواب ۲٬۶۹۱ است و همین‌طور که نوشته شد ۱۹۱٬۷۴۱ بار خودش را صدا می‌زند، چون همان باقی‌مانده‌ها را بارها از نو حساب می‌کند. دو سطر درستش می‌کند: import functools و بعد @functools.lru_cache(maxsize=None) بالای همان تعریف. lru_cache تابع را بر اساس آرگومان‌هایش به خاطر می‌سپارد، و چون این تابع دو آرگومان دارد، کلیدِ حافظه همان جفت است. همان شمارش با حافظه ۵۱۷ فراخوانی شد و جواب مو نزد. این معامله، یعنی به خاطر سپردن به‌جای حساب کردن دوباره، تمام به یاد سپردن زیرمسئله‌ها به‌جای محاسبه دوباره است، و شکل صدا زدنی که زیرش نشسته تابعی که خودش را صدا می‌زند، و جای حالت پایه است.

۰۳ ابزار، و سالی که این حرف درست است

هر دو حرکت بالا در کتابخانه استاندارد پایتون هستند و سال‌هاست که هستند، و همین نکته است: bisect جای نوشتن دستی حلقه نصف کردن را گرفت، که شرط مرزی‌اش در تلاش اول بیشتر وقت‌ها غلط درمی‌آید، و functools.lru_cache جای نگه داشتن یک دیکشنری از جواب‌های حساب‌شده و یادمان ماندن که اول آن را نگاه کنیم. هیچ‌کدام خرجی ندارند، هیچ‌کدام نصب نمی‌خواهند، و از ایران هم برای هیچ‌کدام لازم نیست به مخزنی وصل شوید.

آنکه تاریخ خودش را روی خودش دارد sorted() است. دادن تابع مقایسه دوآرگومانی به آن در پایتون 3.0 برداشته شد، یعنی هفده سال پیش، و هر جوابی در اینترنت که به sorted یک مقایسه‌گر دوآرگومانی می‌دهد از آن قدیمی‌تر است و اجرا نمی‌شود. جایگزینش همان تابع کلید بالاست، و functools.cmp_to_key برای آن مقایسه نادری هست که واقعاً نمی‌شود به‌شکل کلید نوشتش.

۰۴ اشتباه: مرتب کردن داخل حلقه

ارزان‌ترین راه از بین بردن تمام سود بالا این است که مرتب‌سازی داخل همان حلقه‌ای بیفتد که جست‌وجو می‌کند. دویست جست‌وجو روی دویست هزار شماره، وقتی یک بار مرتب شود و بعد دویست بار bisect بخورد، ۰٫۰۳ ثانیه طول می‌کشد. همان دویست جست‌وجو وقتی هر بار اول sorted() صدا زده شود ۷ ثانیه طول می‌کشد، یعنی حدود دویست برابر، و هیچ سطری هم اشتباه نیست. این را در سوم سپتامبر ۲۰۲۶ اندازه گرفتم.

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

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

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