ধাপ গোনা: তোমার লুপটা আসলে কত খরচ করে

যত অ্যালগরিদম তুমি জীবনে শিখবে, সবগুলোই আসলে একটা প্রশ্নেরই উত্তর: এই লাইনটা কতবার চলে? “এটা কি ফাস্ট” না, কারণ ওটা তোমার ল্যাপটপের ব্যাপার; বরং “কয়টা ধাপ”, কারণ ওটা ল্যাপটপ বদলালেও বদলায় না। এই পর্বে শুধু ওই একটা অভ্যাসই তোমাকে ধরিয়ে দেব, কারণ এটা না থাকলে সিরিজের বাকি কিছুই দাঁড়ায় না। কোড C++-এ, যেটা আমাদের জন্য মূলত C-এর সাথে একটা স্ট্যান্ডার্ড লাইব্রেরি, আর সেই লাইব্রেরিটা আমরা কাজে লাগাব।

চলো একদম ছোট একটা জায়গা থেকে শুরু করি। কোনো সংজ্ঞা দিয়ে না, কোনো গ্রিক অক্ষর দিয়েও না। একটা প্রোগ্রাম দিয়ে, যেটা কয়েকটা সংখ্যা যোগ করে।

#১. প্রথম প্রোগ্রাম, প্রথম প্রশ্ন

তোমাকে কতগুলো সংখ্যা দেওয়া হলো, বলা হলো এদের যোগফল বের করো।

long long total(const vector<int> &v) {
    long long sum = 0;
    for (int x : v)
        sum += x;
    return sum;
}

এখন একটাই প্রশ্ন আসল: sum += x লাইনটা কতবার চলে?

প্রতি সংখ্যার জন্য একবার। লিস্টে ১০টা সংখ্যা থাকলে ১০ বার, ১০ লাখ থাকলে ১০ লাখ বার। এটাকে একটা নিয়ম বানিয়ে ফেলো, আর তাতেই এমন একটা কথা বলে ফেললে যেটা দুনিয়ার প্রতিটা কম্পিউটারে সত্যি:

  steps  =  n

এখানে n মানে কয়টা সংখ্যা আছে। ব্যস, এটুকুই মূল ধারণা। সিরিজের বাকি সবকিছু এই এক ধারণাটাই আরও কঠিন প্রোগ্রামে খাটানো।

(স্ট্যান্ডার্ড লাইব্রেরিতে এটা এমনিতেই আছে, আর লুপটা গুনতে শিখে গেলে ওটাই ইউজ করা উচিত: #include <numeric> দিয়ে accumulate(v.begin(), v.end(), 0LL)। ভেতরে সেই একই n-ধাপের লুপই চলে, শুধু চোখের আড়ালে। ওই আড়ালে কী চলছে সেটা জানাই এই পর্বের কাজ।)

খেয়াল করো, আমরা কী করিনি। আমরা সময় মাপিনি। সময় মাপলে জানা যায় তোমার ল্যাপটপ কেমন, ডেটা সেন্টারে গরম পড়েছে কি না, ব্রাউজার খোলা ছিল কি না। গুনলে জানা যায় প্রোগ্রামটা কেমন।

#২. দ্বিতীয় প্রোগ্রাম, দেখতে একই কিন্তু আসলে না

এবার অন্য কাজ। সংখ্যার একটা লিস্ট দেওয়া হলো, প্রশ্ন: এমন কোনো জোড়া আছে কি যাদের যোগফল শূন্য?

সবাই প্রথমে যেটা লেখে, সেই সৎ চেষ্টাটা এখানে:

bool has_zero_pair(const vector<int> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && v[i] + v[j] == 0)
                return true;
    return false;
}

তুলনার লাইনটা কতবার চলে? i-এর প্রতি nটা মানের জন্য ভেতরের লুপ n বার চলে। মানে:

  steps  =  n × n  =  n²

কাগজে দুটো প্রোগ্রাম প্রায় একই রকম জটিল মনে হয়। কিন্তু খরচে এরা কাছাকাছিও না। সংখ্যা বসিয়ে দেখো:

