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

যারা কোনো একটা প্রোগ্রামের 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; } }

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