تسریع در الگوریتم های خود: ملاحظات در طراحی ، انتخاب الگوریتم و اجرای

پیگیری سرعت یکی از معدود ثابت در محاسبات است و توسط دو چیز هدایت می شود: مقدار فزاینده داده ها و منابع سخت افزاری محدود. امروز در دوره Big Data و اینترنت چیزهایی که در هر دو جهت از آن استفاده می کنیم. خوشبختانه ما در محاسبات توزیع شده و موازی بسیار بهتر می شویم ، اما نیاز به سرعت خام در سطح الگوریتمی هرگز از بین نمی رود. اگر بتوانیم الگوریتم های خود را ذاتاً سریعتر کنیم ، از سخت افزار گران قیمت خود بیشتر می شویم و همیشه این یک چیز خوب خواهد بود.

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

این سنتی است که هرگونه بحث در مورد بهینه سازی را با یک بدبختی شروع کنیم تا محتاط باشد. اولین قانون بهینه سازی نات: "این کار را نکنید" و دوم او مانند آن است: "هنوز این کار را نکنید."همچنین به ما گفته می شود که "بهینه سازی زودرس ریشه همه شر است" ، اما چه چیزی "زودرس" را تشکیل می دهد؟چه زمانی خیلی زود است؟

قانون بهینه سازی من در نظر گرفته شده است تا به این سؤال پاسخ دهد: "بدون بهینه سازی بدون کمیت."ما هرگز نباید سعی کنیم یک الگوریتم را تسریع کنیم بدون اینکه ابتدا عملکرد فعلی آن را اندازه گیری کنیم و آن را پروفایل کنیم تا مشخص شود که بیشترین زمان را دارد. استنباط درست در جایی که یک الگوریتم بیشتر وقت خود را صرف می کند ، بسیار دشوار است.

به عنوان مثال ، یک شبیه سازی نوری مونت کارلو که من نوشتم معلوم شد که از یک چهارم کامل از زمان اجرا خود استفاده می کند و ریشه های مربعی از اعداد را بسیار نزدیک به 1 می برد. این به دلیل روند بردارهای جهت گیری مجدد پس از پراکندگی حوادث بود. با نوشتن برخی از کد های بسیار بهینه سازی شده برای این مورد خاص ، من توانستم از اجرای آهسته عمومی در فرآیند ریاضی جلوگیری کنم و در عملکرد کلی حدود 20 ٪ به دست بیاورم ، که این یک چیز کوچک نیست که اجرای آن روزها طول بکشد. هیچ راهی وجود ندارد که بتوانم این سینک زمان را بدون پروفایل کد پیدا کنم.

