زمان زیاد اجرای برنامه

[amirhossein1376]

سلام آیا راهی وجود داره که زمان اجرای کد من پایین بیاد؟

import java.util.Scanner;

public class CountRepeat {
public static void main(String[] args) {


Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}


doSelectionSort(nums);


String outPut = "";
for (int i = 0; i < nums.length; i++) {
if (!outPut.contains(" " + nums[i] + " ")) {
System.out.println(nums[i] + " " + numOf(nums[i], nums));
outPut += " " + nums[i] + " ";
}


}
}


public static void doSelectionSort(int[] a) {


for (int i = 0; i < a.length - 1; i++) {
int index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[index]) {
index = j;
}
}


int smallerNumber = a[index];
a[index] = a[i];
a[i] = smallerNumber;
}
}


public static int numOf(int number, int[] a) {
int count = 0;


if (a.length > 0) {
int value = a[0];
int a1[] = new int[a.length - 1];


if (number == value)
count = 1;


for (int i = 1; i < a.length; i++) {
a1[i - 1] = a[i];
}


return count + numOf(number, a1);
}


else
return 0;


}


}




این کد یه عدد که تعداد اعضای آرایه هست رو میگیره بعدش اعداد آرایه رو میگیره بعد به ترتیب صعودی اعداد و تعداد تکرارشون رو تو حلقه میده بیرون و میخوانم زمانش پایین بیاد

136497

[Raminab]

سلام بله راهی وجود داره , احتمال زیاد این تمرین دانشگاهی یا کلاسی هست به خاطر همین کد رو نمینویسم . در سطح تمرین دانشگاه شاید ی راه خوب این باشه که الگوریتم sort رو از selection به ی الگوریتم سریع تر ( شاید الگوریتم مرتب سازی سریع خوب باشه )
ی کار دیگه که میتونید بکنید(فک کنم سریع تر از روش شما باشه اساتید نطر بدن ...) اینه که آرایه رو 2 در n در نظر بگیرید یک ردیف رو برای اعداد ورودی و یک ردیف رو برای تکرار های این اعداد در نظر بگیرید.
136500
هر عدد که وارد میشه ی سرچ روی ردیف اعداد بزنید اگه وجود داشت خونه ی تکرار اون عدد رو یکی بیشتر کنید .

[ahmad.mo74]

سلام

