efficiency - بازدهی زمان اجرا در برنامه های نوشته شده به زبان جاوا + یک مثال

[jlover]

با سلام

به این مسئله توجه کنید :
http://acm.timus.ru/problem.aspx?space=1&num=1706
و اما تشریح مسئله ( ممکنه درکش براتون وقتگیر باشه ! ) :
من سعی می کنم با همون مثال توضیح بدم. رشته ی abaccc رو در نظر بگیرید به همراه کلید 3
برای رسیدن به خروجی مورد انتظار ، باید ، برای این رشته - ی 6 حرفی - ، به تعداد حروفش ، - 6 تا - زیررشته ، به طول کلید - 3 - در نظر گرفت
( وقتی هم دیگه به پایان رشته رسیدیم دور میزنه )
در اینصورت داریم :

aba
bac
acc
ccc
cca
cac

خاست مسئله اینه که برای هر کدوم از این زیر رشته ها تعداد زیر رشته های ناتهی و متمایز محاسبه بشه

نکته : با کمی دقت متوجه میشیم که حداکثر این تعداد برابر با
k(k+1)/2 خاهد بود که در مورد رشته ی مفروض میشه :
3(3+1)/2 یعنی 6 ( مثل رشته ی bac )
و همینطور کمترین تعداد برابر خاهد بود با k (کلید) که در اینجا میشه 3 ( مثل رشته ی ccc )
من در نسخه ی سوم برنامه م از این نکته استفاده کردم !

یک نکته ی کلیدی هم که من - در هر سه نسخه ی برنامه م _ در الگوریتم بررسی هر کدوم از این رشته ها در متد compute برای بدست آوردن عدد مربوط به هر زیررشته بکار گرفتم اینه که هر رشته ای رو برای مثال بصورت زیر منشعب میکنیم تا بشه یک پیمایش منطقی روش اعمال :

