लाइव डेटा कैप्चर के प्रतिशत

Question

मैं एक एल्गोरिदम खोज रहा हूं जो लाइव डेटा कैप्चर के लिए प्रतिशत निर्धारित करता है।

उदाहरण के लिए, सर्वर अनुप्रयोग के विकास पर विचार करें।

सर्वर इस प्रकार से प्रतिक्रिया समय हो सकता है: 17 एमएस 33 एमएस 52 एमएस 60 एमएस 55 एमएस आदि

यह 90 प्रतिशत प्रतिक्रिया समय रिपोर्ट करने के लिए उपयोगी है, 80 वीं प्रतिशतक प्रतिक्रिया समय , आदि

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

मेमोरी अनुरोधों की संख्या के साथ रैखिक रूप से स्केल का उपयोग करता है।

क्या कोई एल्गोरिदम है जो सीमित स्मृति उपयोग के "अनुमानित" प्रतिशत आंकड़े उत्पन्न करता है? उदाहरण के लिए, मान लीजिए कि मैं इस समस्या को इस तरह हल करना चाहता हूं कि मैं लाखों अनुरोधों को संसाधित करता हूं लेकिन केवल प्रतिशत उपयोग ट्रैकिंग के लिए एक किलोबाइट मेमोरी का उपयोग करना चाहता हूं (पुराने अनुरोधों के लिए ट्रैकिंग को छोड़ना एक विकल्प नहीं है क्योंकि प्रतिशत को माना जाता है सभी अनुरोधों के लिए हो)।

यह भी आवश्यक है कि वितरण का कोई प्राथमिक ज्ञान न हो। उदाहरण के लिए, मैं समय से पहले बाल्टी की किसी भी श्रेणी को निर्दिष्ट नहीं करना चाहता हूं।

Answer 1

मुझे विश्वास है कि इस समस्या के लिए कई अच्छे अनुमानित एल्गोरिदम हैं। एक अच्छा पहला-कट दृष्टिकोण केवल एक निश्चित आकार सरणी का उपयोग करना है (डेटा के 1 के लायक कहें)। कुछ संभावना पी ठीक करें। प्रत्येक अनुरोध के लिए, संभाव्यता पी के साथ, सरणी में अपना प्रतिक्रिया समय लिखें (वहां सबसे पुराना समय बदलना)। चूंकि सरणी लाइव स्ट्रीम का सबसमलिंग है और चूंकि सबसमलिंग वितरण को बरकरार रखता है, इसलिए उस सरणी के आंकड़े करने से आपको पूर्ण, लाइव स्ट्रीम के आंकड़ों का अनुमान मिल जाएगा।

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

यदि आपको लगता है कि आपको पर्याप्त आंकड़े देने के लिए आपको बहुत अधिक स्मृति की आवश्यकता है, तो आपको आगे खोदना होगा। अच्छे कीवर्ड हैं: "स्ट्रीम कंप्यूटिंग", "स्ट्रीम आंकड़े", और निश्चित रूप से "प्रतिशत"। आप "ire और curses" के दृष्टिकोण को भी आजमा सकते हैं।

Answer 2

यदि आप अधिक से अधिक डेटा प्राप्त करते समय स्मृति उपयोग को स्थिर रखना चाहते हैं, तो आपको किसी भी तरह से डेटा resample होना होगा। इसका तात्पर्य है कि आपको किसी प्रकार की rebinning योजना लागू करनी होगी। आप तब तक इंतजार कर सकते हैं जब तक कि आप रिबिनिंग शुरू करने से पहले कच्चे इनपुट की एक निश्चित राशि प्राप्त नहीं कर लेते, लेकिन आप इसे पूरी तरह से नहीं बचा सकते हैं।

