به نام خدا
چند وقت پیش یه سوالی حل کردم که فوق العاده اذیتم کرد.
داستان این بود که 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
در مجموع به ذهنم رسید که یه لیستی از کارهایی تهیه کنم که می تونه سرعت به برنامه رو بدون تغییر در الگوریتم بهبود ببخشه:
(این بخش به روز می شود.)
1.عین آدم کد زدن :
اصلی تعریف دقیقی نداره ولی همه می فهمن چیه.
2.استفاده از زبان برنامه نویسی سریع تر :
زبان های برنامه نویسی رو میشه به طور کلی به دو سطح بالا و پاینن طبقه بندی کرد. بالا بودن سطح یک زبان به معنی استفاده و درک راحت تر اون برای افراد مبتدی یا در مبنای دقیق تر به معنای دور بودن از زبان ماشینه. زبان ها ی سطح بالا سرعت کمتری دارن چون خودشون خیلی از کارها رو انجام میدن که طبیعتن خیلی هاش واسه برنامه نویس به در نخوره.
در کل برای یه برنامه نویس، زبان برنامه نویسی سطح پایین با توجه به سرعت بیشترش، محبوب تره. هرچند دیگه نباید بیش از حد پایین بیایم:)
3.void کردن خروجی توابع و استفاده از متغیر های گلوبال:
می تونین به جای اینکه یه چیزی رو مثل متغیر x رو return کنید، یه متغیر گلوبال تعریف کنین و تمام تغییر هایی رو که می خواستین رو x انجام بدین، رو همین متغیر گلوبال انجام بدین و بعد از صدا زدن تابع هم از همین متغیر گلوبال در نقش خروجی تابع استفاده کنید. اینجوری کلن return حذف میشه و اگه تابع قرار باشه زیاد صدا زده بشه، احتمالن سرعت برنامه هم بهبود پیدا می کنه.
کلن هر کاری کنین که تعداد return ها کم شه خوبه احتمالن(با تأکید مؤکد روی مورد اول).
از این جا به بعد میریم سر سی پلاس پلاس و چند تا راه کار که واسه بهبود سرعت برنامه مفیده رو می گیم.
4.استفاده از دستورات کتابخانه cstdio به جای iostream :
تو سی پلاس پلاس دو کتابخونه داریم که هر کدوم به طور جداگانه دستورات ورودی و خروجی دارن: cstdio و iostream
دستورات اصلی ورودی و خروجی گرتن هرکدوم به شرح زیره:
iostream: cin, cout, cerr
cstdio: scanf, priintf
در مورد جزئیات اینا حرفی نمی زنم. فقط در همین حد که cerr دستوری که خروجی رو توی صفحه کامپیوترتون نشون میده ولی معمولن رو جاج ها تأثیری نداره و چیزی چاپ نمی کنه(هر چند زمان خودش رو می بره). اگه جایی نباید ازش استفاده می کردین احتمالن بهتون میگن.
دستورات ورودی و خروجیه کتابخونه ی cstdio سریع تره. شاید به خاطر این که از C اومدن و سطح C نسبت به C++ پایین تره.
5.استفاده از دستور ;(ios_base::sync_with_stdio(0 :
برنامه یه فضایی رو واسه ذخیره ورودی ها انتخاب می کنه. هر کدوم از این کتاب خونه ها واسه خودشون یه iterator دارن که نشون میده ورودی بعدی که گرفته میشه باید کجا ذخیره بشه. در حالت کلی و بدون زدن دستور بالا هر بار که iterator یکی از کتابخونه ها به خاطر استفاده ازش جلو میره، iterator اون یکی هم جلو میره. چون این ذو تا به صورت پیش فرض با هم sync شدن.
با زدن این دستور این sync از بین میره و خب برنامه به صورت خوبی برای ورودی های بزرگ سریع میشه ولی بعد از زدن این دستور، باید فقط از یکی از این دو کتابخونه استفاده کرد.
6.استفاده از دو دستور (cin.tie(0);cout.tie(0 :
اگه دارین از دستورات کتابخونه iostream استفاده می کنین، این رو بزنین، چیز خوبیه(شنیده شده سرعت دستورات تا 1/3 با زدن دو مورد 3 و 4 کاهش پیدا میکنه. البته فقط شنیده شده;))
اگه کسی راه کار دیگه ای به ذهنش رسید، بگه که اصافه کنم.
هرچند بعد از این موارد لازم به ذکره که این ها فقط می تونن زتا حدی سرعت رو بهبود ببخشن و شاید با حذف یه lg n از اردر برنامتون، سرعت برنامه به حدی تغییر کنه که این چند تا مورد اصلن به حساب نیان (البتبه به جز مورد اول).
باشه که مفید باشه:)
یاعلی
همینجوری
