یادمه یه جایی بحث رو این بود که اگر یک آرایه دو بعدی بزرگ داشته باشیم و فرض کنیم بخوایم و جمع تمام عناصرش رو بدست بیاریم، آیا فرقی میکنه سطر به سطر بریم، ستون به ستون بریم و...؟
شاید از نظر برنامه نویسی و الگوریتم تفاوتی نداشته باشه، اما تو سرعت میتونه تاثیر بذاره (لااقل از نظر تئوری)
ولی این هم به نظر من خیلی تفاوت داره تو نوشتن الگوریتم پردازش آرایه دوبعدی ...
مثلا یکی میاد با recursive مینویسه یکی هم میاد با حلقه ها مینویسه و یکی هم میاد با پردازش موازی مینویسه حالا میشه گفت که پردازش زمانی هر سه روش یکسان هست؟
حالا اگر از بردارها بیتی استفاده شده باشه ویا اصلا از عملگرهای بیتی استفاده نشه بازهم پردازش زمانی نمیتونه فرق داشته باشه!؟
اگر با بازگشت بنویسه باید حواسش به حافظه باشه اگر از حلقه ها استفاده کنه امکان داره از چند حلقه nested استفاده کنه که کارایی میاد پایین و پردازش موازی هم که به cpu خیلی وابسته است و احتمال کوبیدگی(حالتی که چند فرآیند متناوب به یک داده اشتراکی بخواهند دسترسی داشته باشند و کارایی سیستم دچار اختلال میشه.!) تو فرآیندها هم وجود داره!
ولی با هر سه روش میشه انجام داد این که کدومش بهتره برنامه نویس بیشتر تشخیص میده چون میدونه برای چه ماشین هایی داره برنامه مینویسه!
علتشم بحث سخت افزاری هست. درسته ما به حافظه اصلی (Main Memory) دسترسی تصادفی داریم و از این نظر تفاوتی نداره اما خواندن از حافظه اصلی زمان بر هست و برای همین با اولین فراخوانی از یک آدرس در حافظه اصلی بلافاصله تعداد زیادی مقادیر همجوارش هم با هم رو Cache ذخیره میشن و بعد از روی حافظه نهان (Cache) خونده میشه. حافظه نهان هم معمولا دو سطحی است. به هر حال در دسترسی اول سرعت خوبی ندارید و cache miss دارید ولی در دسترسی های بعدی در صورتی که آدرس های همجوار قبلی رو فراخوانی کنید cache hit دارید و مستقیما از حافظه نهان میخونه و دیگه کاری با حافظه اصلی نداره و سرعت به مراتب بالاتر میره. اما اگر آدرس بعدی خیلی دور باشه نسبت به آدرس اول اونوقت اون داده قبلا توی حافظه نهان قرار نگرفته و باید از حافظه اصلی بخونه و هی همین تکرار میشه که سرعت برنامه رو به شدت کاهش میده.
ولی این که مطرح میکنید مدیریتی که خود سیستم عامل داره کنترل اش میکنه!
خلاصه کنم اگر با چنین شرایطی مواجه هستید و از حلقه های زیادی استفاده میکنید بهتره ببینید آیا طبق چیزی که در حافظه ذخیره میشه میخونید یا نه.
من متوجه این حرف شما نمیشم که طبق چیزی که ذخیره میشه میخونید یعنی چی دقیقا! منظور شما این هست که مثلا داریم یک متغیر تعریف میکنیم که تو Stack تعریف شده ولی برای اینکه ازش استفاده کنیم از روی Swap یا همون cache میخونیم مقدار متغیر را
مگر برنامه نویس میتونه در زمان دریافت مقدار بگه الان متغیر کجاست؟؟
مگه کل این فرآیندها از pip های cpu برای اجرای دستورات و همچنین دسترسی به حافظه مستقیم DMA وظایف سطح پایین سیستم عامل هست برنامه نویس میتونه دخالتی داشته باشه؟
مثلا فرض کنید که یک فایل با ورودی 4 میلیارد داده از نوع int دارید حالا می خواهیم ببینیم که کدوم عدد دراین فایل وجود ندارد ترتیب اعداد هم از 1 تا 4،000،000،000. وفقط هم 1 گیگابایت حافظه در دسترس داریم؟
یعنی 32^2 عدد داریم و 1 گیگابایت هم که می شود 8 میلیارد بیت بنابراین میتونیم تمام اعداد را به یک بیت مشخص نگاشت کنیم بدون محدودیت.
حالا منظور این هست که چطور الگوریتمی بنویسیم که سرعت خوبی داشته باشه!
byte[] bitArray = new byte [0xFFFFFFF / 8]; // 268,435,455 / 8
void findNum() throws FileNotFoundException {
Scanner in = new Scanner(new FileReader("file.txt"));
while (in.hasNextInt()){
int n=in.nextInt();
bitArray[n/8] |= 1 << (n%8);
}
int lostInt ;
for (int i=0 ; i < bitArray.length ; i++){
for (int j=0 ; j < 8 ; j++){
if((bitArray[i] & (1 << j)) == 0){ //if first element in the bit vector is zero than this element is a lost number in file
lostInt = i * 8 + j;
return;
}
}
}
}
هدف استفاده از الگوریتم هاست برای پیاده سازی مشکلات دربرنامه نویسی و جستجوی بهترین روش برای سرعت در پردازش هست.
یکم اگر بخواهیم موشکافه تر نگاه کنیم به قضیه الگوریتم نویسی فرض کنید که یه متغیر از نوع int تعریف مکنید ویک مقداری هم بهش تعیین میکنید وبعد یک اشاره گر به همین متغیر int تعریف میکنید خوب همونطور که میدونید مقدار متغیر ما تو stack نگه داشته میشه و اشاره گر مون تو heap ذخیره میشه البته در C++ ,c را عرض میکنم حالا تصور کنید چقدر قدرت و انعطاف می توان داشت در طراحی الگوریتم حالا فرض کنید از اشاره گر نخواهیم استفاده کنیم تو الگوریتم تغییر در سورس کدمون را می تونید تصور کنید!؟
مثلا فرض کنید بخواهید همین کار را تو جاوا انجام بدید خوب تو جاوا که اشاره گرنداریم پس باید از کلاس استاتیک استفاده کنیم که بتونیم با استفاده از اینترفیس ها و الگوی Observer به فیلدهایی که باز هم به صورت استاتیک تعریف میشوند دسترسی داشت چون که برای استفاده از heap باید از استاتیک استفاده کنیم تو جاوا البته منظورم این نیست که کد جاوا بدتر هست یا بهتر است منظور تو کد نویسی یک الگوریتم با توجه به ساختمان طراحی یک محیط برنامه نویسی هست پس باالطبع هرچی بشه با کدنویسی کمتر به هدف الگوریتم نزدیک تر بشیم خیلی هم به بهینه تر نویسی نزدیکتر هستیم. وهمین ظرافت هاست که در برنامه نویسی باعث میشه که یکی مثل Joshua Bloch میاد خیلی از کتابخونه های اندروید را مینویسه یکی هم میاد میره 6 سال رشته x را میخونه مبینه ای بابا کاری نیست که بکنه میگه آهان میرم برنامه نویسی اندروید میکنم پروژه ام میگیره دونه 50،000 تومان...
پاسخ با نقل قول
نوشته شده توسط python2015
