خواندن ورودی و چاپ خروجی در مسابقات برنامه نویسی
دیروز بود که یک سوال ACM (مسابقه برنامه نویسی) دیدم که از اینجا می توانید سوال را ببینید. سوال خیلی آسان به نظر می آمد و شروع به حل کردنش کردم ولی هر چه تلاش می کردم سیستم داوری سایت می گفت زمانی که برنامه شما برای حل این سوال می گیرد از زمان تعیین شده برای حل این سوال بیشتر است (time limit exceeded) .
سوال هم به صورت کلی این است که یک نفر می خواهد امتحان بدهد و امتحانش شامل n سوال است که هر سوال امتیاز مشخصی دارد و هر سوال به یک واحد زمانی برای جواب دادن نیاز دارد و آزمون دهنده هم k واحد زمانی در اختیار دارد حالا بگویید حداکثر آزمون دهنده چه نمره ای را می تواند بگیرد.
همین طور که واضح است سوال بسیار آسان است و با سورت کردن سوال ها بر اساس امتیاز سوال ها و بعد انتخاب k سوال با بیشترین امتیاز می توان به جواب رسید.
ولی بار اول که کدم را برای سایت فرستادم سیستم داوری سایت پیام زمان شما از حد تعیین شده تجاوز کرده است(time limit exceeded) را نشان داد! معمولا این اتفاق زمانی می افتد که الگوریتم و ساختمان داده های مناسبی استفاده نشده باشد. به همین خاطر فکر کردم الگوریتمی که استفاده کرده ام مناسب نیست الگوریتم را بهتر کردم ولی باز نشد! تقریبا هر چه الگوریتم سورت و ساختمان داده بلد بودم تست کردم! از مرج سورت ، کوییک سورت ، رندومایز کوییک سورت بگیرید تا counting sort – درخت redblack tree و … ! ولی هیچ کدام جواب گو نبود! در آخر چون مسیله محدوده ی اعداد را مشخص کرده بوده از Directed map استفاده کردم که آن هم جواب نداد! در کل هر چه تست کردم نشد !
یک چند ساعتی بیخیال سوال شدم بعد یادم آمد که به چنین چیزی البته نه به این شدت سال قبل در codeforces.com برخورده ام! مشکل از cin و cout بود!
وقتی مقدار ورودی و یا خروجی بسیار است cin و cout بسیار کند تر از scanf و prinft زبان سی عمل می کنند! و دلیلش هم این است که cin , cout نیاز دارند که خودشان را با کتابخانه های سی در سطوح پایین تر sync نگه دارند که برای مطالعه ی بیشتر می توانید به این لینک مراجعه کنید:
http://www.quora.com/Is-cin-cout-slower-than-scanf-printf/answer/Aditya-Vishwakarma
بعد از اینکه آن ها را جایگزین کردم مشکل حل شد برای اینکه تفاوت را ببینیم دو برنامه ی متفاوت می نویسیم و هر دو را چک می کنیم.
قبل از آن با استفاده از bash یک فایل شامل چهل میلیون عدد رندوم تولید می کنیم که دو برنامه را با آن تست کنیم:
1 2 3 4 5 6 | #!/bin/bash for((i = 1; i <= 40000000; i++)); do echo $RANDOM >> random.txt done |
اکنون یک فایل شامل ۴۰ میلیون عدد داریم، حالا این فایل را به دو برنامه ی متفاوت زیر می دهیم که هر دو ۴۰ میلیون عدد را از ورودی می خوانند ولی یکی با cin این کار را می کند و دیگر با scanf :
برنامه ی خواندن ۴۰ میلیون عدد با scanf :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> #include <stdio.h> using namespace std; int main(int argc, char *argv[]) { long long int count = 0; int temp; while( 1 == scanf("%d",&temp)) { count++; } printf("%d",count); return 0; } |
برنامه ی خواندن ۴۰ میلیون عدد با cin :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> using namespace std; int main(int argc, char *argv[]) { long long int count = 0; int temp; while(cin >> temp) { count++; } cout << count << endl; return 0; } |
حالا زمانی را که هر دو برنامه برای گرفتن ۴۰ میلیون عدد از ورودی صرف می کنند را اندازه می گیریم.
همان طور که در تصویر زیر می بینید زمان اجرای برنامه scanf برابر ۴.۸۲ ثانیه است و زمان اجرای برنامه ی cin برابر ۱۲.۶۵ ثانیه است!
البته ممکن است با تکرار همین آزمایش این نتیجه را نگیرید! زیرا ممکن است optimization کامپایلرتان فعال باشد در این حالت ممکن است خود کامپایلر عمل سینک کردن cin و cout را غیرفعال کرده باشد یا کار دیگری کرده باشد! در مسابقه های برنامه نویسی کد بدون هیچ optimization کامپایل می شود.
برای آشنایی با همه ی نکات ورودی و خروجی در مسابقات برنامه نویسی می توانید به اسلاید زیر توجه کنید:
سلام
با اسمبلی هم تست و مقایسه کنید
سلام و خسته نباشید و ممنون بابت پست های خوبتون
یه اشکال
اسم سایت codeforces.com نه .org
البته شایدم من اشتباه میکنم
ممنون بابت وقتی که میذارین
:))
ممنون بابت اشاره شما به این اشکال! تصحیح شد!
سلام آقای دلیرانی
واقعا از پستتون لذت بردم ممنونم واقعا…
لطفا از این دست پستها بیشتر قرار بدین…
بعضی از وقت ها هم همون اول کار باید چک کنیم ببینیم اصلا به صرفه هست یک دور مرتب سازی انجام بشه یا نه!!! مثلا اگر تعداد داده های ورودی خیلی خیلی زیاد باشد بعد فقط دنبال ۱ ماکزیمم باشیم اصلا مقرون به صرفه نیست مرتب سازی کنیم. تقریبا اکثر الگوریتم های خوب مرتب سازی پیچیدگی زمانی nlogn دارن، در مقابل اگر تعداد مانکسی هم که می‌خوایم بدست بیاریم k در نظر بگیریم به ازاء هر k باید کل n ورودی پیمایش بشن که پیچیدگی کلی برابر kn میشه. حالا اگر k کمتر از logn بشه همون خطی ماکزیمم ها رو پیدا کنیم خیلی بیشتر به سوده.
برای مرتب سازی هم پیشنهاد میکنم از تیم‌سورت استفاده کنین. تقریبا میشه ادعا کرد بهترین کارایی رو داره.
در ادامه: زبان هایی در مسابقات استفاده می‌شن فقط به سی یا سی پلاس پلاس محدود نیستن. جاوا که تقریبا در همه ی مسابقات استفاده می‌شن، پایتون هم که یواش یواش داره باب میشه(در مسابقه ی code jam که میشه از پاسکال و سی شارپ و آر و متلب و … استفاده کرد.)، به عنوان پیشنهاد برای مقاله ی جدا جالب میشه از زبان های ممختلف بنچ‌مارک بگیرین و مقایسه کنین و پیشنهاد بدین که برای چه مسابقاتی چه زبانی بهتره ولی حتما این رو هم در نطر بگیرین که علاوه بر ارسال برنامه‌ای که جواب درست در زمان و با حافظه ی مورد نظر بدست بیاره زمان تبدیل تفکر به کد هم در نظر بگیرین.
سلام تشکر از کامنت خوبتون – حتما یک پست در مورد پیشنهادتون خواهم گذاشت. ولی توی مسابقات رسمی ACM ICPC فقط از سی پلاس پلاس – سی و جاوا می شه استفاده کرد.
ولی توی مسابقات دیگر چیزهای دیگر هم مجاز است. اون ایده ی بنچ مارک هم حتما دنبال می کنم – ولی توی مسابقات بیشتر از سی پلاس پلاس استفاده می شه چون هم سریع هست و هم کتابخانه های خوبی دارد از جمله اس تی ال .