🌶️ 🙏🏿 ☠️ MapReduce: अधिक उन्नत उदाहरण, zaumi के बिना प्रयास करें ☎️ 🔴 😭

विलंब न करने के लिए, मैं तुरंत " MapReduce विदाउट रुकी " विषय में वादा किए गए MapReduce के लिए कुछ अन्य उदाहरण बताऊंगा । (यदि आप पूरी तरह से समझ नहीं पा रहे हैं कि MapReduce क्या है, तो उस विषय को पहले पढ़ें। आप इसके बिना नहीं समझ पाएंगे)

आइए यहां शहरों में राष्ट्रीयताओं की गणना, छात्रों के औसत ग्रेड और ड्राइव, TIC, पेजरैंक, इनबाउंड लिंक, आला कीवर्ड, समानार्थक, सामाजिक नेटवर्क और आपसी दोस्तों के बारे में बात करते हैं। हम गणितीय संकेतों और ज़ूमी के बिना करने की कोशिश करेंगे।

हालाँकि, विषय ही जटिल है और अभी भी आपके दिमाग को तनाव में डालना है। जब आप समझते हैं - यह बहुत सरल होगा।

भीतर का लिंक

मान लीजिए कि हमारे पास इंटरनेट है। इंटरनेट पर आउटगोइंग लिंक हैं।

मान लीजिए कि प्रवेश द्वार पर हमारे पास मकड़ी द्वारा एकत्र किए गए लिंक के बारे में ऐसा डेटा है:

habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru 
      

        
        
        
      

     thematicmedia.ru -> habrahabr.ru, autokadabra.ru 
      

        
        
        
      

     autokadabra.ru -> habrahabr.ru, yandex.ru

यानी हम जानते हैं कि हबर Apple, MS, Ubuntu और Yandex को संदर्भित करता है लेकिन Habr को कौन संदर्भित करता है? हां, प्रश्न आदिम है, लेकिन हम इसे MapReduce पर विघटित करेंगे। यह आगे और अधिक दिलचस्प होगा और इस उदाहरण की आवश्यकता होगी।

नक्शा कदम (जो हम खुद लिखते हैं) निम्नलिखित करते हैं:

(एक बार फिर - अगर आपको समझ नहीं आ रहा है कि यह किस बारे में है - " बिना Zaumi के MapReduce पढ़ें")।

उदाहरणों में " //

" के बाद आने वाली सभी एक टिप्पणी है, यह केवल यह बताता है कि यह कहां से आया था, मैपरेड्यूस सीधे संबंधित नहीं है।

map("habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com")

->

["thematicmedia.ru", "habrahabr.ru"] //  thematicmedia.ru    habrahabr.ru 
      

        
        
        
      

     ["apple.ru", "habrahabr.ru"] 
      

        
        
        
      

     .....

map("thematicmedia.ru -> habrahabr.ru, autokadabra.ru")

->

["habrahabr.ru", "thematicmedia.ru"] 
      

        
        
        
      

     ["autokadabra.ru", "thematicmedia.ru"] 
      

        
        
        
      

     ....

"कम करें" कदम कुछ भी नहीं करता है, क्योंकि इनपुट पर हमें पहले से ही यह मिलता है:

["autokadabra.ru", ["thematicmedia.ru"]] 
      

        
        
        
      

     ["habrahabr.ru", ["thematicmedia.ru", "autokadabra.ru"]] <-- ,    
      

        
        
        
      

     ....

यहाँ जवाब है - लिंकिंग लिंक।

TIC या PageRank को कौन सी साइटें देती हैं?

अहह, टीआईसी, लिंक ट्रेडिंग की पवित्र कब्र ( लगभग 2010)। चलो रेटिंग की कुछ पारंपरिक इकाई लेते हैं और इसे मेगारैंक कहते हैं (यह टीआईसी हो सकता है, शायद पेजरैंक, आदि - कोई अंतर नहीं है)।

ऐसा सिद्धांत मान लीजिए - प्रत्येक साइट में एक निश्चित मेगारैंक होता है, जिसे वह कुछ मात्रा में "संचारित" करता है, या "प्रसारित नहीं करता है" और आम तौर पर मेगाकैंक को "मारता है"। हम केवल अंतिम साइटों के MegaRank को जानते हैं, कैसे पता करें कि प्रारंभिक कितने MegaRank प्रसारण करता है?

