में किसी आइटम की अनुक्रमणिका ढूंढने का सबसे प्रभावी तरीका मैं वस्तुओं की एक सूची बनाए रखने के लिए एक क्रमबद्ध शब्दकोश का उपयोग कर रहा हूं, जिसमें से मुझे नियमित रूप से शीर्ष x आइटमों की स्थिति की निगरानी करने की आवश्यकता होती है। हर बार जब मैं कोई आइटम अपडेट करता हूं, तो मुझे यह पता लगाने का एक त्वरित तरीका चाहिए कि मैं जिस आइटम का जिक्र कर रहा हूं उसका उपयोग कर रहा हूं। मैं समझता हूं कि मैं पूरी सूची का आकलन कर सकता हूं और अपनी स्थिति को गिन सकता हूं, लेकिन मैं सभी प्रकार के शब्दकोश रेडब्लैक पेड़ पर होने के बाद ओ (लॉग एन) समय या बेहतर के साथ कुछ ढूंढ रहा हूं। प्रत्येक नोड अपने बच्चों का ट्रैक रखने में सक्षम होना चाहिए, और यह एक त्वरित गणना होना चाहिए।सॉर्टेड डिक्शनरी
उत्तर
आप बस को बदल सकते हैं अपने SortedDictionary<TKey, TValue>
एक SortedList<TKey, TValue>
में और उसके बाद का उपयोग IndexOfKey(key)
:
var s = new SortedList<string, string>
{ { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } };
// Outputs 1
Console.WriteLine(s.IndexOfKey("b"));
आंतरिक Array.BinarySearch<TKey>()
का उपयोग करता है, तो यह हे हो जाएगा (लॉग n) है, जो हे की तुलना में तेजी है (n) (जो यह होगा यदि आप इसके माध्यम से आगे बढ़कर सामने से पीछे की ओर खोज करते हैं)।
क्या होगा यदि आपको ओ (लॉग) (एन) खोज के अलावा ओ (1) डालने और हटाने की आवश्यकता है? –
@eranotzer: फिर आपको 'शब्दकोश
सूचकांक द्वारा वस्तुओं तक पहुंचने के लिए एक पेड़ संरचना का निर्माण किया जा सकता है या एलजीएन समय में किसी मौजूदा आइटम की अनुक्रमणिका की रिपोर्ट करने के लिए, आवेषण और हटाए जाने के लिए बहुत ही कम समय की आवश्यकता होती है। ऐसा करने का एक तरीका यह ट्रैक रखना होगा कि प्रत्येक नोड की बाएं और दाएं शाखाओं में कितनी वस्तुएं हैं (डालने या हटाने पर, बच्चों की गिनती बदलते समय पैरेंट नोड्स की नोड गिनती बदलें)। यदि पेड़-आधारित संरचना ऐसी सुविधा प्रदान नहीं करती है, हालांकि, मुझे इसे फिर से निकालने का कोई आसान तरीका नहीं है।
यह वह कोण है जिसे मैं ढूंढ रहा था - लेकिन मैं उस संरचना की तलाश में हूं जो पहले से ही है, या फिर से निकालने का एक आसान तरीका है। – Superman
क्या आपने 'सॉर्टेडलिस्ट' पर स्विच करने पर विचार किया है? यह इंडेक्स द्वारा 'ओ (1) 'पुनर्प्राप्ति कर सकता है। हालांकि, इसमें आवेषण और हटाने पर भयानक प्रदर्शन होता है। –
Ani
चूंकि यह एक वृक्ष संरचना है, इसलिए इंडेक्स की कोई अवधारणा नहीं है। बाएं और दाएं बच्चे के लिंक के साथ बस नोड्स। –
मुझे इस सवाल को समझ में नहीं आता है - पेड़ के सामानों में इंडेक्स नहीं है। – Lee