मैं डेटा के कुछ बहुत बड़े सेटों के साथ काम पर खेल रहा हूं, आम तौर पर कई अरब तत्व, जो सभी memcached क्लाउड में बनाए जाते हैं और समय-समय पर फाइलों में फंस जाते हैं, और मेरे कार्यों में से एक के लिए मैं गिनने की कोशिश कर रहा हूं इस सेट की कार्डिनालिटी।आप पाइथन में कुशलतापूर्वक बहुत बड़े डेटासेट की कार्डिनिटी कैसे गिनते हैं?
कुछ संदर्भों के लिए, प्रत्येक आइटम में एक आईपी और कुछ अन्य विशेषताएं होती हैं जो किसी व्यक्ति की पहचान करती हैं और बेस 64 में एन्कोड की जाती हैं, आइटम का आकार 20 बाइट होता है। कुछ क्षेत्रों को हटाकर किसी आइटम के आकार को कम करना एक संभावना नहीं है।
यहाँ कुछ है कि एक में स्मृति संस्करण के रूप में मेरे डाटासेट emulates (स्ट्रिंग पीढ़ी के लिए this post करने के लिए धन्यवाद) है:
import base64, os
dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]
मेरा पहला दृष्टिकोण इस तरह की एक HashSet उपयोग करने के लिए किया गया था:
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
जबकि सिद्धांत में यह एक छोटे से डेटासेट पर ठीक काम करता है, जैसा कि आप अनुमान लगा सकते हैं कि एक हिचकी है:
- मैं अपने डेटा की विशिष्टता पर कोई धारणा नहीं कर सकता। मेरे पास 50% डेटासेट हो सकता है जो अद्वितीय है, या मेरे पास 100% भी हो सकता है। यह नियमित समय अंतराल पर गतिशील रूप से उत्पन्न होता है और कई कारकों (उदाहरण के लिए दिन का समय)
- डेटासेट आकार 10 बिलियन के आधार पर भिन्न होता है। बेस 64 में एन्कोड किए गए प्रत्येक आइटम में 20 बाइट्स हैं, कभी-कभी 10 बिलियन औसतन कुछ सौ गीगाबाइट होते हैं। दुर्भाग्यवश, मेरे पास उस मशीन के साथ बहुत अधिक RAM तक पहुंच नहीं है!
मैंने अपना होमवर्क किया है और कुछ शोध पत्र, या कुछ अस्पष्ट पुस्तकालयों में पाया है, लेकिन इसका लक्ष्य यह है कि यह समझने के लिए कि कौन सा दृष्टिकोण काम करता है और क्यों।
तो मैं आपको पाइथन उपयोगकर्ताओं से बुला रहा हूं, क्या आप किसी भी एल्गोरिदम के बारे में जानते हैं जो मुझे कार्डिनालिटी का कुशलतापूर्वक अनुमान लगाने में मदद करेगा? जटिलता से मेरा मतलब है कि मुझे समय जटिलता चलाने के बारे में बहुत कुछ परवाह नहीं है, लेकिन मैं अंतरिक्ष जटिलता के बारे में अधिक केंद्रित हूं। मुझे थोड़ा सटीकता बलिदान नहीं लगता है अगर यह प्रदर्शन को काफी बढ़ाता है (इसलिए मुझे अनिवार्य रूप से यूनिक्स की सटीक संख्या जानने की आवश्यकता नहीं है, भले ही यह आदर्श होगा, लेकिन शायद एक व्यावहारिक दृष्टिकोण नहीं है)। मैं कहूंगा कि 5% तक स्वीकार्य होगा। मैं इस परियोजना के लिए विशेष रूप से पायथन में कुछ ढूंढ रहा हूं।
आपकी सहायता के लिए धन्यवाद!
जैसा कि कुछ लोगों ने नोट किया था, मैं हडोप/एमआर का उपयोग कर सकता हूं, लेकिन इस विशिष्ट परियोजनाओं के लिए हम एमआर मार्ग नहीं जाना चाहते हैं, और एक मशीन पर इसे करने के लिए एल्गोरिदम का पता लगाना चाहते हैं, क्योंकि यह कुछ अन्य विभिन्न परियोजनाओं पर लागू किया जाए।
बस एक सुझाव है, लेकिन यह ऐसा कुछ लगता है जो मानचित्र-घटावट ढांचे के लिए अच्छा हो सकता है - आपके डेटा में मैपिंग तत्वों को एक शब्दकोश या किसी चीज़ में गिना जाता है । इसके लिए, आप [MRJob] (https://github.com/Yelp/mrjob) का उपयोग कर सकते हैं, पाइथन मानचित्र-येलप द्वारा बनाए गए ढांचे को कम करें। एमआरजेब के साथ अमेज़ॅन ईसी 2 में इसे चलाने के लिए भी आपके लिए एक अच्छा विचार हो सकता है। मैंने इसे पहले बड़े कॉर्प्रा में शब्द आवृत्ति गणना के लिए उपयोग किया है। मुझे लगता है कि यह इस बात पर निर्भर करता है कि आप व्यक्तिगत डेटा तत्वों को कैसे पार्स करेंगे। – ely
सुझाव के लिए धन्यवाद, हाँ मैंने एमआर के बारे में सोचा है (मैं वास्तव में इसे अन्य परियोजनाओं में बहुत उपयोग कर रहा हूं), लेकिन इस विशिष्ट समस्या के लिए एमआर/हाडोप एक विकल्प नहीं है, हम एल्गोरिदम में देखना चाहते हैं अवधारणा के सबूत के हिस्से के रूप में इसे एक मशीन में करें। –
यदि 100% सटीकता महत्वपूर्ण नहीं है, तो शायद एक ब्लूम फ़िल्टर जो आपको 5% त्रुटि देगा स्मृति में फिट होगा? यदि नहीं, और एक मशीन आवश्यक है, तो आप आसानी से अद्वितीय कुंजी के साथ कुछ सरल nosql डेटाबेस का उपयोग कर सकते हैं, जो डिस्क पर स्टोर करता है और डुप्लिकेट को हटा देता है। यह धीमा हो जाएगा, लेकिन यह आपके पास जो भी रैम है, उसके साथ काम करेगा। आप अभी भी वास्तविक सम्मिलन कार्य को समानांतर कर सकते हैं। –