फिर से, हमारे पास प्रारंभिक डेटा है, साइट ए में मेगारैंक 100 है और साइटों बी, सी, डी से आने वाले लिंक हैं। साइट B में MegaRank 0 है (हम मानते हैं कि MegaRank खराब लिंक द्वारा "मारा गया" है क्योंकि हम इस सिद्धांत को खारिज नहीं कर सकते हैं) और साइट A, D, E, F, और इसी तरह से आने वाले लिंक हैं ...

हम निम्नानुसार कार्य को विघटित करते हैं: साइट ए को बी, सी, डी से कुछ प्राप्त हुआ, जो 100 के बराबर शुरू हुआ। हम मानते हैं कि बी, सी, डी में से प्रत्येक ने साइट ए को 33 मेगा यूनिट दिए। साइट बी ने मेगारैंक को मार दिया है, हम मानते हैं कि इसका मेगारैंक = -500 और शून्य नहीं है। इस प्रकार, हम उन लोगों को बहुत कम आंकने की कोशिश करेंगे जो मेगाकैंक को मारते हैं (मान लीजिए कि यह साइट ए है, जिसका विज्ञापन खराब है और जिसे खोज इंजन द्वारा समझा जाता है)। यह पता चला है कि प्रत्येक साइट A, D, E, F ने 500-4 = -125 = मेगारैंक की इकाइयाँ B को दीं।

आउटगोइंग द्वारा आने वाले लिंक को कैसे गिना जाए - मैंने पहले ही ऊपर वर्णित किया है, हम मान लेंगे कि हमने यह पहले ही कर लिया है ...

तो, हमारे पास इनपुट डेटा है:

A (100) <- B,C,D //     MegaRank=100   B,C,D 
      

        
        
        
      

     B (-500) <- A,D,E

हमारा "मैप" निम्नलिखित करता है:

ए (100) <- बी, सी, डी:

B, 100/3 = 33 //  B  33  MegaRank      B   A 
      

        
        
        
      

     C, 33 
      

        
        
        
      

     D, 33

बी (-500) <- ए, डी, ई, एफ:

A, -500/4 = -125 
      

        
        
        
      

     D, -125 
      

        
        
        
      

     E, -125 
      

        
        
        
      

     F, -125

कटौती के कदम पर आता है:

A (-125) //      ""  -125  MegaRank 
      

        
        
        
      

     B (33) 
      

        
        
        
      

     C (33) 
      

        
        
        
      

     D (33, -125) //      "D"  33-125 = -92  MegaRank 
      

        
        
        
      

     E (-125) 
      

        
        
        
      

     F (-125)

कम करें फिर से सब कुछ जोड़ता है, हम पाते हैं कि ए सबसे बेकार साइट है, जैसे ई, एफ, जो अन्य डेटा की अनुपस्थिति में केवल शून्य मेगारैंक के साथ साइट को संदर्भित करता है। लेकिन डी, इस तथ्य के बावजूद कि यह ए और बी दोनों को संदर्भित करता है, "संदिग्ध" है, लेकिन सिर्फ ए से बेहतर है।

अब हम उन्हें मेगारैंक द्वारा एक ज़ामी (लोकप्रियता के साथ क्रमबद्ध) के बिना MapReduce के उदाहरण के साथ प्रेषित अवरोही क्रम में व्यवस्थित कर सकते हैं।

यह उदाहरण बहुत बेहतर दिखाता है कि MapReduce की आवश्यकता क्यों है - हम एक साथ लाखों लिंक के लिए लाखों साइटों का विश्लेषण कर सकते हैं और एक मशीन पर भी सीमित मेमोरी की समस्या में चल सकते हैं, और अधिक समानांतर शक्ति के लिए अन्य मशीनों को कनेक्ट कर सकते हैं।

(और इससे पहले कि आप पूछने के लिए दौड़ें - हाँ, मैंने टीआईसी में सिद्धांत की जाँच की, हाँ, यह काम करता है :) मेरे पास यह टीआईसी बिना किसी रुचि के है)।

इस प्रकार, साइटों से केवल आउटगोइंग लिंक पर डेटा और साइटों के एक निश्चित पैरामीटर (TIC, PageRank), जिनके लिए ये लिंक निर्देशित हैं, हम उन साइटों को खोज सकते हैं जो इस पैरामीटर को अच्छी तरह से पास करते हैं।

