2012-02-10 21 views
9

में प्राथमिकता बदलें SortedList का उपयोग करके PriorityQueue<T> लिखने के लिए मैंने this question (जेसन द्वारा उत्तर) में दिए गए निर्देशों का पालन किया। मैं समझता हूं कि इस वर्ग के भीतर count फ़ील्ड का उपयोग अद्वितीय प्राथमिकताओं को सुनिश्चित करने और समान प्राथमिकता के बीच एनक्यू ऑर्डर को संरक्षित करने के लिए किया जाता है।प्राथमिकता कतार

हालांकि, count अपने अधिकतम मूल्य तक पहुंचता है और मैं इसके लिए 1 योग करता हूं, बाद वाला 0 से फिर से शुरू होगा, इसलिए बाद की वस्तुओं की प्राथमिकता पिछले आइटम की प्राथमिकता से अधिक होगी। इस दृष्टिकोण मैं एक तरह से करने के लिए "सुरक्षित रूप से" काउंटर count रीसेट के लिए की जरूरत सकता है का उपयोग करना ... वास्तव में, लगता है निम्नलिखित कतार राज्य के लिए (प्रारूप प्राथमिकता में | गिनती | मद):

0 | 123 | एक
0 | 345 | बी
1 | 234 | सी
2 | 200 | डी

अब मान लीजिए कि काउंटर सीमा तक पहुंच गई है, इसलिए मुझे इसे 0 पर रीसेट करना होगा: परिणामस्वरूप, अगले डालने वाले आइटम में काउंटर 0 होगा: उदाहरण के लिए, यदि मैं 1 के बराबर प्राथमिकता वाले तत्व को सम्मिलित करता हूं, तो यह 1 से पहले गलत तरीके से डाला जाएगा 234 | डी

0 | 123 | एक
0 | 345 | बी
1 | 000 | नया तत्व
1 | 234 | सी
2 | 200 | डी

प्राथमिकता की समस्या एक ढेर को लागू करने से हल किया जा सकता: मैं एक Heap श्रेणी का निर्माण, तो मैं आदेश TPriority द्वारा तत्वों को सॉर्ट करने में Heap<KeyValuePair<TPriority, TElement> और एक कस्टम PriorityComparer इस्तेमाल किया। एक int और Telement एक string के रूप में के रूप में TPriority को देखते हुए, PriorityComparer इस प्रकार है:

public class MyComparer : IComparer<KeyValuePair<int, string>> 
{ 
    public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y) 
    { 
     return x.Key.CompareTo(y.Key); 
    } 
} 

... 

int capacity = 10; 
Heap<KeyValuePair<int, string>> queue; 
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer()); 

... 

अद्यतन इस तरह से (PriorityComparer का उपयोग) में, मैं एक प्राथमिकता कतार लागू करने के लिए सफल हुए हैं। अब मैं रनटाइम पर अपने व्यवहार को संशोधित करने के लिए समर्थन जोड़ना चाहता हूं, यानी फीफो से प्राथमिकता सॉर्टिंग और इसके विपरीत स्विच करें। प्राथमिकता कतार के अपने कार्यान्वयन एक IComparer क्षेत्र है के बाद से, मुझे लगता है कि इस क्षेत्र को संपादित करने के लिए, की तरह इस प्रकार एक Comparer संपत्ति जोड़ने के लिए पर्याप्त है:

public IComparer 
{ 
    set 
    { 
     this._comparer = value; 
    } 
} 

इस बीच मैंने सोचा कि मैं एक अलग दृष्टिकोण काफ़ी होगा में: प्राथमिकताओं को प्रबंधित करने के लिए बाइनरी ढेर का उपयोग करने के बजाय, मैं अलग-अलग कतारों को लपेट सकता हूं (प्रत्येक पंक्ति में दी गई प्राथमिकता को संदर्भित किया जाता है)।

public class PriorityQueue<T, int> 
{ 
    private Queue<T> _defaultQueue; 
    private bool _priority; 
    private SortedList<int, Queue<T>> _priorityQueues; 

    public PriorityQueue(int capacity) 
    { 
     this._defaultQueue = new Queue<T>(capacity); 
     this._priority = false; 
     this._priorityQueues = new SortedList<int, Queue<T>>(0); 
    } 

    public void PriorityEnable() 
    { 
     this._priority = true; 
    } 

    public void PriorityDisable() 
    { 

     this._priority = false; 
    } 

    public void Enqueue(T item) 
    { 
     if (this._priority) 
     { 
      // enqueue to one of the queues 
      // with associated priority 
      // ... 
     } 
     else this._defaultQueue.Enqueue(item); 
    } 

