बहुत बड़े डेटा

Question

के लिए डेटा संरचना का चयन करना मेरे पास x (लाख) सकारात्मक पूर्णांक हैं, जहां उनके मान स्वीकृत (+2,147,483,647) जितना बड़ा हो सकते हैं। मान लीजिए कि वे अद्वितीय हैं, लुकअप गहन कार्यक्रम के लिए उन्हें स्टोर करने का सबसे अच्छा तरीका क्या है।

अब तक मैंने एक बाइनरी एवीएल पेड़ या हैश टेबल का उपयोग करने के बारे में सोचा था, जहां पूर्णांक मैप किए गए डेटा (एक नाम) की कुंजी है। हालांकि यह सुनिश्चित नहीं है कि मैं ऐसी बड़ी चाबियाँ और हैश टेबल के साथ इतनी बड़ी मात्रा में कार्यान्वित कर सकता हूं (क्या यह टकराव के लिए प्रवण होने के अलावा 0.8 लोड कारक नहीं बनायेगा?)

क्या मुझे कुछ सलाह मिल सकती है जिस पर डेटा संरचना मेरी स्थिति के लिए उपयुक्त हो सकती है

Answer 1

संरचना की पसंद इस बात पर निर्भर करती है कि आपके पास कितनी मेमोरी उपलब्ध है। मैं उस विवरण के आधार पर मान रहा हूं जिसे आपको लुकअप की आवश्यकता है, लेकिन उन पर लूप न करें, नजदीकी या अन्य समान परिचालन खोजें।

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

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

Answer 2

क्या आपने बी-पेड़ों में देखा है? दक्षता log_m(n) और log_(m/2)(n) के बीच चलती है, इसलिए यदि आप m चयन के आसपास होने के लिए 8-10 या तो तुम अगर स्मृति एक मुद्दा एक नक्शा शायद अपने सबसे अच्छे नहीं है नीचे से 10

Answer 3

के लिए अपनी खोज गहराई रखने के लिए सक्षम होना चाहिए शर्त। मानचित्र ओ (1) का अर्थ है कि जब आप वस्तुओं को देखने के लिए संख्याओं को स्केल करते हैं तो मूल्य खोजने के लिए समय लगता है।

एक नक्शा जहां कुंजी int है, और मान नाम है।

Answer 4

पहले हैश टेबल को आजमाएं। ऐसे कुछ प्रकार हैं जो महत्वपूर्ण मंदी के बिना बहुत घने हो सकते हैं (जैसे ब्रेंट की विविधता)।

आप केवल 32-बिट पूर्णांकों और दुकान नहीं किसी भी संबद्ध रिकॉर्ड करने के लिए की जरूरत है, सबसे सी ++ पुस्तकालयों में hash_set की तरह एक set और नहीं एक map का उपयोग करें। यह केवल 4-बाइट रिकॉर्ड और कुछ स्थिर ओवरहेड और 100% होने से बचने के लिए थोड़ा सा ढेर का उपयोग करेगा। सबसे बुरे मामले में, 'लाखों' संख्याओं को संभालने के लिए आपको कुछ दस मेगाबाइट की आवश्यकता होगी। बड़ा, लेकिन कुछ भी अप्रबंधनीय नहीं है।

यदि आपको इसे अधिक कठिन होने की आवश्यकता है, तो बस उन्हें एक सादे सरणी में सॉर्ट करें और उन्हें लाने के लिए बाइनरी खोज का उपयोग करें। ओ (1) के बजाय यह ओ (लॉग एन) होगा, लेकिन 'लाखों' रिकॉर्ड के लिए यह अभी भी उनमें से किसी एक को पाने के लिए बस कुछ कदम है। सी में आपके पास bsearch() है, जो जितना तेज़ हो सकता है।

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

Answer 5

बिट वेक्टर, सूचकांक सेट के साथ यदि संख्या मौजूद है। आप प्रत्येक नंबर की घटनाओं की संख्या के लिए इसे ट्वीक कर सकते हैं। बेंटले के प्रोग्रामिंग मोती में बिट वैक्टर के बारे में एक अच्छा कॉलम है।