शहरों में जनसंख्या का प्रतिशत

मान लें कि हमारे पास शहर के जिलों की जानकारी है कि 150 रूसी, 190 बेलारूस के, 3 Udmurts Gorod1 के Gdetto क्षेत्र में रहते हैं, और 3 Russians, 5 बेलारूस के लोग Gorod1 के टुट्टो क्षेत्र में रहते हैं।

अब हमारा कार्य शहरों में जनसंख्या के प्रतिशत की गणना करना है (हम इन शहरों के क्षेत्रों में जानते हैं)। एक समस्या है? लाखों जिले, डेटा शहर द्वारा समूहीकृत नहीं हैं और सभी एक साथ मेमोरी में फिट नहीं होंगे ...

MapReduce पर बहुत सरल:

«मानचित्र»:

map(" Gdetto Gorod1 150 , 190 , 3 ")

->

"gorod1", [ (150, ""), (190, ""), (3, "") ]

map(" Tutto Gorod1 3 , 5 ")

->

"gorod1", [ (3, ""), (5, "") ]

map(" Butto Gorod2 1 ")

->

"gorod2", [ (1, "") ]

«कम»:

प्रवेश द्वार पर:

"gorod1", [ (150, ""), (190, ""), (3, ""), (3, ""), (5, "") ] 
      

        
        
        
      

     //  ,     -       
      

        
        
        
      

     "gorod2", [ (1, "") ]

मुझे लगता है कि यह स्पष्ट है कि इन मूल्यों को एक साथ जोड़ना संभव है, जो पहले से ही मेमोरी में फिट होंगे और प्रत्येक शहर में राशि से विभाजित करेंगे।

एक और विकल्प यह कैसे किया जा सकता है - आप अपने लिए सोच सकते हैं।

किसके साथ कम से कम दो सामान्य मित्र हैं?

मान लीजिए कि ए, बी, सी, डी, ई - सॉकेट में फिंगर्स के साथ सोशल नेटवर्क के 30 मिलियन उपयोगकर्ताओं द्वारा आविष्कार किया गया है। मान लीजिए हम जानते हैं कि:

   B, D, E 
      

        
        
        
      

     B   A, D, E 
      

        
        
        
      

     C   B, E

हम कैसे पाते हैं कि उनमें से कम से कम दो पारस्परिक मित्र हैं?

बहुत सरल (अनुमान?) MapReduce। हम प्रत्येक व्यक्ति के लिए हर जोड़े को ब्रूट फ़ोर्स लेते हैं और पहले स्थान पर रखते हैं।

«मानचित्र»:

(B,D), A //   ""      " B   D" 
      

        
        
        
      

     (B,E), A 
      

        
        
        
      

     (D,E), A 
      

        
        
        
      

     (A,D), B 
      

        
        
        
      

     (A,E), B 
      

        
        
        
      

     (D,E), B 
      

        
        
        
      

     (B,E), C

"कम करें" प्राप्त करता है (और उन सभी पंक्तियों को चुनने के अलावा कुछ भी नहीं करता है जिसमें दूसरे तत्व के कई मूल्य हैं):

(A,D), (B) //   "A,D"    "B"  
      

        
        
        
      

     (A,E), (B) 
      

        
        
        
      

     (B,D), (A) 
      

        
        
        
      

     (B,E), (A,C) <--  -   "B,E"   ""   "" 
      

        
        
        
      

     (D,E), (A,B) <--

उत्तर है:

A और C के पारस्परिक मित्र B, E हैं

A और B के परस्पर मित्र D, E हैं

आक्टंग! Algortime O (n ² ) , जो उन लोगों के लिए है जो टैंक में हैं, का अर्थ है कि बड़ी मात्रा में इनपुट डेटा के साथ, सूरज निकलने से पहले काम खत्म करने की अच्छी संभावनाएं हैं। दरअसल, निश्चित रूप से, पहले, लेकिन द्विघात एल्गोरिदम खराब हैं।

कीवर्ड में आला विषयों का पता लगाएं

मान लें कि हमारे पास कुछ कीवर्ड हैं:

