c++ - tutorial - সি++ বই




কিভাবে আধুনিক সি++ মধ্যে ক্লাসিক বাছাই আলগোরিদিম বাস্তবায়ন? (2)

আলগোরিদিম বিল্ডিং ব্লক

আমরা স্ট্যান্ডার্ড লাইব্রেরি থেকে আলগোরিদিম বিল্ডিং ব্লক একত্রিত করে শুরু করি:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next
  • non-member std::begin() / std::end() পাশাপাশি std::next() এর ইটারারেটর সরঞ্জামগুলি কেবলমাত্র সি ++ 11 এবং এর বাইরে উপলব্ধ। সি ++ 98 এর জন্য, এগুলি নিজেরাই লিখতে হবে। Boost.Range থেকে boost::begin() / boost::end() , এবং Boost.Utility থেকে boost::next() বিকল্পগুলি রয়েছে।
  • std::is_sorted অ্যালগরিদম শুধুমাত্র C ++ 11 এবং এর জন্য উপলব্ধ। সি ++ 98 এর জন্য এটি std::adjacent_find এবং হাতের লেখা লিখিত ফাংশন অবজেক্টের ক্ষেত্রে প্রয়োগ করা যেতে পারে। Boost.Algorithm এছাড়াও একটি বিকল্প প্রদান boost::algorithm::is_sorted বিকল্প হিসাবে।
  • std::is_heap অ্যালগরিদম শুধুমাত্র C ++ 11 এবং এর জন্য উপলব্ধ।

Syntactical গুডিজ

C ++ 14 ফর্ম std::less<> এর স্বচ্ছ তুলনাকারীগুলিকে সরবরাহ করে যা তাদের আর্গুমেন্টগুলিতে polymorphically কাজ করে। এটি একটি ইটারারেটর টাইপ প্রদান করা এড়িয়ে চলছে। এটি সি ++ 11 এর ডিফল্ট ফাংশন টেমপ্লেট আর্গুমেন্টগুলির সাথে সমন্বয় হিসাবে ব্যবহার করা যেতে পারে যা < যেমন তুলনা করে এবং ব্যবহারকারীর সংজ্ঞায়িত তুলনা ফাংশন বস্তু আছে এমন আলগোরিদিমগুলি সাজানোর জন্য একটি একক ওভারলোড তৈরি করতে ব্যবহার করে।

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

C ++ 11 এ, একটি পুনরাবৃত্তিযোগ্য টেমপ্লেট উপনামটি একটি ইটারারের মান টাইপ বের করার জন্য সংজ্ঞায়িত করতে পারে যা সাজানোর অ্যালগরিদমগুলির স্বাক্ষরগুলিতে ছোটখাট ক্লাস্টার যোগ করে:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

সি ++ 98 তে, দুইটি ওভারলোড লিখতে হবে এবং typename xxx<yyy>::type সিনট্যাক্স ব্যবহার করতে হবে

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}
  • আরেকটি সিনট্যাক্টিক নিকটিটি হল সি ++ 14 পলিমোফিক ল্যাম্বাসাসের মাধ্যমে ব্যবহারকারী-সংজ্ঞায়িত তুলনাকারীগুলিকে মোড়ানো (ফাংশন টেমপ্লেট আর্গুমেন্টগুলির মতো কমে যাওয়া auto প্যারামিটারগুলির সাহায্যে)।
  • সি ++ 11 শুধুমাত্র মোনোমর্ফিক লেম্বডাস রয়েছে, যা উপরের টেমপ্লেট উপনাম value_type_t ব্যবহারের প্রয়োজন।
  • সি ++ 98 তে, একটিকে একটি স্ট্যাণ্ডলোন ফাংশন বস্তু লিখতে হবে অথবা verbose std::bind1st / std::bind2nd / std::not1 type syntax এ অবলম্বন করতে হবে।
  • Boost.Bind boost::bind সাথে উন্নত boost::bind এবং _1 / _2 স্থানধারক সিনট্যাক্স।
  • C ++ 11 এবং তারপরেও std::find_if_not , যেখানে C ++ 98 এর জন্য std::find_if একটি ফাংশন বস্তুর কাছাকাছি std::not1