तो आपका प्रश्न वास्तव में पूछ रहा है कि "मेरे डेटा को गतिशील रूप से कताई करने का सबसे अच्छा तरीका क्या है"? बहुत सारे दृष्टिकोण हैं, लेकिन यदि आप अपनी मान्यताओं को सीमाओं या वितरण के वितरण के बारे में अपनी धारणाओं को कम करना चाहते हैं, तो एक सरल दृष्टिकोण निश्चित आकार के की बाल्टी पर औसत है, जो लॉगरिदमिक रूप से वितरित चौड़ाई के साथ है। उदाहरण के लिए, मान लें कि आप किसी भी समय स्मृति में 1000 मानों को पकड़ना चाहते हैं। के के लिए आकार चुनें, 100 कहें। अपना न्यूनतम रिज़ॉल्यूशन चुनें, 1ms कहें। (W = 2ms) 1-3ms

तीसरा बाल्टी:: फिर

• पहले बाल्टी 0-1ms के बीच मूल्यों (चौड़ाई = 1ms)
• दूसरा बाल्टी के साथ संबंधित 3-7ms (w = 4ms)
• चौथा बाल्टी: 7-15ms (= 8ms डब्ल्यू)
• ...
• दसवीं बाल्टी: 511-1023ms (w = 512ms)

इस प्रकार कादृष्टिकोण hash table algorithms में उपयोग की जाने वाली चंकिंग सिस्टम के समान है, जो कुछ फाइल सिस्टम और मेमोरी आवंटन एल्गोरिदम द्वारा उपयोग किया जाता है। यह तब अच्छा काम करता है जब आपके डेटा में एक बड़ी गतिशील रेंज होती है।

जैसा कि नए मान आते हैं, आप चुन सकते हैं कि आप अपनी आवश्यकताओं के आधार पर कैसे पुन: नमूना करना चाहते हैं। उदाहरण के लिए, आप moving average ट्रैक कर सकते हैं, first-in-first-out, या कुछ और अधिक परिष्कृत विधि का उपयोग करें।एक दृष्टिकोण के लिए Kademlia एल्गोरिदम देखें (Bittorrent द्वारा उपयोग किया गया)।

आखिरकार, पुनर्जन्म आपको कुछ जानकारी खोना चाहिए। कताई के संबंध में आपके विकल्प यह निर्धारित करेंगे कि कौन सी जानकारी गुम हो गई है। यह कहने का एक और तरीका यह है कि निरंतर आकार मेमोरी स्टोर dynamic range और sampling fidelity के बीच एक व्यापार-बंद का तात्पर्य है; आप कैसे व्यापार करते हैं आप पर निर्भर है, लेकिन किसी भी नमूना समस्या की तरह, इस मूल तथ्य के आसपास कोई नहीं है।

यदि आप वास्तव में पेशेवरों और विपक्ष में रूचि रखते हैं, तो इस मंच पर कोई जवाब पर्याप्त होने की उम्मीद नहीं कर सकता है। आपको sampling theory में देखना चाहिए। इस विषय पर उपलब्ध बड़ी मात्रा में शोध है।

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

संपादित करें: अपनी टिप्पणी का उत्तर देने के लिए, यहां एक साधारण कताई एल्गोरिदम का उदाहरण दिया गया है।

• आप 10 डिब्बे में 1000 मान स्टोर करते हैं। इसलिए प्रत्येक बिन में 100 मान होते हैं। मान लें कि प्रत्येक बिन को गतिशील सरणी (एक 'सूची', पर्ल या पायथन शब्दों में) के रूप में कार्यान्वित किया जाता है।

• एक नया मान की बात आती है में:

  • तय करें कि कौन बिन उस में संग्रहित किया जाना चाहिए, बिन सीमा आपके द्वारा चुने गए पर आधारित है।
  • यदि बिन पूर्ण नहीं है, तो बिन सूची में मान संलग्न करें।
  • यदि बिन भर गया है, तो बिन सूची के शीर्ष पर मान हटाएं, और बिन सूची के नीचे नया मान संलग्न करें। इसका मतलब है कि पुराने मूल्यों को समय के साथ फेंक दिया जाता है।

• 90 वें प्रतिशत को खोजने के लिए, बिन 10 को क्रमबद्ध करें। 90 वां प्रतिशत क्रमबद्ध सूची (तत्व 900/1000) में पहला मान है।