    public T Dequeue() 
    { 
     if (this._priority) 
     { 
      // dequeue from one of the queues 
      // with associated priority and 
      // return 
      // ... 
     } 
     return this._defaultQueue.Dequeue(); 
    } 
} 
  1. कैसे फीफो मोडको प्राथमिकता मोड से संक्रमण का प्रबंधन करने के लिए जब वहाँ अभी भी कर रहे हैं डिफ़ॉल्ट कतार में तत्वों? मैं उन्हें प्राथमिकता कतार में आइटम प्राथमिकता के आधार पर कॉपी कर सकता हूं ... अन्य बेहतर समाधान?
  2. प्राथमिकता मोड से फीफो मोड से संक्रमण का प्रबंधन कैसे करें? इस मामले में, मेरे पास कई प्राथमिकताएं होंगी, जिनमें तत्व हो सकते हैं, लेकिन अब उन्हें प्राथमिकता के अनुसार प्रबंधित नहीं करना है और आगमन के मूल आदेश को भी नहीं जानते ...
  3. मैं अलग-अलग की क्षमता का प्रबंधन कैसे कर सकता हूं कतारों?
  4. उपर्युक्त दो समाधानों के प्रदर्शन के बारे में क्या? कौन सा स्मृति का उपयोग करता है?
+0

क्या मेरी प्रतिक्रिया आपकी समस्या के लिए कोई मदद है? – JeremyK

उत्तर

1

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

आप अधिक मूल्यों की अनुमति देने के लिए लंबे समय तक उपयोग कर सकते हैं। आप अंततः अंत में एक अंत तक पहुंच जाएंगे, इसलिए आपको अद्वितीय मानों के लिए एक नया पैटर्न या अधिकतम पहुंचने पर आइटम को 'रिकॉन्टा' करना होगा (प्रत्येक के माध्यम से लूप और अद्वितीय गणना मान को रीसेट करें)।

शायद इसके बजाय प्रत्येक आइटम के लिए GUID का उपयोग करें?

Guid.NewGuid()

संपादित करें:

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

1 > 0, return greater (1), continue 
1 > 0, return greater (1), continue 
1 == 1, return greater (1), continue 
1 < 2, return less than (-1), insert 

संपादित करें 2:

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

मैंने इस कोड का परीक्षण नहीं किया है, बस एक विचार है कि आप क्या कर सकते हैं।

static string leadingStr = ""; 
static char currentChar = 'a'; 
static Int32 currentId = Int32.MinValue; 

static string getNextId() 
{ 
    if (currentId >= Int32.MaxValue) 
    { 
     currentId = Int32.MinValue; 
     if (currentChar >= 'z') 
     { 
      currentChar = 'a'; 
      leadingStr = leadingStr.Insert(0, "X"); 
     } 
     else 
      currentChar++; 
    } 
    else 
     currentId++; 

    return String.Format("{0}{1}-{2}", leadingStr, currentChar, currentId); 
} 

संपादित करें 3: मान रीसेट करें

static Int64 currentValue = Int64.MinValue; 
static void AddItem(object item) 
{ 
    if (currentValue == Int64.MaxValue) 
     RecountItems(); 

    item.counter = currentValue++; 
    SortedList.Add(item); 
} 

static void RecountItems() 
{ 
    currentValue = 0; 
    foreach (var item in SortedList) 
    { 
     item.counter = currentValue++; 
    } 
} 

संपादित 4: अपने दूसरे प्रश्न के लिए:

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

static Object RemoveNextFIFO() 
{ 
    if (fifoList.Count > 0) 
    { 
     var removedItem = fifoList[0]; 
     fifoList.RemoveAt(0); 
     RemoveItemFromPriority(removedItem); 
     return removedItem; 
    } 
} 

static void RemoveItemFromPriority(Object itemToRemove) 
{ 
    foreach (var counter in priorityQueue) 
    { 
     if (counter == itemToRemove.counter) 
     { 
      priorityQueue.remove(item); 
      break; 
     } 
    } 
} 

static Object RemoveFromFIFO(int itemCounter) 
{ 
    foreach (var item in fifoList) 
    { 
     if (item.counter == itemCounter) 
     { 
      fifoList.Remove(item); 
      return item; 
     } 
    } 
} 

static Object RemoveNextPriority() 
{ 
    if (priorityQueue.Count > 0) 
    { 
     var counter = priorityQueue.Pop(); 
     return RemoveFromFIFO(counter); 
    } 
} 
+0

ठीक है, 'SortedList' स्वचालित रूप से एक' IComparer' का उपयोग कर आइटम सॉर्ट करता: मैं पहले से ही इस _comparer_ बनाया है और वह प्राथमिकता और काउंटर (एक ही प्राथमिकता के साथ आइटम उनके काउंटर की तुलना हल कर रहे हैं) द्वारा छँटाई काम करता है। समस्या यह है कि किसी बिंदु पर काउंटर अपने अधिकतम मूल्य तक पहुंच जाता है और 0 से फिर से शुरू होता है: काउंटर को रीसेट करने से पहले जोड़े गए किसी भी आइटम का अधिक काउंटर होगा और इसलिए वे ऐसा दिखाई देंगे जैसे कि अंतिम लोगों के बाद उन्हें डाला गया था। 'Guid' समस्या को हल नहीं करता है, क्योंकि यह यादृच्छिक है, इसलिए यह सम्मिलन के क्रम को विकृत कर सकता है। – enzom83

