বিগ-ও স্বরলিপির জন্য একটি রুবিস্ট গাইড

আমার কম্পিউটার বিজ্ঞানে কোনো ডিগ্রি নেই। আমরা অনেক রুবিস্ট না. তাই দীর্ঘদিন ধরে আমি বিগ-ও স্বরলিপি সম্পর্কে শেখা এড়িয়ে চলেছি। এটা একটু বেশী উচ্চ গণিত মত দেখায়. মানে:O(N^2) . চলে আসো.

পরিবর্তে, আমি থাম্বের নিয়ম শিখেছি:

• একটি হ্যাশে একটি নির্দিষ্ট আইটেম খোঁজা একটি অ্যারের চেয়ে দ্রুততর হয়
• নেস্টেড লুপ এড়িয়ে চলুন
• আপনার ভিউয়ে তালিকা তৈরি করার সময় দুর্ঘটনাজনিত DB প্রশ্নগুলির জন্য সতর্ক থাকুন

এই নিয়মগুলি চমৎকার, কিন্তু যদি না আপনি বুঝতে পারেন যে কেন তারা কাজ করে, আপনি নিজেকে ভুল করছেন এবং অবর্ণনীয় পারফরম্যান্স সমস্যা খুঁজে পাবেন।

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

বিগ-ও স্বরলিপি হ'ল বর্ণনা করার একটি অভিনব উপায় যে কীভাবে আপনার কোডের কার্যকারিতা এটি প্রক্রিয়াকরণ করা ডেটার পরিমাণের উপর নির্ভর করে।

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

আপনি আশা করবেন যে 100টি আইটেমের একটি অ্যারের প্রক্রিয়াকরণ 10টি আইটেমের অ্যারের চেয়ে ধীর হবে। কিন্তু কত দ্বারা? 10x, 100x? 1000x?

ছোট ডেটাসেটগুলির সাথে এটি একটি বড় চুক্তি নয়, তবে যদি আপনার অ্যাপটি ডেটাবেসের প্রতিটি সারির জন্য দ্রুতগতিতে ধীর হয়ে যায় তবে এটি শীঘ্রই একটি সমস্যা হয়ে দাঁড়ায়৷

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

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

একটু বেশি শক্তিশালী কিছুর জন্য, বিগ-ও চিট শীট দেখুন

স্বরলিপির পাঠোদ্ধার

যতক্ষণ না আপনি বুঝতে পারেন যে স্বরলিপি কীভাবে কাজ করে ততক্ষণ আপনাকে বিভিন্ন বিগ-ও মানগুলির সমস্ত মুখস্থ করতে হবে না।

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

# O(2^n) translated to Ruby
def o(n)
  2 ** n  # This is ruby for 2^n
end

এখনও স্পষ্ট নয়? আমি যদি পদ্ধতি এবং যুক্তিকে আরও ব্যবহারকারী-বান্ধব কিছুতে পুনঃনামকরণ করি তাহলে কেমন হয়?

# O(2^n) translated to prettier Ruby
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) এর মানে হল যে এর গতি তার ডেটা সেটের আকারের উপর নির্ভর করে না।

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

# These should all take the same amount of time
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

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

O(n)

বিপরীতে, Array#find হল O(n) . মানে Array#find অ্যারের আইটেম সংখ্যার উপর রৈখিকভাবে নির্ভর করে। 100টি আইটেম সহ একটি অ্যারে একটি আইটেম সহ একটি অ্যারের চেয়ে 100 গুণ বেশি সময় নেয়

অনেক কোড যা অ্যারেতে পুনরাবৃত্তি করে O(n) অনুসরণ করে প্যাটার্ন

(0..9).each do |i|
  puts i
end

# This example is 1/2 the speed of the previous because it contains 2x the items. 
(0..19).each do |i|
  puts i
end

O(n^2)

কোড যা একটি O(n^2) ফিট করে প্রোফাইল নেস্টেড লুপ জড়িত থাকে। যদি আপনি এটি সম্পর্কে চিন্তা করেন যে অর্থে তোলে. একটি লুপ আপনাকে O(n) দেয় , একটি দ্বিতীয় নেস্টেড লুপ আপনাকে O(n^2) দেয় . যদি — কোনো অপবিত্র কারণে — আপনার একটি 5-স্তরের নেস্টেড লুপ থাকে, তাহলে সেটি হবে 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 সম্মানীয় কুইকসর্ট অ্যালগরিদম ব্যবহার করে, যা গড়ে O(n log n) এবং সবচেয়ে খারাপ ক্ষেত্রে হল O(n^2)

আপনি যদি কুইকসর্টের সাথে পরিচিত না হন তবে এই চমৎকার প্রদর্শনটি দেখুন।

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

নতুন ওয়েব অ্যাপ্লিকেশনগুলির মধ্যে সবচেয়ে সাধারণ সমস্যাগুলির মধ্যে একটি হল যে তারা বিকাশকারীর কম্পিউটারে দ্রুত, কিন্তু উৎপাদনে তারা ধীর এবং ধীর হয়ে যায়।

এটি ঘটে কারণ আপনার ডাটাবেসের রেকর্ডের পরিমাণ সময়ের সাথে সাথে বৃদ্ধি পায়, কিন্তু আপনার কোড DB কে এমন ক্রিয়াকলাপ করতে বলছে যা ভালভাবে পরিমাপ করে না। অর্থাৎ O(n) বা তার থেকেও খারাপ.

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

# This makes the DB iterate over every row of Users
# ...unless you're using a Rails counter cache. 
Users.count

আমরা পোস্টগ্রেস explain ব্যবহার করে এটি দেখতে পারি আদেশ নীচে, আমি একটি গণনা প্রশ্নের জন্য ক্যোয়ারী পরিকল্পনা পেতে এটি ব্যবহার করি। আপনি দেখতে পাচ্ছেন, এটি টেবিলের সমস্ত 104,791 সারিতে একটি অনুক্রমিক স্ক্যান (এর অর্থ লুপিং) করার পরিকল্পনা করছে।

# 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)

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

# This asks the DB to sort the entire `products` table
Products.order("price desc").limit(1)

# If `hobby` isn't indexed, the DB loops through each row of Users to find it. 
User.where(hobby: "fishing")

আপনি explain ব্যবহার করতে পারেন সেইসাথে দেখতে আদেশ. এখানে আমরা দেখতে পাচ্ছি আমরা পুরো টেবিলে একটি সাজানোর (সম্ভবত দ্রুত সাজানো) করছি। যদি মেমরির সীমাবদ্ধতা থাকে, তবে এটি বিভিন্ন কর্মক্ষমতা বৈশিষ্ট্য সহ একটি ভিন্ন সাজানোর অ্যালগরিদম বেছে নিয়েছে।

# 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) খুঁজুন .

এটুকুই, লোকেরা

আমি আশা করি এটি বিগ-ও স্বরলিপির একটি কার্যকর ভূমিকা এবং রুবি বিকাশকারী হিসাবে আপনাকে কীভাবে প্রভাবিত করবে! আপনার কোন প্রশ্ন থাকলে আমাকে @StarrHorne পিং করুন।