यदि आप पुराने मूल्यों को फेंकना पसंद नहीं करते हैं, तो आप इसके बजाय उपयोग करने के लिए कुछ वैकल्पिक योजना लागू कर सकते हैं। उदाहरण के लिए, जब एक बिन पूर्ण हो जाता है (मेरे उदाहरण में 100 मान तक पहुंच जाता है), तो आप सबसे पुराने 50 तत्वों (यानी सूची में पहले 50) का औसत ले सकते हैं, उन तत्वों को त्यागें, और फिर नया औसत तत्व संलग्न करें बिन, आपको 51 तत्वों के बिन के साथ छोड़कर अब 49 नए मूल्य रखने की जगह है। यह पुनर्जन्म का एक साधारण उदाहरण है।

rebinning का एक और उदाहरण downsampling है; उदाहरण के लिए, एक क्रमबद्ध सूची में हर 5 वें मूल्य को फेंकना।

मुझे उम्मीद है कि यह ठोस उदाहरण मदद करता है। दूर करने का मुख्य बिंदु यह है कि निरंतर स्मृति उम्र बढ़ने वाले एल्गोरिदम को प्राप्त करने के कई तरीके हैं; केवल आप तय कर सकते हैं कि आपकी आवश्यकताओं को संतोषजनक क्या है।

Answer 3

बड़े पूर्णांक या कुछ ऐसा गतिशील सरणी टी [] का उपयोग करें जहां टी [एन] प्रतिक्रिया समय एन मिलीसेकंड की संख्या की गणना करता है। यदि आप वास्तव में किसी सर्वर एप्लिकेशन पर आंकड़े कर रहे हैं तो संभवतः 250 एमएस प्रतिक्रिया समय आपकी पूर्ण सीमा है। तो आपके 1 केबी में 0 और 250 के बीच प्रत्येक एमएस के लिए 32 बिट्स पूर्णांक होता है, और आपके पास ओवरफ्लो बिन के लिए कुछ जगह छोड़ने के लिए कुछ कमरा होता है। यदि आप अधिक डिब्बे के साथ कुछ चाहते हैं, तो 1000 डिब्बे के लिए 8 बिट नंबरों के साथ जाएं, और जिस क्षण एक काउंटर बह जाएगा (यानी।उस प्रतिक्रिया समय पर 256 वें अनुरोध) आप बिट्स को सभी डिब्बे में 1 से नीचे स्थानांतरित करते हैं (प्रभावी रूप से सभी डिब्बे में मूल्य को कम करना)। इसका मतलब है कि आप उन सभी डिब्बेों की उपेक्षा करते हैं जो सबसे अधिक देखी जाने वाली बिन पकड़ने वाली देरी के 1/127 वें से कम कैप्चर करते हैं।

यदि आपको वास्तव में, वास्तव में विशिष्ट डिब्बे के सेट की आवश्यकता है तो मैं अनुरोधों के पहले दिन का उपयोग डिब्बे के उचित निश्चित सेट के साथ आने का सुझाव दूंगा। कुछ भी गतिशील, लाइव संवेदनशील प्रदर्शन अनुप्रयोग में काफी खतरनाक होगा। यदि आप उस पथ को चुनते हैं तो आप बेहतर तरीके से जानते होंगे कि आपका क्या कर रहा है, या एक दिन आपको बिस्तर से बाहर निकलने जा रहे हैं ताकि यह बताने के लिए कि आपका आंकड़ा ट्रैकर अचानक 90% सीपीयू और 75% मेमोरी उत्पादन सर्वर पर क्यों खा रहा है।