aba = { a, ab, aba ; b, ba ; a
که خب زیررشته ی a تکراریست.

اگر به صفحه ی زیر مراجعه کنید و توضیحات این حقیر رو ملاحظه بفرمایید میبینید که مسئله ی زمان اجرا (time limit) بدجوری منو تو گل فرو برده :عصبانی++:
http://acm.timus.ru/forum/thread.aspx?space=1&num=1706&id=23887&upd=634057230736032500
شاید ایراد از الگوریتم و استراتژی حل مسئله باشه که من بکار بردم، اما با نگاهی به صفحه ی زیر
http://acm.timus.ru/help.aspx?topic=java
می بینیم که حتی نحوه ی دریافت ورودی و پرداخت خروجی ،هم ،در محاسبه ی طول زمان اجرا تاثیر گذاره و به همین خاطر این موضوع رو در این تالار هم ( بعلاوه ی تالار الگوریتم ) عنوان کردم.
برای مثال زمانیکه از StringBuffer استفاده میکردم (بجای String ) تا شاید زمان اجرا رو بهبود بدم (که تاثیری نداشت:ناراحت: ) مشاهده میشد که میزان خافظه ی مصرفی بالاتر رفته که بدیهی هم هست یا مثلن در برنامه ی اول از متدهای موجود در کلاس ArrayList بغایت برای ساده سازی حل مسئله استفاده شده ، ولی حدس زدم شاید زمانگیر بودن برنامه به این علته و نسخه های دوم و سوم رو ساختم که حلشون کمی پیچیده تره ، حافظه بهبود بسزایی پیدا میکنه ، اما زمان اجرا ...................................:گریه:

من بسته ی هر سه نسخه رو ضمیمه میکنم ، نسخه ی اول برنامه رو که بخونید استراتژی کار دستتون میاد (مستندات پیاده سازیش رو سعی کردم مفصل باشه :خجالت: )

با تشکر

[javanerd]

اول از همه باید با استفاده از یک پروفایلر ببینید که کدوم بخش از برنامه بیشترین زمان اجرا رو به خودش اختصاص میده. می‌تونید از یکی از برنامه‌هایی که اینجا لیست کرده استفاده کنید. من Profiler4j رو توصیه می‌کنم.
http://java-source.net/open-source/profilers

[jlover]

اول از همه باید با استفاده از یک پروفایلر ببینید که کدوم بخش از برنامه بیشترین زمان اجرا رو به خودش اختصاص میده. می‌تونید از یکی از برنامه‌هایی که اینجا لیست کرده استفاده کنید. من Profiler4j رو توصیه می‌کنم.
http://java-source.net/open-source/profilers
سلام؛
من همون profiler4j رو دانلود کردم، بدقت خودآموزش رو خوندم، با پکیج java.lang.instrumentation هم آشنا شدم ...
اولش پروفایلینگ رو با یه برنامه ی ساده (ویرایشگر متن دارای ر.ک.گ) امتحان کردم و کنسول agent درست کار میکرد ...
بعد برنامه ی مورد نظر رو اجرا کردم،چند بار، دو نسخه ی مختلف (چون متوجه شدم سازنده ش گفته متدهای استاتیک رو پروفایل نمیکنه و نسخه ی اول برنامه م همه ش عناصرش استاتیکه ) و هر بار خطای I/O Error : could not refresh the memoryinfo در کنسول دریافت میکنم،التبته برنامه ی من درست اجرا میشه .

چیکارش باس بکنم؟من اولین بار بود که با مفهوم پروفایلینگ برخورد داشتم !

با تشکر

[javanerd]

شاید ایراد از الگوریتم و استراتژی حل مسئله باشه که من بکار بردم، اما با نگاهی به صفحه ی زیر
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>();

[javanerd]

من یه پست دیگه هم در مورد اون برنامه نوشتم:
http://javanerd.wordpress.com/2010/04/09/scope-of-vaiables/

[jlover]

سلام مجدد
با راهنماییهای دوست عزیزمون [javanerd (http://barnamenevis.org/forum/member.php?find=lastposter&t=213269) من برای اولین بار و بطور جدی، مستندات Collections framework API رو مطالعه کردم و نسخه ی جدیدی* از راه حل این مساله پیاده سازی کردم و از شر Execution Time Limit خلاص شدم.
اما بطوریکه در صفحه ی مربوط به نتایج میبینید :
http://acm.timus.ru/status.aspx?space=1&num=1706&author=91441&count=30
اینبار با تجاوز از حد تعیین شده برای حافظه ی مصرفی روبه رو شدم

برای نسخه ی جدید چند نسخه ی آلترناتیو نوشتم که اساسن شبیه هم هستند و تفاوت عمده شون در استفاده کردن یا استفاده نکردن از نوع StringBuffer برای متغیر substringTemp برای نگهداری هر زیرشته (زیر رشته های محاسبه شده برای هر زیررشته ی مشتق از رشته ی اصلی، در متد encode) می باشد.
تفاوتهای جزیی دیگه مربوط به محل اعلان و نمونه سازی HashSet و StringBuffer بوده که با آزمودن اونها در سیستم متوجه شدم تفاوتی در نتیجه به دست نمیده
و نتیجه ی تفاوت اصلی آلترناتیوها (StringBuffer اری یاخیر) : هر زمان که از StringBuffer استفاده شد، زمان اجرا به کمتر از نیم ثانیه میرسید اما حافظه ی مصرفی چند مگابایتی بالاتر میرفت (زمان و حافظه ی مجاز = 3 ثانیه و 64 مگابایت)
و در صورت استفاده نکردن از StringBuffer زمان اجرا بالاتر از حد مجاز میشه (چنانکه در صفحه ی نتایج میبینید)

و کد کامل جدیدترین نسخه از قرار زیره :



/*
* this class implements the encoding requested in problem #1706
* described in the page : http://acm.timus.ru/problem.aspx?space=1&num=1706
*/
/**
* @author Esmaeil Ashrafi <s.ashrafi@gmail.com>
*/
import java.util.HashSet;
import java.io.*;

public class AdvancedEstierlitzEncryption {

PrintWriter out; // output character stream
/*
* this variable stores the first token of user input (a number) as the
* length of each "n" substrings derive from input string
* (where "n" is the length of second input
* (a string) user type in standard input)
*/
int key;

public static void main(String[] args) throws IOException {

new AdvancedEstierlitzEncryption().run();
}

/**
* gets input values, stores them, call the splitter method, "splitIntoSubstrings"
* and finally flushes the output character stream,"out", to ensure printing the result
* @throws IOException
*/
void run() throws IOException {

String input; // the string intended to encrypt
StreamTokenizer in;// to read and tokenize the "key" and the "input" string
in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
key = (int) in.nval;
in.nextToken();
input = in.sval;
out = new PrintWriter(new OutputStreamWriter(System.out));
SplitintoSubstrings(input);
out.flush();
}//end of run

/**
* gets the entire string and splits it to substrings in length
* of "key" (by the manner described in problem) and sends each
* substring to method "encode".
* There will be substrings (and consequent calls to method
* "encode") as many as the length
* of parameter str (the user input)
* @param str - the string to split
*/
void splitIntoSubstrings(String str) {
int m, // for loop iterator
strLen = str.length();
for (m = 0; m <= strLen - key; m++) {
encode(str.substring(m, m + key));
}
for (m = m; m < strLen; m++) {
encode(
str.substring(m).concat(str.substring(0, key - (strLen - m))));
}
}//end of SplitintoSubstrings

/**
* calculates the number of different non-empty substrings
* could be obtained from the parameter "str" and prints the
* count to the character output stream "out"
* @param str - the string to encode
*/
void encode(String str) {
/*
* Since in this advanced version i use different data structure from
* previous version(s), that is "HashSet<String>" instead of "ArrayList<String>",
* I think call to method "size" and method "contain" is useless, because
* every invocation of method "add" implicitly checks the collection (HashSet)
* and adds the substring if and only if the set already does'nt contain
* such substring.
* Thus every trueness of If condition means the presence of a different
* non-empty substring as we need to count.
* So i simply use the counter declared below in If body
*/
int subsCount = 0;
StringBuffer substringTemp = new StringBuffer(1);
HashSet<String> subs = new HashSet<String>((key * (key + 1)) / 2);
for (int i = 0; i < key; i++) {
for (int j = i + 1; j <= key; j++) {
if (subs.add(substringTemp.replace(
0, substringTemp.length(), str.substring(i, j)).toString())) {
++subsCount;
}
}
}

out.print(subsCount);
out.print(" ");

}//end of encode
}//end of class

// again MEMORY limit !


به نظر من، سرریز حافظه ی مجاز، مربوط به زمانی میشه که یک زیررشته ی طولانی (مثلن به طول میزان بیشینه که بر طبق صورت مسئله 1000 هست) و در عین حال با حروف کاملن متمایز (بدون حتی یک حرف تکراری و البته این پیچیده ترین حالت ممکنه و من فکر میکنم اول باید بزرگترین سنگ رو خورد کرد!) وارد متد encode میشه و با توجه به توضیحی که در پست اول راجع به منطق اعمال شده در پیمایش دادم، زمانیکه قراره زیر رشته ی آخر (اینجا به طول هزار) از آرگومان ورودی ساخته بشه و در StringBuffer ما به نام tempSubstring ذخیره بشه، در عین حال در مجموعه ی HashSet ما به نام subs تعداد ((1000*1000+1)/2)-1)شَیء String رو در خودش نگه داری میکنه و تازه برای اندازه گیری تعداد بایت های اشغال شده توسط این مجموعه احتیاج به یه محاسبه ی هندسی هست که واقعن از توان من خارجه و فقط میتونم حدس بزنم که چندین برابر تعداد خونه های این set خاهد بود. خب میتونید تصور کنید که این روش حل چطور حافظه رو میبلعه !

برای حل این معضل آخرین تلاش من (با توجه به دانسته های کنونیم) رو در نسخه ی بعدی (که بعد از ارسال این پست مشغول پیاده سازیش میشم و خیلی خیلی امیدوارم علاوه بر کاهش هزینه ی حافظه به کاهش هزینه ی زمان اجرا هم بیانجامه) ارایه داده خاهد شد.

در آخر عرض کنم علاوه بر اینکه پذیرای نظر دوستان هستم، یادآوری این نکته رو خالی از لطف نمیبینم که امیدوارم این بحث رو محدود به مسئله ی بنده در نظر نگیرید، چرا که تا همینجا من فکر میکنم ما حداقل به اهمیت انتخاب ساختمان داده ی مناسب از کتابخانه ی استاندارد جاوا برای بیشینه کردن بازدهی برنامه هامون پی بردیم و اگر این مسئله حل شد سعی میکنم با کمک شما نکات دیگه ای رو هم آشکار کنیم

با تشکر
----------------------------------------------------------------------------
* در این نسخه سعی کردم حداکثر تلاشم رو در بکارگیری نامهای مناسب و همچنین ارائه ی مستندات پیاده سازی انجام بدم. از اینرو حتی اگر کسی به لحاظ پیچیدگی پیاده سازی در نسخه های پیشین که ضمیمه شده نمیتونست چندان تمایلی به ملاحظه شون داشته باشه، میتونه با همین نسخه شروع کنه

[jlover]

از چاه به چاله و برعکس :عصبانی++:
تغییرات فقط در متد encode اعمال شدند و مربوط به اساس منطق پیمایش میشه :


void encode(String str) {
/*
* Since in this advanced version i use different data structure from
* previous version(s), that is "HashSet<String>" instead of "ArrayList<String>",
* I think call to method "size" and method "contain" is useless, because
* every invocation of method "add" implicitly checks the collection (HashSet)
* and adds the substring if and only if the set already does'nt contain
* such substring.
* Thus every trueness of If condition means the presence of a different
* non-empty substring as we need to count.
* So i simply increament the counter declared below in If body
*/
int subsCount = 0;
StringBuffer substringTemp = new StringBuffer(1);
for (int k=0; k<key-1; k++){
HashSet<String> subs = new HashSet<String>(key - k);
for ( int i = 0, j=k+1; i < key-k; i++, j++) {
if (subs.add(substringTemp.replace(
0, substringTemp.length(), str.substring(i, j)).toString())) {
++subsCount;
}
}
}
++subsCount; // the whole string itselt is always a legal substring
out.print(subsCount);
out.print(" ");

}//end of encode

چندین بار با تغییرات جزیی (مثلن بکارنگرفتن متغیر subStringTemp : StringBuffer و فرستادن مستقیم str.substring(i, j که فکر میکنم باید هم همینطور باشه و بافر کردنش بی مورده ) امتحان کردم و در همه ی موارد همونطور که انتظار میرفت بهبود چشمگیر میزان حافظه رو شاهد بودم (کمتر از 5 مگابایت) و لی باز هم به سد Time Limit برمیخوردم.

اساس پیمایش هم به این صورت شد که اول همه ی رشته های تک حرفی جدا شده و در صورت تکراری نبودن (با استفاده از متد add موجود در HashSet ) شمارنده افزایش پیدا میکنه، بار بعد دو حرفیها، والی آخر (بنابر اینHashSet اول بیشترین عنصر رو داره و بعد همینطور یکی یکی از تعداد عناصرش (که بعنوان ظرفیت اولیه در متد سازنده ش لحاظ میشه) کم شده و ما شاهد کاهش فوق العاده ی حافظه ی مصرفی خاهیم بود.
در آخر هم دییگه طولانیترین زیررشته که عین خود آرگومان هستش بدون هیچ محاسبه ای به عنوان یک زیررشته ی مجاز (ناتهی و غیرتکراری) در نظر گرفته شده و یک واحد به شمارنده اضافه میشه.

نمیدونم دیگه چیکار میشه کرد...

[javanerd]

خوب این کد داره نزدیک میشه به کدی که آدم می‌تونه پرینت بگیره و بعد از ظهر کنار پنجره بنشینه و چای بنوشه و به جای یک قطعه شعر این کد رو بخونه.

اما من در مورد این کد هم زیاد حرف دارم. از جمله در مورد این قسمت
for (m = m; m < strLen; m++) {

[jlover]

خوب این کد داره نزدیک میشه به کدی که آدم می‌تونه پرینت بگیره و بعد از ظهر کنار پنجره بنشینه و چای بنوشه و به جای یک قطعه شعر این کد رو بخونه.

اما من در مورد این کد هم زیاد حرف دارم. از جمله در مورد این قسمت
for (m = m; m < strLen; m++) {
اینم...چی بگم که فکر نکنید آدم خصیصی هستم :افسرده:
صرفه جویی :افسرده:

البته میشه عبارت m=m رو با عبارت زیر جایگزین کرد و نتیجه یکی خاهد بود، اما فکر نمیکنم منظور شما این باشه که این مورد تاثیری در بازدهی کلی برنامه داشته باشه !


m = strLen-key+1 ;

به هر حال میخاستم تا جاییکه امکان داره از متغیر m استفاده کنم !

[javanerd]

اینم...چی بگم که فکر نکنید آدم خصیصی هستم :افسرده:
صرفه جویی :افسرده:

اگر می‌خواهید صرفه‌ویی کنید در اولین نگاه این یکی راه خیلی بهتریه:


for (; m < strLen; m++)
حداقل اگر روزی کسی کد رو خوند، سرگیجه نمی‌گیره.

[aryazahra]

اول از همه باید با استفاده از یک پروفایلر ببینید که کدوم بخش از برنامه بیشترین زمان اجرا رو به خودش اختصاص میده. می‌تونید از یکی از برنامه‌هایی که اینجا لیست کرده استفاده کنید. من Profiler4j رو توصیه می‌کنم.
http://java-source.net/open-source/profilers



سلام با تشکر از راهنمایی های مفیدتان.من یک برنامه نوشتم که مشکل outofmemory:heapspace داره. می خواستم با یه ابزاری بفهمم کدوم قسمت برنامم داره مشکل ایجاد می کنه. این پروفایلر هایی که شما فرستادید من بلد نیشتم باهاشون کار کنم. لطفا یه پروفیلر یا ابزار ساده به من معرفی کنید.
خیلی ممنون