দ্রুত input-output: contest-এর code একই লাইন দিয়ে শুরু হয় কেন

Kenji-র program এক মিলিয়ন সংখ্যা পড়ে, আর প্রতিটা আবার print করে। Program-টা ঠিক, তবু judge-এ গিয়ে পায় Time Limit Exceeded। Kenji তো আগেভাগেই optimise করতে ভালোবাসে, ও loop-টা নতুন করে লিখতে বসে যায়। অথচ loop-এ কোনো দোষ নেই। সময় যাচ্ছে পড়া আর print করায়, আর main-এর শুরুর দুইটা লাইন সেটা সারিয়ে দেয়। কতটা সারায়, এই lesson সেটা মেপে দেখায়।

Buffer, sync আর tie

Buffer হলো memory-র একটা টুকরা, যেখানে character-রা অপেক্ষা করে। Program output সেখানে জমায়, তারপর operating system-এর হাতে দেয় বড় বড় খেপে, একটা একটা character করে না। অপেক্ষায় থাকা character-গুলো হাতে তুলে দেওয়াকে বলে flush। Input-ও একই নিয়মে চলে: একটা বড় খেপ ঢোকে, আর read-গুলো সেখান থেকে নেয়।

নিজে থেকে C++ দুইটা কথা দিয়ে রাখে, আর দুইটাতেই সময় খরচ হয়। প্রথমটা হলো sync: std::cin আর std::cout C-এর stdin আর stdout-এর সাথে তাল মিলিয়ে চলে। প্রতিটা character যায় C-এর input-output function-এর ভিতর দিয়ে, তাই printf আর std::cout পালা করে নিরাপদে লিখতে পারে। এই নিরাপত্তার দাম তুমি দাও প্রতিটা character-এ, printf একবারও call না করলেও।

দ্বিতীয়টা হলো tie: std::cin বাঁধা থাকে std::cout-এর সাথে, তাই প্রতিটা read-এর আগে std::cout flush হয়। Keyboard-এর সামনে এতে সুবিধা আছে: program অপেক্ষা শুরু করার আগেই "Enter n:"-এর মতো প্রশ্নটা screen-এ চলে আসে। কিন্তু judge কোনো প্রশ্ন পড়ে না।

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int price = 0;
    int count = 0;

    std::cin >> price >> count;
    std::cout << price * count << '\n';
    return 0;
}

100

তাই প্রথম লাইনটা C++ stream-দের নিজের buffer দেয়, আর দ্বিতীয়টা প্রতিটা read-এর আগের flush থামিয়ে দেয়।

std::endl মানে '\n', সাথে একটা flush

std::endl একটা newline পাঠায়, তারপর std::cout flush করে। '\n' শুধু newline-টা পাঠায়। বাইরে যে character-গুলো যায়, সেগুলো একই।

#include <iostream>

int main()
{
    std::cout << "first line" << std::endl;
    std::cout << "second line" << '\n';
    return 0;
}

first line
second line

Output দেখে flush ধরা যায় না, ধরা যায় শুধু সময়ে। প্রতিটা flush মানে operating system-এর কাছে একবার যাওয়া, আর প্রতি লাইনে একবার করে গেলে সেটা জমে পাহাড় হয়। std::endl ঠিক তখনই কাজের, যখন একটা লাইন এখনই বের হওয়া দরকার। যেমন, একটা interactive judge তোমার প্রশ্নের জন্য বসে আছে। আরেকটা হলো এমন একটা লাইন, যেটা পরের মুহূর্তে program crash করলেও তোমাকে দেখতেই হবে। তাই output হুবহু একই; std::endl শুধু বদলায় লাইনটা কখন বের হবে।

মেপে দেখা: এক মিলিয়ন সংখ্যা ঢোকা আর বের হওয়া Intermediate

চারটা program n = 1,000,000 পড়ে, তারপর এক মিলিয়ন পূর্ণসংখ্যা, আর প্রতিটা আবার print করে নিজের লাইনে। ওদের মধ্যে তফাত শুধু লাইন দুইটায় আর লাইন শেষ করার ধরনে। নিচে সবচেয়ে দ্রুতটা, কাজের চারপাশে একটা timer বসানো।

#include <chrono>
#include <cstdio>
#include <iostream>

