Payamvdn/NorthPersian_fa_wiki huggingface dataset:
Best Nested Loop join cost: 13.17 Sort Merge cost: 6.08 Hash join cost: 4.57 Best:: JoinMethod: Hash مشاهده می شود که کمترین زمان اجرا متعلق به روش hash join است، پس از این روش برای اجرای نقشه پرسش استفاده می شود. ملاحظات عمومی. همیشه یک معامله بین زمان صرف شده برای بدست آوردن بهترین نقشه اجرای پرسش و کیفیت نقشه انتخاب شده وجود دارد. بهینه ساز مستقلاً نمی تواند بهترین انتخاب را داشته باشد. سیستم های مدیریت پایگاه داده متفاوت راه های متفاوتی برای ایجاد تعادل بین دو فاکتور ذکر شده دارند. بهینه سازهای هزینه محور میزان استفاده پرسش را از منابع سیستم ارزیابی می کنند و آن را به عنوان مبنایی برای انتخاب یک نقشه اجرا در نظر می گیرند. این مدل از بهینه سازها به هر نقشه ممکن برای اجرای پرسش یک هزینه تخمین می زنند و سپس کمترین آنها را انتخاب می کنند. هزینه هایی که برای تخمین زدن زمان اجرای یک پرسش در نظر گرفته می شوند عبارتند از تعداد عملیات های I/O مورد نیاز، میزان دستور مورد نیاز به زبان ماشین برای اجرای پرسش، میزان حافظه بافر مورد نیاز از دیسک، زمان مورد نیاز دیسک و عامل های دیگر که توسط فرهنگ داده مشخصی می شود. دو نو
ع بهینه سازی وجود دارد. بهینه ساز منطقی -که زنجیره ای از جبر رابطه ای برای اجرای پرسش تولید می کند-و بهینه سازی فیزیکی برای مشخص کردن مجری هر عملیات استفاده می شود. پیاده سازی. تعداد زیادی از بهینه سازهای پرسش، نقشه های پرسش را به شکل درختی نشان می دهند که از تعدادی گره تشکیل شده است. هر گره این درخت یک عملیات مورد نیاز برای اجرای نقشه پرسش را نشان می دهد. این گره ها به شکل یک درخت مرتب شده اند که برای به دست آوردن نتیجه نهایی باید گره های درخت را به ترتیب از پایین به بالا اجرا کنیم و نتیجه هر گره را به عنوان ورودی گره پدر در نظر بگیریم. تعداد بچه های هر گره می تواند صفر یا بیشتر باشد به عنوان مثال یک گره که حاوی دستور join است دو بچه دارد که شامل عملوندهای ورودی آن است ولی یک دستور sort صرفاً یک ورودی (ورودی که می خواهیم مرتب شود) دارد. برگ های درخت گره هایی هستند که نتایج را با پویش دیسک انجام می دهند. برای مثال این گره ها می توانند اینکار را با index scan یا sequential scan انجام دهند. یک نمونه :جبر رابطه ای عبارت formula_12 است. تخمین هزینه. یکی از دشوارترین مسائل در بهینه سازی پرسش، تخمین دقیق هزینه برای
نقشه های پرسش است. بهینه سازها هزینه نقشه های پرسش را با استفاده از مدل های ریاضی که شدیداً به اندازه یا تعداد زوج ها (سطرها) که در یال های درخت اجرای پرسش قرار دارد وابسته است تخمین می زنند. تخمین اندازه بستگی به تخمین (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(join) می شود) در گزاره های پرسش دارد. سیستم های پایگاه های داده قدیمی تعداد منتخب ها را از طریق آمارهای جزئی توزیع مقادیر در هر ستون مثل نمودارهای histogram تخمین می زنند. این روش برای تخمین منتخب های یک گزاره خوب کار می کند. اگرچه تعداد زیادی از پرسش ها چندین شرط را تواماً با هم دارند به طور مثال: select student.ID ,student.name ,student.last_name from student where student.name= 'ali' and student.major = "cs" بهینه سازی هزینه محور. یک بهینه ساز پرسش تنها به درخت پرسش وابسته نیست، بهینه ساز پرسش هزینه اجرای یک پرسش را با رویکردها و الگوریتم های مختلف تخمین زده و مقایسه می کند و در نهایت رویکردی را انتخاب می کند که کمترین هزینه را داشته باشد. برای اینکه این دیدگاه بتواند درست کار کند باید بتوان تخمین دقیقی از هزینه اجرای پر
سش بدست آورد تا در نهایت رویکردهای مختلف اجرای پرسش عادلانه و واقع گرایانه مقایسه شوند. همچین باید این نکته را در نظر گرفت بهینه ساز باید تعداد محدودی رویکرد اجرای پرسش را بررسی کند در واقع اگر قرار باشد تمام حالت های اجرا را در نظر بگیرد زمان زیادی از دست می رود. بنابر این دیدگاه بهینه سازی هزینه محور مناسب پرسش های کامپایل شده است. تصمیم گیری در فرایند بهینه سازی پرسش ساده و چالش های زیاده دارد. فرایند کلی بهینه سازی هزینه محور را می توان به شکل زیر خلاصه کرد: اجزای هزینه در بهینه سازی پرسش. هزینه انتقال (خواندن یا نوشتن) بلاک های اطلاعات بین دیسک حافظه ثانویه و بافرهای حافظه اصلی. این هزینه به اسم هزینه ورودی و خروجی دیسک ((disk I/O (input/output) هم شناخته می شود. هزینه جستجوی یک فایل در دیسک به نوع دسترسی به آن فایل بستگی دارد به طور مثال آیا فایل مرتب شده است؟ در هم سازی صورت گرفته است؟ اندیس گذاری انجام شده است؟ و… عوامل مختلف دیگر. هزینه ذخیره سازی هر فایل میانی که با اجرای پرسش تولید شده است برروی دیسک را گویند. این هزینه شامل هزینه انجام عملیات روی رکوردهای حافظه اصلی در طول اجرای پرسش است. این هزین
ه شامل عملیاتی است که در داخل حافظه انجام می شود مثل:جستجو، مرتب سازی، ادغام چند رکورد برای یک عملیات join. این هزینه به اسم CPU cost(واحد پردازش مرکزی) هم شناخته می شود. این هزینه مربوط به تعداد بافر مورد نیاز از حافظه در طول اجرای پرسش می باشد. هزینه انتقال پرسش و نتایج آن از محل پایگاه داده به محل یا ترمینالی که پرسش از آنجا فرستاد شده است. در :پایگاه داده توزیع شده، این هزینه شامل هزینه انتقال جدول ها و نتایج آن بین کامپیوترهای مختلف در طول ارزیابی پرسش است.
خلیل بیگ خاصمحمدف () سردمدار و دیپلمات آذربایجانی بود. وی زمامداری وزارت های دادگستری و داخله (کشور) در جمهوری دمکراتیک آذربایجان را در سال ۱۹۱۸ بر عهده داشت. زندگی نامه. خلیل بیگ خاصمحمدف در سال ۱۸۷۳، در خانواده ای وکیل در شهر گنجه به دنیا آمد. وی دانش آموخته رشته حقوق از دانشگاه دولتی مسکو در سال ۱۸۹۵ بود. خلیل بیگ تأثیرات زیادی در رابطه با شکل گیری جهان بینی خود از «اسمائیل بیگ گاسپیرانلی» گرفت. شروع فعالیت سیاسی خلیل بیگ خاصمحمدف به دوران دانشجویی اش برمی گردد؛ زمانی که وی عضو «سازمان هم میهنان مسلمان قفقاز» بود. او سپس به عنوان وکیل مدافع در دادگاههای منطقه ای کراسنودار و گنجه کار کرد. کارنامه سیاسی. خلیل بیگ خاصمحمدف در پاییز سال ۱۹۰۵، همراه با برادرش «علی اکبر» در تأسیس سازمان «دفاعی» حضور پیدا کردن؛ سازمانی سیاسی که در گنجه فعال بود. این گروه که شامل روشنفکرانی نظیر نصیب بیگ یوسف بیگلی، «اسماعیل زیادخانف» و احمدبیگ آقایف بود، با هدف مقابله با فعالیت های فدراسیون انقلابی ارمنی پایه گذاری شده بود. خاصمحمدف نماینده دوره اول و دوم دومای روسیه بود. در نوامبر ۱۹۱۱، وی به همراه ۵ نماینده آذربایجانی دیگر در س
خنرانی کم سابقه ای در دومای روسیه، سیاست تبعیضآمیزی را که، آذربایجانیان و سایر مردمان مسلمان قفقاز را با تحمیل پرداخت مالیات از گذراندن خدمت سربازی در نیروهای مسلح این امپراتوری منع می کرد، به باد انتقاد شدید گرفت. او به عنوان عضو حزب مساوات، فعالانه در جنبش ملی آذربایجان برای تأسیس جمهوری خودمختار در داخل مرزهای امپراتوری روسیه مشارکت داشت. خلیل بیگ خاصمحمدف در تأسیس جمهوری دمکراتیک آذربایجان به سال ۱۹۱۸ نقش چشمگیری ایفا نمود. او نماینده شورای ملی و از امضاکنندگان اعلامیهٔ استقلال جمهوری دمکراتیک آذربایجان در ۲۸ ماه مه سال ۱۹۱۸ در شهر تفلیس بود. در دوره جمهوری دمکراتیک آذربایجان، خواصمحمدف به ترتیب سکانداری چند وزارت را در ۴ کابینه دولت از مجموع ۵ کابینه بر عهده داشت. او در ۲۸ ماه مه سال ۱۹۱۸، به عنوان وزیر دادگستری منصوب شده و تا ۱۷ ژوئن همان سال در این سمت باقی ماند. از ۲۶ دسامبر ۱۹۱۸ تا ۱۶ ژوئن ۱۹۱۹ سکان هدایت وزارت داخله در دست او بود. این سیاستمدار آذربایجانی در ۲۴ دسامبر ۱۹۱۹ مجدداً به زمامداری وزارت دادگستری رسید، که تا ۱ آوریل ۱۹۲۰، یعنی پایان هیئت دولت پنجم عهده دار آن شد. وی در دوران ریاست خود بر چ
ند وزارتخانه مختلف، همکاری قوی ای بین وزارت های دفاع، امنیت ملی و کشور نسبت به تهدیدهای خارجی علیه حاکمیت ملی و دولت داری ایجاد کرد. در اویل ماه آوریل سال ۱۹۲۹، خواصمحمدف به عنوان سفیر جمهوری دمکراتیک آذربایجان در ترکیه تعیین شد؛ ولی از آنجا که همزمان با ورود او به استانبول، دولت متبوعش به دست بلشویکها سقوط کرد، تا آخر عمرش در این کشور پنادنده شد و در سال ۱۹۴۵ درگذشت.
روش تنظیم برنده یا برنده تنظیم شده الگوریتمی است برای تقسیم formula_1 کالا بین دو گروه به منصفانه ترین شکل ممکن. این روش توسط (به انگلیسی: Steven Brams) و (به انگلیسی: Alan D. Taylor) طراحی شده است. این الگوریتم formula_1 کالا را به گونه ای بین دو گروه تقسیم می کند که: با گذشت بیش از نیم قرن از تولد نظریه بازی ها به عنوان یک رشته دانشگاهی، همچنان بسیاری از مذاکره کنندگان و واسطه های با تجربه بدون استفاده از نظریهٔ بازی ها و موضوعات مربوط به آن به کار خود ادامه می دهند. در دهه های گذشته امیدها افزایش یافته است که روش های ریاضی برای تقسیم منصفانه بتواند این فاصله را کم کند. از این روش می توان برای حل و فصل اختلاف های بین المللی، فسخ مشارکت و همچنین در زمینه طلاق استفاده کرد. توصیف الگوریتم. هدف، تقسیم مجموعه ای از اشیا، اجناس، ابزار و هر چیز مورد اختلاف بین دو نفر به منصفانه ترین شکل ممکن است. حل یک مثال. فرض کنیم علی و رضا می خواهند مجموعه ای از دارایی ها را با استفاده از این روش بین خود تقسیم کنند. این دارایی ها شامل خانه، قایق، کلبه کوهستانی و آپارتمان ساحلی است. فرض کنیم هر کدام صد امتیاز را مطابق جدول زیر
بین چهار مورد ذکر شده تقسیم کرده باشند: در مرحله اول هر یک از دارایی ها به کسی تعلق می گیرد که مقدار ارزش بیشتری برای آن تعیین کرده باشد. پس در مرحله اول داریم: همان طور که در شکل بالا می بینید، جمع امتیازها برابر نیست. چون این مقدار برای علی بیشتر از رضا است پس لازم است از دارایی فعلی علی کسر و به دارایی رضا اضافه کنیم. برای این که تصمیم بگیریم کدام شی را منتقل کنیم، نسبت امتیاز علی به امتیاز رضا را برای «خانه» و «کلبه» که فعلاً در جمع دارایی های علی است، به دست می آوریم: این نسبت، میزان اهمیت شی برای افراد نسبت به یکدیگر را اندازه گیری می کند. همان طور که می بینید این عدد برای «خانه» به نسبت «کلبه» عدد کوچکتری است؛ به این معنا که «خانه» نسبت به «کلبه» برای علی ارزش کمتری دارد برای همین ابتدا خانه را از علی گرفته به رضا می دهیم: با این کار این بار جمع امتیاز رضا بیشتر از علی می شود پس باید «خانه» را به علی بازگردانیم و این بار کسری از «خانه» را از علی به رضا منتقل کنیم به طوریکه جمع امتیاز آنان پس از این انتقال برابر شود. چون مقدار امتیازها قرار است برابر شود، معادله زیر برقرار خواهد بود: formula_3 با انتقال
formula_4 از سهم «خانه» به رضا، مجموع امتیاز هر دو طرف برابر formula_5 خواهد شد و کار تقسیم به پایان می رسد. با این روش هر دو به میزان برابری از رضایتمندی رسیده اند. چالش. در استفاده از این روش اگر یکی از طرف ها ارزش گذاری طرف مقابل را از قبل بداند و مطمئن باشد که طرف مقابل طبق همان ارزش گذاری عمل می کند، می تواند تقلب کند و با استفاده از این اطلاعات ارزش گذاری خود را به گونه ایxvhpd ;vni تا سهم بیشتری را از آن خود کند. به عنوان نمونه مثال زیر را در نظر بگیرید: فرض کنید جدول ارزش گذاری نسبی زیر را داشته باشیم: طبق روش تنظیم برنده ، formula_6 ،formula_7 و formula_8 از formula_9 به نفر اول و formula_10 ،formula_11 و formula_12 از formula_9 هم به نفر دوم می رسد و مجموع امتیاز برای هر کدام برابر formula_14 خواهد بود. اگر نفر اول از ارزش گذاری نفر دوم با خبر باشد، می داند که formula_6 و formula_7 به او می رسد پس کافی است امتیاز آن دو را تنها به میزان خیلی کمی بیشتر از امتیاز نفر دوم ارزش گذاری کند و باقی امتیاز خود را به اشیا دیگری که تمایل به گرفتن آنها دارد، اضافه کند. برای مثال می تواند به formula_6 عدد formul
a_18 و به formula_7 عدد formula_20 را نسبت دهد. بدین شکل formula_21 امتیاز اضافه برای او باقی می ماند که می توانند آن را بین بقیه اشیا مورد علاقه اش توزیع کند. اگر به شی formula_9 سه امتیاز بیشتر، به شی formula_10 دو امتیاز بیشتر و به formula_11 نه امتیاز بیشتر بدهد، آنگاه داریم: اگر روش تنظیم برنده را برای این مقادیر جدید اجرا کنیم formula_6 ،formula_7 و formula_27 از formula_9 به نفر اول و formula_10 ،formula_11 و formula_31 از formula_9 به نفر دوم می رسد و این بار مجموع امتیاز برای هر کدام برابر formula_33 خواهد بود که به نسبت قبل عدد کمتری است ولی نفر اول با اعمال این تغییرها درصد بیشتری از formula_9 را به نسبت قبل از آن خود کرده است و برای نفر اول این نتیجه در حقیقت رضایتمندی و مطلوبیت بهتری دارد که ناشی از دانستن اطلاعات توزیع امتیازهای نفر مقابل بوده است. محدودیت ها. این روش تنها برای تقسیم بین دو نفر پاسخ گو خواهد بود و برای تعداد افراد بیشتر، نتیجه یک تقسیم عادلانه نخواهد بود. به مثالی از کتاب تقسیم عادلانهتوجه کنید: برای این که تقسیم به گونه ای باشد که میزان رضایتمندی سه طرف برابر باشد و نیز کارایی
پارتو را داشته باشد باید formula_10 را به نفر سوم، formula_6 را به نفر دوم و formula_9 را به نفر اول بدهیم؛ ولی با این کار نتیجه، حسادت برانگیز خواهد بود؛ زیرا شی formula_6 برای فرد سوم نسبت به نفر دوم ارزشمندتر است. برای این مسئله نمی توان با استفاده از این روش یک تقسیم عادلانه ارائه داد و باید از روش های جایگزین دیگری استفاده کرد.
در مبحث محاسبات، الگوریتمهای حافظه خارجی (الگوریتم های خارج از هسته) به الگوریتم هایی می گویند که به منظور پردازش داده هایی طراحی می شوند که به دلیل حجم بالا، در حافظه اصلی رایانه گنجانده نمی شوند. این الگوریتم ها باید به گونه ای طراحی شوند که در بهترین زمان بتوانند به داده های درون حافظه های کمکی مانند هارد درایودسترسی داشته باشند و آن ها را استخراج کنند. الگوریتم های حافظه خارجی، در مدل حافظه خارجی بررسی می شوند. مدل. مدل حافظه خارجی (مدل I/O یا مدل disk access) یک نوع مدل محاسبه ایده آل شده است که منظور آنالیز الگوریتم حافظه خارجی به کار می رود. این مدل یک ماشین انتزاعیمانند مدل ماشین RAM می باشد با این تفاوت که علاوه بر حافظه اصلی حافظه cache هم وجود دارد. زمان اجرای یک الگوریتم در مدل حافظه خارجی را تعداد خواندن و نوشتن هایی که بر روی حافظه انجام می شود تعیین می کند. این مدل همچنین بیان می کند که خواندن و نوشتن از حافظه cache بسیار سریع تر از حافظه اصلی است. مدل حافظه خارجی نخستین بار از سوی الوک آگاروال و جفری ویتر در سال ۱۹۸۸ معرفی شد. این مدل کمی مرتبط با مدل cache-oblivious می باشد ولی الگوریتم ها در
مدل حافظه خارجی ممکن است هم، اندازه بلاک و هم، اندازه حافظه cache را بدانند به همین دلیل گاهی از این مدل تحت عنوان مدل cache-aware یاد می کنند. این مدل شامل یک پردازنده و حافظه داخلی می باشد و همچنین یک حافظه cache در این مدل وجود دارد که اندازه آن را M در نظر می گیریم. این cache به یک حافظه خارجی بدون محدودیت متصل است. هردو حافظهٔ داخلی و خارجی بهبلاک هایی با اندازه B تقسیم می شوند. یک عملیات ورودی/خروجی یا انتقال حافظه در واقع انتقال یک بلاک شامل B عنصر پیوسته از حافظه خارجی به حافظه داخلی می باشد و زمان اجرای این الگوریتم با استفاده از تعداد این عملیات ها بدست می آید. الگوریتم. الگوریتم ها در مدل حافظه خارجی این مزیت را دارند که با بدست آوردن یک شیء از حافظهٔ خارجی می توان کل بلاک آن شیء را بدست آورد. پیدا کردن یک عنصر میان N عنصر در این مدل با استفاده از یک درخت بی امکان پذیر است؛ که در این درخت هر یک از عملیات پیدا کردن، درج کردن و حذف کردن در زمان formula_1 انجام می شود. مرتب سازی خارجی، یک نوع مرتب سازی است که روی حافظه خارجی صورت می گیرد. این مرتب سازی را می توان با استفاده از مرتب سازی تجمعی که مشاب
ه مرتب سازی سریع است انجام داد. زمان این مرتب سازی برای مرتب کردن N عنصر formula_2 می باشد. کاربردها. این مدل برای تحلیل و بررسی داده هایی که به دلیل حجم بالا در حافظه داخلی جا نمی شوند بسیار مناسب است. برای مثال در سیستم های جغرافیایی، به خصوص سیستم های مدلسازی ارتفاعات که حجم داده ها از چندین گیگابایت و حتی ترابایت نیز بیشتر می شود از مدل حافظه خارجی استفاده می شود.
الگوریتم جابه جایی یای انحصاری، الگوریتمی است که با استفاده از عملگر بیتی یای انحصاری مقدار دو متغیر را بدون استفاده از متغیر دیگری یا تغییر نوع متغیرها با یکدیگر جابه جا می کند. الگوریتم. الگوریتم به شرح زیر است: X := X XOR Y Y := Y XOR X X := X XOR Y این الگوریتم معادل ۳ دستور در زبان ماشین است. همچنین چون یای انحصاری خاصیت جابه جایی دارد، دو عبارت X XOR Y و Y XOR X برابرند. این الگوریتم در حالتی که دو متغیر X و Y برابر باشند (منظور از برابری دو متغیر، یکی بودن آدرس آن هاست نه یکی بودن مقادیر آن ها)، به درستی کار نمی کند زیرا پس از خط اول مقدار X برابر 0 شده و چون آدرس X و Y یکی است، مقدار Y هم برابر 0 می شود و دو متغیر مقادیر واقعی خود را از دست می دهند. اثبات درستی الگوریتم. با استفاده از ویژگی های یای انحصاری. ویژگی های یای انحصاری عبارتند از: فرض کنید ثباتهای R۱ و R۲ به ترتیب دارای مقادیر A و B باشند، الگوریتم را برای R۱ و R۲ مرحله به مرحله اجرا می کنیم: با استفاده از جبر خطی. یای انحصاری را می توان به عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در میدان ۲ در نظر گرفت. در این صورت الگوریتم را می توان
با ضرب یک ماتریس ۲ formula_12۲ در میدان ۲ معادل کرد. برای سادگی فرض می کنیم X و Y یک بیت باشند. در این صورت مرحله اول الگوریتم معادل خواهدبود با: X := X XOR Y Y := Y که معادل ماتریسی آن formula_13است. داریم: formula_14 دنباله دستورات الگوریتم را می توان به صورت ضرب ماتریس های ۲ formula_12۲ نشان داد: formula_16 برای تعمیم به وقتی که X و Y برادارهای بیتی به طول n اند، یای انحصاری معادل ماتریس ۲n formula_12۲n formula_18است. باید توجه کرد که این ماتریس بر روی متغیرها (که در حافظه آدرس دارند) اعمال نمی شوند بلکه بر روی مقادیر اعمال می شوند. نمونه کد. کد زیر، کد الگوریتم به زبان C است: void xorSwap (int *x, int *y) if (x != y) *x ^= *y; *y ^= *x; *x ^= *y; باید توجه کرد که کد ابتدا بررسی می کند که آیا آدرس دو متغیر یکی است یا خیر زیرا اگر یکی باشد، همان گونه که پیش از این گفته شد مقدار متغیر ۰ خواهدشد. همچنین می توان الگوریتم را به صورت یک ماکرو تعریف کرد: /* درصورتی که دو متغیر برابر باشند، به درستی کار نمی کند. */ /* ابتدا یکی نبودن آدرس ها را بررسی می کند، سپس دو متغیر را جابه جا می کند. */ دلایل استفاده از الگو
ریتم. در بیشتر موارد در عمل استفاده از یک ثبات دیگر برای جابه جایی بهینه تر است و در موارد محدودی جابه جایی با یای نحصاری ممکن است در عمل به کار بیاید مانند: دلایل عدم استفاده از الگوریتم. بیشتر کامپایلرهای جدید متغیرهای موقت را پس از استفاده، آزاد می کنند لذا از نظر حافظه و زمان الگوریتم جابه جایی سه طرفه با این الگوریتم تفاوتی ندارد. ضمن آنکه این الگوریتم برای کسی که با روش آن آشنا نباشد نامفهوم است. در کامپوترهای جدید، الگوریتم جابه جایی یای انحصاری از الگوریتم جابه جایی سه طرفه کنتر است. از پردازنده های x۸۶ اینتل و ای ام دی به بعد، جابه جایی بین ثبات ها بدون تأخیر انجام می شود. حتی اگر ثباتی برای استفاده نباشد، دستور XCHG حداقل به اندازه سه عملیات یای انحصاری سریع خواهدبود. دلیل دیگر آن است که پردازنده ها حتی الامکان دستورات را موازی اجرا می کنند. در الگوریتم یای انحصاری، ورودی های هر عملگر به خروجی مرحله قبل بستگی دارد لذا نمی توان مراحل آن را موازی اجرا کرد. تعمیم به دیگر عملگرها. در این الگوریتم، یای انحصاری می تواند با هر عملگری که ۴ خاصیت گفته شده را داشته باشد، جایگزین شود. با جایگزین کردن یای انحصا
ری با جمع و تفریق خواهیم داشت: void addSwap (unsigned int *x, unsigned int *y) if (x != y) *x = *x + *y; *y = *x - *y; *x = *x - *y; برخلاف یای انحصاری، در این نوع پردازنده یا زبان برنامه نویسی استفاده شده باید از هم نهشتی یا اعداد بزرگ استفاده کنند تا بتوان مطمئن شد که عملگرها سرریز ندارند؛ لذا کاربرد این از کاربرد یای انحصاری کمتر خواهدبود.
پمپ یونی نوعی پمپ خلاء است که در شرایط ایدئال به کمک آن می توان تا فشارهای formula_1میلی بار را ایجاد کرد. پمپ یونی به کمک یک ولتاژ نسبتاً بالا، در حدود ۳ تا ۷ کیلوولت، گازهای درون محفظه خلاء را یونیزه می کند، که اینکار باعث می شود یون ها شتاب پیدا کرده و توسط یک الکترود صلب جذب شوند. انواع. سه گونه عمده از پمپ های یونی وجود دارد: مدل استاندارد و متعارف آن یعنی پمپ دیودی، پمپ دیودی خاص (noble diode pump) و پمپ تریود (triode pump).
ضرب ماتریس یکی از اعمال پایه در بسیاری از الگوریتم های آنالیز عددی محسوب می شود به همین دلیل در راستای بهبود زمان آن تلاش های بسیاری انجام شده است. کاربردهای ضرب ماتریس در بسیاری از زمینه های مختلف همچون علم محاسبه، بازشناخت الگو ، پردازش تصویر ، کار با نرم افزارهای ۳ بعدی و حتی زمینه های به ظاهر بی ربط مانند شمردن تعداد گشت ها در یک گراف دیده می شود. الگوریتم های بسیاری برای این کار روی سیستم های رایانش موازی طراحی شده است که در آن چند هسته به صورت همزمان و موازی عملیات را انجام می دهند. اگر از تعریف ضرب ماتریس به صورت مستقیم استفاده کنیم برای ضرب دو ماتریس زمان طول خواهد کشید که به صورت می توانیم نمایش دهیم. الگوریتم هایی با زمان اجرای بهتری برای این کار ارائه شده اند. برای مثال در ده سال ۱۹۶۹ استراسن در این زمینه الگوریتمی بر پایه ماتریس های 2×2 ارائه داد اما به طور کلی هنوز نمی دانیم بهترین الگوریتم برای این کار چیست. (در واقع پیچیدگی زمانی آن مشخص نیست) الگوریتم پیمایشی. طبق تعریف ضرب ماتریس می توانیم یک الگوریتم برای این کار ارائه دهیم. به ازای ماتریس formula_1 که یک ماتریس formula_2 است و ماتریس formul
a_3 که یک ماتریس formula_4 است می خواهیم ماتریس formula_5 که ماتریسی formula_6 است را محسابه کنیم. طبق تعریف ضرب ماتریس formula_7 بنابراین به ازای هر دوتایی formula_8 می توانیم با formula_9 مقدار formula_10 را محاسبه کنیم. یعنی در کل الگوریتمی با زمان اجرای formula_11 خواهیم داشت. اگر فرض کنیم هر سه ماتریس formula_12 هستند آنگاه الگوریتم formula_13 خواهد بود. 1 Input: matrices and 2 Let be a new matrix of the appropriate size 3 For from 1 to : 4 For from 1 to : 5 Let 6 For from 1 to : 7 Set 8 Set 9 Return بررسی رفتار حافظه نهان (کش). در الگوریتم بالا ترتیب حلقه ها را می توانیم جابه جا کنیم. اگر چه این جابه جایی در مدت زمان اجرای الگوریتم تأثیری نخواهد داشت اما این ترتیب در بحث های مربوط به دسترسی حافظه (access pattern) و مسائل مربوط به استفاده از حافظه نهان پردازنده مهم است. مثلاً اینکه ماتریس ها به ترتیب سطری یا ستونی (یا ترکیبی از این دو) ذخیره شوند در زمان حافظهٔ نهان پردازنده تأثیر گذار خواهد بود. حتی اگر حالت بهینه را در نظر بگیریم که حافظهٔ کش شرکت پذیر کامل با formula_14 سطر حافظهٔ formula_15 بیتی باشد
و ماتریس های formula_16 و formula_17 به صورت سطری ذخیره شده باشند، این الگوریتم بهینه نخواهد بود. هنگامی که formula_18 از آنجایی که ماتریس ها به صورت سطری ذخیره شده اند هر پیمایش حلقهٔ داخلی در الگوریتم (یک پیمایش روی سطر ماتریس اول و ستون ماتریس دوم) یک خطای کش به هنگام دسترسی به خانه ی های ماتریس دوم به همراه خواهد داشت؛ و این به این معناست که الگوریتم در بدترین حالت حاوی formula_19 خطای کش خواهد بود. امروزه -یعنی از سال ۲۰۱۰- خطای کش ها به نسبت اعمال پردازنده تأثیر بیشتری روی زمان اجرا می گذارند بنابراین بهتر است با روشی این خطای کش ها را کاهش دهیم. برای حل این مشکل ماتریس ها را به بلوک هایی از اردر formula_20 تایی تقسیم می کنیم. با اینکار کل یک زیرجدول در حافظهٔ کش قرار می گیرد و این بلوک ها در هم ضرب می شوند. ضرب هر بلوکی هیچ خطای کشی به همراه نخواهد داشت. 01 Input: matrices and 02 Let be a new matrix of the appropriate size 03 Pick a tile size 04 For from 1 to in steps of : 05 For from 1 to in steps of : 06 For from 1 to in steps of : 07 Multiply and into , that is: 08 For from to : 09 For from to : 10
Let 11 For from to : 12 Set 13 Set 14 Return تعداد خطاهای کش در این مدل برابر formula_21 خواهدبود. مخرج formula_22 باعث می شود در پردازنده های جدید خطاهای کش در زمان اجرا تأثیر گذار نشوند و صرفاً تحلیل زمانی الگوریتم تأثیر گذار باشد. الگوریتم تقسیم و حل. حال سعی می کنیم روشی تقسیم و حل برای ضرب ماتریس ها ارائه دهیم. ابتدا فرض کنید ماتریس هایمان formula_12 هستند. در این روش مطابق زیر ماتریس ها را به چهار بلوک تقسیم می کنیم که اندازهٔ آن ها تقریباً برابرند. اگر ماتریس های مان اندازه شان توانی از دو باشد (یعنی ماتریسی با ابعاد formula_25 ) می توانیم این الگوریتم را به کار بگیریم. به صورت زیر دو ماتریس را در هم ضرب می کنیم. این الگوریتم شامل ۸ ضرب ماتریس های کوچکتر formula_27 خواهد بود که به صورت بازگشتی محاسبه می شود و پایهٔ آن ضرب اسکالر formula_28 است. همچنین جمع کردن ماتریس ها به صورتی که در بالا گفته شده formula_29 طول خواهد کشید. توجه کنید اگر ماتریس ما ابعادش توانی از ۲ نبود باز هم می توانیم این الگوریتم را به کار ببریم. کافیست با اضافه کردن سطرهایی تمام صفر و ستون هایی تمام صفر به پایین و راست ماتریس ابع
ادش را توانی از دو کنیم. با اضافه کردن آن ها اندازهٔ ماتریس حداکثر ۴ برابر خواهد شد (تعداد ستون ها و سطرها هر کدام ۲ برابر خواهند شد) بنابراین تفاوتی در تحلیل زمانی ایجاد نمی شود به علاوه افزودن سطر و ستون تمام صفر تأثیری در حاصل ضرب نخواهدگذاشت. با توجه به مطالب گفته شده برای تحلیل زمانی آن می توانیم رابطهٔ زیر را بنویسیم: بر طبق قضیه ی اصلی می توانیم این الگوریتم را تحلیل زمانی کنیم. می دانیم formula_32 بنابراین formula_33 خواهد بود. در نتیجه این الگوریتم با الگوریتم ابتدایی ای که بررسی کردیم تفاوتی از نظر زمانی ندارد. ماتریس های غیر مربعی. این الگوریتم در عمل برای ماتریس های غیر مربعی سریع تر عمل می کند. کافیست به جای تقسیم کردن هر دو ماتریس به چهار تکه یکی از ماتریس ها را به دو تکهٔ برابر (یا تقریباً برابر) با تقسیم کردن سطرها یا ستون ها تقسیم کنیم. در زیر می توانید الگوریتم چنین کاری را ببینید: Inputs: matrices of size , of size . Base case: if is below some threshold, use an unrolled version ofthe iterative algorithm. Recursive cases: If , split horizontally: formula_34 Else, If , split vertically: form
ula_35 Otherwise, . Split vertically and horizontally: formula_36 بررسی رفتار حافظه نهان (کش). الگوریتم گفته شده در این بخش تقسیم بندی را تا جایی می تواند ادامه دهد که کل ماتریس در حافظهٔ کش جا شوند و بنابراین از نظر تعداد خطاهای کش مانند روش تقسیم بندی بلوکی عمل می کند. با این تفاوت که در آن الگوریتم خود پیاده سازی الگوریتم با توجه به اندازهٔ کش پردازندهٔ هدف انجام می شود (پارامتر formula_37 ای را باید در خود متن الگوریتم تعیین کنیم) در حالیکه این الگوریتم برای کش های پویا با اندازه های مختلف بهینه تر عمل خواهد کرد. تعداد خطاهای کش در این الگوریتم با formula_14 خط حافظهٔ کش که هر خط formula_15 بیت دارد به صورت زیر خواهد بود: الگوریتم های بهتر از formula_41. الگوریتم هایی وجود دارند که زمان اجرای بهتری از الگوریتم های فوق دارند. اولین الگوریتم کشف شده که اینگونه بود الگوریتم استراسن بود که در سال ۱۹۶۹ توسط وولکر استراسن (Volker Strassen) کشف شد. این الگوریتم به «الگوریتم سریع ضرب ماتریس» نیز معروف است. این الگوریتم بر مبنای ضرب دو ماتریس formula_42 با ۷ عملیات ضرب است که در عوض تعداد بیشتری جمع و عملیات ریاضی