Module ১৪ · যে algorithm-গুলো প্রতি সপ্তাহেই লাগবে: accumulate থেকে nth_element

ভেতরের কথা: introselect, next_permutation-এর চারটা চাল, আর যে যোগফল ঘুরে যায়

Proপড়াlesson ৫ / ৯

Kenji-র একটা job 10,000,000টা sensor reading-এর মাঝের মানটা বের করে। sort দিয়ে Compiler Explorer-এ লেগেছিল 1.3 থেকে 2.5 second; nth_element দিয়ে প্রায় 0.1 second। একই রাতে ওর 100,000টা reading-এর যোগফল, যার প্রতিটা 100,000, বেরোল 1410065408।

আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…

ভেতরের কথা: introselect, next_permutation-এর চারটা চাল, আর যে যোগফল ঘুরে যায় এর ভেতরে কী আছে

GCC 12-এর নিজের next_permutation, লাইন ধরে ধরে
চারটা চাল, এক call-এ এক ধাপ করে
একটা call-এ গড়ে প্রায় 3টা তুলনা কেন
nth_element আসলে introselect
মেপে দেখা: introselect বনাম sort
partial_sort আসলে একটা heap
accumulate-এর loop, আর যে যোগফল wrap করে
Source-এ unique আর minmax_element
Performance lab: sort, nth_element আর partial_sort