+0

क्या आपके डेटा में अतिरिक्त पैरामीटर संलग्न करना संभव होगा? यही है, अगर आपके पास 0 से 255 (केवल एक उदाहरण) से कोई आईडी थी, तो उसके बाद 0 से 255 तक एक आईडी सेकेंड हो सकता है, जहां आप पहले आईडी को चेक करते हैं तो idSecond? तो आपके पास 0,0 से 0,1 तक ... 255,255 तक सबकुछ होगा जो आपकी अनुमत संख्याओं को स्क्वायर करेगा? दो लम्बाई का उपयोग निश्चित रूप से आपकी आवश्यकताओं से अधिक होगा, है ना? - एक प्रशिक्षु प्रोग्रामर से। – BlackVegetable

+1

@BlackVegetable: _ क्या आपके डेटा में एक अतिरिक्त पैरामीटर संलग्न करना संभव हो सकता है? _ यदि कोई विकल्प नहीं है, तो मुझे लगता है कि एकमात्र अधिकार एक और पैरामीटर जोड़ना है, शायद वर्तमान दिनांक और समय वाला लंबा। – enzom83

1

आप "धोखा" कर सकता है और BigInteger उपयोग करें ताकि आप कभी नहीं "संख्या से बाहर चलाने"। यह निश्चित रूप से समय के साथ प्रदर्शन की क्रमिक गिरावट की ओर जाता है, लेकिन शायद इससे कोई फर्क नहीं पड़ता।

एक साथ heap-आधारित प्राथमिक कतार के साथ संयोजित करें और आप सेट हैं!


"फीफो से प्राथमिकता छंटाई और उपाध्यक्ष प्रतिकूल करने के लिए स्विच" की कोशिश मत करो - बस में तत्वों डाल दोनों डेटा कार्य (Queue और प्राथमिकता कतार) के लिए उपयुक्त संरचनाओं।

+0

मुझे बस "फीफो से प्राथमिकता सॉर्टिंग और इसके विपरीत" स्विच करने की आवश्यकता है। इस तरह, जब कतार एक निश्चित सीमा से भर जाती है, तो यह प्राथमिकता कतार में बदल जाती है। फिर, जब एक निश्चित दहलीज के नीचे भरने का स्तर कम हो जाता है, तो यह फीफो में जाता है। – enzom83

+0

@ enzom83 क्यों? आप क्या खत्म करने की कोशिश कर रहे हैं? –

+0

मुझे कनेक्शन में आउटगोइंग संदेशों के प्रवाह को नियंत्रित करने की आवश्यकता है, इसलिए मैं प्रत्येक कनेक्शन के लिए कतार का उपयोग करता हूं: यदि कतार में बहुत सारे संदेश हैं, तो शायद कनेक्शन धीमा है तो मैं आउटगोइंग संदेशों को प्राथमिकता लागू कर सकता हूं। – enzom83

1

Queue और Priority Queue दोनों का उपयोग करते हुए मैं क्या कर सकता है।
लेकिन यदि आपको ...

किसी तत्व के लिए एक कुंजी उपयोग 2 कुंजी के बजाय।
पहली कुंजी priority प्राथमिकता होगी।
दूसरी कुंजी time एक काउंटर होगा जो टाइमस्टैम्प की तरह होगा।

नियमित व्यवहार के लिए priority कुंजी का उपयोग करें।

जब ढेर भरा हुआ है, इसे time कुंजी द्वारा।
फिर n आवश्यक तत्वों को हटा दें।
अब HEAPIFY इसे फिर से priority कुंजी के साथ नियमित रूप से व्यवहार करने के लिए वापस जाने के लिए।

+0

जब ढेर भरा हुआ हो, तो मुझे _priority_ कुंजी (समय के अनुसार नहीं) द्वारा _re-heapify_ करना चाहिए ... – enzom83

+0

यह एक मजेदार विचार है, कतार + प्राथमिकता कतार जाने का रास्ता है। –

+0

मुझे लगता है कि मैं एक ढेर का उपयोग करूंगा: यह पर्याप्त है कि प्रत्येक तत्व प्राथमिकता सहित, चूंकि डुप्लिकेट ढेर के लिए कोई समस्या नहीं है (जिन वस्तुओं के समान मूल्य है, आगमन के क्रम में रखा गया है, और जोड़ने की आवश्यकता नहीं है खेत)। जैसे ही कुछ तत्व ('एन' तत्व) कतार से हटा दिए जाते हैं, मैं एक दूसरे के बराबर नई प्राथमिकताओं के साथ फिर से साबित करता हूं। – enzom83

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