শেষ সারিটা আরেকবার পড়ো। দশ লাখ ধাপ চোখের পলকে শেষ। কিন্তু এক লাখ কোটি ধাপ, খুব আশাবাদী হয়ে সেকেন্ডে একশো কোটি ধাপ ধরলেও, লাগে প্রায় সতেরো মিনিট। দেখতে একই কোড, একদিকে সতেরো মিনিট, আরেকদিকে কিছুই না।

এই জায়গাতেই অভ্যাসটা নিজের দাম তুলে নেয়। এজন্যই লেখার আগে আমরা গুনি।

#৩. যে হিসাবটা কনটেস্টে তোমাকে বাঁচাবে

আজকালকার হার্ডওয়্যার সেকেন্ডে মোটামুটি $10^8$ থেকে $10^9$ সাধারণ কাজ করতে পারে। কনটেস্টের সমস্যায় সাধারণত এক-দুই সেকেন্ডের টাইম লিমিট থাকে। তাই কাজের নিয়মটা দাঁড়ায়:

তোমার সমাধানের ধাপ দশ কোটির নিচে থাকা চাই।

এবার এর সাথে সমস্যায় দেওয়া ইনপুটের সাইজটা মিলিয়ে নাও, দেখবে সমস্যাটাই বলে দিচ্ছে কোন অ্যালগরিদম লাগবে। এই টেবিলটা এই পোস্টের সবচেয়ে কাজের জিনিস। আমি এখনো এটা দেখি।

যে সমস্যায় লেখা “n সর্বোচ্চ ২,০০,০০০”, সেটা সোজা কথায় বলে দিচ্ছে যে $n^2$ চলবে না, তোমাকে $n\log n$-এর আশপাশে কিছু খুঁজতে হবে। এটা সমস্যার ভেতরে লুকানো কোনো ইঙ্গিত না। এটাই সমস্যার আসল কথা।

#৪. ধাপগুলো কোথায় লুকিয়ে থাকে

লুপ চোখে দেখা গেলে গোনা সহজ। গড়বড় হয় সেসব ধাপে যেগুলো তুমি নিজে হাতে লেখোনি।

লাইব্রেরি কলের ভেতরে লুকানো লুপ। এটা দেখতে এক লাইন:

bool present(const vector<int> &v, int x) {
    return find(v.begin(), v.end(), x) != v.end();   // v-এর ভেতর হাঁটে: n ধাপ পর্যন্ত
}

কিন্তু এটা এক ধাপ না। find পুরো ভেক্টর হেঁটে x খোঁজে, মানে n ধাপ পর্যন্ত। একই ভেক্টরের ওপর লুপের ভেতরে এটা রাখলে নেস্টেড লুপ না লিখেই তুমি $n^2$ লিখে ফেললে। মানগুলো একবার একটা হ্যাশ সেটে ঢুকিয়ে নিলে সেই একই প্রশ্ন প্রায় এক ধাপে নেমে আসে:

long long count_present(const vector<int> &v, const vector<int> &queries) {
    unordered_set<int> seen(v.begin(), v.end());   // সেট বানানো: n ধাপ, একবার
    long long hits = 0;
    for (int x : queries)
        hits += seen.count(x);                     // প্রতি কোয়েরি: প্রায় ১ ধাপ
    return hits;
}

লুপের ভেতর স্ট্রিং বানানো। এটা একটু সূক্ষ্ম, আর মজার ব্যাপার হলো C++ এখানে অনেক ভাষার চেয়ে ভালো করে। প্রতিবার নতুন করে পুরো স্ট্রিং বানালে এতক্ষণ যা জমেছে সব কপি হয়, আর সেই কপিগুলো যোগ হয়ে দাঁড়ায় $1+2+3+\cdots +n$, মানে $n(n+1)/2$, মানে ছদ্মবেশে $n^2$:

string bad(const vector<char> &chars) {
    string s;
    for (char c : chars)
        s = s + c;            // s + c আস্ত নতুন স্ট্রিং বানায়: মোট O(n²)
    return s;
}

তার বদলে জায়গামতোই যোগ করো। push_back (আর +=) স্ট্রিংয়ের নিজের বাফারটাই বাড়িয়ে নেয়, তাই পুরো লুপটা লিনিয়ার:

string good(const vector<char> &chars) {
    string s;
    for (char c : chars)
        s.push_back(c);       // জায়গামতো বাড়ে: প্রতিটায় amortised O(1), মোট O(n)
    return s;
}

