جستجو در تالارهای گفتگو
در حال نمایش نتایج برای برچسب های 'الگوریتم'.
4 نتیجه پیدا شد
-
سلام. من یک تکه کد در اختیار دارم که عمل تبدیل تاریخ میلادی به شمسی رو انجام میده. از اونجایی که کد داکیومنت نداره و چیزی ازش متوجه نمیشم و احتمال میدم که تا تعداد سالهای کمی رو پشتیبانی کنه. شما چه الگوریتمی رو برای این کار توصیه میکنید؟ اگر امکان داره لطفا با توضیح و مرحله به مرحله پاسخ بدید.
-
با نگاهی به الگوی جستجو تحت الگوریتم Boyer-Moore در استاندارد جدید یعنی C++17 میتوان به کنترل بیشتر و حتی سرعت بسیار بالاتری نسبت به کتابخانهٔ Boost رسید. با استاندارد ۱۷ در سیپلاسپلاس، اکنون میتوانید از الگوریتمهای پیشرفتهتر و بهتری در عین حال سریعتری برای جستجو استفاده کنید. از این پس، شما میتوانید کنترل بیشتر و همچنین افزایش کارآیی امیدوار کنندهای در بسیاری از موارد داشته باشید که به صورت پیشفرض در استاندارد ۱۷ ارائه شدهاست. معرفی روشهای سادهتری برای یافتن الگو در یک رشته O (nm) جایی که n طول تمام رشته است و m طول الگو است وجود دارد. این روشها به عنوان روشهای دوم و بهتری میتوان در نظر گرفته شوند. در C++17 الگوریتم جستجو در استاندارد std::search به دو روش زیر بهروز رسانی شده است: از این پس شما میتوانید از قانون مجوز استفاده از نسخهٔ پیشفرض الگوریتم استفاده کنید، اما به صورت موازی عمل میکند. شما میتوانید یک شیء جستجوگر برای مدیریت جستجو فراهم کنید. بنابراین ما سه نوع جستجوگر خواهیم داشت: default_searcher boyer_moore_searcher boyer_moore_horspool_searcher حالت پیشفرض از جستجو به صورت زیر خواهد بود: #include <iostream> #include <string> #include <algorithm> #include <functional> int main() { std::string in = "Hello, World from new C++ 17"; std::string needle = "C++"; auto it = std::search(in.begin(), in.end(), std::default_searcher(needle.begin(), needle.end())); if(it != in.end()) std::cout << "The string " << needle << " found at offset " << it - in.begin() << '\n'; else std::cout << "The string " << needle << " not found\n"; } پیشپردازش هر دو الگوریتم Boyer Moore و Boyer Moore Horspool از برخی اطلاعات در رابطه با رشته الگو استفاده میکنند تا بتوانند مقایسههای بینظیری را انجام دهند. به منظور هوشمندانهتر شدن هر یک از الگوریتمها یک عمل پیشپردازشی را انجام میدهند که الگوی ورودی را تحلیل میکند. پیچیدگی پیشپردازش معمولاً به اندازهٔ الفبای رشته بستگی دارد. در کتابخانهٔ Boost (بوست) اگر شما با کتابخانهٔ بوست کار کرده اید، ممکن است شما با الگوریتمهای جستجو آشنا باشید. در نسخهٔ ۱.۵۰ (در تاریخ ژوئن ۲۰۱۲ میلادی) مجموعهٔ جدیدی از الگوریتمها به کتابخانه اضافه شده است. در کتابخانه سه شیء جستجوگر وجود دارد: الگوریتم جستجوی Boyer-Moore الگوریتم جستجوی Boyer-Moore-Horspool الگوریتم جستجوی Knuth-Morris-Pratt نحوهٔ استفاده از این روشها در استاندارد ۱۷ چگونه است؟ در سیپلاسپلاس ۱۷ سه نوع سربار اضافی بر روی ویژگیهای std::search اضافه شده است. template<class ForwardIterator, class Searcher> ForwardIterator search( ForwardIterator first, ForwardIterator last, const Searcher& searcher ); هر جستجوگر معمولاً دو ورودی تکرار کننده را میگیرند. شروع و پایان الگو، و سپس یک پیشفرض باینری که معمولاً آن با عملگر برابر است. آنها ممکن است از پارامترهای دیگر نیز استفاده کنند، برای مثال، یک تابع هَش (مخلوط) کننده. در کل، شما میتوانید آن را به صورت زیر استفاده کنید: std::string testString = "Hello Super World"; std::string needle = "Super"; auto it = search(testString.begin(), testString.end(), boyer_moore_searcher(needle.begin(), needle.end())); if (it == testString.end()) cout << "The string " << needle << " not found\n"; برخی از آزمونهای پایه برای آزمایش مخزنی ارائه شده است که در آن نمونه کُد آن آمده است. در این مثال نمونههایی نوشته شده است که برخی از آنها کارایی و سرعت بسیار خوبی را در الگوریتمهای جدید با استفاده از MSVC نشان میدهد. آزمایشها چطور کار میکنند؟ برنامه یک فایل را بارگذاری میکند، مانند کتابی که شامل متنی با ۵۰۰ کیلوبایت اندازه است. تمام محتوای فایل در یک رشتهٔ ورودی ذخیره میشود. یک الگو انتخاب شده است که N آخرین حرف از رشته ورودی است. برنامه از چندین الگوریتم استفاده میکند و بارها در جستجو هر یک از ITER ها را اجرا میکند. برای مثال نسخهٔ std::string::find به صورت زیر آمده است: RunAndMeasure("string::find", [&]() { for (size_t i = 0; i < ITERS; ++i) { std::size_t found = testString.find(needle); if (found == std::string::npos) std::cout << "The string " << needle << " not found\n"; } }); نسخهٔ boyer_moore_horspool به صورت زیر: RunAndMeasure("boyer_moore_horspool_searcher", [&]() { for (size_t i = 0; i < ITERS; ++i) { auto it = std::search(testString.begin(), testString.end(), std::boyer_moore_horspool_searcher( needle.begin(), needle.end())); if (it == testString.end()) std::cout << "The string " << needle << " not found\n"; } }); در اینحا نتیجه بر روی سخت افزار با پردازندهٔ i7 4720HQ و Win 10 همراه با MSVC 2017 15.8 ریلیز ۶۴ بیت میباشد. الگو از ۱۰۰۰۰ حرف انتهای متن ورودی تشکیل شده است: .\searchers.exe ..\..\SampleBooks\book-test.txt 1000 10000 string length: 547412 test iterations: 1000 pattern length: 10000 string::find: 693.449 ms default searcher: 1102.25 ms boyer_moore_searcher: 133.558 ms boyer_moore_horspool_searcher: 37.0234 ms الگو در اینجا اکنون ۱۰۰ حرف آخر از متن ورودی است: .\searchers.exe ..\..\SampleBooks\book-test.txt 1000 200 string length: 547412 test iterations: 1000 pattern length: 200 string::find: 158.612 ms default searcher: 467.518 ms boyer_moore_searcher: 58.8752 ms boyer_moore_horspool_searcher: 56.7017 ms البته توجه داشته باشید که، نتایج نمونه نیاز به تحقیق بیشتری دارند. برای مثال در الگوهای کوتاه، استفاده از روش string::find معمولاً سریعتر است. بنابراین، الگوریتم Horspool سریعتر از الگوریتم boyer_moore در این مورد بوده است. واقعیت مهم در مورد std::search این است که آن یک الگوریتم عمومی است! بنابراین شما میتوانید آن را فقط برای رشتهها استفاده کنید. در اینجا مثالی آورده شده است که برای جستجوی یک الگو از شمارههای موجود در یک بردار از عددهای صحیح است. std::vector<int> testVector(1000000); std::iota(testVector.begin(), testVector.end(), 0); std::vector vecNeedle(testVector.end() - 1000, testVector.end()); auto it = std::search(testVector.begin(), testVector.end(), std::boyer_moore_horspool_searcher( vecNeedle.begin(), vecNeedle.end())); if (it == testVector.end()) std::cout << "The pattern " << needle << " not found\n"; خلاصهٔ نتیجه در این مقاله به صورت مختصر در رابطه با قابلیتهای جدیدی را که در سیپلاسپلاس ۱۷ دریافت کردهایم اشاره شده است. مهم این است که بدانید الگوریتمهای جدید همیشه سریعتر از std::string::find (برای رشتهها) نیستند.
-
- سیپلاسپلاس
- جستجو
- (و 6 مورد دیگر)
-
آیا فایلهای شما نیاز قابل توجهی به صرفهجویی در حافظهی سرور دارند؟ در این مقاله ما به شما خواهیم گفت که چگونه توسط چه الگوریتمهایی میتوانید اطلاعات خود را تا ۹۰٪ فشرده سازی کنید. الگوریتمهای فشرده سازی دادهها (دو نوع اصلی فشردهسازی داده وجود دارد) فشردهسازی بیاتلاف اطلاعات (کاملاً برگشت پذیر) فشردهسازی با اتلاف (بخش کوچکی از دادهها از دست میروند و بازسازی کامل آنها امکان پذیر نیست) اولین نوع فشرده سازی زمانی مورد استفاده قرار میگیرد که اطمینان حاصل شود دادههای فشرده شده بازیابی شده و بدون تحریف باشند. این نوع فشرده سازی هیچ کدام از دادههای اصلی را حذف نمیکند و با کاسته شدن حجم آن مصرف فضای کمی برای فشردهسازی به دست میآورد. اجازه دهید بعضی از رایجترین الگوریتمهای فشردهسازی از نوع فشردهسازی بیاتلاف یا همان (lossless) را در نظر بگیریم: تکنیک کُدگذاری هافمَن (Huffman) — این امر مستلزم جایگزینی کد یکسانی برای نمادهایی با کدهای نامحدود است، بسته به تکرار وقوع یک نماد در متن هستند میباشد. در کد گذاری استاندارد هافمن، فرض شدهاست که هر نماد در مجموعهای که کدها از آن استخراج میشوند، ارزشی یکسان با بقیه دارد: کد کلمهای که طول آن N است ارزشی برابر N خواهد داشت، مهم نیست که چند رقم آن ۱ و چند رقم آن ۰ است. وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقمهای کل ۲ چیز یکسانند. کد هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طولهای غیر همسانی داشته باشند، به خاطر خصوصیتهای واسطهٔ انتقال. مثالی بر این ادعا، الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول میکشد، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد. تکنیک رمزگذاری شانون-فانو (Shannon–Fano) — این یک پیشوند است، که به عنوان یک الگوریتم کُد گذاری یکتواخت است. این تکنیک فشردهسازی را بر اساس احتمالات نشان میدهد. مانند الگوریتم هافمَن، این تکنیک بر روی افزونگی پیام است. در رمزگذاری شانون-فانو، نمادها به ترتیب احتمال از زیاد به کم مرتب شدهاند و پس از آن به دو مجموعه که احتمال کلشان تا حد ممکن به هم نزدیک است تقسیم میشوند. سپس اولین رقم رمز همهٔ نمادها به آنها اختصاص داده میشود؛ نمادها در مجموعهٔ اول "۰" و در مجموعهٔ دوم "۱" میگیرند. تا زمانی که مجموعهای با بیش از یک عضو باقی بماند، همین فرایند برای تعیین ارقام متوالی رمزهایشان، روی آنها تکرار میشود. وقتی یک مجموعه به یک نماد کاهش پیدا کند بدان معناست که رمز آن نماد کامل است و پیشوند هیچ رمزِ نماد دیگری را تشکیل نمیدهد. این الگوریتم کدگذاریهای با طول متغیر نسبتاً کارامدی تولید میکند. تکنیک طول اجرا (Run-length) — این تکنیک به جای مجموعهای از نمادهای مکرر با کد نماد و تعداد تکرار اشاره داد. یک شکل ساده از فشردهسازی دادهها است که در آن دادههای یکسان پشت سر هم به صورت مقادیر تکی و تعداد تکرارشان ذخیره میشوند. اگرچه آسان است و میتوان به راحتی آن را درک کرد اما هنوز کارآیی چندانی ندارد. تکنیک ال زد دابلیو (Lempel–Ziv–Welch) — الگوریتمهای فشردهسازی این گروه (LZ78، LZ77، و LZW) در ایدهی جستجو برای متن مشترک هستند. الگوریتم کاراکترها را متراکم کرده و در واژه نامه به جای کاراکتر، رشتههای متراکم شده را قرار میدهد تا اینکه به رشتهای برسد که در واژه نامه قرار دارد. الگوریتم ساخت کدهای نابرابر که توسط هافمَن پیشنهاد شده است یکی از مهمترین دستاوردهای تئوری اطلاعات از دیدگاههای نظری و کاربردی است. بهتر است کدهای باینری C = {c1, ..., cm} با با طول های {l1,.. ,IM} برای پیامهای مورد نظر بهینه باشد. در صورتی که شرط به این گونه باشد pi < pj, then li > lj طول مقدار در قالب lM = maxm1m از نظر کُدنویسی بهینه شده است دو کُد lM = maxmlm که طول آن است در سمبُل آخر متفاوت خواهد بود. اگر کد C دارای شرایط مطلوبی باشد، آنگاه C به عنوان کُد X مطلوب خواهد بود. ورودی: اندازهی الفبای M خروجی: درخت دودوییِ کد هافمَن مقداردهی اولیه: تعداد گِره (نودهای) پردازش شده M0=M میباشد. با اجرای شرط While M0>1 do مراحل بعدی به صورت زیر باید انجام شوند: یافتن دو گِره (نود) با کمترین احتمال در صف از نودهای پردازش شده حذف نودها را از صف پردازش تولید یک نود جدید با دو گرده انتخاب شده به عنوان فرزند. به این ترتیب که، وزن نودها برابر است با مجموع نودهای فرزند. افزودن گِره (نود) جدید به صف. لینک کردن نودهای جدید با لبههای نودهای حذف شده М0 <– М <– 1. اگر بیشتر از یک نود در صف وجود داشته باشد، مراحل ۲ تا ۵ را تکرار کنید.
-
مهندسی ویژگیها (FE) بخش بزرگی از یادگیری ماشین (ML) و یادگیری عمیق است. مقاله فوق را برای آشنایی بیشتر با اینکه ویژگی مهندسی چگونه به توسعهدهنگان در کار با داده کمک میکند مطالعه کنید. دادهها بدون توجه به اندازه و مقایس کسبوکارهای مُدرن، شرکتها و سازمانها به عنوان دارایی از نوع طبقه-اولِ آنها تبدیل شده است. هر سیستم هوشمند، صرف نظر از پیچیدگی آن، باید بر اساس داده باشد. در قلب هر سیستم هوشمند، ما یک یا چند الگوریتم بینش دادهای را بر اساس مجموعهای از دادههای یادگیری، مانند یادگیری ماشین، یادگیری عمیق و یا روشهای آماری استفاده میکنیم که این اطلاعات را برای جمع آوری دانش و ارائه بینش هوشمند بیش از یک دوره زمانی نیاز داریم. الگوریتمها خودشان کاملاً مجزا کار میکنند و نمیتوانند خارج از جعبه دادههای خام که برای آنها مشخص شده است کار کنند. هر سیستم بینش اطلاعاتی هوشمند، اساساً شامل یک خط یا نقطهی سر-به-سر با استفاده از دادههای خام برای استفاده از تکنیکهای پردازش دادهها جهت گردآوری، پردازش و خواص ویژگیهای مهندسی از این دادهها است. ما معمولاً تکنیکهایی مانند مُدلهای آماری یا مدلهای یادگیری ماشین را برای مدل سازی بر روی این ویژگیها استفاده میکنیم و در صورت لزوم برای استفاده آنها در آینده بر اساس مشکلاتی که میتوان به آنها اشاره کرد به صورت دستی حل میشوند. به طور معمول یک سامانهی یادگیری ماشین مبتنی بر «فرایندهای استاندارد صنعت متقابل برای دادهکاوی» در زیر نشان داده شده است. به دست آوردن دادههای خام و ساختن مُدل بر روی این دادهها به طور مستقیم میتواند به عنوان عملی بیمورد تلقی شود، زیر ما نتایج و کارایی مورد نظر را نمیگیریم و همچنین الگوریتمها خود به طور خودکار ویژگی معنی دار از دادههای خامِ ساده را به صورت خودکار نمایش نمیدهند. جنبهی تهیه دادها در شکل بالا ذکر شده است، جایی که ما متودولوژیهای مختلفی را برای استخراج ویژگیها یا ویژگیهای معنی دار از دادههای خامِ پس از تجزیه و تحلیل مورد نیاز از پیش رونده و پیش پردازش برخورد میکنیم. مهندسی ویژگی یک هنر و همچنین یک عِلم است و به همین دلیل دانشمندانِ دادهها اغلب ۷۰٪ از زمان خود را در مرحله آماده سازی دادهها قبل از فازِ مُدل سازی صرف میکنند. این به ما درکِ (بینشِ) این را میدهد که چرا ویژگی مهندسی یک فرایند تبدیل اطلاعات (دادهها) به یک ویژگی به عنوان ورودی برای مُدلهای یادگیری ماشین عمل میکند. یعنی آن ویژگی با کیفیتِ خوب در بهبود عملکرد کلی و دقت مُدل کمک میکند. ویژگی ها نیز به سوالات اصلی و اساسی بسیار وابسته هستند. بنابراین، حتی ممکن است کار یادگیری ماشین در سناریوهای متفاوت مانند طبقهبندی رویدادهای IoT به رفتارهای عادی و غیر طبیعی یا طبقهبندی احساسات مشتری، ویژگیهای استخراج شده در هر سناریو بسیار متفاوت از یکدیگر عمل کند. ویژگیها چه چیزهایی هستند؟ یک ویژگی، به طور معمول، یک نمایش خاص در رأس دادههای خام است که خصوصیات قابل اندازهگیری آن به صورت منحصربفرد (خصوصی) است. که معمولاً در یک ستون از یک مجموعه داده نقش بسته اند. با توجه به یک مجموعهای از دادههای دو بعدی، هر مشاهده توسط یک ردیف و هر ویژگی توسط یک ستون نشان داده میشود که یک مقدار خاص برای مشاهده دارد. بنابراین، مانند مثال در شکل بالا، هر سطر به طور خاص یک ویژگی از بُردار را نشان میدهد و همه آنها مجموعهای از ویژگیها در همه مشاهدات به شمار میآیند، همچنین یک ماتریس ویژگی دو بُعدی است، که به عنوان یک مجموعهای از ویژگیها شناخته میشود. این شبیه به قاب دادهها یا صفحات گستردهای است که داده های دو بعدی را نشان میدهند. به طور معمول، الگوریتمهای یادگیری ماشین با این ماتریسهای عددی یا تانسورها کار میکنند. از این رو بیشترین تکنیکهای ویژگیهای مهندسی تبدیل دادههای خام به عنوان نمایندهای از دادههایی که میتوانند توسط این الگوریتم ها قابل فهم و درک باشند را انجام میدهد. ویژگیها میتوانند از دو نوع اصلی بر اساس مجموعه دادهها باشند. ویژگیهای خام (خالص) ذاتی مستقیماً از مجموعه دادهها و بدون دستکاری اطلاعات و یا مهندسی اضافی به دست میآیند. ویژگیهای مشتق شده معمولاً از ویژگیهای مهندسی به دست میآیند، جایی که ویژگیهای دادههای موجود را از آن استخراج میکنیم. مهندسی ویژگیها دادههای عددی معمولاً دادهها را به شکل ارزشهای اسکالِر نشان میدهند که مشاهدات، ضبط دادهها یا اندازه گیری آنها را نشان میدهد. منظور ما در اینجا دادههای عددی به عنوان دادههای مستمر است نه گُسَسته که به طور معمول به عنوان اطلاعات طبقه بندی شده ارائه میشوند. دادههای عددی میتوانند به عنوان یک بُردار از مقادیر نشان داده شود که هر مقدار یا موجودیت بُردار میتواند خود یک ویژگی خاص را نشان دهد. عدد صحیح (Integer) و شناور (Float) رایج ترین و به طور گستردهای از انواع دادههای عددی برای دادههای عددی مُداوم استفاده میشوند. حتی داده های عددی میتوانند به طور مستقیم به مُدل های یاد گیری ماشین انتقال یابند. شما برای هر یک از سِناریوهای مربوطه نیاز به ویژگیهایِ مهندسی دارید که مربوط به مشکلات و حوزهی مرتبط با آنها برای ساخت یک مُدل است. از این رو، نیاز به مهندسی ویژگیها هنوز هم در جای خود باقی است.