टैग के लिए कुशल डेटास्ट्रक्चर?

Question

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

स्टैक ओवरफ्लो में लगभग 28532 अलग-अलग टैग हैं, आप सभी टैग के साथ एक टेबल बना सकते हैं और उन्हें एक पूर्णांक असाइन कर सकते हैं, इसके अलावा आप उन्हें आवृत्ति के अनुसार क्रमबद्ध कर सकते हैं ताकि सबसे आम टैग में सबसे कम संख्या हो। फिर भी उन्हें "1 32 45" प्रारूप में एक स्ट्रिंग की तरह संग्रहीत करना एक खोज और परिप्रेक्ष्य को संग्रहीत करने से थोड़ा अक्षम है

एक और विचार टैग को एक परिवर्तनीय बिटरैरे के रूप में सहेजना होगा जो एक लुकअप से आकर्षक है और परिप्रेक्ष्य को क्रमबद्ध करना है । चूंकि सबसे आम टैग सबसे पहले आप संभावित रूप से टैग की थोड़ी मात्रा में टैग फिट कर सकते हैं।

समस्या यह निश्चित रूप से होगी कि असामान्य टैग भारी बिटरारे उत्पन्न करेंगे। क्या 0 के बड़े स्पैन के लिए "संपीड़न" बिटरैर के लिए कोई मानक है? या किसी को पूरी तरह से कुछ अन्य संरचना का उपयोग करना चाहिए?

संपादित

मैं एक DB समाधान या एक समाधान है, जहां मैं स्मृति में पूरे टेबल रखने की जरूरत है, लेकिन व्यक्तिगत

Answer 1

आइटम फ़िल्टर के लिए एक संरचना के लिए नहीं देख रहा हूँ तुम 2 के साथ दूसरी तालिका की जरूरत है फ़ील्ड: tag_id question_id

यही है। फिर आप tag_id, question_id और question_id पर टैग इंडेक्स बनाते हैं, tag_id - जो इंडेक्स को कवर करेगा, इसलिए आपके सभी प्रश्न बहुत तेज होंगे।

Answer 2

अपने प्रश्न को कमजोर नहीं करना है, लेकिन 28k रिकॉर्ड वास्तव में बहुत से नहीं हैं। क्या आप शायद समय से पहले अनुकूलित कर रहे हैं? मैं पहली बार डीबी टेबल पर 'नियमित' सूचकांक का उपयोग करने के लिए चिपक जाता हूं। वे जो कठोर हेरिस्टिक का उपयोग करते हैं वे आमतौर पर बहुत ही कुशल होते हैं और हरा करने के लिए तुच्छ नहीं होते हैं (या यदि आप वास्तव में समय पर प्रयास के लायक हैं और लाभ काफी बड़े हैं?)।

यह भी निर्भर करता है कि आप वास्तव में टैग क्वेरी कहां करते हैं, क्या उपयोगकर्ता वास्तव में 200ms के समय को अनुकूलित करने के लिए अनुकूलित कर रहा है?

पहले उपाय के बाद अनुकूलित :-)

संपादित

एक डीबी के बिना मैं शायद एक मास्टर तालिका एक आईडी (यदि संभव हो तो यह स्मृति में पकड़) के साथ सभी टैग धारण करना होगा। प्रत्येक पोस्ट के साथ आईडी की नियमित क्रमबद्ध सूची रखें।

यह सुनिश्चित नहीं है कि समानता के आधार पर कितना संग्रहण मदद करेगा। एक क्रमबद्ध सूची जिसमें आप नियमित बाइनरी खोज कर सकते हैं, पर्याप्त तेज़ी से साबित हो सकता है; उपाय :-)

यहां आपको प्रत्येक टैग क्वेरी के लिए सभी पोस्ट फिर से शुरू करने की आवश्यकता होगी।

यदि यह धीमा होने वाला होता है तो आप प्रत्येक टैग के लिए पोस्ट पहचानकर्ताओं की जेब संग्रहित कर सकते हैं। यह डेटा संरचना कुछ हद तक बड़ी हो सकती है और इसके लिए फ़ाइल ढूंढने और पढ़ने के लिए फ़ाइल की आवश्यकता हो सकती है।

एक छोटी सी तालिका के लिए आप एक हैश मूल्य (डुप्लीकेट के साथ) के आधार पर एक बनाने का सहारा ले सकते हैं। इस तरह आप उन पदों की एक छोटी उम्मीदवार सूची में जल्दी से उतरने के लिए इसका उपयोग कर सकते हैं, जिन्हें देखने के लिए आगे की जांच की आवश्यकता है कि वे मेल खाते हैं या नहीं।

Answer 3

मुझे लगता है कि आपने अपना प्रश्न बहुत अधिक बताया है; आपने डेटा डेटाटाइक्चर तक पहुंचने के बारे में बहुत कुछ नहीं कहा, जो कि बहुत महत्वपूर्ण है।

कहा जा रहा है कि, मैं प्रत्येक टैग के लिए घटनाओं की संख्या को गिनने का सुझाव देता हूं और फिर टैग के लिए उपयोग किए जा सकने वाले सबसे छोटे एन्कोडिंग के साथ Huffman coding का उपयोग करने का सुझाव देता हूं। यह पूरी तरह से सही नहीं है, लेकिन जब तक आप यह प्रदर्शित नहीं करते हैं कि यह अनुचित है, तब तक मैं इसके साथ रहूंगा। फिर आप कोड को प्रत्येक प्रश्न के साथ जोड़ सकते हैं।

Answer 4

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