سریع ترین روش برای پرکردن آرایه با صفر

Question

سلام.

فرض کنید یک آریه به صورت زیر دارم.

__int64 arr[128]; 
//some process
//fill it by zero

حالا قصد دارم با صفر پرش کنم شما چه روشی پیشنهاد میدید؟

Answer 1

سلام. سه روش واسه این کار سراغ دارم. یکی کد زیره که در همون تعریف آرایه مقدار صفر رو به آرایه میدید و سپس آرایه رو با اون مقدار صفر پر میکنه

#include <iostream>
#include <ctime>
using namespace std;
int main()
{
	clock_t time;
	time = clock();
	_int64 arr[100] = {0};
	time = clock() - time;
	cout << ((float)time) / CLOCKS_PER_SEC << " seconds" << endl;
	cin.get();
}

وقتی که برنامه بالا رو اجرا کنید خروجی به شما صفر ثانیه می ده

در مورد محاسبه زمان اجرا برنامه این لینکو ببین

روش دوم هم استفاده ار تابع fill_n هستش که در زیر استفاده شده.پارامتر اول

این تابع نام آرایه، دومی اندازه آرایه و سومی هم مقدار پیش فرضی که میخواین با اون آرایه پر بشه

#include <iostream>
#include <ctime>
using namespace std;
int main()
{
	clock_t time;
	time = clock();
	_int64 arr[100] = { 0 };
	fill_n(arr, 100, 0);
	time = clock() - time;
	std::cout << ((float)time) / CLOCKS_PER_SEC << " seconds" << std::endl;
	std::cin.get();
}

که خروجی این روش هم صفر ثانیه هست.

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

توی این لینک نوشته احتمالا این روش سریع ترین روش باشه چونکه به صورت مستقیم به زبان اسمبلی نوشته شده و از این بابت بهینه شده است اما وقتی که این روش رو

هم مثل کدهای بالا اجرا می شه خروجی صفر ثانیه رو می ده

#include <iostream>
#include <ctime>
using namespace std;
int main()
{
	clock_t time;
	time = clock();
	_int64 arr[100];
	memset(arr, 0, sizeof(arr));
	time = clock() - time;
	cout << ((float)time) / CLOCKS_PER_SEC << " seconds" << endl;
	cin.get();
}

با توجه به خروجی های به دست آمده نمیشه گفت کدوم روش سریع تره. 

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

که اندازه آرایه مثلا 100 باشه یا 10000!

اما فرض کن شما می خوای مقادیر 100 خانه آرایه رو چاپ کنی که واسه این کار یک حلقه فور به شکل زیر توی کدت قرار میدی

for (int i = 0; i < 100; i++)
	{
		cout << arr[i] << "\t";
	}

اما وقتی که برنامه رو اجرا کنی می بینی یک مدت زمانی طول کشید و در خروجی مثلا می نویسه 0.089 ثانیه و اگر بار دیگه برنامه اجرا کنی می نویسه 0.03 ثانیه و ...

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

کلا بین دو روش بالا که برای پر کردن آرایه ذکر شد هیچ فرقی از لحاظ زمانی وجود نداره حتی اگه اندازه آرای رو مقداری بیش از 100 قرار بدی 

Comments

مطمئناً اين تست برای 100 خونه آرايه يا چند صد تا هيچ فرقی نميکنه بايد مقدار ارايه رو به چندين هزار تغيير بديد و برنامه رو تو حالت ريليس تست کنيد

---

این زمانی که گرفتید درست نیست
چون شما وقتی که آرایه میسازید و ازش استفاده نمی کنید کامپایلر اون آرایه رو کلا حذف می کنه و اصلا بهش مقدار نمیده پس کدتون حتی اگر آرایه 10000 عنصری هم بسازید باز زمان صفر هست .
بعد این که  _int64 arr[100] = {0 با memset انجام میشه و هیچ تفاوت خاصی با memset نداره.
fill_n هم با for معمولی تفاوتی نداره هر 2 تا از loop استفاده می کنن .
درباره این که معمولا بصورت دستی با اسمبلی پیاده سازی میشه من جایی همچین چیزی ندیدم . این پیاده سازی memset  کامپایلر gccهست https://github.com/gcc-mirror/gcc/blob/3ba965c0a3571219c638da1ba3ce64ed6623556e/libgcc/memset.c
همین طور که مشخصه چیز خاصی هم نداره .
 اگر alignment دیتا رعایت شده باشه و cpu هم  SSE رو پشتیبانی کنه میشه از چیزی که هست سریع تر هم نوشت (البته شاید خود کامپایلر هم بتونه کد SSE رو جاهایی که بشه تولید کنه)