लॉग एंबोरिदम

Question

लॉग इन करें हमें इन ~ 50 जीबी डेटा फाइलें मिलती हैं जिनमें 16 बाइट कोड शामिल हैं, और मैं किसी भी कोड को ढूंढना चाहता हूं जो 1/2% समय या उससे अधिक होता है। क्या डेटा पर एक ही पास में ऐसा कोई तरीका है जो मैं कर सकता हूं?

संपादित करें: बहुत सारे कोड हैं - यह संभव है कि प्रत्येक कोड अलग हो।

EPILOGUE: मैंने दारायस बेकन को सबसे अच्छे उत्तर के रूप में चुना है, क्योंकि मुझे लगता है कि सबसे अच्छा एल्गोरिदम वह बहुसंख्यक तत्व का एक संशोधन है जिसे उन्होंने लिंक किया है। अधिकांश एल्गोरिदम को केवल थोड़ी मात्रा में स्मृति का उपयोग करने के लिए संशोधित किया जाना चाहिए - जैसे 201 कोड 1/2% मुझे लगता है। असल में आप केवल 201 अलग-अलग कोडों की गिनती स्ट्रीम चलते हैं। जैसे ही आपको 201 अलग-अलग कोड मिलते हैं, आप प्रत्येक कोड में से एक को छोड़ देते हैं (काउंटर से 1 कटौती, 0 जो भी हो जाता है उसे भूल जाते हैं)। अंत में, आप अधिकतर एन/201 बार गिर गए हैं, इसलिए किसी भी कोड की तुलना में अधिक बार होनी चाहिए जो अभी भी आसपास होनी चाहिए।

लेकिन यह एक दो पास एल्गोरिदम है, एक नहीं। उम्मीदवारों की गणना के लिए आपको दूसरे पास की आवश्यकता है। यह देखना वास्तव में आसान है कि इस समस्या के किसी भी समाधान को कम से कम 2 पास का उपयोग करना चाहिए (आपके द्वारा लोड किए जाने वाले तत्वों का पहला बैच अलग हो सकता है और उनमें से एक कोड बिल्कुल 1/2% हो सकता है)

के लिए धन्यवाद नौकर!

Answer 1

Metwally et al., Efficient Computation of Frequent and Top-k Elements in Data Streams (2005)। याहू में मेरे काम के लिए मैंने कुछ अन्य प्रासंगिक कागजात पढ़े थे जिन्हें मैं अब नहीं ढूंढ सकता; लेकिन यह एक अच्छी शुरुआत की तरह दिखता है।

संपादित करें: आह, यह Brian Hayes article देखें। यह संदर्भ के साथ, डेमैन एट अल के कारण एक सटीक एल्गोरिदम स्केच करता है। यह बहुत कम स्मृति के साथ एक पास में करता है, जिसमें वे मौजूद होते हैं, जिनमें अक्सर आप जिन वस्तुओं की तलाश कर रहे हैं, उनमें से एक समूह का एक सेट प्रदान करते हैं। सटीक गणना प्राप्त करना एक (अब-ट्रैक्टेबल) दूसरा पास लेता है।

Answer 2

यह कोड के वितरण पर निर्भर करेगा। यदि वहां कुछ अलग-अलग कोड हैं, तो आप मानचित्र के साथ कोर में http://en.wikipedia.org/wiki/Frequency_distribution बना सकते हैं। अन्यथा आपको शायद http://en.wikipedia.org/wiki/Histogram बनाना होगा और फिर प्रत्येक बाल्टी में कोड की आवृत्तियों की जांच करने वाले डेटा पर एकाधिक पास करना होगा।

Answer 3

यह इस बात पर निर्भर करता है कि कितने अलग कोड मौजूद हैं, और आप कितनी मेमोरी उपलब्ध हैं।

मेरा पहला विचार काउंटर के रूप में कोड के साथ काउंटरों की हैश तालिका बनाना होगा। पूरी फाइल के माध्यम से लूप, संबंधित कोड के काउंटर में वृद्धि, और कुल संख्या गिनती। अंत में, काउंटर के साथ सभी कुंजियों को फ़िल्टर करें जो (* समग्र-काउंटर 1/200) से अधिक है।

Answer 4

यदि फ़ाइलें पूरी तरह से 16-बाइट कोड हैं, और आप जानते हैं कि प्रत्येक फ़ाइल कितनी बड़ी है, तो आप प्रत्येक फ़ाइल में कोड की संख्या की गणना कर सकते हैं। फिर आप 0.5% थ्रेसहोल्ड पा सकते हैं और प्रत्येक कोड की घटनाओं की गणना करने के लिए किसी भी अन्य सुझावों का पालन कर सकते हैं, प्रत्येक आवृत्ति रिकॉर्डिंग, जिसकी आवृत्ति दहलीज को पार करती है।

Answer 5

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

Answer 6

स्मृति में फ़ाइल के क्रमबद्ध भाग, जैसे कि आप प्रदर्शन कर रहे थे और बाहरी प्रकार। प्रत्येक खंड में सभी क्रमबद्ध कोड लिखने के बजाय, आप केवल प्रत्येक अलग कोड और उस खंड में घटनाओं की संख्या लिख ​​सकते हैं। अंत में, प्रत्येक कोड के घटनाओं की संख्या को खोजने के लिए इन सारांश रिकॉर्ड्स को मर्ज करें।

यह प्रक्रिया किसी भी आकार के डेटा के पैमाने पर है, और यह केवल इनपुट डेटा पर एक पास बनाता है। एकाधिक मर्ज पास की आवश्यकता हो सकती है, इस पर निर्भर करता है कि आप कितनी सारांश फाइलें खोलना चाहते हैं।

---

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

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

तो, आप प्रत्येक कोड से जुड़े इनपुट के अनुपात को जानते हैं।

यह मूलतः पाइपलाइन sort * | uniq -c

हर कोड सिर्फ एक बार दिखाई देता है तो यह है कि कोई समस्या नहीं है; आपको बस उन्हें गिनने में सक्षम होना चाहिए।