मान लीजिए कि हम उन पर प्रकाश डालना चाहते हैं, जिनके बारे में हम लिख सकते हैं। इस तरह के "आला" विषय पर विचार किया जा सकता है जिसमें इस शब्द की भागीदारी के साथ कम से कम कुछ अलग-अलग कीवर्ड हैं और खुद एक कीवर्ड है। उदाहरण के लिए, "कॉफी बनाने वाले" एक विषय हैं, क्योंकि "कॉफी बनाने वाले" और "बाबराब कॉफी निर्माता", लेकिन "गेराज" एक आला नहीं हैं, क्योंकि वे अपने आप में एक कीवर्ड नहीं हैं। "मिले" भी एक "आला" नहीं है, क्योंकि इसमें अलग-अलग कीवर्ड नहीं हैं, केवल खुद को छोड़कर। वैसे कैसे? MapReduce के बिना इसे खोजने के लिए तैयार हैं? :)

और यह बहुत सरल है। हम प्रत्येक पंक्ति लेते हैं और इसे शब्दों में तोड़ देते हैं (अधिमानतः एन-ग्राम में, लेकिन यह स्वयं है)। उनमें से प्रत्येक के लिए हम "पूर्ण" जारी करते हैं यदि यह शब्द पूरी लाइन पर कब्जा करता है, या "भाग" यदि यह केवल एक भाग पर कब्जा करता है। यानी ऊपर दिए गए उदाहरण से:

«मानचित्र»:

, PART //   " " 
      

        
        
        
      

     , PART //   " " 
      

        
        
        
      

     , FULL //   "" 
      

        
        
        
      

     , FULL 
      

        
        
        
      

     , FULL 
      

        
        
        
      

     , PART 
      

        
        
        
      

     , PART 
      

        
        
        
      

     , PART 
      

        
        
        
      

     , FULL 
      

        
        
        
      

     , FULL

प्रवेश द्वार पर "कम करें":

, (PART, FULL) 
      

        
        
        
      

     , (FULL, PART, PART) 
      

        
        
        
      

     , (PART) 
      

        
        
        
      

     , (PART, FULL, FULL) 
      

        
        
        
      

     , (FULL)

अब हम सिर्फ यह देखते हैं कि PART और FULL कहां हैं: "babrababr", "gates" और "कॉफी बनाने वाले" - हम जो खोज रहे थे वह हमारे "niches" थे।

छद्म शब्द की खोज करें

मान लीजिए कि हमारे पास इंटरनेट है। माना कि वहां कई वाक्यांश हैं, लेकिन उनमें से हम देखते हैं कि "एक बड़ा कंप्यूटर खरीदा", "एक महंगा कंप्यूटर खरीदा" जैसे वाक्यांश हैं ... यहाँ हम सोचते हैं कि "महंगा" और "बड़ा" छद्म समानार्थी हैं। हमें एक खराब साइट बनाने और वेबकैश कमाने की आवश्यकता है जब तक कि गोटू खोज इंजन हमारी खराब साइट को बाहर नहीं फेंक देता है।

समस्या यह है कि अरबों शब्द हैं, पर्याप्त स्मृति नहीं होगी। हां, और यह "कल एक कंप्यूटर खरीदा" हो सकता है, और "कल" बिल्कुल "बड़ा" नहीं है और सामान्य तौर पर यह गलती से एक बार में मिल गया ... क्या करना है? क्या एल्गोरिथ्म का उपयोग करें (ठीक है, ठीक है, पत्थरों को हटा दें, मुझे पता है कि आप सभी ने इसका अनुमान लगाया था)। चलो चलते हैं!

हम इनपुट डेटा लेते हैं और सही क्रम में हम इसमें से तीन शब्दों का चयन करते हैं, ब्याज के लिए मैं केवल वही छोड़ता हूं जिसकी आवश्यकता है:

चरण 1 (हमें दो चरणों के कैस्केड की आवश्यकता होगी):

«मानचित्र»:

" * ", "" //   "  " 
      

        
        
        
      

     " * ", "" //   "  " 
      

        
        
        
      

     " * ", "" 
      

        
        
        
      

     " * ", "" 
      

        
        
        
      

     " * ", ""

एक तारांकन सिर्फ एक तारांकन चिह्न है, जिसका अर्थ है "कोई भी शब्द यहाँ है," ताकि Reduce इस तरह से आए:

" * ", ["", "", ""] 
      

        
        
        
      

     //   ""  ""     
      

        
        
        
      

     
      

        
        
        
      

     " * ", ["", ""]

कम कुछ नहीं करता।

