[GUIDE] Faster I/O Method in C/C++

By -
যারা কোনো একটা প্রোগ্রামের Run Time নিয়ে বিশেষভাবে উদ্বিগ্ন থাকো, বিশেষ করে তাদের জন্যেই এই আর্টিকেল ।

মূল আলোচনায় যাওয়ার আগে Sphere Online Judge এর INTEST প্রব্লেমটা সলভ করে আসো । যদি প্রব্লেমটা সলভ করতে না পারো, তাহলে পুরো আর্টিকেলটা পড়ে ফেলো । আর যদি প্রব্লেমটা সলভ করতে পারো, তাহলে তোমার প্রোগ্রামের Run Time টা একটু দেখে নাও ।

মূল আলোচনায় আসা যাক এবার ।

আমি যদি C তে কোড করি, তাহলে কোডটা এমন হতে পারে :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int main() 
{ 
    int n, k, t, c = 0;

    scanf("%d%d", &n, &k);
    while (n--) {
        scanf("%d", &t);
        if (t % k == 0) {
            c++;
        }
    }
    printf("%d\n", c);

    return 0;
}

উপরের কোডটা AC হবে কি না, আমি জানি না । কারণ, আমি এই কোড সাবমিট দেইনি ।

যারা C++ এর cin এবং cout অবজেক্ট দু'টি নিয়ে কাজ করতে অভ্যস্ত, তারা উপরের কোডটাই এভাবে লিখতে পারে :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;
 
int main() 
{
    int n, k, t, c = 0;

    cin >> n >> k;
    while (n--) {
        cin >> t;
        if (t % k == 0) {
            c++;
        }
    }
    cout << c << endl;

    return 0;
}

আশ্চর্য্যজনক হলেও সত্য যে cin/cout এর কোডের চাইতেও scanf/printf এর কোড তুলনামূলক ফাস্ট run করবে । তবে আমরা চাইলে cin/cout এর কোডটিকেও scanf/printf এর মতো ফাস্ট করে ফেলতে পারি শুধুমাত্র দুইটি লাইন যোগ করে ।

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, t, c = 0;

    cin >> n >> k;
    while (n--) {
        cin >> t;
        if (t % k == 0) {
            c++;
        }
    }
    cout << c << endl;

    return 0;
}

cin Standard I/O এর সাথে Synchronize করে, যার ফলে cin তুলনামূলক Slower. বাই ডিফল্ট এই সিঙ্ক্রোনাইজেশান on/true থাকে অর্থাৎ sync_with_stdio(true) থাকে যেটাকে উপরে কোডে false করে দেওয়া হয়েছে !

প্রশ্ন হচ্ছে, এর চাইতেও ফাস্ট কি সম্ভব ? যদি সম্ভব হয়, তবে কীভাবে ?
হ্যাঁ, সম্ভব । কীভাবে সম্ভব, নিচে দেখিয়ে দিলাম ।

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;
 
void fastScan(int &number);
 
int main() 
{ 
    int n, k, t, count = 0;

    fastScan(n);
    fastScan(k);

    while (n--) {
        fastScan(t);
        if (t % k == 0) {
            count++;
        }
    }
    printf("%d\n", count);

    return 0; 
}
 
void fastScan(int &number) 
{ 
    /// Variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    /// Extract current character from buffer
    c = getchar();
    if (c == '-') {
        /// Number is negative
        negative = true;

        /// Extract the next character from the buffer
        c = getchar();
    }

    /// Keep on extracting characters if they are integers
    /// i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c > 47 && c < 58); c = getchar()) {
        number = number *10 + c - 48;
    }

    /// If scanned input has a negative sign,
    /// Negate the value of the input number
    if (negative) {
        number *= -1;
    }
}

এখানে scanf() দিয়ে integer reading এর পরিবর্তে অন্য একটি ফাংশান fastScan() ডিফাইন করা হয়েছে যেটি মূলত getchar() ফাংশান দিয়ে ডাটা পড়ে । getchar() যেহেতু ক্যারেকটার রিড করার ফাংশান, সেহেতু 46-47 নাম্বার লাইনে সেই ক্যারেকটারগুলো মিলিয়ে নাম্বার বানানো হচ্ছে । এমনিতে ক্যারেকটার ভেরিয়েবল রিড করার জন্য আমি নিজেও এতোদিন scanf() ইউজ করে আসছি । কিন্তু getchar() যে এতো ফাস্ট আমি আগে কখনো কল্পনাই করিনি ।