সাবরেঞ্জ কপি করা। “প্রথম এলিমেন্টের পরের সবটা” নতুন একটা ভেক্টর হিসেবে নিলে, vector<int>(v.begin() + 1, v.end()), ওই এলিমেন্টগুলো কপি হয়: $\mathcal{O}(n)$। যে রিকার্সিভ ফাংশন প্রতি কলে এটা করে, সে রিকার্শনের চেহারা যা বলছে তার চেয়ে অনেক বেশি কাজ করছে। কপি না দিয়ে ইনডেক্স, বা রেঞ্জ পাস করো।

তিনটাই ধরা পড়ে একটা অভ্যাসে: লুপের প্রতি লাইনে নিজেকে জিজ্ঞেস করো, এটা কি সত্যিই এক ধাপ। লাইনটা যদি পুরো একটা কালেকশন ছুঁয়ে ফেলে, তাহলে এক ধাপ না।

#৫. হাতে-কলমে উদাহরণ: সবচেয়ে বড় ধারাবাহিক যোগফল

এবার একটা সত্যিকারের সমস্যা, আর দেখার মতো তিনটা ভার্সন। সমস্যা: কতগুলো সংখ্যা দেওয়া, তাদের মধ্যে পাশাপাশি থাকা একটা টুকরার সবচেয়ে বড় যোগফল বের করতে হবে। [3, -2, 5, -1]-এর উত্তর 6, আসে [3, -2, 5] থেকে।

ভার্সন এক: প্রতিটা টুকরা নিয়ে যোগ করো। শুরু আর শেষ বাছতে দুটো লুপ, যোগ করতে তৃতীয়টা।

long long best_v1(const vector<int> &a) {
    int n = a.size();
    long long best = a[0];
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            long long s = 0;
            for (int k = i; k <= j; k++)
                s += a[k];
            best = max(best, s);
        }
    return best;
}

তিনটা নেস্টেড লুপ: $n^3$। $n=5000$-এ সেটা $1.25\times 10^{11}$ ধাপ। বহুত ধীর।

ভার্সন দুই: বারবার যোগ করা বন্ধ করো। তৃতীয় লুপটা পুরো অপচয়। j এক ঘর ডানে সরলে যোগফলের জন্য একটা যোগই লাগে, নতুন করে হাঁটা লাগে না।

long long best_v2(const vector<int> &a) {
    int n = a.size();
    long long best = a[0];
    for (int i = 0; i < n; i++) {
        long long s = 0;
        for (int j = i; j < n; j++) {
            s += a[j];
            best = max(best, s);
        }
    }
    return best;
}

$n^2$। $n=5000$-এ ২৫ লাখ ধাপ, চলে যায়। $n=10^6$-এ যায় না।

ভার্সন তিন: প্রশ্নটাই পাল্টে দাও। “সবচেয়ে ভালো টুকরা কোনটা” না জিজ্ঞেস করে জিজ্ঞেস করো “এখানে শেষ হওয়া সবচেয়ে ভালো টুকরা কোনটা”। বাঁ থেকে ডানে হাঁটো, প্রতি জায়গায় ঠিক দুটো অপশন: আগের টুকরাটা টেনে নিয়ে যাও, নাকি ওটা ফেলে দিয়ে এখান থেকে নতুন করে শুরু করো।

long long best_v3(const vector<int> &a) {
    long long best = a[0], here = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        here = max((long long)a[i], here + a[i]);   // টেনে নাও, নাকি নতুন শুরু
        best = max(best, here);
    }
    return best;
}

একটা লুপ। $n$ ধাপ। $n=10^6$-এ এক মিলিসেকেন্ড।

  a       3    -2     5    -1
          |     |     |     |
  here    3     1     6     5      extend or restart
  best    3     3     6     6      the running answer

এটাই কাদানের অ্যালগরিদম, আর আমি এটা দেখাচ্ছি মুখস্থ করার জন্য না। দেখাচ্ছি গল্পের আকৃতিটার জন্য: $n^3\to n^2\to n$, আর প্রতিটা ধাপ এসেছে পুনরাবৃত্ত কাজ চোখে পড়া আর সেটা দুবার করতে রাজি না হওয়া থেকে। অ্যালগরিদম ডিজাইন মানে এটাই। এই সিরিজের প্রায় প্রতিটা পর্ব এরই আরেকটা রূপ।

