2013-03-29 8 views
5

मान लें कि मेरे पास लाखों तार हैं। प्रत्येक स्ट्रिंग का एक मूल्य है। मैं इनपुट स्ट्रिंग द्वारा इस मान को पुनर्प्राप्त करना चाहता हूं लेकिन मैं इन सभी तारों को स्टोर नहीं करना चाहता क्योंकि वे बहुत सी जगह लेते हैं। मैं हैश टेबल का उपयोग नहीं कर सकता क्योंकि इसकी स्मृति में सभी या कम से कम कई तारों को स्टोर करने की आवश्यकता है। तो मेरे मामले के लिए अच्छी डेटा संरचना क्या है (मुझे किसी भी स्ट्रिंग को जोड़ने या हटाने की ज़रूरत नहीं है, मेरे पास पहले से ही तैयार डेटा है और पढ़ना केवल ऑपरेशन की अनुमति है)तारों को स्टोर करने के लिए मेमोरी कुशल तरीका

+2

प्रोग्रामिंग भाषा क्या है? इसके अलावा, क्या कई समान तार हैं? –

+0

@ jdv-Jan de Vaan कोई भी तार अनूठा नहीं है। मुझे नहीं लगता कि मेरा प्रश्न भाषा विशिष्ट है लेकिन मैं सी # पसंद करता हूं। – Neir0

+1

यह स्पष्ट नहीं है कि आपको क्या करना है। क्या आपको बस उन नंबरों को निकालने और दूसरी फ़ाइल में सहेजने की आवश्यकता है? या क्या आपको उनके साथ कुछ गणना करने की ज़रूरत है? क्या इनपुट ऑर्डर संरक्षित नहीं है तो यह ठीक है? –

उत्तर

0

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

यदि आप लुकअप करते हैं तो आप रचनात्मक थे कि आप हैश तालिका में प्रत्येक स्ट्रिंग का संकुचित रूप भी संग्रहित कर सकते हैं। आम तौर पर तार कितने समय तक होते हैं?

+0

औसत लंबाई 10 अक्षरों है। कम से कम मैं अपने हैशटेबल की एक आइटम बाल्टी के साथ तारों को स्टोर नहीं कर सकता। तो मुझे लगता है कि इस दृष्टिकोण को सुधारने का कोई तरीका मौजूद है। – Neir0

4

उपयोग एक trie आम सबस्ट्रिंग भंडारण को रोकने के लिए ..

+0

ट्री अच्छा विचार है लेकिन यह बहुत धीमी हैशटेबल है। – Neir0

+0

@ लार्समैन हे!हालांकि मैंने इस तरह के बारे में कुछ बड़े रेगेक्स पैटर्न की दक्षता को अधिकतम करने के लिए किया है, हालांकि अब मुझे आश्चर्य है कि अगर यह रेगेक्स स्ट्रिंग को पार्स किया जाता है तो यह स्वचालित रूप से किया जाता है। यह जानकर अच्छा लगा कि इसे क्या कहा जाता है। – Nolo

+0

एक हैशटेबल तारों को संग्रहित करने का एक स्मृति प्रभावी तरीका नहीं है, हालांकि – argentage

1

आप Judy tree है, जो एक संस्करण स्ट्रिंग कुंजी के लिए बनाया गया दोनों तेजी से और कॉम्पैक्ट डिज़ाइन किया गया है, और है को देखने के लिए चाहते हो सकता है। इसका कार्यान्वयन sourceforge पर उपलब्ध है।

2

यदि आप शब्द सूची को पूर्व-संसाधित कर सकते हैं तो CMPH जैसे सही हैंश पर एक नज़र डालें।

CMPH डॉक्स से (gperf एक और है, लेकिन छोटे डेटा सेट के लिए अनुकूलित लगता है।):

एक परिपूर्ण हैश फंक्शन टकराव के बिना मीटर पूर्णांक संख्याओं के एक समूह में एन चाबियों का एक स्थिर सेट नक्शे, जहां एम एन से बड़ा या बराबर है। यदि एम n के बराबर है, तो फ़ंक्शन को न्यूनतम कहा जाता है।

...

CMPH लाइब्रेरी एक आसान से उपयोग, उत्पादन गुणवत्ता, तेजी से एपीआई में नवीनतम और अधिक कुशल एल्गोरिदम समाहित। पुस्तकालय को बड़ी प्रविष्टियों के साथ काम करने के लिए डिज़ाइन किया गया था जो मुख्य स्मृति में फिट नहीं हो सकते हैं। इसका उपयोग 100 मिलियन से अधिक कुंजी के साथ सेट के लिए न्यूनतम परिपूर्ण हैश फ़ंक्शंस बनाने के लिए सफलतापूर्वक किया गया है, ...

संबंधित मुद्दे