با درود
دوستان این حلقه اولی فور اضافه نیست؟ یک هزینه رو دستمون بزاره که بعد بخواهیم موازی اش کنیم؟
اصلا کار به موازی هم نداشته باشیم. حلقه فور اول اضافه نیست؟ بعد هم اندیس ش با حلقه فور دوم یکسان هست. یعنی با هم حرکت میکنن؟
![[تصویر: 404322_rg2ahvoztgo1.jpg]](https://img.manesht.ir/404322_rg2ahvoztgo1.jpg)
![[تصویر: 404322_f0w9ssl5xucj.jpg]](https://img.manesht.ir/404322_f0w9ssl5xucj.jpg)
این یک شبه کد هست.حلقه ی اولی کلا بیرونه(حلقه ی خارجی هست)
یک بار حلقه ی خارجی اجرا میشه بعدش n بار حلقه های داخلی تا زمانی که شرطشون برقرار نباشه و خارج بشن. بعدش دوباره حلقه خارجی یک دونه دیگه اجرا میشه و به همین ترتیب . . .
(۲۹ اردیبهشت ۱۳۹۵ ۱۲:۰۰ ب.ظ)samanbeigmiri نوشته شده توسط: این یک شبه کد هست.حلقه ی اولی کلا بیرونه(حلقه ی خارجی هست)
یک بار حلقه ی خارجی اجرا میشه بعدش n بار حلقه های داخلی تا زمانی که شرطشون برقرار نباشه و خارج بشن. بعدش دوباره حلقه خارجی یک دونه دیگه اجرا میشه و به همین ترتیب . . .
خوب داداش حلقه خط ۳ به چه درد میخوره؟ چه بخواهیم موازی اش کنیم. اصلا میشه نزاشتنش. کار خاصی نمیشه.
بعد جدا از این موضوع ، چون حلقه ۳ و ۵ ، با هم i هاش داره کار میکنه، پس هزینه اضافه نیست؟ یک هزینه هست درسته؟ چون با هم افزاسش پیدا میکنن.
نه، درسته در i ها مشترکن، اما اگر بلاک بندی(با آکولاد) کنید ، میفهمید که از هم جدا هستن . . . به ازای هر بار اجرای حلقه بیرونی حلقه های داخلی به اندازه ای که براشون تعیین شده اجرا میشن.
الگوریتم اینا یادم نیست ولی اگر اشتباه نکنم:
۱. حلقه اول برای مقدار دهی اولیه بوده و مورد نیاز هست.
۲. هر دو پارالل با هم اجرا نمیشن، بلکه حلقه های داخلش(iteration ها) با هم run میشن.
۳. عکسارو از کتاب Introduction to Algorithms گذاشتی(که بهتر بود ذکر میشد) در چاپ سوم ویرایش سوم کتاب این شبه کد کمی تصحیح شده:
این صفحه جدید هست(به خاطر محدودیت حجم کیفیت عکسو کم کردم)
[attachment=19956]
احتمالا نسخه دانلودی/خریداری شده کتاب چاپ قدیمی بوده، بقیه ۱۵۰ تصحیح اشتباه تو لینک زیر هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اکثر کتابای مهم Errata Page دارند و اصلاحات کتاب توش ذکر میشه.
ممنون از پاسخ شما
الان خط ۳ و ۵ هر دو متغیر i دارند . . وقتی یک افزایش پیدا کنه یعنی i بالایی هم افزاش داشته چون حوزه ها یکی هست
شما می فرمائید خط ۳ و ۵ جدا از هم هستند؟ اگر اینطور هست پس این الگوریتم در حال ترتیبی باید از مرحله تتا n به توان ۳ باشه
اما الان n به توان ۲ هست . پس میشه گفت ۳ و ۵ با هم افزایش دارند
بابت تصحیح الگوریتم هم ممنون. والا کتاب من ویراسش سوم هست. و یرایش جدید تر نیست. جسارتا شما این ویرایش که این عکس رو ازش گذاشتید میشه در اخیتار ما بزارید؟
(۲۹ اردیبهشت ۱۳۹۵ ۰۶:۱۶ ب.ظ)samanbeigmiri نوشته شده توسط: نه، درسته در i ها مشترکن، اما اگر بلاک بندی(با آکولاد) کنید ، میفهمید که از هم جدا هستن . . . به ازای هر بار اجرای حلقه بیرونی حلقه های داخلی به اندازه ای که براشون تعیین شده اجرا میشن.
اگر بلاک بندی بشه. بله و حق با شماست
پس در حالت ترتیبی کتاب چرا گفته از تتا n به توان ۲ هست؟ پس باید تتا n به توان ۳ بشه. چون ۳ تا حلقه n تایی داریم. در حالت تریبی
(۲۹ اردیبهشت ۱۳۹۵ ۰۷:۱۶ ب.ظ)irpersian20 نوشته شده توسط: ممنون از پاسخ شمادرسته خب، شما یه کاری کن، الگوریتم رو کاملا تریس کن تا دستت بیاد چی به چیه از مرتبه n به توان ۲ چرا که حلقه ها دو تاش تو در تو هست یعنی در حالت کلی یه همچین چیزی میشه : (برای خط ۳ و (۵ و ۶) ) خط سه میشه n و خط ۵ و ۶ چون تو در تو هست و در یک بلاکه{به هم وابسته هستند} در هم ضرب میشن که میشه n به توان ۲
الان خط ۳ و ۵ هر دو متغیر i دارند . . وقتی یک افزایش پیدا کنه یعنی i بالایی هم افزاش داشته چون حوزه ها یکی هست
شما می فرمائید خط ۳ و ۵ جدا از هم هستند؟ اگر اینطور هست پس این الگوریتم در حال ترتیبی باید از مرحله تتا n به توان ۳ باشه
اما الان n به توان ۲ هست . پس میشه گفت ۳ و ۵ با هم افزایش دارند
بابت تصحیح الگوریتم هم ممنون. والا کتاب من ویراسش سوم هست. و یرایش جدید تر نیست. جسارتا شما این ویرایش که این عکس رو ازش گذاشتید میشه در اخیتار ما بزارید؟
(۲۹ اردیبهشت ۱۳۹۵ ۰۶:۱۶ ب.ظ)samanbeigmiri نوشته شده توسط: نه، درسته در i ها مشترکن، اما اگر بلاک بندی(با آکولاد) کنید ، میفهمید که از هم جدا هستن . . . به ازای هر بار اجرای حلقه بیرونی حلقه های داخلی به اندازه ای که براشون تعیین شده اجرا میشن.
اگر بلاک بندی بشه. بله و حق با شماست
پس در حالت ترتیبی کتاب چرا گفته از تتا n به توان ۲ هست؟ پس باید تتا n به توان ۳ بشه. چون ۳ تا حلقه n تایی داریم. در حالت تریبی
[tex]n n^2[/tex]
وقتی بلاک بندی کنی اجرای هر خط در یک بلاک با اجرای خطوط دیگه در سایر بلاک ها جمع میشه.
. اگرم داری از CLRS میخونی پیشنهادم اینه که اگر اولین بارتونه این کارو نکنید. یا حداقل یه کتاب رو باهاش موازی بخونید مثلا مدرسان کتابش خوبه یا مثلا نیپولیتان.
(۲۹ اردیبهشت ۱۳۹۵ ۰۷:۱۶ ب.ظ)irpersian20 نوشته شده توسط: ممنون از پاسخ شما
الان خط ۳ و ۵ هر دو متغیر i دارند . . وقتی یک افزایش پیدا کنه یعنی i بالایی هم افزاش داشته چون حوزه ها یکی هست
شما می فرمائید خط ۳ و ۵ جدا از هم هستند؟ اگر اینطور هست پس این الگوریتم در حال ترتیبی باید از مرحله تتا n به توان ۳ باشه
اما الان n به توان ۲ هست . پس میشه گفت ۳ و ۵ با هم افزایش دارند
بابت تصحیح الگوریتم هم ممنون. والا کتاب من ویراسش سوم هست. و یرایش جدید تر نیست. جسارتا شما این ویرایش که این عکس رو ازش گذاشتید میشه در اخیتار ما بزارید؟
(۲۹ اردیبهشت ۱۳۹۵ ۰۶:۱۶ ب.ظ)samanbeigmiri نوشته شده توسط: نه، درسته در i ها مشترکن، اما اگر بلاک بندی(با آکولاد) کنید ، میفهمید که از هم جدا هستن . . . به ازای هر بار اجرای حلقه بیرونی حلقه های داخلی به اندازه ای که براشون تعیین شده اجرا میشن.
اگر بلاک بندی بشه. بله و حق با شماست
پس در حالت ترتیبی کتاب چرا گفته از تتا n به توان ۲ هست؟ پس باید تتا n به توان ۳ بشه. چون ۳ تا حلقه n تایی داریم. در حالت تریبی
راستش متوجه نمیشم منظورت رو.
چطور میشه n به توان ۳ ؟ ۳ حلقه تو در تو نیست که. حلقه اول n بار اجرا و سپس حلقه دوم n به توان ۲ اجرا میشه. n رو حساب نمی کنیم چون order پایین هست و در نتیجه میشه n به توان دو.
البته من الگوریتم اینا حالیم نیست از یکی دیگه بپرس، احتمالا اشتباه هم باشه نظرم. همینطوری دارم میگم :دی
در مورد کتاب:
کتاب من و تو هر دو ویرایش سوم هستند.(ویرایش آخر همین سه هست)
فقط کتاب تو ویرایش سوم چاپ پایین هست کتاب من ویرایش سوم چاپ آخر.
متاسفانه نسخه مورد استفاده من آنلاین هست و pdf نیست وگرنه مشکلی نبود.
عالی بود ممنون