রুবি ডেভেলপারদের জন্য Big-O কেন গুরুত্বপূর্ণ: একটি প্র্যাক্টিক্যাল গাইড

আমার কম্পিউটার সাইন্সে ডিগ্রী নেই। অনেক রুবিস্টের মতো। তাই অনেক দিন আমি Big-O নোটেশন শিখতে এড়িয়ে যাচ্ছিলাম। এটি কিছুটা হায়ার ম্যাথের মতো দেখে। মানে: O(N^2)। সেরিয়াসলি?

বদলে, আমি থাম্ব রুল শিখলাম:

• Hash-এ নির্দিষ্ট আইটেম খুঁজে বের করা Array-র চেয়ে ফাস্ট
• নেস্টেড লুপ এড়িয়ে চলুন
• ভিউতে লিস্ট জেনারেট করার সময় অকস্মিক DB কোয়েরি থেকে সতর্ক থাকুন

এই রুলগুলো ভালো, কিন্তু যদি না বুঝেন কেন এগুলো কাজ করে, তবে আপনি ভুল করবেন এবং অঘটিত পারফরম্যান্স সমস্যায় পড়বেন।

কেন এটি গুরুত্বপূর্ণ?

Big-O নোটেশন শুধু আপনার কোডের পারফরম্যান্স কীভাবে প্রসেস করা ডেটার পরিমাণের ওপর নির্ভর করে সেটি বর্ণনা করার একটি ফ্যান্সি উপায়।

পারফরম্যান্স মানে দুটি জিনিসের একটা: স্পিড, বা র‍্যাম ইউজেজ। কম্পিউটার সাইন্স ক্লাসে আপনি এদের "টাইম কমপ্লেক্সিটি" এবং "স্পেস কমপ্লেক্সিটি" বলতেন। Big-O নোটেশন দুটোর জন্যও ব্যবহার হয়, কিন্তু আমরা এখানে স্পিডের ওপর ফোকাস করব, কারণ সেটি বেশি কমন।

আপনি আশা করবেন ১০০ আইটেমের অ্যারে প্রসেস করা ১০ আইটেমের চেয়ে স্লো হবে। কিন্তু কতটুকু? ১০x, ১০০x? ১০০০x?

ছোট ডেটাসেটে এটা বড় সমস্যা নয়, কিন্তু আপনার অ্যাপ যদি ডেটাবেসের প্রতিটি রো জন্য এক্সপোনেনশিয়ালি স্লো হয়, তো দ্রুত সমস্যা হয়ে যায়।

বিস্তারিতে যাওয়ার আগে, আমি একটি কুইক চার্ট বানালাম সাধারণ Big-O গুলো এবং ইমোজি দিয়ে দেখাচ্ছি কীভাবে আপনি ফিল করবেন যত ডেটা স্কেল হয়।

তাই কেউ যদি বলে Array#bsearch Array#find-এর চেয়ে ভালো কারণ এটি O(log n) বনাম O(n), আপনি শুধু 😁 এবং 😕 তুলনা করে বুঝতে পারবেন তারা কিছু বোঝাতে পারছেন।

কিছুটা আরও রোবাস্ট কিছুর জন্য, Big-O Cheat Sheet চেক করুন।

নোটেশন বোঝা

আপনাকে সব olika Big-O ভ্যালু মেমোরাইজ করতে হয় না, যতক্ষণ আপনি নোটেশনটি কীভাবে কাজ করে সেটি বুঝেন।

উদাহরণস্বরূপ, ভয়াবহ O(2^n) নিন। আপনি যদি এটিকে রুবিতে এক্সপ্রেস করতে চান, এটা এইরকম দেখাবে:

# O(2^n) রুবিতে ট্রান্সলেট
def o(n)
  2 ** n # এটি রুবিতে 2^n
end

এখনও স্পষ্ট নয়? মেথড এবং আর্গুমেন্টের নাম কিছুটা ইউজার-ফ্রেন্ডলি করে দিলে কেমন?

# O(2^n) প্রিটিয়ার রুবিতে ট্রান্সলেট
def execution_time(size_of_dataset)
  2 ** size_of_dataset
end

আপনি সবগুলোর জন্য এটি করতে পারেন:

# O(1)
def o1_execution_time(size_of_dataset)
  1
end

# O(n)
def on_execution_time(size_of_dataset)
  size_of_dataset
end

# O(n^2)
def on2_execution_time(size_of_dataset)
  size_of_dataset * size_of_dataset
end
...etc

এখন আপনি নোটেশনটি কীভাবে কাজ করে সেটি জানেন, চলুন কিছু টিপিক্যাল রুবি কোড দেখি এবং সেগুলো কীভাবে রিলেট করে।

O(1)

যখন আমরা কিছুকে O(1) বলি, এর মানে এর স্পিড এর ডেটাসেটের সাইজের ওপর নির্ভর করে না।

উদাহরণস্বরূপ, হ্যাশ লুকআপ টাইম হ্যাশ সাইজের ওপর নির্ভর করে না:

# এই সব একই সময় নিবে
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

এটিই কারণ আমরা টেন্ড করি বলতে যে বড় ডেটাসেটের জন্য হ্যাশ অ্যারে থেকে ফাস্ট।

O(n)

বিপরীতে, Array#find হলো O(n)। এর মানে Array#find অ্যারেতে আইটেমের সংখ্যার ওপর লিনিয়ারলি ডিপেন্ড করে। ১০০ আইটেমের অ্যারে ১ আইটেমের অ্যারে থেকে ১০০ গুণ বেশি সময় নিবে সার্চ করতে।

অ্যারে এর ऊपर ইটারেট করা অনেক কোড O(n) প্যাটার্ন ফলো করে।

(0..9).each do |i|
  puts i
