C++17 با معرفی یک
سازوکار جدید و انعطافپذیر برای جستجوی الگو در محدودههای داده، تحولی
اساسی در این حوزه ایجاد کرد. هستهی این تحول، تابع std::search با امضای جدیدی است که بهجای دریافت دو محدوده (محدودهی جستجو و الگو)، یک شیء جستجوگر (Searcher) دریافت میکند .
این تغییر ظاهراً ساده، در واقع دریچهای به دنیای الگوریتمهای پیشرفتهی
جستجو گشوده است و به برنامهنویسان اجازه میدهد تا از کارآمدترین روشها
برای یافتن یک الگو در یک متن طولانی استفاده کنند، بدون اینکه نیازی به
پیادهسازی دستی آنها داشته باشند.
جستجوگرهای استاندارد: سه ابزار قدرتمند
کتابخانهی استاندارد C++17 سه نوع جستجوگر مختلف را ارائه میدهد که هر کدام برای سناریوی خاصی بهینهسازی شدهاند و همگی در هدر <functional> تعریف شدهاند :
default_searcher
std::default_searcher یک جستجوگر عمومی است که عملیات جستجو را به پیادهسازی استاندارد و سنتی std::search واگذار میکند .
این جستجوگر، انتخاب پیشفرض و سادهای است که در مواردی که الگوی جستجو
کوتاه است یا دادهها حجم کمی دارند، عملکرد قابلقبولی ارائه میدهد. با
این حال، مزیت اصلی دو جستجوگر دیگر در کارایی بسیار بالاتر آنها برای
الگوهای بلندتر و مجموعهدادههای بزرگتر نمایان میشود.
boyer_moore_searcher
std::boyer_moore_searcher پیادهسازی استاندارد از الگوریتم معروف بویِر-مور (Boyer-Moore) است .
این الگوریتم هوشمند، جستجو را از انتهای الگو به سمت ابتدای آن انجام
میدهد و با استفاده از جدولهای پرش (Skip Tables)، از مقایسههای
غیرضروری جلوگیری میکند. بهعنوان مثال، اگر حرف انتهایی الگو در متن با
حرفی مطابقت نداشته باشد که در کل الگو وجود ندارد، الگوریتم میتواند
بهیکباره چندین کاراکتر را رد کند و سرعت جستجو را بهطور چشمگیری افزایش
دهد. این جستجوگر به یک تابع درهمسازی (Hash) برای کارایی بیشتر نیاز دارد که بهطور پیشفرض از std::hash استفاده میکند .
boyer_moore_horspool_searcher
std::boyer_moore_horspool_searcher پیادهسازی سادهتری از الگوریتم بویِر-مور است که به هورسپول (Horspool) معروف است .
این نسخه، تنها از جدول پرش مبتنی بر حرف آخر الگو استفاده میکند و در
نتیجه حافظهی کمتری مصرف میکند و برای بسیاری از کاربردهای عملی، عملکردی
بسیار نزدیک به نسخهی کامل بویِر-مور دارد، درحالیکه پیادهسازی سبکتری
دارد.
نحوهی استفاده و ملاحظات کلیدی
استفاده از این جستجوگرها بسیار ساده و شهودی است. بهجای ارسال محدودهی الگو به std::search، یک شیء جستجوگر ساخته شده و به تابع ارسال میشود . با این حال، نکات مهمی در استفاده از آنها وجود دارد:
نیاز به تکرارگرهای تصادفی: هر دو جستجوگر بویِر-مور و هورسپول، برای کارایی بالا نیاز به تکرارگرهای با دسترسی تصادفی (RandomAccessIterator) دارند . این بدان معناست که نمیتوان از آنها برای کانتینرهایی مانند std::list یا std::forward_list استفاده کرد.
پیشپردازش الگو: این جستجوگرها در زمان ساخت، الگو را پیشپردازش (Preprocess) میکنند و ساختارهای دادهی داخلی مانند جدولهای پرش را میسازند .
بنابراین اگر قصد دارید یک الگو را در چندین متن مختلف جستجو کنید، بهتر
است یک بار شیء جستجوگر را ساخته و سپس از آن برای جستجو در متون مختلف
استفاده کنید تا سربار پیشپردازش تنها یک بار پرداخت شود. در صورت کمبود
حافظه، این جستجوگرها ممکن است استثنای std::bad_alloc پرتاب کنند .
پشتیبانی در کامپایلرها: یکی از نکات مهم، وضعیت پشتیبانی کامپایلرها از این ویژگی است. برای مثال، برخی از نسخههای قدیمی اپل کلنگ (Apple Clang) از std::boyer_moore_searcher پشتیبانی نمیکردند ، بنابراین بهتر است پیش از استفاده گسترده، از پشتیبانی کامپایلر هدف اطمینان حاصل کنید.
جمعبندی
C++17 با معرفی جستجوگرهای default_searcher، boyer_moore_searcher و boyer_moore_horspool_searcher،
امکان استفاده از الگوریتمهای پیشرفتهی جستجو را بهصورت استاندارد و
کارآمد فراهم کرده است. انتخاب بین این سه جستجوگر به نیاز شما بستگی دارد:
default_searcher برای حالتهای ساده و عمومی، boyer_moore_horspool_searcher برای تعادل بین عملکرد و مصرف حافظه، و boyer_moore_searcher برای سناریوهایی که حداکثر سرعت جستجو اهمیت دارد، مناسبترین گزینهها هستند.
کلیدواژه ها : std::search-الگوریتم جستجو در C++17-std::default_searcher-std::boyer_moore_searcher-std::boyer_moore_horspool_searcher-جستجوی پیشرفته در C++-الگوریتم بوییر مور در C++-جستجوگرهای C++17-Searcher overload C++-مقایسه الگوریتمهای جستجو-بهبود عملکرد جستجو در C++-پیشپردازش الگو در جستجو-std::search searcher-آموزش std::search-الگوریتم هورسپول در C++-جستجوی رشته در C++17