এই কোড কতোটা ফাস্ট, তোমরা নিজেরা সাবমিট দিয়ে স্বচক্ষে দেখতে পারো !

আমি যদি আবারো প্রশ্ন করি, এটার চাইতেও কি ফাস্ট সম্ভব ?
মজার ব্যাপার হলো, হ্যাঁ সম্ভব ! getchar() এর জায়গায় যদি getchar_unlocked() লিখি, তাহলে এটা getchar() এর চাইতেও ফাস্ট কাজ করবে । তবে getchar_unlocked() এর কিছু সমস্যা আছে । তার মধ্যে প্রধান ২টা সমস্যা হলো,
১. এটি Standard C/C++ ফাংশান নয়, বরং POSIX ফাংশান । তাই তোমার Windows PC তে যদি নিচের কোডটি রান করতে না পারো, তাহলে অবাক হইও না ! তবে Sphere Online Judge এই কোড এক্সেপ্ট করেছে ।
২. getchar_unlocked() একটি Non Thread-Safe ফাংশান । যারা Multi Thread প্রোগ্রামিং করে, তাদের জন্য অসুবিধার কারণ হতে পারে এই ফাংশান ।

আমি নিচে কোডটি দিলাম ।

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

/// Here, fastScan() uses getchar_unlocked() to read from buffer
/// getchar_unlocked() is not an Standard C/C++ function rather than a POSIX one
/// Thus, this program will not run on Windows platform but on Linux
 
void fastScan(int &number);
 
int main() 
{ 
    int n, k, t, count = 0;

    fastScan(n);
    fastScan(k);

    while (n--) {
        fastScan(t);
        if (t % k == 0) {
            count++;
        }
    }
    printf("%d\n", count);

    return 0; 
}
 
void fastScan(int &number)
{
    /// Variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    /// Extract current character from buffer
    c = getchar_unlocked();
    if (c == '-') {
        /// Number is negative
        negative = true;

        /// Extract the next character from the buffer
        c = getchar_unlocked();
    }

    /// Keep on extracting characters if they are integers
    /// i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c > 47 && c < 58); c = getchar_unlocked()) {
        number = number *10 + c - 48;
    }

    /// If scanned input has a negative sign,
    /// Negate the value of the input number
    if (negative) {
        number *= -1;
    }
}


এই আর্টিকেলে শুধুমাত্র একটি সিম্পল টেকনিক নিয়ে আলোচনা করলাম । ইন্টারনেটে খুঁজলে তোমরা এর চেয়েও ভালো কিছু পেতে পারো ।

Comments

Post a Comment

Popular posts from this blog

return keyword কী ?

By -
সদ্য প্রোগ্রামিং জগতে আসা অনেকেই return keyword টির কাজ বুঝতে পারে না । তাদের কথা ভেবে এই পোস্ট লিখা । return keyword টি function এর সাথে ওতপ্রোতভাবে জড়িত । তাই এখানে function এর মাধ্যমেই আলোচনা করার চেষ্টা করলাম । মনে করো, তোমার খুব চা খেতে ইচ্ছে করছে কিন্তু তুমি চা বানাতে জানো না বা পারো না । তুমি তোমার ছোট বোনকে চা বানিয়ে দিতে বললে । তোমার ছোটবোন তোমাকে বললো, যদি তুমি তাকে চা বানানোর উপকরণগুলো এনে দাও, তবেই সে তোমাকে চা বানিয়ে দিবে ! এবার এসো আমরা একটা তালিকা বানাই । চা বানাতে কী কী লাগবে ? চা পাতা, পানি, দুধ, চিনি ! তুমি যে চা খেতে চাইছো, সে চা কী ধরণের বস্তু ? নিশ্চয়ই তরল । এবার এই তথ্যগুলো নিয়ে আমরা একটা function লিখার চেষ্টা করবো । একটা function লিখতে হলে সেই function এর শুরুতে প্রথম যে শব্দ বা keyword টি লিখতে হয়, সেটি হলো ঐ function এর return data type অর্থাৎ function টি কী ধরণের data তোমাকে return করবে, সেটি । তো, আমরা যে চা খাওয়া নিয়ে কথা বলছিলাম, সে ক্ষেত্রে return type কী হতে পারে ? অবশ্যই তরল ! এরপর লিখতে হয় ঐ function টির একটি যুতসই নাম, নিজের ইচ্ছেমতো নাম । তবে না
Read more