int main()
{
    std::freopen("out.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;

    auto start = std::chrono::steady_clock::now();
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        int x = 0;
        std::cin >> x;
        std::cout << x << '\n';
    }
    std::cout.flush();
    auto stop = std::chrono::steady_clock::now();

    long long ms = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
    std::FILE* f = std::fopen("out.txt", "r");
    std::fseek(f, 0, SEEK_END);
    std::cerr << n << " numbers, " << std::ftell(f) << " bytes written, " << ms << " ms\n";
    return 0;
}

তিনটা খুঁটিনাটি বলে রাখা দরকার। Compiler Explorer 32 KB output-এর পরে program থামিয়ে দেয়, তাই stream চালু হওয়ার আগেই std::freopen stdout-কে একটা file-এ পাঠিয়ে দেয়, out.txt-এ। std::chrono-এর লাইনগুলো loop-এর আগে আর পরে একটা ঘড়ি দেখে; auto লম্বা type-টা compiler-কে দিয়ে লিখিয়ে নেয়, আর সেটা বুঝিয়ে বলবে lesson 04। শেষের লাইনগুলো file-টা মাপে, আর ফলাফল print করে stderr-এ, মানে error stream-এ।

বাকি তিনটা program হয় লাইন দুইটা বাদ দেয়, নয়তো '\n'-কে std::endl বানায়, নয়তো দুইটাই করে। প্রতিটা একবার করে চালানো হয়েছে Compiler Explorer-এ, x86-64 GCC 12.2-এ, runner-এর command line দিয়ে: g++ -O2 -std=c++17। Input-এ ছিল 0 থেকে 99-এর মধ্যে এক মিলিয়ন পূর্ণসংখ্যা, প্রতি লাইনে দশটা, সব মিলিয়ে 2,893,323 byte। প্রতিটা program লিখেছে একই 2,893,315 byte।

D-তে দুইটা বদলই আছে, আর এটা নিয়েছে 58 ms, যেখানে A নিয়েছে 750 ms: প্রায় 13 গুণ দ্রুত। মাঝের দুইটা দেখায়, কেন দুইটাই লাগে। C-তে লাইন দুইটা আছে, কিন্তু std::endl প্রতি লাইনে একবার flush করে: operating system-এর কাছে এক মিলিয়ন বার যাওয়া। B-তে লাইনের শেষে '\n', কিন্তু tie তখনো প্রতিটা read-এর আগে std::cout flush করে, আর program প্রতি লাইনেই একবার পড়ে।

লাইন দুইটার কাজ আলাদা করে দেখতে, একই site-এ একই input দিয়ে প্রতিটা আরও পাঁচবার চালানো হয়েছে। শুধু sync-এর লাইন, সাথে '\n', নিয়েছে 433 থেকে 2,158 ms, কারণ tie তখনো প্রতিটা read-এর আগে flush করে। শুধু tie-এর লাইন নিয়েছে 128 থেকে 193 ms: প্রতি read-এ flush নেই, কিন্তু প্রতিটা character তখনো C-এর function-এর ভিতর দিয়ে যায়। তিনটা বদল একসাথে থাকলেই কেবল পড়া আর লেখা দুইটাই চলে বড় বড় খেপে।

এই run-গুলো একটা ব্যস্ত, ভাগাভাগি করা মেশিনে, আর Playground-এর runner আরেকটা মেশিন। আবার চালালে A, B আর C কয়েকশো millisecond করে সরে গেছে, এমনকি নিজেদের মধ্যে ক্রমও বদলেছে, অথচ D থেকেছে 58 থেকে 66 ms-এ। ভরসা রাখো D-এর এগিয়ে থাকায়, ঠিক কত millisecond তাতে না। তাই লাইন দুইটা আর '\n' একসাথে চলে: তিনটার যেকোনো একটা বাদ দিলে program অন্তত দুই গুণ ধীর হয়েছে, আর বেশিরভাগ run-এ সাত গুণেরও বেশি।

Input শেষ না হওয়া পর্যন্ত পড়া: while (std::cin >> x)

অনেক input বলেই না কয়টা মান আসছে। তখন input ফুরানো পর্যন্ত পড়ে যাও। std::cin >> x ফেরত দেয় std::cin-কেই, আর lesson 01-এর শিকলগুলো এভাবেই কাজ করে। একটা stream-কে শর্ত হিসেবে বসালে সেটা ততক্ষণ সত্য, যতক্ষণ তার শেষ read সফল হয়েছে।

