Priority Queue

Queue မွာ ေနာက္ထပ္ တစ္မ်ဳိး ရွိတာကေတာ့ Priority Queue ပါ။ အရင္လာ အရင္ထြက္ ဆိုေပမယ့္ အေရးႀကီးတာကို ဦးစားေပးၿပီး ေနာက္မွလာေပမယ့္ အရင္ ထြက္ဖို႔ လိုပါတယ္။ ထည့္လိုက္သည့္ data ရဲ႕ Priority ေပၚမွာ မူတည္ၿပီးေတာ့ ျပန္ထုတ္ဖို႔ လိုပါတယ္။

pyqueue.py နဲ႔ အတူတူ pqueue.py ကို ဖန္တီးပါတယ္။

from pyqueue import Queue class PQueue: def __init__(self): self.items = {} def isEmpty(self): return len(self.items) == 0 def enqueue(self, item,priority=0): if priority not in self.items: self.items[priority] = Queue() queue = self.items[priority] queue.enqueue(item) def dequeue(self): keys = list(self.items.keys()) if len(keys) > 0 : cursor = keys[-1] myqueue = self.items[cursor] val = myqueue.dequeue() if myqueue.size() == 0 : del self.items[cursor] return val return "" def size(self): size = 0 for key in self.items.keys(): size = size + self.items[key].size() return size

Priority Queue ဟာ queue ေတြကို Priority အလိုက္ စီၿပီးေတာ့ ျပန္ ထုတ္ေပးတာပါ။ Code ကို မရွင္းျပခင္မွာ အရင္ဆံုး စမ္းၾကည့္ ရေအာင္။

from pqueue import PQueue p = PQueue() p.enqueue("HELLO",1) p.enqueue("H",2) p.enqueue("E",5) p.enqueue("L",3) p.enqueue("O",3) p.enqueue("Sample",9) # 7 print(p.size()) #Sample print(p.dequeue()) #E print(p.dequeue()) #4 print(p.size()) #L print(p.dequeue()) #O print(p.dequeue()) #H print(p.dequeue()) #1 print(p.size())

enqueue လုပ္တဲ့ အခါမွာ value နဲ႔ priority ပါပါတယ္။ သို႔ေပမယ့္ ျပန္ထုတ္သည့္ အခါမွာ Priority အျမင့္ဆံုး က အရင္ ထြက္လာပါလိမ့္မယ္။

p = PQueue()

p.enqueue("HELLO",1)
p.enqueue("H",2)
p.enqueue("E",5)
p.enqueue("L",3)
p.enqueue("O",3)
p.enqueue("Sample",9)

အဲဒီမွာ priority အျမင့္ဆံုးက "Sample" ပါ။ ဒါေၾကာင့္ ေနာက္ဆံုးမွ ထည့္ေပမယ့္ ပထမဆံုး ထြက္လာတာကို ေတြ႕ပါလိမ့္မယ္။

အခု ကၽြန္ေတာ္တို႔ PQueue() ကို ေလ့လာၾကည့္ရေအာင္။

ကၽြန္ေတာ္တို႔ဟာ Queue ေတြကို priority အလိုက္ စီရမွာ ျဖစ္တဲ့ အတြက္ array အစား dictionary ကို အသံုးျပဳထားပါတယ္။ ေနာက္ အခန္းမွာ Dictionary အေၾကာင္းကို ရွင္းျပေပးပါမယ္။ enqueue လုပ္တဲ့ အခါမွာ item dictionary ရဲ႕ Priority အခန္း မွာ Queue Object ရွိမရွိ စစ္ပါတယ္။

if priority not in self.items:
    self.items[priority] = Queue()

ဆိုတာက self.items ထဲမွာ key name က priority ရွိ မရွိၾကည့္တာပါ။ မရွိဘူးဆိုရင္ Queue Object အသစ္ တစ္ခု ေဆာက္ၿပီး ထည့္လိုက္ပါတယ္။

queue = self.items[priority]
queue.enqueue(item)

item ထဲကေန ၿပီးေတာ့ priority key ေပၚမွာ မူတည္ၿပီးေတာ့ Queue object ကို ထုတ္လိုက္ပါတယ္။ ၿပီးေတာ့ Queue ထဲမွာ enqueue လုပ္ေပးပါတယ္။

p.enqueue("HELLO",1)
p.enqueue("H",2)
p.enqueue("E",5)
p.enqueue("L",3)
p.enqueue("O",3)
p.enqueue("Sample",9)

အဲဒီလို ဆိုရင္ data ေတြ အေနနဲ႔

{
    1 : ["HELLO"],
    2 : ["H"],
    3 : ["L","O"],
    5 : ["E"],
    9 : ["Sample"]
}

ဆိုၿပီး ရွိေနပါမယ္။

dequeue အပိုင္းကေတာ့ နည္းနည္း ရႈပ္ေထြးပါတယ္။

keys = list(self.items.keys())

keys ထဲမွာ [1,2,3,5,9] ဆိုၿပီး ေရာက္လာပါမယ္။

if len(keys) > 0 :

keys မွာ အခန္း ရွိမရွိ စစ္ပါတယ္။

cursor = keys[-1]

-1 ဆိုတာကေတာ့ ေနာက္ဆံုး အခန္းကို ဆြဲထုတ္လိုက္ပါတယ္။

myqueue = self.items[cursor]
val = myqueue.dequeue()

ၿပီးေတာ့ queue object ကို ဆြဲထုတ္ပါတယ္။ ၿပီးေတာ့ dequeue() လုပ္ၿပီးေတာ့ data ကို ဆြဲထုတ္လိုက္ပါတယ္။

if myqueue.size() == 0 :
    del self.items[cursor]

queue ထဲမွာ data မရွိေတာ့ရင္ အခန္းကို ဖ်က္ခ်လိုက္ပါတယ္။

size = 0
for key in self.items.keys():
    size = size + self.items[key].size()

size တြက္ ကေတာ့ ႐ိုး႐ိုးေလးပါပဲ။ item ထဲမွာ ရွိတဲ့ queue ေတြ အားလံုးရဲ႕ size ကို ေပါင္းၿပီးေတာ့ return ျပန္ေပးလိုက္ ရံုပါပဲ။

results matching ""

    No results matching ""