स्टेज 2 (कैस्केड):

"मैप" - इनपुट प्राप्त होता है जो थोड़ा अधिक लिखा जाता है, और दूसरे मूल्यों (["बड़ा", "कल", "प्रिय"]) से संपूर्ण खोज द्वारा जोड़े देता है:

,  //   ["", "", ""] 
      

        
        
        
      

     ,  //   ["", "", ""] 
      

        
        
        
      

     ,  //   ["", "", ""] 
      

        
        
        
      

     ,  //   ["", "", ""] 
      

        
        
        
      

     ,  //   ["", "", ""] 
      

        
        
        
      

     ,  //   ["", "", ""] 
      

        
        
        
      

     
      

        
        
        
      

     ,  //   ["", ""] 
      

        
        
        
      

     ,  //   ["", ""]

कम करने पर, वे निम्नानुसार आएंगे:

इस बात पर ध्यान न दें कि कहीं उद्धरण हैं, कहीं पर इसका कोई गुप्त अर्थ नहीं है, बस इसे कहीं रख दें, कहीं नहीं।

अब "कमी" केवल शब्दों को कोष्ठक (इसके तर्क का दूसरा तत्व) में गिना जा सकता है, जो स्मृति में फिट होगा और उन तत्वों को त्याग देगा जो केवल एक बार होते हैं:

 - (2) // ""  - "",  2  
      

        
        
        
      

      - (2)

आक्टंग! जटिलता ओ (एन ² ) फिर से!

शामिल हों

मान लीजिए हमारे पास पहले से ही दो MapReduce हैं जिन्हें हमें संयोजित करने की आवश्यकता है। बता दें कि एक मैपरेड्यूस एक दर्जन शिक्षक पत्रिकाओं की कक्षा में छात्रों के औसत ग्रेड को औसत मानता है, और दूसरा व्यक्ति सैकड़ों पुलिस स्टेशनों के आंकड़ों के आधार पर पिछले एक साल में पुलिस को छात्रों की संख्या पर विचार करता है। हम दो MapReduce को एक परिणाम में कैसे मर्ज कर सकते हैं ... दूसरे शब्दों में, INNER JOIN या OUTER JOIN करें।

पहला MapReduce उत्पादन (स्कोर):

, ("", 3.5)

और दूसरा MapReduce उत्पादित (ड्राइव):

, ("", 2)

फिर सीधे सीधे एक पंक्ति में यह सब संचारित करें:

, ("", 3.5) 
      

        
        
        
      

     , ("", 2)

फिर "कम" पर आपको प्राप्त होगा:

, [ ("", 3.5), ("", 2) ]

एक निष्कर्ष के बजाय

यह स्पष्ट है कि MegaRanks, niches, friends, synonyms, राष्ट्र, twosomes केवल MapReduce के उपयोग से दूर हैं, लेकिन अब के लिए, मुझे लगता है कि यह आपके लिए यह सोचने के लिए पर्याप्त है कि इसका उपयोग कैसे किया जाए। मुझे उसके लिए बहुत सारे एप्लिकेशन मिले हैं और हर समय उसका उपयोग करते हैं।

जैसा कि मैंने पहले ही कहा था - लगभग किसी भी SQL क्वेरी को MapReduce पर विघटित किया जाता है, यह बस थोड़ा प्रशिक्षण लेता है। क्यों? फिर, तेज होने के लिए, और हमेशा नहीं, SQL में आवश्यक कार्य बिल्कुल भी नहीं हैं। उदाहरण के लिए, इनपुट लाइन से n- ग्राम (क्रिया वाक्यांश) का एक ही जनरेटर ... शायद मैं गलत हूं, लेकिन यह तथ्य कि MapReduce एक ड्रॉप डेड है और बहुत उपयोगी है (और एक ही समय में आश्चर्यजनक रूप से चतुराई से नेटवर्क पर वर्णित) एक तथ्य है। मुझे आशा है कि यह आपको MapReduce नेटवर्क में खींचना संभव था।

अंतिम विषय में, पायथन और पीएचपी में मैपरेड्यूस का एक संदर्भ कार्यान्वयन है।

योय हाजी

देखें, हमेशा की तरह, हैबर से ,

2010

(किसी दिन मैं संक्षेप में समझाना सीखूंगा ....)

MapReduce: अधिक उन्नत उदाहरण, zaumi के बिना प्रयास करें