چرا از Arrays.sort (http://www.tutorialspoint.com/java/util/arrays_sort_int.htm) استفاده نکردی؟
این متد از DualPivotQuickSort (https://en.wikipedia.org/wiki/Quicksort#Variants) برای primitive type ها استفاده میکنه. برای آبجکت هام از TimSort (https://en.wikipedia.org/wiki/Timsort) استفاده میکنه که هر دوی این الگوریتم ها جز بهترین الگوریتما هستن.

برای پیدا کردن تعداد تکرار هم بهتره که از Map استفاده کنی. به این دلیل که هم اعضای تکراری آرایه واردش نمیشن و هم اینکه پیچیدگی زمانی برای پیدا کردن یه ورودی توی مپ (O(1 هست.
(راهنمایی : اگر از TreeMap استفاده کنی دیگه نیازی به مرتب کردن آرایه هم نیست)

[amirhossein1376]

سلام

چرا از Arrays.sort (http://www.tutorialspoint.com/java/util/arrays_sort_int.htm) استفاده نکردی؟
این متد از DualPivotQuickSort (https://en.wikipedia.org/wiki/Quicksort#Variants) برای primitive type ها استفاده میکنه. برای آبجکت هام از TimSort (https://en.wikipedia.org/wiki/Timsort) استفاده میکنه که هر دوی این الگوریتم ها جز بهترین الگوریتما هستن.

برای پیدا کردن تعداد تکرار هم بهتره که از Map استفاده کنی. به این دلیل که هم اعضای تکراری آرایه واردش نمیشن و هم اینکه پیچیدگی زمانی برای پیدا کردن یه ورودی توی مپ (O(1 هست.
(راهنمایی : اگر از TreeMap استفاده کنی دیگه نیازی به مرتب کردن آرایه هم نیست)

تمرین دانشگاهه! استادمونم میگه تا جایی که میشه از متدای آماده استفاده نکنین

[-سیّد-]

ضمن تشکر از دوستان، این رو هم اضافه کنم که می‌تونید از Multiset موجود در کتابخانه‌ی guava استفاده کنید. کار این کلاس اینه که یه Set هست، با این تفاوت که تعداد المان‌هایی که واردش می‌کنید رو می‌شمره. یعنی اگه یه المان تکراری واردش کنید، تعدادش رو زیاد می‌کنه. در نهایت هم می‌تونید ازش فهرست تمام Entry ها به همراه تعداد تکرارشون رو بپرسید. اینجا بیشتر توضیح دادم:
http://blog.yooz.ir/?q=node/28

اما اگه می‌خواین همونطور که گفتید از کتابخونه‌های موجود هر چه کمتر استفاده کنید (البته خیلی کار جالبی نیست! برای تمرین نوشتن الگوریتم sort خوبه ها! ولی این که دیگه از هیچ کتابخونه‌ای استفاده نکنید خیلی جالب نیست! اتفاقاً هنر یه برنامه‌نویس (هر زبونی، نه فقط جاوا) اینه که کتابخونه‌های موجود در اون زبان رو هم به خوبی بشناسه و سر جاش ازشون استفاده کنه)، می‌تونید همونطور که گفتن از یک Map استفاده کنید از Integer به Integer، و هر دفعه ازش get کنید، اگه null برگردوند یعنی اولین بار هست با اون عدد برخورد می‌کنید، در نتیجه توش یه put با مقدار صفر می‌زنید. اما اگه بهتون یه مقدار برگردوند، بعلاوه‌ی یک می‌کنید و توش put می‌کنید (این تقریباً همون کاریه که Multiset انجام می‌ده).
اگه باز هم می‌خواین سرعت اجرای کد بره بالاتر، می‌تونید بقیه‌ی نکاتی که توی اون پست بلاگ گفتم رو هم اعمال کنید.

[MortezaZandi]

سلام
اگه نمی توانید از توابع استاندارد استفاده کنید، از نکات زیر برای بهبود کارائی کد خود استفاده نمایید:


کمتر در بدنه حلقه طول آرایه ها را بازیابی کنید، هربار که طول آرایه ای را بدست می آورید سربار اضافی بر روی پردازنده بوجود خواهید آورد، بهتر است قبل از ورود به حلقه طول آرایه را در یک متغییر عددی ذخیره کرده و در بدنه حلقه از آن متغیر استفاده نمایید.
در حلقه ها ی با تعداد دور بالا سعی کنید از عملیات جمع زدن رشته ها خود داری نماید و این کار را به انتهای کد موکول کنید، زیرا هر بار که رشته ای را در حافظه جمع می زنید یا تغییر می دهید رشته قبلی در حافظه به صورت زباله رها شده و رشته جدیدی ساخته خواهد شد،که در زبان های جدید به صورت خودکار عملیات جمع آوری زباله را فراخوانی میکند، در صورت امکان از قابلیت هایی مانند StringBuilder در ویژوال استادیو برای جمع زدن رشته ها استفاده نمایید، سرعت انجام کار 10 برابر سریع تر از کار با رشته ها به صورت مستقیم است.
استفاده از حلقه ای بزرگ بهتر از فراخوانی های مکرر به توابع دیگر است ، در صورت امکان سعی کنید از فراخوانی توابع دیگر در بدنه حلقه ها خود داری نمایید، زیرا با هربار فراخوانی تمام بدنه تابع به همراه متغیرهای آن در حافظه موقت ذخیره خواهند شد که مجدد باید بازیابی شوند.
عملیات نمایش خروجی را اکیدا در بدنه حلقه ها انجام ندهید تا از سرعت پردازنده بهره ببرید.
بدلیل اینکه آرایه ها به همان ترتیب سطری که دارند در حافظه ذخیره می شوند ، سعی کنید عملیات پیمایش آرایه های دوبعدی را به صورت سطری انجام دهید تا ستونی.
برای استفاده از فقط یک تابع از فراخوانی کتابخانه ای بزرگ خودداری نمایید و تا جایی که ممکن است این توابع را خودتان پیاده سازی نمایید.
هنگام آزمایش کد هایتان مطمئن باشید رایانه خود را بر روی حالت ذخیره نیرو تنظیم نکرده باشید، زیرا در این حالت پردازنده کمتر از توان واقعی خود بازدهی دارد.
با جستجوی How to improve performance in ... نکات بسیاری برای بهبود سرعت کدها خواهید یافت و همچنین روش های غلط کدنویسی را شناسایی خواهید کرد.

[-سیّد-]

ممنون از نکاتی که گفتید. ولی من با همه‌ی این نکاتی که گفتید موافق نیستم. مثلاً:


۳. استفاده از حلقه ای بزرگ بهتر از فراخوانی های مکرر به توابع دیگر است ، در صورت امکان سعی کنید از فراخوانی توابع دیگر در بدنه حلقه ها خود داری نمایید، زیرا با هربار فراخوانی تمام بدنه تابع به همراه متغیرهای آن در حافظه موقت ذخیره خواهند شد که مجدد باید بازیابی شوند.

این که گفتید در حالتی صادقه که JIT در کار نباشه، که الان سالهاست که دارن روی JIT کار می‌کنن و JIT انقدر هوشمند شده که این چیزهای ساده رو بتونه تشخیص بده. اگه کد ++C بود شاید، ولی توی جاوا این چیزا تقریباً هیچ تأثیری نداره.


۶. برای استفاده از فقط یک تابع از فراخوانی کتابخانه ای بزرگ خودداری نمایید و تا جایی که ممکن است این توابع را خودتان پیاده سازی نمایید.


چرا؟ کی گفته اگه پروژه‌ی من برای استفاده از مثلاً Multiset به guava وابسته بشه، سرعت اجرای کد پایین میاد؟ بین این دو تا هیچ ارتباطی نیست. تنها چیزی که وابستگی به یه کتابخونه اضافه می‌کنه، اینه که حجم خروجی نهایی شما زیاد می‌شه. یعنی اگه کل پروژه رو بکنید یه Jar (که در این حالت بهش می‌گن Fat Jar)، حجمش بالاتر می‌ره و در نتیجه فقط موقع شروع برنامه یه مقدار بیشتر طول می‌کشه. البته وابستگی به کتابخونه‌های دیگه مسائل دیگه‌ای هم مثل conflict توی نسخه‌ی کتابخونه‌های مورد استفاده ایجاد می‌کنه، ولی ربطی به سرعت اجرای برنامه نداره.

یه بخشایی از حرفاتون هم اثرش انقدر توی سرعت پایینه که اصلاً به چشم نمیاد. مثلاً:


۱. کمتر در بدنه حلقه طول آرایه ها را بازیابی کنید، هربار که طول آرایه ای را بدست می آورید سربار اضافی بر روی پردازنده بوجود خواهید آورد، بهتر است قبل از ورود به حلقه طول آرایه را در یک متغییر عددی ذخیره کرده و در بدنه حلقه از آن متغیر استفاده نمایید.


این کار اثرش توی سرعت زیر ۱ درصد هست (خیلی کمتر از این حرفاس، حتی شاید زیر یک صدم درصد). چون اصل کاری که برنامه‌ی شما می‌کنه عملیات محاسباتی هست که سنگینه، دسترسی به یه متغیر که طول یه آرایه رو به شما برگردونه در مقابل عملیات محاسباتی‌ای که برای مثلاً مرتب‌سازی انجام می‌دید، هیچی نیست.

بعضی از نکاتی که گفتید هم شدیداً درست هستند و مؤثر. مثل:

۲. در حلقه ها ی با تعداد دور بالا سعی کنید از عملیات جمع زدن رشته ها خود داری نماید و این کار را به انتهای کد موکول کنید، زیرا هر بار که رشته ای را در حافظه جمع می زنید یا تغییر می دهید رشته قبلی در حافظه به صورت زباله رها شده و رشته جدیدی ساخته خواهد شد،که در زبان های جدید به صورت خودکار عملیات جمع آوری زباله را فراخوانی میکند، در صورت امکان از قابلیت هایی مانند StringBuilder در ویژوال استادیو برای جمع زدن رشته ها استفاده نمایید، سرعت انجام کار 10 برابر سریع تر از کار با رشته ها به صورت مستقیم است.


یا:


۴. عملیات نمایش خروجی را اکیدا در بدنه حلقه ها انجام ندهید تا از سرعت پردازنده بهره ببرید.

[MortezaZandi]

سلام دوستان عزیز ، چون هدف انتشار دانش هست این پست رو جواب دادم.
با رعایت نکاتی ظریفی مانند آنچه گفته شد بار پردازشی بر روی پردازنده در پروژه ... از صددرصد به 5 درصد رسید، که البته تعداد مختصری را بیان کردم. (بنحصر به زبانی نیست)

یکی از اون نکات:

فرق این دو کد روو بسنجید:(شبه کد)
1-

for 1 -1,000,000
{
try
{
throw new exception
}
catch()
{}
}



2-

for 1 - 1,000,000
{
try
{}
catch()
{}
}


این یعنی پرتاب استثنا به تعداد بالا در کدی که خطا داره هزینه سنگینی برای برنامه نویس در پی خواهد داشت.

برای درک این موضوع قبل و بعد از انجام کد از زمان سنج با دقت میلی ثانیه یا کمتر استفاده کنید.

برخی نکات برای صرفه جویی در مصرف حافظه و برخی برای کاهش بار پردازشی هستند.

پیروز باشید

[-سیّد-]

خوب همونطور که بالاتر گفتم، بعضی از نکاتی که گفتید دقیقاً وابسته به زبان هست. مثلاً در زبان جاوا به علت وجود موجودی مانند JIT بعضی مسائل که توی زبان‌هایی مثل ++C مطرح هستند، اینجا مطرح نیستند. البته کامپایلرهای ++C و بقیه‌ی زبان‌ها هم موقع کامپایل در حد امکان بهینه‌سازی‌هایی انجام می‌دن، ولی اون خیلی از بهینه‌سازی زمان اجرا که JIT انجام می‌ده محدودتره. اینجا بیشتر در این مورد بحث کردم:
http://barnamenevis.org/showthread.php?489039-JVM-%D9%88-%D8%AA%D9%81%D8%A7%D9%88%D8%AA-%D9%88%D8%B8%DB%8C%D9%81%D9%87-%D8%A2%D9%86-%D8%A8%D8%A7-%DA%A9%D8%A7%D9%85%D9%BE%D8%A7%DB%8C%D9%84%D8%B1&p=2198993&viewfull=1#post2198993
و همچنین پست‌های دیگه توی همون thread، مثل پست آخر:
http://barnamenevis.org/showthread.php?489039-JVM-%D9%88-%D8%AA%D9%81%D8%A7%D9%88%D8%AA-%D9%88%D8%B8%DB%8C%D9%81%D9%87-%D8%A2%D9%86-%D8%A8%D8%A7-%DA%A9%D8%A7%D9%85%D9%BE%D8%A7%DB%8C%D9%84%D8%B1&p=2211781&viewfull=1#post2211781

مثالی هم که زدید، تا حدی درسته، ولی کاملاً درست نیست. موقع نتیجه‌گیری‌های اینچنینی باید خیلی مواظب باشید که اشتباه نکنید. باید تستتون دقیق باشه. اینجا در موردش بیشتر صحبت کردم:
http://blog.yooz.ir/?q=node/29

[MortezaZandi]

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

just intime debugger در پلت فرم های جدید وجود دارد و منظور بنده این بود که هر کدام از اون نکات سرباری برای حافظه یا پردازنده هستند(ناچیز یا زیاد)
حتی اگر 1 میلی ثانیه هم باشد در 10 میلیون اجرا قابل توجه است ، به هر حال تا وقتی روش بهتری وجود دارد نباید به خاطر اثرات ریز عواقب کدنویسی غیر بهینه را نادیده بگیریم.