[Python] Introduction

By -
আসসালামু আলাইকুম ওয়ারাহমাতুল্লাহ। আশা করি, আল্লাহ্‌র রহমাতে ভালো আছেন। এটা একদম বিগিনার লেভেলের কোনো গাইড না। প্রোগ্রামিং সম্পর্কে যাদের আইডিয়া আছে, বিশেষ করে যারা C/C++ সম্পর্কে জানে, তাদের জন্য এই গাইড উপকারী হবে বলে মনে করি। এই গাইডগুলোতে প্রোগ্রামিং কনসেপ্টগুলো নিয়ে খুব বেশি গভীর আলোচনা হবে না। C++ এ ক্লাস ডিক্লেয়ার করতে পারা মানুষ যদি জানতে চায় একই কাজ Python এ কীভাবে করা যায়, তাহলে এই গাইড তার উপকারে আসতে পারে। মূলত, এখানে C/C++ এর সাথে Python এর Syntactic Differences নিয়েই বেশি আলোচনা করবো। P.S. 1: কম্পিটিটিভ প্রোগ্রামারগণ এর চাহিদা পূরণ করার আশা রাখি। বিভিন্ন Data Structures, Algorithm (C++ STL এর বিকল্প) নিয়ে আলোচনা করার ইচ্ছা আছে। P.S. 2: Python এর প্রচুর লাইব্রেরি রয়েছে, যার ফাংশানও অসংখ্য। জনপ্রিয় লাইব্রেরিগুলো নিয়েও লিখার ইচ্ছা আছে। P.S. 3: এই গাইডগুলোকে রেফারেন্স বলা যেতে পারে। আমার নিজের জন্যেই আসলে এখানে লিখছি। কখনো কোনো কিছুর প্রয়োজন পড়লে এখানে এসে যাতে মনে করে নিতে পারি। P.S. 4: আমি জানি না, আমার এই লিখা কেউ পড়বে কি না। যদি কেউ পড়ে থাকেন, তবে আপনার ম
Read more

[GUIDE] UVa OJ - 375 - Inscribed Circles and Isosceles Triangles

By -
Image
শুরুতেই এই প্রব্লেমটা সহজ ভাষায় ব্যাখ্যা করার চেষ্টা করি । Figure : 1 খেয়াল করো । একটি সমদ্বিবাহু ত্রিভুজের ভূমি b এবং উচ্চতা h দেওয়া আছে । প্রথমে এর তিনটি কোণকে সমদ্বিখণ্ডিত করতে হবে । সমত্রিখণ্ডক তিনটির ছেদবিন্দু (চিত্রে O বিন্দু)-কে কেন্দ্র করে এমন একটি বৃত্ত আঁকতে হবে যেটি ত্রিভুজের ৩টি বাহুকে স্পর্শ করে । তারপর আরও একটি বৃত্ত (এই রঙের ) আঁকতে হবে যেটি ত্রিভুজের সমান দুই বাহু (চিত্রে AB এবং AC ) কে এবং তার নিচের বৃত্তকেও (এই রঙের ) স্পর্শ করে । এর উপরের বৃত্তগুলোও এভাবে এঁকে যেতে হবে । কিন্তু এভাবে তো অসীম সংখ্যক বার যাওয়া যাবে; তাহলে থামবো কোথায় ? এই প্রশ্নের উত্তর মূল স্টেটমেন্টেই দেওয়া আছে । এই যে বৃত্তের একটা Stack তৈরি হচ্ছে, যে বৃত্তের ব্যাসার্ধ 0.000001 এর চেয়ে ছোট হয়ে যাবে, তখনই আমাদের থেমে যেতে হবে ! প্রব্লেমের আউটপুটে দিতে হবে Stack এর সবগুলো বৃত্তের পরিধির যোগফল । তো, বৃত্তের পরিধি হিসেব করতে হলে আমাদের কী জানতে হবে ? অবশ্যই বৃত্তের ব্যাসার্ধ । কীভাবে আমরা এই বৃত্তগুলোর ব্যাসার্ধ বের করতে পারি ? প্রথমে আমরা Figure : 1 এর  ΔABC থেকে  ΔABD কে আলাদা করে
Read more