शीर्ष एन तत्वों को क्रमबद्ध क्रम में रखने के लिए सबसे अच्छी डेटा संरचना क्या है?

Question

मैं एक डेटा संरचना की तलाश में हूं जो शीर्ष n तत्वों को this question के समान रखता है, लेकिन क्रमबद्ध क्रम को बनाए रखने की अतिरिक्त आवश्यकता के साथ। जाहिर है, मैं बस अंत में सॉर्ट कर सकता हूं लेकिन फ्लाई पर इसे करने का एक और अधिक प्रभावी तरीका हो सकता है। अंत में सम्मिलन, कभी भी निष्कासन नहीं होगा, और फिर अंत में शीर्ष n तत्वों के माध्यम से पुनरावृत्ति होगी।

यह प्रश्न भाषा अज्ञेयवादी है लेकिन यह सी # में होगा, इसलिए देशी .NET संग्रह का उपयोग करने वाला एक उत्तर बेहतर है।

संपादित करें: मुझे यह स्पष्ट करना चाहिए कि सॉर्ट ऑर्डर केवल अंत में मायने रखता है जब शीर्ष n तत्वों को फिर से चालू किया जाता है। जिस तरह से सम्मिलन होते हैं, वैसे ही सॉर्ट ऑर्डर अप्रासंगिक है जब तक कि शीर्ष n तत्व बनाए रखा जाता है।

Answer 1

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

एक स्व-संतुलित बाइनरी खोज पेड़ स्थिर कारक द्वारा एक अंतर्निहित ढेर से धीमा है।

आप सॉर्ट किए गए तत्वों का उपयोग कैसे करना चाहते हैं? यदि आप क्रमबद्ध अनुक्रम के माध्यम से फिर से शुरू करना चाहते हैं, तो एक सामान्य स्व-संतुलित बाइनरी खोज पेड़ पर्याप्त होगा।

यदि आप किसी भी समय क्रमबद्ध अनुक्रम में किसी भी तत्व (किसी अन्य लक्जरी ...) में किसी भी तत्व को एक्सेस करना चाहते हैं तो आपको पेड़ को बढ़ाने की आवश्यकता है। असल में, प्रत्येक नोड में एक अतिरिक्त क्षेत्र होगा जिसमें नोड्स की संख्या को इसके उप-भाग में शामिल किया जाएगा, जिसमें स्वयं भी शामिल है।

Answer 2

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

एसटीएल के आंशिक क्रम जैसे प्री-बिल्ट आंशिक सॉर्टिंग विधियों में देखें।

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

Answer 3

आपको हमें एन के आदेश और एक आइटम डालने के क्रम पर एक सुराग देना होगा।

मुझे लगता है कि सॉर्ट ऑर्डर प्रासंगिक है, आप कैसे और जानेंगे कि कौन से तत्व शीर्ष n का हिस्सा हैं? सिर्फ इसलिए कि आप केवल सभी प्रविष्टियों के अंत में शीर्ष n चाहते हैं संरचनाओं या एल्गोरिदम के लिए/पूर्वाग्रह बना सकते हैं।