তাই while (std::cin >> x) একটা মান পড়ে, read কাজ করল কি না দেখে, আর body চালায় শুধু সেই মানের জন্য, যেটা সত্যিই এসেছে। Read ব্যর্থ হয় input শেষ হলে, বা এমন কিছু এলে যেটা সংখ্যা না। তখন loop থেমে যায়। Zara ওর তাপমাত্রার খাতা থেকে গোনে কয় দিন শূন্যের নিচে ছিল।

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int x = 0;
    int below = 0;

    while (std::cin >> x) {
        if (x < 0) {
            below++;
        }
    }
    std::cout << "days below zero: " << below << '\n';
    return 0;
}

days below zero: 2

Keyboard থেকে দিলে input তোমাকেই শেষ করতে হয়: Linux আর macOS-এ Ctrl+D, Windows-এ Ctrl+Z, তারপর Enter। Playground-এ input শেষ হয় input box-এর লেখা যেখানে শেষ, সেখানে। তাই যতগুলো সংখ্যা এসেছে, loop ঠিক ততবার চলে, আর যে read ব্যর্থ হয়, সেটাই loop শেষ করে।

পুরো লাইন: std::getline আর রয়ে যাওয়া newline

>> প্রতিটা space-এ থেমে যায়, তাই একটা বইয়ের নাম পুরোটা পড়তে পারে না। std::getline(std::cin, line) পরের newline পর্যন্ত প্রতিটা character একটা std::string-এ পড়ে, space-সহ। Newline-টা নিজে ফেলে দেয়। খালি লাইন দিলে পাওয়া যায় খালি string।

>>-এর মতো এটাও stream-টা ফেরত দেয়, তাই while (std::getline(std::cin, line)) input শেষ না হওয়া পর্যন্ত লাইন ধরে ধরে পড়ে। এবার ফাঁদটা। Maria-র library-র input-এ প্রথম লাইনে একটা সংখ্যা, পরের লাইনে বইয়ের নাম।

#include <iostream>
#include <string>

int main()
{
    int copies = 0;
    std::string title;

    std::cin >> copies;
    std::getline(std::cin, title);
    std::cout << "copies: " << copies << '\n';
    std::cout << "title: [" << title << "]\n";
    return 0;
}

copies: 3
title: []

ওই output-টা দুই লাইনের input 3 আর The Little Prince-এর জন্য। বইয়ের নাম খালি! >> 3-এর ঠিক পরেই থেমেছে, আর ওই লাইনের newline-টা stream-এ রেখে গেছে। তারপর std::getline পড়েছে ওই newline পর্যন্ত: একটা খালি লাইন, যেটা আসলে প্রথম লাইনেরই বাকি অংশ।

সমাধান হলো, পরের লাইন পড়ার আগে সংখ্যার লাইনটা শেষ করে নেওয়া। এমন একটা string-এ আরেকবার std::getline, যেটা তুমি কখনো ব্যবহার করবে না, কাজটা করে দেয়, আর সংখ্যার পরের space থাকলে সেগুলোও খেয়ে ফেলে।

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    std::string rest;
    std::string title;

    std::cin >> n;
    std::getline(std::cin, rest);
    for (int i = 1; i <= n; i++) {
        std::getline(std::cin, title);
        std::cout << i << ". " << title << " (" << title.size() << " characters)\n";
    }
    return 0;
}

1. The Little Prince (17 characters)
2. Matilda (7 characters)
3. Treasure Island (15 characters)

তাই >> কোনো লাইনের শেষ সংখ্যাটা পড়ার পরে একটা std::getline সেই লাইনটা শেষ করে, আর পরেরটা পড়ে আসল লাইন।

একটা লাইনের ভিতর দিয়ে character ধরে ধরে হাঁটা

একটা std::string পড়া যায় C-এর char array-এর মতো করে। line.size() বলে এতে কয়টা character আছে, আর line[i] হলো index i-এর character, 0 থেকে শুরু। একটা লাইনের শব্দগুলো খুঁজে বের করতে এটুকুই যথেষ্ট, C-তে যেভাবে করতে।

এখানে শব্দ মানে এমন character-এর একটা টানা সারি, যেগুলো space না। index i-তে একটা শব্দ শুরু হয়, যখন line[i] space না, আর হয় i হলো 0, নয়তো line[i - 1] একটা space। এই পরীক্ষা পরপর দুই-তিনটা space-কে পাত্তা দেয় না, লাইনের শুরু বা শেষের space-কেও না।

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string line;

    while (std::getline(std::cin, line)) {
        std::string initials;
        for (int i = 0; i < (int)line.size(); i++) {
            bool starts = line[i] != ' ' && (i == 0 || line[i - 1] == ' ');
            if (starts) {
                initials += line[i];
            }
        }
        std::cout << initials << '\n';
    }
    return 0;
}