সি ++ স্টাইল

এখনও কোন সাধারণ গ্রহণযোগ্য সি ++ 14 শৈলী নেই। ভাল বা খারাপের জন্য, আমি স্কট মায়ার্স এর খসড়া কার্যকরী আধুনিক সি ++ এবং হেরব সটারের পুনঃপ্রবর্তিত GotW অনুসরণ করি । আমি নিম্নলিখিত শৈলী সুপারিশ ব্যবহার করুন:

  • হেরব Sutter এর "Almost সর্বদা অটো" এবং স্কট Meyers এর "স্বতঃস্ফূর্ত ধরনের ঘোষণা ঘোষণা করুন" সুপারিশ, যার জন্য সংক্ষিপ্তত্ব নিরস্ত করা হয়, যদিও তার স্বচ্ছতা কখনও কখনও disputed
  • স্কট মেয়ের্সের "পার্থক্য () এবং {} বস্তুগুলি তৈরি করার সময়" এবং ভাল পুরোনো বন্ধনীযুক্ত সূচনা () জেনারেটিক কোডগুলিতে সাইড-ধাপে সর্বাধিক-ভেক্সিং-পার্স সমস্যাগুলির পরিবর্তে ব্রেসড-ইনিশিয়ালাইজেশান {} নির্বাচন করুন।
  • স্কট মায়ার্স এর "টাইপডফের জন্য উদীয়মান ঘোষণাগুলি পছন্দ করুন" । টেমপ্লেটগুলির জন্য এটি যে কোনওভাবেই আবশ্যক, এবং typedef পরিবর্তে এটি সর্বত্র ব্যবহার করে সময় সঞ্চয় করে এবং সামঞ্জস্য যোগ করে।
  • আমি কিছু সাজানোর for (auto it = first; it != last; ++it) প্যাটার্ন ব্যবহার for (auto it = first; it != last; ++it) , যাতে লুপ ইনভেরিয়েন্টটি ইতিমধ্যে সাজানো উপ-রেঞ্জগুলির জন্য চেক করার অনুমতি দেয়। উত্পাদন কোডে, while (first != last) এবং একটি ++first লুপের ভিতরে কোথাও ++first কিছুটা ভাল হতে পারে।

নির্বাচন সাজানোর

নির্বাচন সাজানোর যেকোনো উপায়ে ডেটা O(N²) হয় না, তাই এটির রানটাইম সর্বদা O(N²) । যাইহোক, নির্বাচন সাজানোর swaps সংখ্যা কমানোর সম্পত্তি আছে। অ্যাপ্লিকেশনগুলিতে যেখানে সোয়াপিং আইটেমগুলির দাম বেশি হয়, নির্বাচন সাজানোর খুব ভালভাবে পছন্দসই অ্যালগরিদম হতে পারে।

স্ট্যান্ডার্ড লাইব্রেরি ব্যবহার করে এটি বাস্তবায়ন করতে, অবশিষ্ট সর্বনিম্ন উপাদানটি খুঁজতে std::min_element ব্যবহার করুন এবং iter_swap এটিকে স্থান থেকে iter_swap করতে:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

উল্লেখ্য যে selection_sort ইতিমধ্যে প্রক্রিয়াভুক্ত পরিসীমা [first, it) তার লুপ invariant হিসাবে সাজানো। std::sort এর র্যান্ডম অ্যাক্সেস ইটারারেটরগুলির তুলনায় ন্যূনতম প্রয়োজনীয়তা এটিরেটরগুলিকে এগিয়ে নিয়ে যায়

