मेरे पास 100+ मिलियन तारों का एक सेट है, प्रत्येक 63 वर्ण तक लंबा है। मेरे पास बहुत सी डिस्क स्पेस और बहुत कम मेमोरी है (512 एमबी)। मुझे अकेले अस्तित्व के लिए पूछताछ की जरूरत है, और कोई अतिरिक्त मेटाडाटा स्टोर नहीं है।तारों के बड़े सेट में अस्तित्व की जांच करने का कुशल तरीका
मेरा डी फैक्टो समाधान एक बीडीबी बीटी है। क्या कोई बेहतर विकल्प हैं? मुझे लेवलडब और क्योटो कैबिनेट के बारे में पता है, लेकिन फायदे की पहचान करने के लिए पर्याप्त परिचित नहीं है।
यदि झूठी सकारात्मक स्वीकार्य हैं, तो एक संभावित समाधान bloom filter का उपयोग करना होगा। ब्लूम फ़िल्टर हैंश टेबल के समान हैं, लेकिन बाल्टी की एक तालिका को इंडेक्स करने के लिए एक हैश मान का उपयोग करने के बजाय, यह एक बिट सरणी को इंडेक्स करने के लिए एकाधिक हैंश का उपयोग करता है। उन सूचकांक से संबंधित बिट्स सेट हैं। फिर, परीक्षण करने के लिए कि स्ट्रिंग फ़िल्टर में है या नहीं, स्ट्रिंग फिर से धोया गया है, और यदि संबंधित इंडेक्स सेट हैं, तो स्ट्रिंग फ़िल्टर में "अंदर" है।
यह तारों के बारे में कोई जानकारी संग्रहीत नहीं करता है, इसलिए यह बहुत कम स्मृति का उपयोग करता है - लेकिन यदि दो तारों के बीच टकराव होता है, तो कोई टकराव समाधान संभव नहीं होता है। इसका मतलब है कि झूठी सकारात्मक हो सकती है (क्योंकि फिल्टर में मौजूद एक स्ट्रिंग फ़िल्टर में मौजूद स्ट्रिंग के समान इंडेक्स में हैश हो सकती है)। हालांकि, कोई झूठी नकारात्मक नहीं हो सकती है; वास्तव में सेट में मौजूद कोई भी स्ट्रिंग ब्लूम फ़िल्टर में पाई जाएगी।
fewPythonimplementations हैं। अपने आप को रोल करना भी मुश्किल नहीं है; मुझे bitarray एस का उपयोग करके एक बार एक त्वरित और गंदे खिलने वाले फ़िल्टर को कोडिंग करना याद है जो बहुत अच्छी तरह से प्रदर्शन करता है।
आपके "त्वरित और गंदे कार्यान्वयन ने झूठी सकारात्मकताओं को कैसे हल किया? – martineau
@ मार्टिनौ, ठीक है, यह वास्तव में नहीं था। मेरे मामले में झूठी सकारात्मक स्वीकार्य थी। मैं संभावित डुप्लिकेट की तलाश में एक बहुत बड़े डेटासेट पर फिर से चल रहा था।मुझे यह सुनिश्चित करने की आवश्यकता नहीं थी कि वे डुप्लीकेट थे; मैं आगे प्रसंस्करण के लिए डेटासेट को पतला कर रहा था। रचनात्मकता के लिए – senderle
आपने कहा कि आपके पास बहुत सारी डिस्क है, हुह? एक विकल्प तारों को नेस्टेड उपनिर्देशिका में फ़ाइल नाम के रूप में स्टोर करना होगा। आप या तो तार सीधे इस्तेमाल कर सकते हैं: d/r/e/w/ sears
में या तार का एक हैश इसी तरह की प्रक्रिया ले रहे हैं और पालन करते हुए
f0/10/fe/6e/20d12ed895c10b93b2f81c6e नाम की एक खाली फ़ाइल बनाएं।इसे ओएस-अनुकूलित, हैश-टेबल आधारित अनुक्रमित नोएसQL डेटाबेस के रूप में सोचें।
साइड लाभ:
+1 - लेकिन ओएस का उपयोग करके धीमी गति से घोंसला वाली फ़ाइलों के अस्तित्व की जांच करने के लिए धीमा हो सकता है, इन्हें पहले स्थान पर बनाने का उल्लेख नहीं करना चाहिए। – martineau
असल में अब मैं इसके बारे में और सोचता हूं, नेस्टेड उपनिर्देशिका का एक गुच्छा क्यों है? इसके बजाय बस प्रत्येक स्ट्रिंग के लिए एक खाली फ़ाइल बनाएं और उन्हें एक ही निर्देशिका में स्टोर करें। बेशक कुछ फाइल सिस्टम समस्याएं हो सकती हैं ... – martineau
परीक्षण के बिना, मुझे यकीन नहीं है कि यह धीमा होगा या नहीं। यह वास्तव में फाइल सिस्टम के आधार पर काफी spritely हो सकता है। छोटी निर्देशिकाओं के साथ बहुत सी फाइल सिस्टम बहुत तेज हैं, और अधिकांश (सभी?) आधुनिक एफएस कैश निर्देशिका लुकअप अच्छी तरह से हैं। वह नेस्टेड उपनिर्देशिकाओं के लिए प्रेरणा थी। –
क्या आप कभी-कभी झूठी सकारात्मक सहन कर सकते हैं? – senderle
झूठी नकारात्मक अस्वीकार्य हैं; कभी-कभी झूठे सकारात्मक संभावित रूप से सहनशील होते हैं। –
बस उन्हें 'सेट' में संग्रहीत करें और ओएस के वर्चुअल मेमोरी मैनेजर को आवश्यकतानुसार डिस्क पर जाने दें। आप इसे 'पिकले' का उपयोग करके डिस्क पर स्पष्ट रूप से सहेज सकते हैं। डेटाबेस बनाने की जरूरत नहीं है। – martineau