#৬. যেটা কেউ প্রথমে বলে না

ধাপ গোনা বলে দেয় খরচটা কীভাবে বাড়ে। সামনের গুণিতক সংখ্যাটা নিয়ে সে ইচ্ছে করেই চুপ থাকে। $100n$ ধাপের একটা প্রোগ্রাম আর $2n$ ধাপের একটা, দুটোই "$n$", অথচ একটা আরেকটার চেয়ে পঞ্চাশ গুণ ধীর।

এটা কোনো দোষ না, এটাই আসল উদ্দেশ্য। বৃদ্ধির হারটাই নতুন ল্যাপটপে টিকে থাকে; গুণিতকটা টেকে না। তবে এর মানে দুটো সৎ কথা:

১. ছোট ইনপুটে “খারাপ” অ্যালগরিদমই প্রায়ই জেতে। এক ডজনের কম এলিমেন্টে ইনসার্শন সর্ট কুইকসর্টকে হারায়, আর এজন্যই আসল সর্ট নিচের দিকে গিয়ে ইনসার্শন সর্টে সুইচ করে। ২. দুটো সমাধানের বৃদ্ধির হার এক হলে গুণিতকটাই বাকি থাকে, আর তখন তুমি সত্যিই মাপো। এই সিরিজের ২১তম পর্ব পুরোটাই সেই গুণিতক নিয়ে, যেটা আসে মেমরি থেকে, ধাপের হিসাব থেকে না।

#৭. যে প্র্যাকটিসটা আসলে কাজে দেয়

এক সপ্তাহ এটা করো, অভ্যাসটা থেকে যাবে। নিজের লেখা যেকোনো ফাংশন নাও, লিখে তিনটা প্রশ্নের উত্তর দাও:

১. n কী? নাম দাও। এখানে অর্ধেক গোলমালের কারণই হলো এমন প্রোগ্রাম যার ভেতর দুটো আলাদা সাইজ আছে, যেমন r সারি আর c কলামের একটা গ্রিড, অথচ একটা অক্ষর দিয়ে বোঝানো হচ্ছে। ২. সবচেয়ে ভেতরের লাইনটা n-এর হিসাবে কতবার চলে? ৩. সমস্যা যে ইনপুট সাইজ দিচ্ছে, তাতে ওটা কি দশ কোটির নিচে?

প্রথম প্রশ্নের উত্তর দিতে না পারলে বুঝবে সমস্যাটা তুমি এখনো ঠিকমতো বোঝোনি। এটা যত মনে করো তার চেয়ে বেশিবার ঘটে, আর আগেভাগে ধরা পড়াটাই আসল লাভ।

#সংক্ষেপে

• সবচেয়ে ভেতরের লাইনটা কতবার চলে সেটা গোনো। সময় মেপো না; সময় মাপে তোমার ল্যাপটপকে, গোনা মাপে তোমার প্রোগ্রামকে।
• কাগজে $n$ আর $n^2$ সমান সহজ লাগে। দশ লাখ এলিমেন্টে একটা চোখের পলকে হয়, আরেকটায় সতেরো মিনিট।
• সেকেন্ডে মোটামুটি দশ কোটি ধাপই বাজেট। সমস্যার ইনপুট সাইজ বলে দেয় কোন অ্যালগরিদম চাওয়া হচ্ছে।
• নিরীহ দেখতে লাইনের ভেতরে ধাপ লুকায়: ভেক্টরে find, s = s + c দিয়ে স্ট্রিং বানানো, সাবরেঞ্জ কপি করা। কোনো লাইন পুরো কালেকশন ছুঁলে, সেটা এক ধাপ না।
• ভালো অ্যালগরিদম প্রায় সবসময়ই আসে পুনরাবৃত্ত কাজ চোখে পড়া আর সেটা আবার না করা থেকে। এটাই পুরো ট্রিক, সিরিজের বাকিটা এরই বিভিন্ন রূপ।

পরের পর্ব: বৃদ্ধির হারকে নাম দেওয়া, আর কেন $\mathcal{O}(n)$ আসলে গতি না, বরং একটা বক্ররেখার আকৃতি নিয়ে দাবি।