বাদ দেওয়া বিবরণ :

  • নির্বাচন সাজানোর একটি প্রাথমিক পরীক্ষার সাথে অপ্টিমাইজ করা যেতে পারে if (std::distance(first, last) <= 1) return; (অথবা ফরওয়ার্ড / ডাইরেক্টিকাল ইটারারেটরের জন্য: if (first == last || std::next(first) == last) return; )।
  • বিডেরাকশনাল ইটারারেটরগুলির জন্য , উপরের পরীক্ষাটিকে অন্তর্বর্তী [first, std::prev(last)) উপর একটি লুপ দিয়ে মিলিত করা যেতে পারে, কারণ শেষ উপাদানটিকে অবশিষ্ট অবশিষ্ট উপাদান বলে নিশ্চিত করা হয় এবং কোনও সোয়াপের প্রয়োজন হয় না।

সন্নিবেশ সাজানোর

যদিও এটি O(N²) সবচেয়ে খারাপ-কেসের সময়ের সাথে প্রাথমিক সোর্সিং অ্যালগরিদমগুলির মধ্যে একটি, তবে সন্নিবেশ O(N²) পছন্দসই অ্যালগরিদম হয় যখন তথ্যটি প্রায় সাজানো হয় (কারণ এটি অভিযোজিত ) বা সমস্যাটির আকার ছোট (কারণ এটির কম উপরি). এই কারণগুলির জন্য, এবং এটি স্থিতিশীল কারণ, উচ্চতর ওভারহেড ডিভাইড-এবং-বিজয় সাজানোর অ্যালগরিদমগুলির জন্য সন্নিবেশ বা দ্রুত সাজানোর মতো, সন্নিবেশ সাজানোর প্রায়শই পুনরাবৃত্তিমূলক বেস কেস (যখন সমস্যার আকার ছোট হয়) হিসাবে ব্যবহৃত হয়।

স্ট্যান্ডার্ড লাইব্রেরির সাথে insertion_sort প্রয়োগ করতে, বর্তমান উপাদানটি যেখানে যেতে হবে সেই অবস্থানটি খুঁজে পেতে std::upper_bound ব্যবহার করুন এবং অবশিষ্ট উপাদানগুলিকে ইনপুট পরিসরের উপরে std::upper_bound জন্য std::upper_bound ব্যবহার করুন:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

উল্লেখ্য যে insertion_sort ইতিমধ্যে প্রক্রিয়াভুক্ত পরিসীমা [first, it) তার লুপ invariant হিসাবে সাজানো। সন্নিবেশ সাজানোর এছাড়াও ফরওয়ার্ড iterators সঙ্গে কাজ করে।

বাদ দেওয়া বিবরণ :

  • সন্নিবেশ সাজানোর একটি প্রাথমিক পরীক্ষার সাথে অপ্টিমাইজ করা যেতে পারে if (std::distance(first, last) <= 1) return; (অথবা ফরওয়ার্ড / ডাইরেক্টিকাল ইটারারেটরের জন্য: if (first == last || std::next(first) == last) return; ) এবং অন্তর্বর্তী [std::next(first), last) একটি লুপ [std::next(first), last) , কারণ প্রথম উপাদান জায়গায় হতে নিশ্চিত করা এবং একটি ঘূর্ণন প্রয়োজন হয় না।
  • বিডেরাকশনাল ইটারারেটরের জন্য , সন্নিবেশ বিন্দুটি খুঁজে পেতে বাইনারি অনুসন্ধানটি আদর্শ লাইব্রেরীর std::find_if_not ব্যবহার করে বিপরীত রৈখিক অনুসন্ধানের মাধ্যমে প্রতিস্থাপিত হতে পারে।

চারটি লাইভ উদাহরণ ( C++14 , C++11 , সি ++ 98 এবং বুস্ট , C++98 ) নীচের অংশে:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();
  • র্যান্ডম ইনপুটগুলির জন্য এটি O(N²) তুলনা দেয়, তবে এটি প্রায়শই সাজানো ইনপুটগুলির জন্য O(N) তুলনাগুলির সাথে তুলনা করে। বাইনারি অনুসন্ধান সর্বদা O(N log N) তুলনা ব্যবহার করে।
  • ছোট ইনপুট রেঞ্জের জন্য, একটি রৈখিক অনুসন্ধানের আরও ভাল মেমরি এলাকা (ক্যাশে, প্রিফচিং) বাইনারি অনুসন্ধানকে আয়ত্ত করতে পারে (অবশ্যই এটি অবশ্যই পরীক্ষা করে দেখুন)।