ماژول های cprofile و پروفایل در پایتون (که هر دو بخشی از توزیع ActivePython هستند ، پروفایل قطعی را ارائه می دهند ، و این باعث می شود که نتایج به طور منطقی تفسیر شود. سایر زبانها ممکن است از پروفایل بر اساس نمونه گیری پیشخوان برنامه پشتیبانی کنند ، که می تواند از اجرا تا اجرا به دلیل اجرای متفاوت باشد. تأثیرات آماری حتی با پروفایل قطعی ، برخی از قسمت های برنامه ممکن است به دلیل محدودیت منابع یا استفاده از اعداد تصادفی در خود کد دارای تغییرات در عملکرد باشند. I/O و ارتباطات هر دو زمینه ای هستند که وابستگی های خارجی می توانند بر عملکرد تأثیر بگذارند ، بنابراین این امربهتر است در صورت امکان این موارد را به طور جداگانه مشخص کنید.

این فرض می کند که ما کد را به پروفایل داریم ، اما شتاب الگوریتمی می تواند در چندین سطح مختلف در فرآیند توسعه انجام شود: طراحی ، انتخاب الگوریتم و اجرای.

طرح

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

این امر به ویژه هنگام کار بر روی مشکلات بهینه سازی مفید است. یکی اغلب کد مانند این را می بیند:

x = sqrt (برخی از بیان پیچیده)

گرفتن ریشه مربع-یک عملیات غیر منطقی گران قیمت حتی در این روزهای سخت افزار ریاضی سریع-هیچ چیز را به محاسبه نمی کند ، مگر اینکه احتمالاً در بازی نهایی بهینه سازی ، جایی که انحنای سطح نزدیک حداقل می تواند برای بسیار مهم باشدکارآیی الگوریتم. این در مورد هر عملکرد یکنواختی که نتیجه نهایی شما را پیچیده می کند صادق است: اغلب می توان با آن پخش شد.

یکی دیگر از رویکردهای کاملاً کلی ، نمونه برداری از داده ها به جای برده داری با استفاده از هر نقطه داده موجود است. این ترفند پشت همبستگی شبه ، که یک الگوریتم ثبت نام فوق العاده سریع است: با استفاده از یک مجموعه کوچک از پیکسل ها برای برآورد یک انتگرال همبستگی متقابل ، سرعت بخشیدن به ثبت نام با سفارشات بزرگی امکان پذیر بود. چند سال بعد از یک روش مشابه در الگوریتم اطلاعات متقابل استفاده شد.

سوال اصلی طراحی باید این باشد: "آیا من واقعاً باید آن را محاسبه کنم؟"ممکن است چیزی وجود داشته باشد که با نتیجه ای که به آن اهمیت می دهید ارتباط برقرار کند ، اما می توان آن را خیلی سریعتر محاسبه کرد.

انتخاب الگوریتم

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

1. مشکلات اغلب با یک مقیاس معین همراه است ، بنابراین رفتار مقیاس پذیر الگوریتم بی ربط است. اگر چیزی در ده میلیون پایگاه داده خوب باشد ، اگر هرگز مجموعه داده های بزرگ را نداریم ، عملکرد آن در صد میلیون نفر بی ربط است.
2. عوامل اصلی مهم: یک الگوریتم O (N ** 2) ممکن است یک عامل پیشرو بسیار کوچکتر از یک الگوریتم معادل O (N*log (n)) به دلیل پیچیدگی پایین باشد.
3. صحبت از پیچیدگی ، الگوریتم هایی با عملکرد بزرگ و بهتر اغلب پیچیده تر هستند و باعث می شوند آنها شکننده تر ، اشکال زدایی دشوارتر و نگهداری آن دشوار باشند.

مشهورترین مورد شکنندگی احتمالاً QuickSort است که از O (n*log (n)) به o (n ** 2) تخریب می شود وقتی که ورودی از قبل مرتب شده است. این یک مورد خوشبختانه برای مشاهده است ، اما الگوریتم های پیچیده تر با عملکرد متوسط خوب هنوز هم می توانند در موارد خاص بد ناکام باشند و اشکال زدایی این رفتار می تواند پیچیده و وقت گیر باشد. از آنجا که چنین خرابی هایی به طور معمول نادر است ، با مواجهه با آنها پس از استقرار غیر معمول نیست و با یک وضعیت عجیب و غریب روبرو می شوید که "گاهی اوقات همه چیز به آرامی اجرا می شود" بدون هیچ دلیل آشکار.

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

جزئیات اجرای

الگوریتم اجرای آن نیست. حتی الگوریتم های نسبتاً ساده و کارآمد می توانند به شدت اجرا شوند که ممکن است منجر به عملکرد کندتر شود. تماس های عملکردی غیر ضروری یک مورد مشترک است. استفاده از بازگشت به جای حلقه ها می تواند سرعت را تحت تأثیر قرار دهد.

در بسیاری از موارد ، کد با کارایی بالا به زبانی نسبتاً پایین مانند C ، C ++ یا حتی Fortran نوشته شده و از یک زبان سطح بالا خوانده می شود. نحوه سفارش و سازمان یافته این تماس ها می تواند تفاوت بزرگی در عملکرد ایجاد کند: به طور کلی فراخوانی در مرزهای زبان یک عمل گران است ، بنابراین استفاده از رابط ها به گونه ای که به حداقل برسد این توصیه می شود.

زبانهای سطح بالا اغلب شامل ترفندهایی هستند که سرعت بخشیدن به آنها را افزایش می دهد. به عنوان مثال ، توابع SUM () و MAP () پایتون هر دو در آرایه ها بسیار سریعتر از حلقه ها هستند. حلقه بیش از 100،000،000 عدد صحیح و جمع بندی آنها 4. 4 ثانیه بر روی دستگاه دسک تاپ من طول می کشد ، اما اگر از مبلغ () در آرایه استفاده کنم 0. 63 ثانیه است. علاوه بر این ، ژنراتورها در حلقه ها (Xrange به جای دامنه در پایتون 2 ، دامنه () در پایتون 3) به طور کلی سریعتر از توابع ایجاد لیست غیر تنبل هستند.

عملکرد نقشه () بسیار سریعتر از حلقه زدن است: حلقه زدن روی یک آرایه 100،000،000 عدد صحیح و گرفتن ریشه مربع 10 ثانیه بر روی دسک تاپ من طول می کشد ، اما همان فرآیند با استفاده از نقشه (Math. sqrt ، lstdata) نیمی از آن زمان طول می کشد.

رویکردهای سطح پایین

تکنیک های قدرتمندتری در پایتون وجود دارد ، مانند استفاده از کتابخانه هسته ریاضی Numpy و Cython و اینتل (MKL) ، که در ActivePython ActiveState موجود است. ممکن است محدودیت هایی وجود داشته باشد که از استفاده از یک یا چند مورد از این تکنیک ها برای یک مشکل معین جلوگیری کند ، اما آنها ارزش دارند که به عنوان بخشی از "زرادخانه کارآیی" شما در نظر داشته باشند. فقط حتماً ابتدا عملکرد الگوریتم خود را تعیین کنید!

برای کسب اطلاعات بیشتر در مورد تسریع در الگوریتم ها و کسب بینش بیشتر در مورد بهینه سازی MKL Intel ، وبینار من را تماشا کنید ، "شتاب الگوریتم های خود را در تولید با پایتون و اینتل MKL" ، با سرگئی مایدانوف ، مدیر مهندسی نرم افزار از اینتل.

تام رادکلیف

تام رادکلیف بیش از 20 سال تجربه در زمینه توسعه نرم افزار ، علوم داده ، یادگیری ماشین و مدیریت در دانشگاه و صنعت دارد. او یک مهندس حرفه ای (PEO و APEGBC) است و دارای مدرک دکترای فیزیک از دانشگاه کوئین در کینگستون است. تام اشتیاق به فرآیندهای کمی و داده محور را برای فعال سازی به ارمغان می آورد. او عمیقاً متعهد به ایده های تئوری احتمال بیزی است و یک احتمال پذیرش بیزی بالا را به این ایده اختصاص می دهد که قرار دادن بهترین ابزارهای نرم افزاری در دست خلاق ترین و تواناترین مردم ، جهان را به مکانی بهتر تبدیل می کند.

صفحه اصلی »وبلاگ فعال در مورد ActivePython» یادگیری ماشین »تسریع الگوریتم های شما: ملاحظات در طراحی ، انتخاب الگوریتم و اجرای

نویسنده وبلاگ

تام رادکلیف بیش از 20 سال تجربه در زمینه توسعه نرم افزار ، علوم داده ، یادگیری ماشین و مدیریت در دانشگاه و صنعت دارد. او یک مهندس حرفه ای (PEO و APEGBC) است و دارای مدرک دکترای فیزیک از دانشگاه کوئین در کینگستون است. تام اشتیاق به فرآیندهای کمی و داده محور را برای فعال سازی به ارمغان می آورد. او عمیقاً متعهد به ایده های تئوری احتمال بیزی است و یک احتمال پذیرش بیزی بالا را به این ایده اختصاص می دهد که قرار دادن بهترین ابزارهای نرم افزاری در دست خلاق ترین و تواناترین مردم ، جهان را به مکانی بهتر تبدیل می کند.