Ruby डेवलपर्स के लिए Big-O क्यों मायने रखता है: एक व्यावहारिक गाइड

मेरे पास कंप्यूटर साइंस की डिग्री नहीं है। हम Rubyists में से बहुतों के पास नहीं है। इसलिए लंबे समय तक मैंने Big-O नोटेशन सीखने से परहेज किया। यह थोड़ा बहुत हायर मैथ जैसा दिखता है। मेरा मतलब: O(N^2). चलो भी।

इसके बजाय, मैंने थंब रूल सीखे:

• Hash में एक विशिष्ट आइटम ढूंढना Array की तुलना में तेज है
• नेस्टेड लूप से बचें
• अपने व्यू में लिस्ट जनरेट करते समय आकस्मिक DB क्वेरी से सावधान रहें

ये नियम अच्छे हैं, लेकिन जब तक आप यह नहीं समझते कि वे क्यों काम करते हैं, आप खुद को गलतियां करते हुए और अकथनीय प्रदर्शन समस्याओं का सामना करते हुए पाएंगे।

यह क्यों मायने रखता है?

Big-O नोटेशन सिर्फ आपके कोड के प्रदर्शन का वर्णन करने का एक फैंसी तरीका है कि यह प्रोसेस किए जा रहे डेटा की मात्रा पर कैसे निर्भर करता है।

प्रदर्शन का मतलब दो चीजों में से एक है: गति, या RAM उपयोग। कंप्यूटर साइंस क्लास में आप इन्हें "टाइम कॉम्प्लेक्सिटी" और "स्पेस कॉम्प्लेक्सिटी" के रूप में संदर्भित करेंगे। Big-O नोटेशन दोनों के लिए उपयोग किया जाता है, लेकिन हम यहां गति पर ध्यान केंद्रित करने जा रहे हैं, क्योंकि यह अधिक सामान्य उपयोग प्रतीत होता है।

आप उम्मीद करेंगे कि 100 आइटम की एक सरणी को प्रोसेस करना 10 आइटम की सरणी की तुलना में धीमा होगा। लेकिन कितना? 10x, 100x? 1000x?

छोटे डेटासेट के साथ यह कोई बड़ी बात नहीं है, लेकिन यदि आपका ऐप डेटाबेस में प्रत्येक पंक्ति के लिए तेजी से धीमा होता जाता है तो यह जल्द ही एक समस्या बन जाता है।

विवरण में जाने से पहले, मैंने एक त्वरित चार्ट बनाया जो सामान्य Big-O को इमोजी के साथ दिखाता है कि वे आपके डेटा के स्केल के रूप में आपको कैसा महसूस कराएंगे।

तो जब कोई कहता है कि Array#bsearch Array#find से बेहतर है क्योंकि यह O(log n) बनाम O(n) है, तो आप बस 😁 की तुलना 😕 से कर सकते हैं और देख सकते हैं कि वे कुछ सही कह रहे होंगे।

कुछ अधिक मजबूत के लिए, Big-O चीट शीट देखें।

नोटेशन को समझना

आपको सभी अलग-अलग Big-O मानों को याद रखने की आवश्यकता नहीं है, जब तक आप समझते हैं कि नोटेशन कैसे काम करता है।

उदाहरण के लिए, भयानक भयानक O(2^n) लें। यदि हम इसे Ruby में व्यक्त करते, तो यह ऐसा दिख सकता है:

# O(2^n) को Ruby में अनुवादित
def o(n)
  2 ** n # यह Ruby में 2^n के लिए है
end 

अभी भी स्पष्ट नहीं? क्या होगा अगर मैं मेथड और आर्गुमेंट का नाम कुछ अधिक उपयोगकर्ता-अनुकूल रखूं?

# O(2^n) को प्रिटियर 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 

अब जब आप जानते हैं कि नोटेशन कैसे काम करता है, तो आइए कुछ विशिष्ट Ruby कोड को देखें और देखें कि यह कैसे संबंधित है।

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 सरणी में आइटम की संख्या पर रैखिक रूप से निर्भर करता है। 100 आइटम वाली सरणी को खोजने में एक आइटम वाली सरणी की तुलना में 100 गुना अधिक समय लगेगा।

सरणियों पर पुनरावृति करने वाला बहुत सारा कोड O(n) पैटर्न का पालन करता है।

(0..9).each do |i|
  puts i
end
# यह उदाहरण पिछले की आधी गति का है क्योंकि इसमें 2x आइटम हैं।
(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) के बारे में जानना महत्वपूर्ण है क्योंकि यह बहुत सारे सामान्य सर्च एल्गोरिदम का वर्णन करता है। Ruby का Array#sort वरिष्ठ क्विकसॉर्ट एल्गोरिदम का उपयोग करता है, जो औसतन O(n log n) है और सबसे खराब स्थिति में O(n^2) है।

यदि आप क्विकसॉर्ट से परिचित नहीं हैं, तो इस उत्कृष्ट प्रदर्शन को देखें।

इसे एक साथ रखना: आपका डेटाबेस

नए वेब एप्लिकेशन के साथ सबसे आम समस्याओं में से एक यह है कि वे डेवलपर के कंप्यूटर पर तेज होते हैं, लेकिन प्रोडक्शन में वे धीमे और धीमे होते जाते हैं।

ऐसा इसलिए होता है क्योंकि आपके डेटाबेस में रिकॉर्ड की मात्रा समय के साथ बढ़ती जाती है, लेकिन आपका कोड DB से ऐसे ऑपरेशन करने के लिए कह रहा है जो अच्छी तरह से स्केल नहीं करते। यानी O(n) या बदतर।

उदाहरण के लिए, क्या आप जानते हैं कि Postgres में, काउंट क्वेरी हमेशा O(n) होती हैं?

# यह DB को Users की हर पंक्ति पर पुनरावृति करने के लिए मजबूर करता है
# ...जब तक आप Rails काउंटर कैश का उपयोग नहीं कर रहे हैं।
Users.count 

हम इसे Postgres 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) 

बहुत सारे सामान्य Rails इडियम्स अनजाने में अनुक्रमिक स्कैन ट्रिगर कर सकते हैं, जब तक कि आप विशेष रूप से डेटाबेस को उन्हें रोकने के लिए ऑप्टिमाइज़ नहीं करते।

# यह DB से पूरे `products` टेबल को सॉर्ट करने के लिए कहता है
Products.order("price desc").limit(1)
# यदि `hobby` इंडेक्स्ड नहीं है, तो DB Users की प्रत्येक पंक्ति के माध्यम से लूप करता है इसे खोजने के लिए।
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) 

इन सभी समस्याओं का उत्तर, निश्चित रूप से, इंडेक्सिंग है। डेटाबेस को इंडेक्स का उपयोग करने के लिए कहना Ruby में थोड़ा सा ऐसा है जब आप एरे फाइंड O(n) के बजाय हैश लुकअप O(1) का उपयोग करते हैं।

बस इतना ही, दोस्तों

मुझे उम्मीद है कि यह Big-O नोटेशन का एक उपयोगी परिचय रहा है और यह एक Ruby डेवलपर के रूप में आपको कैसे प्रभावित करता है! यदि आपके कोई प्रश्न हैं तो मुझे @StarrHorne पर पिंग करें।