tlotr
atwied

atotc

তাই একটা লাইন আসলে character-এর একটা array, যেটার উপর দিয়ে হাঁটা যায়, আর শব্দ শুরু হয় যেখানে space বা লাইনের শুরুর পরে একটা non-space আসে।

Sync বন্ধ করার পরে printf আর std::cout

Bob এখনো scanf আর printf লেখে, আর মাঝে মাঝে অভ্যাসের বশে লাইন দুইটাও বসিয়ে দেয়। Sync বন্ধ থাকলে দুই পরিবারই নিজের নিজের buffer রাখে, আর ওদের ক্রম ঠিক রাখার দায় কারও না।

#include <cstdio>
#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::printf("1. printf\n");
    std::cout << "2. cout\n";
    std::printf("3. printf\n");
    std::cout << "4. cout\n";
    return 0;
}

দুইটা system কী print করেছে, দেখো। কোনোটাই code-এর ক্রমে না।

Program শেষ হলে প্রতিটা buffer খালি হয়, আর কোনটা আগে খালি হবে, সেটা নির্ভর করে নিচের library-র উপর। তাই একই program তোমার মেশিনে ঠিক দেখাতে পারে, আর judge-এ গিয়ে উল্টাপাল্টা হয়ে যেতে পারে। নিয়ম হলো, এক program-এ এক পরিবার। scanf আর printf চাইলে সবখানে ওদেরই ব্যবহার করো, আর লাইন দুইটা বাদ দাও; ওরা এমনিতেই দ্রুত। তাই sync একবার বন্ধ হলে মেশানো output-এর ক্রম আর তোমার হাতে থাকে না।

String-এর ভিতরের সংখ্যা: std::istringstream-এর দিকে একটা ইশারা

কখনো কখনো যে সংখ্যাগুলো দরকার, সেগুলো আগে থেকেই একটা std::string-এর ভিতরে থাকে, যেমন std::getline-এর আনা একটা লাইন। std::istringstream, যেটা আসে <sstream> header থেকে, এমন একটা stream, যেটা stdin-এর বদলে একটা string থেকে পড়ে। >> এর উপর ঠিক std::cin-এর মতোই কাজ করে।

#include <iostream>
#include <sstream>
#include <string>

int main()
{
    std::string prices = "12 7 30";
    std::istringstream in(prices);
    int x = 0;

    while (in >> x) {
        std::cout << "price " << x << '\n';
    }
    return 0;
}

price 12
price 7
price 30

String stream ঠিকমতো শেখাবে Module 3। আপাতত এটুকু মনে রাখো: std::cin-এর জন্য যে >> loop লিখতে পারো, সেটা একটা string-এর উপরেও চলে।

while (!std::cin.eof()) {
    std::cin >> x;
    if (x < 0) {
        below++;
    }
}

for (int i = 0; i < n; i++) {
    std::cin >> x;
    std::cout << x << std::endl;
}

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> a;
std::scanf("%d", &b);

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int total = 0;
    int players = 0;

    std::cin >> total >> players;
    std::cout << "total score: " << total << '\n';
    std::cout << "per player: " << total / players << '\n';
    return 0;
}

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // Read integers until the input ends. Print their sum and how many
    // there were, on one line, separated by one space.

    return 0;
}

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string line;
    int lines = 0;
    int words = 0;

    // Read the input line by line with std::getline until it ends.
    // Count every line, and every word inside every line.

    std::cout << lines << ' ' << words << '\n';
    return 0;
}

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    std::cin >> n;

    // Read the n lines of text that follow with std::getline.
    // For every word, print the number of its line (1 to n),
    // one space and the word, one word per output line.

    return 0;
}

#include <iostream>
#include <sstream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // Read the input line by line until it ends. Print the total of each
    // line on its own line, then one last line: the word total, one
    // space, and the total of every number in the input.

    return 0;
}

এরপর pointer দিয়ে লেখা Maria-র swap হয়ে যায় একটাও star ছাড়া swap, আর lesson 03 বুঝিয়ে বলে সেই &-এর কথা, যেটা এখন নতুন একটা মানে নিয়েছে।