দ্রুত সাজানোর

সাবধানে প্রয়োগ করা হলে, দ্রুত সাজানোর জোরালো এবং O(N log N) প্রত্যাশিত জটিলতা আছে, তবে O(N²) সবচেয়ে খারাপ-কেস জটিলতা যা প্রতিকূলভাবে নির্বাচিত ইনপুট ডেটা দিয়ে ট্রিগার করা যেতে পারে। যখন একটি স্থিতিশীল সাজানোর প্রয়োজন হয় না, দ্রুত সাজানোর একটি চমৎকার সাধারণ উদ্দেশ্য সাজানোর হয়।

এমনকি সহজতম সংস্করণের জন্য, দ্রুত শ্রেণীকরণ অন্যান্য ক্লাসিক সাজানোর অ্যালগরিদমগুলির তুলনায় স্ট্যান্ডার্ড লাইব্রেরির প্রয়োগের জন্য আরও জটিল। নিচের পদ্ধতিটি ইনপুট সীমা [first, last) এর মধ্যম উপাদানটি পিভট হিসাবে সনাক্ত করার জন্য কিছু ইটারারেটর ইউটিলিটি ব্যবহার করে, তারপর std::partition (যা O(N) ) থেকে দুটি কল ব্যবহার করে যথাক্রমে নির্বাচিত পিভটের চেয়ে ছোট, সমান এবং বৃহত্তর উপাদানগুলির সেগমেন্টগুলিতে ব্যাপ্ত। অবশেষে পিভটের তুলনায় ছোট এবং বড় উপাদানগুলির সাথে দুটি বাহ্যিক অংশগুলি ক্রমানুসারে সাজানো হয়:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

যাইহোক, দ্রুত সাজানোর সঠিক এবং কার্যকর পেতে বরং চতুর, প্রতিটি উপরে পদক্ষেপ যত্নসহকারে চেক এবং উত্পাদন স্তর কোড জন্য অপ্টিমাইজ করা আছে। বিশেষ করে, O(N log N) জটিলতার জন্য, পিভটটি ইনপুট ডেটাগুলির একটি সুষম বিভাজনে রূপান্তরিত হতে পারে, যা O(1) পিভটের জন্য সাধারণভাবে গ্যারান্টিযুক্ত করা যায় না, তবে কোনটি যদি পিভট সেট করে তবে এটি নিশ্চিত করা যাবে ইনপুট পরিসীমা O(N) মধ্যম হিসাবে।

বাদ দেওয়া বিবরণ :

  • উপরের প্রয়োগটি বিশেষভাবে বিশেষ ইনপুটগুলির জন্য ঝুঁকিপূর্ণ, যেমন এটি " অঙ্গ পাইপ " ইনপুট 1, 2, 3, ..., N/2, ... 3, 2, 1 জন্য O(N^2) জটিলতা আছে। মাঝারি সবসময় সব অন্যান্য উপাদান চেয়ে বড় কারণ)।
  • ইনপুট রেন্ডার রক্ষীদের কাছ থেকে এলোমেলোভাবে নির্বাচিত উপাদানগুলি থেকে median-of-3 পিভট নির্বাচন প্রায় সাজানো ইনপুটগুলির বিরুদ্ধে যা জটিলতার অন্যথায় O(N^2) বিপর্যয় ঘটায়।
  • 3-উপায় বিভাজন ( বিভাজনগুলির তুলনায় ছোট, সমান এবং বড় উপাদানগুলিকে আলাদা করে) std::partition দুটি কল দ্বারা দেখানো হয়েছে এই ফলাফলটি অর্জনের জন্য সবচেয়ে কার্যকরী O(N) অ্যালগরিদম নয়।
  • র্যান্ডম অ্যাক্সেস ইটারারেটরগুলির জন্য , একটি নিশ্চিত O(N log N) জটিলতাটি std::nth_element(first, middle, last) ব্যবহার করে মাঝারি পিভট নির্বাচন মাধ্যমে অর্জন করা যেতে পারে, এর পরে quick_sort(first, middle, cmp) quick_sort(middle, last, cmp) quick_sort(first, middle, cmp) এবং quick_sort(middle, last, cmp) quick_sort(first, middle, cmp) quick_sort(middle, last, cmp)
  • এই গ্যারান্টিটি একটি খরচে আসে তবে, কারণ std::nth_element এর O(N) জটিলতার স্থির ফ্যাক্টর O(1) এর মাঝারি-এর-3 std::nth_element জটিলতার চেয়ে আরও ব্যয়বহুল হতে পারে O(N) std::partition কল করুন (যা ডেটাতে একটি ক্যাশে-বান্ধব একক ফরোয়ার্ড পাস)।

