صف اولویت ها در زبان پایتون چیست ؟
صف اولویت ها در زبان پایتون چیست ؟
ADT صف اولویت رابط مشابهی به عنوان ADT صف دارد، اما از لحـاظ معنـایی متفـاوت اسـت. رابط باز هم به صورت زیر است: __init :__یک صف خالی جدید را مقداردهی میکند. insert :یک عضو جدید به صف اضافه میکند. remove :یک عضو از صف حذف میکند و برمیگرداند. عضـوي کـه برگردانـده مـیشـود، آن است که اولویت بالاتري دارد. isEmpty :بررسی میکند که آیا صف خالی است یا نه. تفاوت معنایی در اینجا است که عضو حذف شونده الزاماً اولین عضـو اضـافه شـده نیسـت. ایـن عضو، عنصري است که بالاترین اولویت را دارد. اینکه اولویتها چیسـتند و چگونـه بـا یکـدیگر مقایسـه میشوند بهوسیلۀ پیادهسازي صف اولویت مشخص نمیشود. این موضوع به عناصري که در صف وجـود دارند بستگی دارد. براي مثال اگر اعضاي درون صف، اسمها باشند، ما احتمالاً آنها را بر اساس ترتیب حـروف الفبـا انتخاب میکنیم. اگر امتیازهاي بازي بولینگ باشد، احتمالاً از بالاترین عدد به سمت پـایینتـرین عـدد حرکت میکنیم ولی اگر امتیازهاي بازي گلف باشند از پایینترین عدد به سمت بالاترین عدد میرویـم. در طول مدتی که ما میتوانیم عضوهاي داخل صف را با هم مقایسـه کنـیم، مـیتـوانیم عضـوي را کـه بالاترین اولویت را دارا است پیدا کرده و حذف کنیم. این پیادهسازي صف اولویت، یک لیست پایتون را به عنوان مشخصه دارد که شامل اقلام داخـل صف میباشد:
class PriorityQueue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def insert(self, item):
self.items.append(item)
متد مقداردهی اولیه، isEmpty و insert همگی ونیرهایی بر روي عملیات لیست هسـتند. تنها متد جالب remove است:
class PriorityQueue:
…
def remove(self):
maxi = 0
for i in range(1,len(self.items)):
if self.items[i] > self.items[maxi]:
maxi = i
item = self.items[maxi]
self.items[maxi:maxi+1] = []
return item
در آغاز هر تکرار، maxi اندیس بزرگترین عضوي را که تاکنون دیدهایم (بالاترین اولویت) نگـه میدارد. در هر بار تکرار حلقه برنامه iامین عضو را با عضو منتخب مقایسه مـیکنـد. اگـر عضـو جدیـد بزرگتر است، مقدار maxi به i تغییر خواهد یافت. وقتی دستور for کامل شد، maxi اندیس بزرگترین عضو است. ایـن عضـو از لیسـت حـذف شده و برگردانده میشود. بیایید پیادهسازي را آزمایش کنیم:
>> q = PriorityQueue()
>>> q.insert(11)
>>> q.insert(12)
>>> q.insert(14)
>>> q.insert(13)
>>> while not q.isEmpty(): print q.remove()
14
13
12
11
اگر صف شامل رشتهها و اعداد ساده باشد آنها به ترتیب الفبـایی یـا شمارشـی از زیـاد بـه کـم حذف میشوند. پایتون میتواند بزرگترین عدد صحیح یـا رشـته را پیـدا کنـد زیـرا آنهـا را بـر اسـاس عملگرهاي مقایسهاي پیشساخته میسنجند. اگر صف شامل یک نوعِ شیئی باشد، مجبور است یک متد __cmp __فراهم میکند. وقتی کـه remove از عملگر < براي مقایسۀ اقلام استفاده میکنـد، متـد __cmp __را بـر روي یکـی از اعضـا احضار میکند و عضو دیگر را به عنوان پارامتر به آن میفرستد. تا زمانیکه متد __cmp __به درسـتی کار کند، صف اولویت کار میکند.
برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید
ثبت نام
با ایمیل خود وارد شویدورود