शीर्ष आइटम में से किसी भी आइटम को क्यों रखें n? आप आकार एन + 1 के क्रमबद्ध सेट (thinking of Python's deque) का उपयोग कर सकते हैं। जोड़ते समय, सूची के माध्यम से पुनरावृत्त करें और सेट में सही स्थान पर नया आइटम डालें। जब सेट आकार (एन + 1) हो जाता है, तो प्रत्येक डालने के बाद अंतिम आइटम को हटा दिया जाता है। इस तरह से आपके पास हमेशा n आइटम हैं जिनके साथ डेटा संरचना को बढ़ाए बिना आइटम को कभी भी पुनर्प्राप्त नहीं किया जाएगा।

इसके अलावा, यदि आप नीचे तत्व का मान रखने के (के n पिछले, इसे कहते ख) तो आप उस का उपयोग डालने पूर्णतः छोड़ कर सकते हैं। यह ओ (1) की तुलना की तुलना को सीमित करता है जब नई वस्तु xबी से बड़ी है।

Answer 4

यह उत्तर केली के समान है लेकिन एक परीक्षण कोड उदाहरण है। चूंकि एन का आकार छोटा < 100 है, इसलिए मैंने एक साधारण प्रविष्टि प्रकार का उपयोग किया, यदि बाइनरी सर्च लुकअप के साथ संशोधित किया गया है तो आइटम की संख्या कुछ (गैर-अनुकूलित) मान (उदा। 20 आइटम) से ऊपर है। मैंने इसका उपयोग दिखाने के लिए नमूना कंसोल ऐप (सी #) शामिल किया है। मैंने यह सुनिश्चित करने के लिए संक्षेप में इसका परीक्षण किया कि यह काम करता है, लेकिन इस समय मैंने इसका पूर्ण विश्लेषण नहीं किया। यह संरचना स्मृति उपयोग को कम करने के लिए अनुकूलित है।

public class TopNStructure<T> : IEnumerable<T> where T : IComparable<T> 
{ 
    private const int SizeForLinearOrBinaryInsert = 20; 

    private int _maxSize; 
    private int _currentSize; 
    private T[] _items; 
    private IComparer<T> _comparer; 

    /// <summary> 
    /// The number of items 
    /// </summary> 
    public int Count { get { return _currentSize; } } 

    public TopNStructure(int maxSize, IComparer<T> comparer) 
    { 
     if (maxSize <= 0) 
     { 
      throw new ArgumentOutOfRangeException("Max size must be a postive, non-zero value"); 
     } 
     _maxSize = maxSize; 
     _currentSize = 0; 
     _items = new T[maxSize]; 
     _comparer = comparer; 
    } 

    public TopNStructure(int maxSize) 
     : this(maxSize, Comparer<T>.Default) { } 

    /// <summary> 
    /// Adds an item to this structure 
    /// </summary> 
    /// <param name="item">The item to add</param> 
    /// <returns>True if the item was added, false otherwise</returns> 
    public bool Add(T item) 
    { 
     if (_currentSize == 0) 
     { 
      _items[0] = item;    
     } 
     else if (_currentSize == _maxSize) 
     { 
      if (_comparer.Compare(_items[_currentSize - 1], item) <= 0) 
      { 
       return false; 
      } 
      else 
      { 
       Insert(item); 
       return true; 
      } 
     } 
     else if (_currentSize == 1) 
     { 
      if (_comparer.Compare(_items[0], item) <= 0) 
      { 
       _items[1] = item; 
      } 
      else 
      { 
       _items[1] = _items[0]; 
       _items[0] = item; 
      }    
     } 
     else 
     { 
      if (_comparer.Compare(_items[_currentSize - 1], item) <= 0) 
      { 
       _items[_currentSize] = item; 
      } 
      else 
      { 
       Insert(item); 
      } 
     } 
     _currentSize++; 
     return true; 
    } 

    /// <summary> 
    /// Insert the item into the data structure 
    /// </summary> 
    /// <param name="item">The item to insert</param> 
    private void Insert(T item) 
    { 
     int start = 0; 
     if (_currentSize >= SizeForLinearOrBinaryInsert) 
     { 
      start = Array.BinarySearch<T>(_items, 0, _currentSize, item, _comparer); 
      if (start < 0) 
      { 
       start = ~start; 
      } 
      ShiftAndInsert(item, start, _currentSize);     
      return; 
     } 
     else 
     { 
      for (int i = start; i < _currentSize; i++) 
      { 
       if (_comparer.Compare(_items[i], item) > 0) 
       { 
        ShiftAndInsert(item, i, _currentSize);      
        return; 
       } 
      } 
      _items[_currentSize] = item; 
     }       
    } 

    /// <summary> 
    /// 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="maxIndex"></param> 
    private void ShiftAndInsert(T item, int index, int maxIndex) 
    { 
     if (maxIndex >= _maxSize) 
     { 
      maxIndex = _maxSize - 1; 
     } 
     for (int i = maxIndex; i > index; i--) 
     { 
      _items[i] = _items[i - 1]; 
     } 
     _items[index] = item; 
    } 


    public IEnumerator<T> GetEnumerator() 
    { 
     return ((IEnumerable<T>)_items).GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return _items.GetEnumerator(); 
    } 
} 

static void Main(string[] args) 
{ 
    TopNStructure<double> data = new TopNStructure<double>(25); 

    Random rand = new Random(132151); 
    for (int i = 0; i < 50; i++) 
    { 
     double value = rand.NextDouble(); 
     data.Add(value); 
    } 

    int j = 0; 
    foreach (double value in data) 
    { 
     Console.WriteLine("{0} {1}", j, value); 
     j++; 
    } 
    Console.ReadKey(); 
} 

Answer 5

यहां पहली बार एक समान डेटा संरचना है, जो इस समय सम्मिलन गति को बेहतर बनाने के लिए आंतरिक लिंक्ड सूची का उपयोग कर रही है। आप कुछ गति खो देते हैं क्योंकि आप सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग नहीं कर सकते हैं, लेकिन सम्मिलन और निकासी (वस्तुओं> एन) ओ (1) हैं और बाइनरी खोज की कमी को संतुलित करना चाहिए। यह संरचना अधिक स्मृति का उपयोग करती है क्योंकि लिंक्ड सूची में 2 अतिरिक्त पॉइंटर्स हैं।

public class TopNStructureLinkedList<T> : IEnumerable<T> where T : IComparable<T> 
{ 
    private const int SizeForLinearOrBinaryInsert = 20; 

    private int _maxSize; 
    private int _currentSize; 
    private LinkedList<T> _items; 
    private IComparer<T> _comparer; 
    private LinkedListNode<T> _largestItemNode; 

    /// <summary> 
    /// The number of items 
    /// </summary> 
    public int Count { get { return _currentSize; } } 

    public TopNStructureLinkedList(int maxSize, IComparer<T> comparer) 
    { 
     _maxSize = maxSize; 
     _currentSize = 0; 
     _items = new LinkedList<T>(); 
     _comparer = comparer; 
     _largestItemNode = null; 
    } 

    public TopNStructureLinkedList(int maxSize) 
     : this(maxSize, Comparer<T>.Default) { } 

    /// <summary> 
    /// Adds an item to this structure 
    /// </summary> 
    /// <param name="item">The item to add</param> 
    /// <returns>True if the item was added, false otherwise</returns> 
    public bool Add(T item) 
    { 
     if (_currentSize == 0) 
     { 
      _largestItemNode = _items.AddFirst(item);    
     } 
     else if (_currentSize == 1) 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       _largestItemNode = _items.AddAfter(_largestItemNode, item);     
      } 
      else 
      { 
       _items.AddBefore(_largestItemNode, item);     
      } 
     } 
     else if (_currentSize == _maxSize) 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       return false; 
      } 
      else 
      { 
       Insert(item); 
       _largestItemNode = _items.Last.Previous; 
       _items.RemoveLast(); 
       return true; 
      } 
     } 
     else 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       _largestItemNode = _items.AddAfter(_largestItemNode, item);  
      } 
      else 
      { 
       Insert(item); 
      } 
     } 
     _currentSize++; 
     return true; 
    } 

    /// <summary> 
    /// Insert the item into the data structure 
    /// </summary> 
    /// <param name="item">The item to insert</param> 
    private void Insert(T item) 
    { 
     LinkedListNode<T> node = _largestItemNode.Previous; 
     while (node != null) 
     {    
      if(_comparer.Compare(node.Value, item) <= 0) { 
       _items.AddAfter(node, item); 
       return; 
      } 
      node = node.Previous;    
     } 
     _items.AddFirst(item); 

    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return ((IEnumerable<T>)_items).GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return _items.GetEnumerator(); 
    } 
} 

Answer 6

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

एक सरणी के के शीर्ष तत्वों को खोजने के लिए Selection Algorithm का उपयोग करके आपको ओ (के लॉग एन) की जटिलता मिलती है। के एन से कम है, तो यह बेहतर है।

QuickSelect के लिए विकिपीडिया आलेख में एक कार्यान्वयन है। इसके अलावा, एक शुद्ध प्राथमिकता क्यूई का उपयोग करना (एक अलग तरीके से यहां वर्णित अधिकांश लोगों में) आसान है। एक नज़र में:

create_heap(array) // O(n) 
for(int i=0; i<k; i++) 
    sorted[i] = heap_pop(array) //O(log n)