সাজানোর মার্জ করুন

যদি O(N) অতিরিক্ত স্থানটি কোনও উদ্বেগের বিষয় না থাকে, তবে সাজানোর বিয়োগটি একটি চমৎকার পছন্দ: এটি শুধুমাত্র স্থিতিশীল O(N log N) সাজানো অ্যালগরিদম বাছাই করে।

স্ট্যান্ডার্ড অ্যালগরিদম ব্যবহার করে এটি বাস্তবায়ন করা সহজ: ইনপুট পরিসরের মাঝামাঝি [first, last) সনাক্ত করতে কিছু ইটারারেটর ইউটিলিটি ব্যবহার করুন এবং std::inplace_merge দুটি পুনরাবৃত্তিযুক্ত সাজানো অংশগুলি একত্রিত করুন:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

std::inplace_merge ইটারারেটর প্রয়োজন, বোতল হচ্ছে std::inplace_merge । উল্লেখ্য যে লিঙ্ক তালিকা বাছাই করার সময়, একত্রিত মজুরি শুধুমাত্র O(log N) অতিরিক্ত স্থান (পুনরাবৃত্তির জন্য) প্রয়োজন। পরের অ্যালগরিদম std::list<T>::sort স্ট্যান্ডার্ড লাইব্রেরীতে সাজানো হয়।

হিপ সাজানোর

হিপ সাজানোর বাস্তবায়ন করা সহজ, একটি O(N log N) ইন-স্থানে সাজানোর সঞ্চালন করে তবে স্থিতিশীল নয়।

প্রথম লুপ, O(N) "heapify" ফেজ, অ্যারেটিকে হিপ অর্ডারে রাখে। দ্বিতীয় লুপ, O(N log N ) "সাজানোর" ফেজ, বার বার সর্বোচ্চ নিষ্কাশন এবং হিপ অর্ডার পুনরুদ্ধার। স্ট্যান্ডার্ড লাইব্রেরি এই অত্যন্ত সহজবোধ্য করে তোলে:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

std::make_heap এবং std::sort_heap ব্যবহার করার জন্য এটি "প্রতারণার" বিবেচনায় আপনি এক স্তরের গভীরে যেতে পারেন এবং std::make_heap এবং std::sort_heap এই ফাংশনগুলি লিখতে পারেন:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

স্ট্যান্ডার্ড লাইব্রেরী push_heap এবং pop_heap উভয় জটিলতা O(log N) হিসাবে উল্লেখ করে। উল্লেখ্য যে পরিসরের বাইরের লুপটি [first, last) make_heap জন্য O(N log N) জটিলতার make_heap , যখন std::make_heap শুধুমাত্র O(N) জটিলতা রয়েছে। সামগ্রিক O(N log N) heap_sort জটিলতা জটিলতার জন্য এটি কোন ব্যাপার নয়।

বিবরণ বাদ দেওয়া হয়েছে : O(N) make_heap বাস্তবায়ন

পরীক্ষামূলক

এখানে চারটি লাইভ উদাহরণ ( C++14 , C++11 , সি ++ 98 এবং বুস্ট , C++98 ) বিভিন্ন ধরণের পাঁচটি অ্যালগরিদম পরীক্ষা করছে (সম্পূর্ণ বা কঠোর হওয়া মানে নয়)। শুধু লকটিতে বিশাল পার্থক্যগুলি লক্ষ্য করুন: সি ++ 11 / সি ++ 14 প্রায় 130 টি লক, সি ++ 98 এবং বুস্ট 190 (+ 50%) এবং সি ++ 98 এর চেয়ে বেশি 270 (+ 100%)।

std::nth_element + স্ট্যান্ডার্ড স্ট্যান্ডার্ড লাইব্রেরী থেকে std::sort algorithm (এবং তার চাচাতো ভাইরাসের std::partial_sort এবং std::nth_element ) বেশিরভাগ বাস্তবায়নের মধ্যে জটিল এবং হাইব্রিড সংযোজন আরও প্রাথমিক সাজানোর অ্যালগরিদম যেমন নির্বাচন সাজানোর, সন্নিবেশ সাজানোর, দ্রুত সাজানোর , সাজানোর সাজান, বা সাজানোর সাজান।

https://codereview.stackexchange.com/ এখানে এই এবং ক্লাসিক সাজানোর অ্যালগরিদমগুলি বাস্তবায়নের অন্যান্য দিকগুলির সম্পর্কিত বাগ, জটিলতা এবং অন্যান্য দিক সম্পর্কিত বোন সাইটগুলিতে অনেক প্রশ্ন রয়েছে। প্রস্তাবিত বেশিরভাগ প্রয়োগগুলি কাঁচা লুপ, সূচী ম্যানিপুলেশন এবং কংক্রিটের ধরনগুলি ব্যবহার করে এবং সঠিকতা এবং দক্ষতার পরিপ্রেক্ষিতে বিশ্লেষণ করার জন্য সাধারণত অ-তুচ্ছ।

প্রশ্ন : উপরে উল্লেখিত ক্লাসিক সাজানোর অ্যালগরিদমগুলি কীভাবে আধুনিক সি ++ ব্যবহার করে প্রয়োগ করা যেতে পারে?

  • কোন কাঁচা loops , কিন্তু <algorithm> থেকে স্ট্যান্ডার্ড লাইব্রেরি এর অ্যালগরিদম বিল্ডিং ব্লক মিশ্রন
  • ইন্টেরেটর ইন্টারফেস এবং সূচক ম্যানিপুলেশন এবং কংক্রিট ধরনের পরিবর্তে টেমপ্লেট ব্যবহার
  • সি ++ 14 শৈলী , সম্পূর্ণ স্ট্যান্ডার্ড লাইব্রেরি সহ, পাশাপাশি সিনট্যাক্টিক গোলমাল reducers যেমন auto , টেমপ্লেট aliases, স্বচ্ছ তুলনাকারী এবং polymorphic lambdas।

নোট :

  • শর্টিং অ্যালগরিদমগুলির প্রয়োগের উপর আরও রেফারেন্সের জন্য Wikipedia , রোজেটা কোড বা http://www.sorting-algorithms.com/
  • শান প্যারেন্টের কনভেনশনগুলির (স্লাইড 39) অনুসারে, একটি কাঁচা লুপ অপারেটরের সাথে দুটি ফাংশন গঠনের চেয়ে লুপের for দীর্ঘতর। সুতরাং f(g(x)); বা f(x); g(x); f(x); g(x); বা f(x) + g(x); কাঁচা loops না, এবং neither select_sort এবং insertion_sort মধ্যে loops হয় না।
  • আমি C ++ 14 হিসাবে বর্তমান C ++ 1y, এবং C ++ 98 এবং C ++ 03 উভয় C ++ 98 হিসাবে চিহ্নিত করার জন্য স্কট মেয়ের্সের পরিভাষা অনুসরণ করি, তাই এর জন্য আমাকে শিখাও না।
  • @ মাহেরদাদ এর মতামতগুলিতে প্রস্তাবিত হিসাবে, আমি উত্তরটির শেষে লাইভ উদাহরণ হিসাবে চারটি বাস্তবায়ন প্রদান করি: C ++ 14, C ++ 11, C ++ 98 এবং Boost এবং C ++ 98।
  • উত্তর নিজেই সি ++ 14 পদে উপস্থাপন করা হয়। যেখানে প্রাসঙ্গিক, আমি সিন্ট্যাকটিক এবং লাইব্রেরি পার্থক্য নির্দেশ করে যেখানে বিভিন্ন ভাষা সংস্করণ ভিন্ন।

মূলত কোড পর্যালোচনা পাওয়া অন্য ছোট এবং বরং মার্জিত এক। আমি ভাগ ভাগ মূল্য ছিল।

সাজানোর গণনা

যদিও এটি বরং বিশেষ, সাজানোর গণনা একটি সাধারণ পূর্ণসংখ্যা সাজানো অ্যালগরিদম এবং প্রায়শই দ্রুত হতে পারে তবে সাজানোর পূর্ণসংখ্যাগুলির মান খুব বেশি দূরে নয়। উদাহরণস্বরূপ, 0 এবং 100 এর মধ্যে থাকা এক মিলিয়নের পূর্ণসংখ্যা সংগ্রহ করার জন্য যদি কখনও কখনও এটি আদর্শ হয় তবে এটি আদর্শ।

স্বাক্ষরিত এবং স্বাক্ষরিত পূর্ণসংখ্যার সাথে কাজ করে এমন একটি খুব সাধারণ গণনা সাজানোর বাস্তবায়ন করার জন্য, সংগ্রহের জন্য সংগ্রহের মধ্যে ক্ষুদ্রতম এবং সর্বশ্রেষ্ঠ উপাদানগুলি খুঁজে বের করতে হবে; তাদের পার্থক্য বরাদ্দ করতে গণনা অ্যারের আকার বলতে হবে। তারপর, সংগ্রহের মাধ্যমে একটি দ্বিতীয় পাস প্রতিটি উপাদান ঘটনার সংখ্যা গণনা করা হয়। অবশেষে, আমরা আসল সংগ্রহে প্রতি পূর্ণসংখ্যাটির প্রয়োজনীয় সংখ্যাটি আবার লিখি।

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

যদিও এটি শুধুমাত্র তখনই কার্যকর, যখন সংখ্যার পূর্ণসংখ্যাগুলির পরিসরটি ছোট বলে মনে হয় (সাধারণত সাজানোর সংগ্রহের আকারের চেয়ে বড় নয়), গণনা অনুসারে আরও বেশি জেনারিক এটি তার সেরা ক্ষেত্রে ধীর করে তুলবে। যদি পরিসীমাটি ছোট হতে না হয়, তবে অন্য অ্যালগরিদম যেমন একটি রডিক্স সাজানোর , ska_sort বা spreadsort ব্যবহার করা যেতে পারে।