end
# এই উদাহরণটি আগেরটির অর্ধেক স্পিড কারণ এতে ২x আইটেম আছে।
(0..19).each do |i|
  puts i
end

O(n²)

O(n^2) প্রোফাইলে ফিট হওয়া কোড সাধারণত নেস্টেড লুপ ইনভল্ভ করে। চিন্তা করলে মেনে যাবেন। একটা লুপ দিয়ে O(n), দ্বিতীয় নেস্টেড লুপ দিয়ে O(n^2)। যদি—কোনো অনহোলি কারণে—আপনার ৫-লেভেল নেস্টেড লুপ হয়, তবে সেটি O(n^5) হবে।

data = (0..100)
data.each do |d1|
  data.each do |d2|
    puts "#{ d1 }, #{ d2 }"
  end
end

O(n log n)

O(n log n) কোড সাধারণত কোনো কেউ একটি অন্যথায় O(n^2) অ্যালগরিদম যে কাজটি করত, সেটি কম করার একটি চালাক উপায় খুঁজে পেলে হয়।

আপনি কোডের এক টুকরো দেখে বলতে পারবেন না এটা O(n log n)। এখানেই হায়ার ম্যাথ আসে, এবং এখানেই আমি হার মানি।

কিন্তু O(n log n) সম্পর্কে জানা গুরুত্বপূর্ণ কারণ এটি অনেক কমন সার্চ অ্যালগরিদম বর্ণনা করে। রুবির Array#sort দীর্ঘদিনের quicksort অ্যালগরিদম ব্যবহার করে, যা গড়ে O(n log n) এবং ওৰ্স্ট-কেসে O(n^2)।

আপনি যদি quicksort-র সাথে পরিচিত ন হন, এই চমৎকার ডেমো দেখুন।

সবকিছু একসাথে: আপনার ডেটাবেস

নতুন ওয়েব অ্যাপ্লিকেশনের সবচেয়ে কমন সমস্যা হচ্ছে সেগুলো ডেভেলপারের কম্পিউটারে ফাস্ট, কিন্তু প্রোডাকশনে তারা ধীরে ধীরে স্লো হয়ে যায়।

এটি হয় কারণ আপনার ডেটাবেসের রেকর্ডের পরিমাণ সময়ের সাথে বৃদ্ধি পায়, কিন্তু আপনার কোড ডিবিকে এমন অপারেশন করতে বলে যা স্কেল করে না। অর্থাৎ O(n) বা ওৰ্স।

উদাহরণস্বরূপ, আপনি কি জানতেন পোস্টগ্রেসে, কাউন্ট কোয়েরি সবসময় O(n)?

# এটি ডিবিকে ইউজারস টেবিলের প্রতিটি রোতে ইটারেট করতে বাধ্য করে
# ...যদি না আপনি রেইলস কাউন্টার ক্যাশ ব্যবহার করেন।
Users.count

আমরা এটি পোস্টগ্রেস explain কমান্ড ব্যবহার করে দেখতে পারি। নিচে, আমি একটি কাউন্ট কোয়েরির কোয়েরি প্ল্যান পাওয়ার জন্য explain ব্যবহার করছি। আপনি দেখতে পাচ্ছেন, এটি ১০৪,৭৯১ রো위에 একটি সিকোয়েনশিয়াল স্ক্যান (অর্থাৎ লুপিং) করার প্ল্যান করছে।

# explain select count(*) from users;
QUERY PLAN
-----------------------------------------------------------------
Aggregate (cost=6920.89..6920.90 rows=1 width=0)
-> Seq Scan on users (cost=0.00..6660.71 rows=104701 width=0)
(2 rows)

অনেক কমন রেইলস ইডিয়োম অনিচ্ছাকৃত সিকোয়েনশিয়াল স্ক্যান ট্রিগার করতে পারে, যদি না আপনি স্পেসিফিক্যালি ডেটাবেস অপ্টিমাইজ করেন সেগুলো রোধ করার জন্য।

# এটি ডিবিকে পুরো `products` টেবিল সর্ট করতে বলে
Products.order("price desc").limit(1)

# যদি `hobby` ইনডেক্সড না হয়, ডিবি ইউজারস টেবিলের প্রতিটি রো লুপ করে খুঁজে বের করবে।
User.where(hobby: "fishing")

আপনি explain কমান্ড ব্যবহার করে এটিও দেখতে পারেন। এখানে আমরা পুরো টেবিলে একটি সর্ট (প্রবাবলি quicksort) করছি। যদি মেমরি কনস্ট্রেইন্ট থাকে, তবে এটি অন্য সর্টিং অ্যালগরिदম বেছে নিতে পারে ভিন্ন পারফরম্যান্স ক্যারাক্টারিস্টিক্সের সাথে।

# explain select * from users order by nickname desc limit 1;
QUERY PLAN
-------------------------------------------------------------------------
Limit (cost=7190.07..7190.07 rows=1 width=812)
-> Sort (cost=7190.07..7405.24 rows=104701 width=812)
Sort Key: nickname
-> Seq Scan on users (cost=0.00..6606.71 rows=104701 width=812)

এই সব সমস্যার উত্তর হচ্ছে, অবশ্যই, ইনডেক্সিং। ডেটাবেসকে ইনডেক্স ব্যবহার করতে বলা রুবিতে হ্যাশ লুকআপ O(1) ব্যবহার করার মতো অ্যারে ফাইন্ড O(n)-এর বদলে।

শেষ, সব শেষ

আশা করি Big-O নোটেশন এবং কীভাবে এটি আপনাকে রুবি ডেভেলপার হিসেবে প্রভাবিত করে সেটি নিয়ে একটি উপকারী ইন্ট্রোডাকশন হয়েছে! প্রশ্ন থাকলে @StarrHorne-এ পিং করুন।