कंप्यूटर वैज्ञानिकों ने गणना का एक नया कुशल तरीका ईजाद किया

 (quantamagazine.org)
2 पॉइंट द्वारा GN⁺ 2024-05-17 | 1 टिप्पणियां | WhatsApp पर शेयर करें

नया कुशल counting algorithm विकसित

परिचय

  • कल्पना कीजिए, आप एक आदिम वन में wild animal sensing कर रहे हैं।
  • आप digital camera से जानवरों की तस्वीरें लेते हैं, और यह जानना चाहते हैं कि बिना दोहराव वाले जानवरों की संख्या कितनी है।
  • मौजूदा तरीकों में सभी जानवरों को याद रखना और उनकी तुलना करना पड़ता है, लेकिन यह अक्षम है।

समस्या की स्थिति

  • Facebook जैसे बड़े प्लेटफ़ॉर्म पर हर दिन login करने वाले unique users की संख्या गिनना मुश्किल होता है।
  • हाल ही में कंप्यूटर वैज्ञानिकों ने लंबी सूची में unique items की संख्या का अनुमान लगाने का एक नया तरीका प्रस्तावित किया है।
  • इस algorithm को केवल कम संख्या में items याद रखने होते हैं।

CVM algorithm

  • CVM algorithm 40 से अधिक वर्षों से अध्ययन की जा रही unique elements problem को हल करने की दिशा में एक महत्वपूर्ण कदम है।
  • यह algorithm data stream में unique elements की संख्या का कुशलतापूर्वक अनुमान लगा सकता है।
  • "नया algorithm आश्चर्यजनक रूप से सरल है और implement करना आसान है" - Andrew McGregor

उदाहरण: Hamlet audiobook

  • Hamlet में 30,557 शब्द हैं। इनमें से कितने unique हैं, यह जानने के लिए सामान्यतः सभी शब्दों को याद रखना पड़ता है।
  • CVM algorithm memory usage कम करने के लिए randomization का उपयोग करता है।

CVM algorithm कैसे काम करता है

  • पहला round: 100 शब्द दर्ज करें, और duplicate शब्दों को coin toss से हटा दें।
  • दूसरा round: duplicate शब्दों को बनाए रखना और कठिन बनाने के लिए दो coin toss की आवश्यकता होती है।
  • तीसरा round: तीन coin toss की आवश्यकता होती है।
  • kवें round तक इसे दोहराकर unique शब्दों की संख्या का अनुमान लगाया जाता है।

accuracy की जाँच

  • accuracy memory size के अनुसार बदलती है।
  • Hamlet में unique शब्दों की संख्या 3,967 है; 100 memory के साथ औसत अनुमान 3,955 था, जबकि 1,000 memory के साथ औसत अनुमान 3,964 था।

निष्कर्ष

  • "मूलभूत और अच्छी तरह से अध्ययन की गई समस्याओं में भी सरल लेकिन non-intuitive समाधान मौजूद हो सकते हैं" - William Kuszmaul

GN⁺ की राय

  • data streaming स्थितियों में उपयोगी: CVM algorithm बड़े data stream में unique items का कुशल अनुमान लगा सकता है, इसलिए यह real-time analysis के लिए उपयोगी है।
  • memory efficiency: memory usage को न्यूनतम रखते हुए भी यह उच्च accuracy बनाए रख सकता है, इसलिए memory constraints वाले environments में यह विशेष रूप से लाभदायक है।
  • randomization का महत्व: randomization के जरिए जटिल समस्या को सरलता से हल किया जा सकता है, इसलिए अन्य क्षेत्रों में भी इसके अनुप्रयोग की संभावना बड़ी है।
  • तकनीक अपनाने के विचार: इस algorithm को अपनाते समय memory size और accuracy के बीच संतुलन पर विचार करना चाहिए। यदि memory पर्याप्त न हो तो accuracy घट सकती है।
  • संबंधित तकनीक: HyperLogLog जैसे अन्य unique element estimation algorithms के साथ इसकी तुलना करना उपयोगी हो सकता है। हर algorithm के फायदे और सीमाओं को समझकर स्थिति के अनुसार सर्वोत्तम solution चुनना महत्वपूर्ण है।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-17
Hacker News राय

Hacker News टिप्पणियों का सारांश

  • HyperLogLog जैसा एल्गोरिद्म
    HyperLogLog जैसे एल्गोरिद्म का इस्तेमाल करते हुए, सिक्का उछालने की लगातार शृंखला के जरिए एक सरल एल्गोरिद्म समझाया गया है। यह खास तौर पर streaming data में कुशलता से काम करता है और कम memory इस्तेमाल करता है.

  • एल्गोरिद्म की व्याख्या में त्रुटि की ओर इशारा
    यह बताया गया कि एल्गोरिद्म की व्याख्या गलत थी, और code example के जरिए सही तरीका प्रस्तुत किया गया। पहले शब्द को store करके बाद में delete करने का तरीका अधिक सटीक परिणाम देता है.

  • पेपर की सिफारिश
    यह कहा गया कि paper ब्लॉग पोस्ट जितना ही पढ़ने में आसान है, लेकिन अधिक जानकारी देता है। इसमें streaming data में set cardinality का अनुमान लगाने वाले एक सरल एल्गोरिद्म को समझाया गया है.

  • Python implementation उदाहरण
    streaming algorithm का Python implementation उदाहरण दिया गया है। छोटे code के जरिए एल्गोरिद्म को समझना और अभ्यास करना संभव है.

  • सिस्टम refactoring में उपयोगी
    एक ऐसे सिस्टम को refactor किया जा रहा है जो visit count को table में insert करके गिनती करता है, और इसमें कहा गया कि यह तरीका HyperLogLog approach का एक दिलचस्प विकल्प हो सकता है.

  • memory-efficient तरीका
    यह उल्लेख किया गया कि computer scientists ने memory-efficient तरीके से subset के आकार का अनुमान लगाने की विधि विकसित की है.

  • Chernoff Bound पर चर्चा
    paper में इस्तेमाल किए गए Chernoff Bound के एक variant पर चर्चा की गई। यह भी कहा गया कि यह स्पष्ट नहीं है कि क्या यह variant proof की शुद्धता को प्रभावित करता है.

  • unique element estimation और counting में अंतर
    यह कहा गया कि unique elements की संख्या का अनुमान लगाना और वास्तव में उन्हें count करना बहुत अलग बातें हैं, और इसी वजह से शीर्षक को अनुपयुक्त बताया गया.

  • कुशल stream algorithm का परिचय
    stream में शीर्ष k items खोजने के लिए एक कुशल और आसानी से implement किए जा सकने वाले एल्गोरिद्म का परिचय दिया गया। Karp, Shenker & Papadimitriou के paper की सिफारिश की गई.

  • रचनात्मक सोच का महत्व
    "box के बाहर सोचने" के उदाहरण का आनंद लेने की बात कही गई और यह जोर दिया गया कि समस्या-समाधान के लिए सही सवाल खोजना महत्वपूर्ण है। उम्मीद जताई गई कि अलग-अलग उदाहरणों के जरिए रचनात्मक सोच को आत्मसात कर उसे लागू किया जा सके.