به نام خدا
چند وقت پیش یه سوالی حل کردم که فوق العاده اذیتم کرد.
داستان این بود که n تو سوال تا 100000 بود و الگوریتم من هم n.sqrt n. محدودیت زمانی برنامه هم 1 ثانیه بود. اگه تا حالا یه کم با جاج کدفرسس ور رفته باشین دیتتون اومده که سرعتش بسیار بالاست. خب من هم کد سوالو زدم و سابمیت کردم و (بعد از این که یه بار به خاطر باگ رو تست 4 رانگ خورد) رو تست 13 تایم لیمیت شدم.
خب یه کم با کد ور رفتم و تا تست 38 رفتم و دوباره تایم خوردم.
باز چند بار با کد ور رفتم و این دفعه تا تست 46 رفت.
تا این جای کار من 8 بار سابمیت کرده بودم و همش غلط بود.
بارها و بارها کد رو از لحاظ تایم بهبود دادم. سعی کردم توابع رو بهینه تر کنم. از جمله کار هایی که کردم:
1.ورودی یکی از توابعی رو که باید جند بار، هر بار به ازای یک عدد مثل x، صدا زده می شد رو تغییر دادم. این صورت که تابع یک بازه می گرفت و اینجوری کمتر صدا زده می شد.
2.تمام توابع رو به صورت void در آوردم و با تغییر متغیر های گلوبال کاری که می خواستم رو می کردم.
3.توابع کد رو از حالت بازگشتی در آوردم و با حلقه کارم رو راه انداختم.
هیچ کدوم از این کار ها باعث نشد برنامه در عمل بهتر کار کنه و برنامه همچنان از تست 46 جلو تر نمی رفت. حتی تمام توابع رو حذف کردم ولی خب برنامه بدتر شد و بهتر نشد.
این رو باید بگم که کلن مسئله ی بهبود سرعت برنامه با حذف توابع درست نیست ولی خب گفتم شاید جواب بده که نداد. حتی در افسانه های قدیم آمده است که با تقسیم برنامه به چند تابع سرعت افزایش می یابد. در کل فکر نمی کنم خیلی فرقی کنه که شما برنامه رو با چند تابع بنویسید یا بدون تابع.
خب یه نگاهی به کد کسایی که قبلن سوال رو زده بودن کردم و... :|
سوالی که محدودیت زمانی 1 ثانیه داره رو یکی با تایم 1278ms زده و اکسپت شده!!!!!!!!!!(حدسم اینه که محدودیت زمانی سوال رو برای یه مدت کوتاه افزایش دادن یا جاج قاطی کرده)
اگه یه نگاهی به اینجا بزنید می بینید که علاوه بر اون دو تا کد با تایم عجیب و غریب، تعداد زیادی کد با 998ms هم بود. نکته ی مثبت این بود که فهیمدم بقیه هم مشکل من رو دارن و یه کم خیالم راحت تر شد.
مورد عجیب دیگه هم 3 نفری بودن کخ سوال رو زیر 150ms زده بودن.
خلاصه این که تفاوت آشکاری بین نحوه ی زدن کد سوال وجود داشت و آدم رو به شدت مشتاق به مقایسه ی کد ها می کرد ولی من خویشتن داری کردم و تمام تلاشم رو به کار بستم که کد بقیه رو نبینم.(طبیعیه چرا)
تا این که یه چیزی به ذهنم رسید و در کمال تعجب، برنامه رو دز اولین تلاش با زمان اجرای 342ms (!) اکسپت کرد. و اما اون ایده نه چندان خلاقانه استفاد از دستورات ورودی و خروجی C خدابیامرز و کتابخانه ی cstdio بود.
من تا قبل از زدن این سوال تقریبن مطمئن بودم که دستورات iostream با زدن خط زیر بسیار نزدیگ به سرعت دستورات کتابخانه cstdio کار می کنن ولی در عمل تفاوت آشکاری وجود داشت.
;(ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0
در مجموع به ذهنم رسید که یه لیستی از کارهایی تهیه کنم که می تونه سرعت به برنامه رو بدون تغییر در الگوریتم بهبود ببخشه:
