से सामान्य तत्व खोजें दो पूर्णांक सरणी हैं, प्रत्येक में बहुत बड़ी फाइलें हैं (प्रत्येक का आकार रैम से बड़ा है)। आप रैखिक समय में सरणी में सामान्य तत्व कैसे पाएंगे।दो बहुत बड़े Arrays
मुझे इस समस्या का एक अच्छा समाधान नहीं मिल रहा है। कोई विचार?
एक फ़ाइल पर एक पास बिटमैप (या Bloom filter बनाता है अगर पूर्णांक रेंज स्मृति में बिटमैप के लिए बहुत बड़ी है)।
दूसरी फ़ाइल पर एक पास डुप्लीकेट (या ब्लूम फ़िल्टर का उपयोग करने वाले उम्मीदवार) को ढूंढता है।
यदि आप ब्लूम फ़िल्टर का उपयोग करते हैं, तो परिणाम संभाव्य है। नए पास झूठी सकारात्मक को कम कर सकते हैं (ब्लूम फिल्टर में झूठी नकारात्मक नहीं है)।
ठीक है। मुझे अब ब्लूम फिल्टर के बारे में पढ़ना होगा। बकवास: पी –
4 बाइट्स पूर्णांक के लिए, आपको ब्लूम फ़िल्टर की आवश्यकता नहीं है, केवल स्मृति के 0.5 गीगाइट्स। – AProgrammer
जो मैं अनुमान लगाता हूं,। एक अच्छा समाधान की तरह लगता है। धन्यवाद। –
ओ (एन) समय जटिलता के साथ सामान्य तत्वों को खोजने के लिए आप स्पष्ट रूप से हैश तालिका का उपयोग कर सकते हैं।
सबसे पहले, आपको पहले सरणी का उपयोग करके हैश तालिका बनाने की आवश्यकता है, फिर इस हैश तालिका का उपयोग करके दूसरी सरणी की तुलना करें।
सूची का आकार रैम की तुलना में ग्रेटर है .. आपके हैशटेबल में कोई सरणी पूरी तरह से नहीं रखेगी ..:/ –
बेशक आपको फ़ाइल-आधारित हैश को लागू करना होगा। – CashCow
कृपया विस्तृत करें ... आपका क्या मतलब है –
मान लीजिए कि आप एक ही आकार के साथ पूर्णांक की बात कर रहे हैं, और बाइनरी मोड में फ़ाइलों में लिखे गए हैं, तो आप पहले 2 फाइलों को सॉर्ट करें (एक क्विकॉर्ट का उपयोग करें, लेकिन फ़ाइल "ऑफसेट्स" को पढ़ने और लिखना)। फिर आपको केवल 2 फाइलों की शुरुआत से आगे बढ़ने की जरूरत है, और मैचों की जांच करें, यदि आपके पास एक मैच है तो आउटपुट को दूसरी फ़ाइल में लिखें (मान लीजिए कि आप परिणाम को मेमोरी में भी स्टोर नहीं कर सकते हैं) और फ़ाइलों पर आगे बढ़ते रहें ईओएफ तक।
छंटनी ओ (एन) आवश्यक नहीं है। –
निश्चित आकार पूर्णांक छंटनी वास्तव में ओ (एन): रेडिक्स सॉर्ट है। लेकिन बड़ी फ़ाइलों को संभालना तो स्मृति एक समस्या हो सकती है। – blaze
सॉर्ट करें फ़ाइलें। निश्चित लंबाई पूर्णांक के साथ यह ओ (एन) समय में किया जा सकता है:
क्रमबद्ध फ़ाइलों पर पूर्णांक का एक सामान्य सबसेट मिलता है: संख्याओं की तुलना करें, यदि वे बराबर हैं तो इसे लिखें, फिर छोटी संख्या वाले फ़ाइल पर एक नंबर आगे बढ़ें। यह ओ (एन) है।
सभी परिचालन ओ (एन) और अंतिम एल्गोरिदम ओ (एन) भी हैं।
संपादित करें: यदि आपके पास बिटमैप्स के लिए पर्याप्त स्मृति है तो बिटमैप विधि बहुत तेज है। यह विधि किसी निश्चित आकार पूर्णांक के लिए काम करती है, उदाहरण के लिए 64-बिट। आकार 2 का बिटमैप कम से कम कुछ वर्षों के लिए व्यावहारिक नहीं होगा :)
पूर्णांक आकार मानना 4 बाइट है। अब हमारे पास अधिकतम 2^32 पूर्णांक हो सकते हैं यानी मेरे पास सभी पूर्णांक का प्रतिनिधित्व करने के लिए 2^32 बिट्स (512 एमबी) का बिटकवेक्टर हो सकता है जहां प्रत्येक बिट 1 पूर्णांक को दोहराता है। 1. इस वेक्टर को सभी शून्यों के साथ प्रारंभ करें 2. अब एक फ़ाइल के माध्यम से जाएं और यदि आप एक पूर्णांक पाते हैं तो इस वेक्टर में बिट्स सेट करें। 3. अब अन्य फ़ाइल के माध्यम से जाएं और बिट वेक्टर में किसी भी सेट बिट की तलाश करें।
समय जटिलता O (n + m) अंतरिक्ष जटिलता 512 एमबी
यह केवल तभी काम करेगा जब एक ही आउटपुट की तरह कई घटनाओं का इलाज किया जा सके। मेरी राय में बढ़िया –
2^32 बिट्स 512 एमबी है, है ना? – blaze
यह उपरोक्त समाधान ' –
चलो कहते हैं कि पर्याप्त रैम या तो दिए गए फ़ाइल सरणी (एफए) के हैश का 5% धारण करने के लिए उपलब्ध है करते हैं।
तो, मैं फ़ाइल सरणी (एफए 1 और एफए 2) को 20 हिस्सों में विभाजित कर सकता हूं - सामग्री का एक एमओडी 20 कहें। हमें एफए 1 (0) मिलता है ....एफए 1 (1 9) और एफए 2 (0) ...... एफए 2 (1 9)। यह रैखिक समय में किया जा सकता है।
स्मृति में हैश एफए 1 (0) और इस हैश के साथ एफए 2 (0) की सामग्री की तुलना करें। अस्तित्व के लिए हैशिंग और जांच निरंतर समय संचालन है।
इस हैश को नष्ट करें और एफए 1 (1) के लिए दोहराएं ... एफए 1 (1 9)। यह भी रैखिक है। तो, पूरा ऑपरेशन रैखिक है।
वे क्रमबद्ध हैं? –
नहीं .. यादृच्छिक संख्या –
आकार का पूर्णांक क्या है? – harold