अतिरिक्त आंकड़ों के लिए: औसत और भिन्नता के लिए कुछ nice recursive algorithms हैं जो बहुत कम स्मृति लेते हैं। ये दो आंकड़े बहुत सारे वितरण के लिए अपने आप में उपयोगी हो सकते हैं क्योंकि central limit theorem बताता है कि पर्याप्त रूप से बड़ी संख्या में स्वतंत्र चर से उत्पन्न होने वाले वितरण सामान्य वितरण (जो कि माध्य और भिन्नता से पूरी तरह से परिभाषित हैं) तक पहुंचते हैं, आप इनमें से एक का उपयोग कर सकते हैं पिछली एन पर normality tests जहां एन पर्याप्त रूप से बड़ी है लेकिन आपकी स्मृति आवश्यकताओं से बाधित है) गीलेर की निगरानी करने के लिए सामान्यता की धारणा अभी भी है।

Answer 4

मैंने अभी एक blog post on this topic प्रकाशित किया है। मूल विचार "95% प्रतिशत प्रतिक्रियाओं के पक्ष में 500ms-600ms या उससे कम लेने के पक्ष में सटीक गणना के लिए आवश्यकता को कम करना है" (500ms-600ms के सभी सटीक प्रतिशत के लिए)

आप किसी भी संख्या की बाल्टी का उपयोग कर सकते हैं किसी भी मनमाने ढंग से आकार (जैसे 0ms-50ms, 50ms-100ms, ... बस कुछ भी जो आपके उपयोगकेस को फिट करता है)। आम तौर पर, यह अंतिम बाल्टी (यानी> 5000ms) में एक निश्चित प्रतिक्रिया समय (जैसे वेब अनुप्रयोग के लिए 5 सेकंड) से अधिक सभी अनुरोधों के लिए कोई समस्या नहीं होनी चाहिए।

प्रत्येक नए कब्जे वाले प्रतिक्रिया समय के लिए, आप बस उस बाल्टी के लिए काउंटर बढ़ाते हैं जिसमें यह गिरता है। एन-वें प्रतिशत का अनुमान लगाने के लिए, जो कुछ भी आवश्यक है, वह काउंटर को तब तक जोड़ रहा है जब तक कुल योग का प्रतिशत न हो।

इस दृष्टिकोण के लिए केवल 8 बाइट प्रति बाल्टी की आवश्यकता है, जो 1K स्मृति के साथ 128 बाल्टी ट्रैक करने की अनुमति देता है। 50 एमएमएस की ग्रैन्युलरिटी का उपयोग करके वेब एप्लिकेशन के प्रतिक्रिया समय का विश्लेषण करने के लिए पर्याप्त से अधिक)। (200 मि.से बाल्टी प्रति के साथ 60 काउंटरों का प्रयोग करके)

उदाहरण के लिए, यहाँ एक Google Chart मैं पर कब्जा कर लिया डेटा के 1 घंटे से बनाया है:

response times http://j.mp/3bTf36

अच्छा, हैं ना?:) Read more on my blog।

Answer 5

पेपर में परिभाषित सरल एल्गोरिदम का प्रयास करें "कई प्रतिशत के साथ-साथ अनुमान के लिए अनुक्रमिक प्रक्रिया" (राटिकेन)। यह तेज़ है, 2 * एम + 3 मार्कर (एम प्रतिशत के लिए) की आवश्यकता होती है और जल्दी सटीक अनुमान लगाती है।

Answer 6

(यह काफी कुछ समय हो गया है के बाद से इस प्रश्न पूछा गया था, लेकिन मैं कुछ संबंधित शोध पत्र का कहना है करना चाहते हैं)

में डेटा धाराओं की अनुमानित प्रतिशतक पर अनुसंधान के एक महत्वपूर्ण राशि हुई है पिछले कुछ साल। पूर्ण एल्गोरिथ्म परिभाषा के साथ कुछ दिलचस्प कागजात:

• A fast algorithm for approximate quantiles in high speed data streams

• Space-and time-efficient deterministic algorithms for biased quantiles over data streams

• Effective computation of biased quantiles over data streams

इन कागजों के सभी के लिए उप रैखिक अंतरिक्ष जटिलता के साथ एल्गोरिदम का प्रस्ताव डेटा स्ट्रीम पर अनुमानित प्रतिशत की गणना।