बिग-ओ नोटेशन के लिए एक रूबीस्ट गाइड

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

इसके बजाय, मैंने अंगूठे के नियम सीखे:

• हैश में किसी खास आइटम को ढूंढना ऐरे की तुलना में तेज़ है
• नेस्टेड लूप से बचें
• अपने विचारों में सूचियां बनाते समय आकस्मिक डीबी प्रश्नों से सावधान रहें

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

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

बिग-ओ नोटेशन यह वर्णन करने का एक शानदार तरीका है कि आपके कोड का प्रदर्शन उसके द्वारा संसाधित किए जा रहे डेटा की मात्रा पर निर्भर करता है।

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

आप उम्मीद करेंगे कि 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)

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

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

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

ऐसा इसलिए होता है क्योंकि आपके डेटाबेस में रिकॉर्ड की मात्रा समय के साथ बढ़ती है, लेकिन आपका कोड डीबी को ऐसे ऑपरेशन करने के लिए कह रहा है जो अच्छी तरह से स्केल नहीं करते हैं। अर्थात। 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 पिंग करें यदि आपके कोई प्रश्न हैं।