نوشته شده توسط
jlover
شاید ایراد از الگوریتم و استراتژی حل مسئله باشه که من بکار بردم، اما با نگاهی به صفحه ی زیر
http://acm.timus.ru/help.aspx?topic=java
می بینیم که حتی نحوه ی دریافت ورودی و پرداخت خروجی ،هم ،در محاسبه ی طول زمان اجرا تاثیر گذاره و به همین خاطر این موضوع رو در این تالار هم ( بعلاوه ی تالار الگوریتم ) عنوان کردم.
برای مثال زمانیکه از StringBuffer استفاده میکردم (بجای String ) تا شاید زمان اجرا رو بهبود بدم (که تاثیری نداشت
) مشاهده میشد که میزان خافظه ی مصرفی بالاتر رفته که بدیهی هم هست یا مثلن در برنامه ی اول از متدهای موجود در کلاس ArrayList بغایت برای ساده سازی حل مسئله استفاده شده ، ولی حدس زدم شاید زمانگیر بودن برنامه به این علته و نسخه های دوم و سوم رو ساختم که حلشون کمی پیچیده تره ، حافظه بهبود بسزایی پیدا میکنه ، اما زمان اجرا ...................................
با تشکر
من برنامهی شما را با یک ورودی به طول ۱۷۰۰ و کلید k=500 اجرا کردم. پس از دو دقیقه اولین خروجی روی صفحه ظاهر شد. پس از حدود ۵ دقیقه کل برنامه را بستم.
بعد فقط یک خط از برنامهی شما رو تغییر دادم (تاکید میکنم فقط یک خط) و کارآیی برنامه به طور چشمگیری بهبود پیدا کرد. در هر ثانیه دو خروجی روی صفحه ظاهر میشد. (نزدیک به ۱۲۰ برابر بهبود!!!)
حتما میپرسید مشکل کجا بود؟
در برنامهی شمااز یک ساختمان داده به اسم sub استفاده شده است که از عملیات زیر را روی یک سری داده انجام میدهد.
contain
add
clear
از بین این عملیاتها دوتای اول در یک حلقهی for تو در تو قرار دارند و مهمترین سهم را در زمان اجرای برنامه دارند.
شما از یک ArrayList برای پیادهسازی این ساختمان داده استفاده کرده بودید. از آنجا که ArrayList با استفاده از آرایهها پیادهسازی میشود زمان اجرای هر یک از عملیات بالا به صورت زیر است:
contain = o(n)
add = o(n)
clear = o(n)
من به جای ArrayList از یک HashSet استفاده کردم. از آنجا که HashSet با استفاده از HashTable پیادهسازی میشود، در آن زمان اجرای عملیات به صورت زیر است.
contain = o(1)
add = o(1)
clear = o(n)
یعنی تنها تغییری که من در کد دادم جایگزین کردن سطر
private static ArrayList<String> sub = new ArrayList<String>();
با سطر زیر بود:
private static HashSet<String> sub = new HashSet<String>();