বাদ দেওয়া বিবরণ :

  • আমরা অ্যালগরিদম দ্বারা গৃহীত মানের std::minmax_element পাশাপাশি প্রথম std::minmax_element সংগ্রহের মাধ্যমে প্যারামিটার হিসাবে সীমা অতিক্রম করতে পারতাম। এটি একটি কার্যকরভাবে-ছোট পরিসীমা সীমা অন্য উপায়ে পরিচিত হলে এটি আরও দ্রুততর অ্যালগরিদম তৈরি করবে। (এটি সঠিক হতে হবে না; ধ্রুবক 0 থেকে 100 পাস করা এক মিলিয়ন উপাদানের চেয়েও বেশি উত্তরের চেয়ে আরও ভাল। এটি সত্যের সীমানার 1 থেকে 95 বলে মনে করা হয়। 0 থেকে 1000 এমনকি এটি মূল্যবান হবে; অতিরিক্ত উপাদান শূন্য সঙ্গে একবার লেখা হয় এবং একবার পড়া হয়)।

  • ফ্লাইতে ক্রমবর্ধমান counts একটি পৃথক প্রথম পাস এড়াতে অন্য উপায়। প্রতিবার যখন এটি বৃদ্ধি করতে counts তখন counts দ্বিগুণ করে সাজানো উপাদানটি প্রতি (O) 1 বার সময় দেয় (প্রমাণের জন্য হ্যাশ টেবিল সন্নিবেশ মূল্য বিশ্লেষণটি দেখুন যা সূচকীয় উত্থানটি কী)। নতুন max std::vector::resize জন্য বৃদ্ধি পাচ্ছে std::vector::resize নতুন শূন্য উপাদান যোগ করার জন্য। ফ্লাইতে min পরিবর্তন করা এবং সামনে নতুন শূন্য উপাদানগুলি সন্নিবেশ করাতে পারে ভেক্টর std::copy_backward পরে std::copy_backward দিয়ে। তারপর std::fill নতুন উপাদান শূন্য std::fill

  • বৃদ্ধি বৃদ্ধি লুপ একটি হিস্টোগ্রাম হয়। যদি তথ্য অত্যন্ত পুনরাবৃত্তিমূলক হওয়ার সম্ভাবনা থাকে এবং বিন্দুর সংখ্যা ছোট, তবে একই বিনতে স্টোর / পুনরায় লোডের সিরিয়ালাইজেশান ডেটা নির্ভরতার বোতামটি হ্রাস করার জন্য একাধিক অ্যারেতে এটি অকার্যকর হতে পারে। এর অর্থ হল শুরুর দিকে শূন্যের বেশি সংখ্যক এবং শেষের দিকে লুপের আরো অনেক কিছু, তবে আমাদের CPU গুলির শতকরা 0 থেকে 100 সংখ্যাগুলির উদাহরণের জন্য এটি সর্বাধিক মূল্যবান হওয়া উচিত, বিশেষ করে যদি ইনপুটটি ইতিমধ্যে (আংশিকভাবে) সাজানো হতে পারে এবং একই সংখ্যা দীর্ঘ রান আছে।

  • উপরে অ্যালগরিদম ইন, আমরা প্রত্যেকটি উপাদান একই মান (যা ক্ষেত্রে সাজানোর সাজানো হয়) আছে যখন প্রাথমিকভাবে ফিরে একটি min == max চেক ব্যবহার করুন। কোনও অতিরিক্ত সময় নষ্ট না হওয়া পর্যন্ত সংগ্রহের চরম মূল্যগুলি খুঁজে বের করার সময় সংগ্রহটি ইতিমধ্যেই বাছাই করা হয়েছে কিনা তা সম্পূর্ণরূপে যাচাই করা সম্ভব। (যদি প্রথম পাসটি এখনও মিনি এবং সর্বোচ্চ আপডেট করার অতিরিক্ত কাজের সাথে সংযুক্ত থাকে)। তবে এই ধরনের অ্যালগরিদমটি স্ট্যান্ডার্ড লাইব্রেরীতে বিদ্যমান নয় এবং লেখার বাকিটিকে গণনা অনুসারে সাজানোর চেয়ে আরও ক্লান্তিকর হবে। এটা পাঠক জন্য ব্যায়াম হিসাবে বামে হয়।

  • যেহেতু অ্যালগরিদমটি কেবল পূর্ণসংখ্যা মানগুলির সাথে কাজ করে, তাই স্ট্যাটিক দাবিগুলি ব্যবহারকারীদের সুস্পষ্ট টাইপ ভুলগুলি করতে বাধা দেওয়ার জন্য ব্যবহার করা যেতে পারে। কিছু প্রসঙ্গে, std::enable_if_t সাথে একটি প্রতিস্থাপন ব্যর্থতা পছন্দ করা যেতে পারে।

  • যদিও আধুনিক সি ++ শান্ত, ভবিষ্যতে সি ++ এমনকি শীতল হতে পারে: কাঠামোগত বাইন্ডিং এবং রেঞ্জ TS এর কিছু অংশ অ্যালগরিদম এমনকি ক্লিনারও তৈরি করবে।






c++-faq