از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
سرفصلهای مطلب
معرفی
از ذخیره اعداد صحیح ساده گرفته تا مدیریت گردشهای کاری پیچیده، ساختارهای داده زمینه را برای برنامههای کاربردی قوی فراهم میکنند. در میان آنها، صف اغلب به عنوان جذاب و همه جا ظاهر می شود. در مورد آن فکر کنید – الف خط در بانک، منتظر نوبت شما در یک پیشخوان فست فود یا بافر کردن وظایف در یک سیستم کامپیوتری – همه این سناریوها با مکانیک یک صف طنین انداز می شوند.
اولین نفر در صف ابتدا خدمات دریافت می کند و افراد جدید در پایان به آنها ملحق می شوند. این یک نمونه واقعی از یک صف در عمل است!
برای توسعه دهندگان، به خصوص در پایتون، صف ها فقط ساختارهای نظری از یک کتاب درسی علوم کامپیوتر نیستند. آنها معماری اساسی را در بسیاری از کاربردها تشکیل می دهند. از مدیریت وظایف در چاپگر گرفته تا اطمینان از پخش یکپارچه داده ها در پخش زنده، صف ها نقش مهمی دارند.
در این راهنما، ما عمیقاً در مفهوم صف، بررسی ویژگیهای آنها، برنامههای کاربردی دنیای واقعی و مهمتر از همه، نحوه پیادهسازی و استفاده مؤثر از آنها در پایتون خواهیم پرداخت.
ساختار داده صف چیست؟
با گشت و گذار در چشم انداز ساختارهای داده، ما اغلب با کانتینرهایی مواجه می شویم که قوانین مجزایی برای ورود و بازیابی داده ها دارند. در این میان، صف به دلیل ظرافت و صراحت خود متمایز است.
اصل FIFO
در هسته خود، صف یک ساختار داده خطی است که به آن پایبند است First-In-First-Out (FIFO) اصل این بدان معنی است که اولین عنصر اضافه شده به صف اولین عنصری است که حذف می شود. برای تشبیه آن به یک سناریوی مرتبط: یک صف از مشتریان را در پیشخوان بلیط در نظر بگیرید. فردی که اولین بار وارد می شود، ابتدا بلیط خود را دریافت می کند و هر ورودی بعدی در پایان صف می کشد و منتظر نوبت خود است.
توجه داشته باشید: یک صف دو سر دارد – عقب و جلو. قسمت جلو نشان می دهد که عناصر از کجا حذف می شوند و قسمت عقب نشان می دهد که عناصر جدید در کجا اضافه می شوند.
عملیات صف اولیه
-
نوبت دهی – عمل از اضافه کردن یک عنصر تا انتها (عقب) از صف.
-
Dequeue – عمل از حذف کردن یک عنصر از جلو از صف
-
زیرچشمی یا جلو – در بسیاری از مواقع، صرفاً مشاهده عنصر جلو بدون برداشتن آن سودمند است. این عملیات به ما این امکان را می دهد که این کار را انجام دهیم.
-
خالی است – عملیاتی که به تعیین اینکه آیا صف دارای عناصری است یا خیر کمک می کند. این می تواند در سناریوهایی که اقدامات مشروط به داشتن داده در صف است، بسیار مهم باشد.
توجه داشته باشید: در حالی که برخی از صف ها اندازه محدودی دارند (صف های محدود)، برخی دیگر به طور بالقوه می توانند تا زمانی که حافظه سیستم اجازه می دهد رشد کنند (صف های نامحدود).
سادگی صف ها و قوانین عملکرد واضح آنها، آنها را برای انواع برنامه های کاربردی در توسعه نرم افزار، به ویژه در سناریوهایی که نیاز به پردازش منظم و سیستماتیک دارند، ایده آل می کند.
با این حال، درک نظریه فقط اولین قدم است. همانطور که به جلو می رویم، به جنبه های عملی می پردازیم و نحوه پیاده سازی صف ها در پایتون را نشان می دهیم.
نحوه پیادهسازی صفها در پایتون – لیستها در مقابل Deque در مقابل ماژول صف
پایتون با کتابخانه استاندارد غنی و سینتکس کاربر پسند خود، مکانیسم های مختلفی را برای پیاده سازی و کار با صف ها ارائه می دهد. در حالی که همه در خدمت هدف اساسی مدیریت صف هستند، آنها با تفاوت های ظریف، مزایا و مشکلات احتمالی خود همراه هستند. بیایید هر رویکرد را تشریح کنیم، مکانیک و بهترین موارد استفاده آن را نشان دهیم.
توجه داشته باشید: همیشه قبل از انجام عملیات وضعیت صف خود را بررسی کنید. به عنوان مثال، قبل از حذف صف، بررسی کنید که آیا صف خالی است تا از خطا جلوگیری شود. به همین ترتیب، برای صف های محدود، قبل از قرار گرفتن در صف، از وجود فضای خالی اطمینان حاصل کنید.
استفاده از لیست های پایتون برای پیاده سازی صف ها
استفاده از لیست های داخلی پایتون برای پیاده سازی صف ها بصری و ساده است. نیازی به کتابخانه های خارجی یا ساختارهای داده پیچیده نیست. با این حال، این رویکرد ممکن است برای مجموعه داده های بزرگ کارآمد نباشد. حذف یک عنصر از ابتدای لیست (pop(0)) زمان خطی می گیرد که می تواند باعث مشکلات عملکرد شود.
توجه داشته باشید: برای برنامههایی که نیاز به عملکرد بالا دارند یا آنهایی که با حجم قابلتوجهی از دادهها سروکار دارند، به آن بروید collections.deque برای پیچیدگی زمانی ثابت برای هر دو صف و در صف.
بیایید با ایجاد یک لیست برای نشان دادن صف خود شروع کنیم:
queue = ()
فرآیند افزودن عناصر به انتهای صف (صف بندی) چیزی جز الحاق آنها به لیست نیست:
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) # Output: ('A', 'B', 'C')
همچنین، حذف عنصر از جلوی صف (dequeuing) معادل حذف تنها عنصر اول لیست است:
# Dequeue
queue.pop(0)
print(queue) # Output: ('B', 'C')
استفاده کردن collections.deque برای پیاده سازی صف ها
این رویکرد بسیار کارآمد است به عنوان deque با استفاده از a اجرا می شود لیست دوگانه پیوند خورده. از ضمیمه های سریع O(1) پشتیبانی می کند و از هر دو انتها باز می شود. نقطه ضعف این رویکرد این است که آن است اندکی برای مبتدیان کمتر بصری است.
اول از همه، ما وارد می کنیم deque شی از collections ماژول و صف ما را مقداردهی اولیه کنید:
from collections import deque
queue = deque()
در حال حاضر، ما می توانیم استفاده کنید append() روش صف بندی عناصر و popleft() روش حذف عناصر از صف:
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) # Output: deque(('A', 'B', 'C'))
# Dequeue
queue.popleft()
print(queue) # Output: deque(('B', 'C'))
با استفاده از پایتون صف ماژول برای پیاده سازی صف
این queue ماژول در کتابخانه استاندارد پایتون رویکرد تخصصی تری را برای مدیریت صف ارائه می دهد و موارد استفاده مختلف را ارائه می دهد:
- SimpleQueue – یک صف اولیه FIFO
- LifoQueue – یک صف LIFO، در اصل یک پشته
- صف اولویت – عناصر بر اساس اولویت تخصیص داده شده در صف قرار می گیرند
توجه داشته باشید: را انتخاب کنید queue ماژول، که طراحی شده است ایمن با نخ. این تضمین می کند که عملیات همزمان در صف منجر به نتایج غیرقابل پیش بینی نمی شود.
این رویکرد عالی است زیرا به صراحت برای عملیات صف طراحی شده است. اما، اگر بخواهیم کاملاً صادق باشیم، ممکن است برای سناریوهای ساده بیش از حد باشد.
حالا بیایید شروع به استفاده از queue ماژول با وارد کردن آن به پروژه ما:
import queue
از آنجایی که ما یک صف ساده FIFO را پیاده سازی می کنیم، آن را با استفاده از آن مقداردهی اولیه می کنیم SimpleQueue() سازنده:
q = queue.SimpleQueue()
عملیات Enqueue و Dequeue با استفاده از آن اجرا می شوند put() و get() روش های از queue مدول:
# Enqueue
q.put('A')
q.put('B')
q.put('C')
print(q.queue) # Output: ('A', 'B', 'C')
# Dequeue
q.get()
print(q.queue) # Output: ('B', 'C')
توجه داشته باشید: عملیات صف می تواند استثناهایی را ایجاد کند که در صورت عدم کنترل، می تواند جریان برنامه شما را مختل کند. برای جلوگیری از آن، عملیات صف خود را در آن بپیچید try-except بلوک ها
به عنوان مثال، رسیدگی به queue.Empty استثنا در هنگام کار با queue مدول:
import queue
q = queue.SimpleQueue()
try:
item = q.get_nowait()
except queue.Empty:
print("Queue is empty!")
کدام پیاده سازی را انتخاب کنیم؟
انتخاب شما برای اجرای صف در پایتون باید با الزامات برنامه شما هماهنگ باشد. اگر حجم زیادی از داده ها را مدیریت می کنید یا به عملکرد بهینه نیاز دارید، collections.deque یک انتخاب قانع کننده است با این حال، برای برنامه های چند رشته ای یا زمانی که اولویت ها مطرح می شوند، queue ماژول راه حل های قوی ارائه می دهد. برای اسکریپتهای سریع یا زمانی که تازه شروع میکنید، فهرستهای پایتون ممکن است کافی باشد، اما همیشه مراقب مشکلات احتمالی عملکرد باشید.
توجه داشته باشید: اختراع مجدد چرخ با اجرای سفارشی عملیات صف زمانی که پایتون از قبل راه حل های داخلی قدرتمندی ارائه می دهد.
قبل از ایجاد راهحلهای سفارشی، با پیشنهادات داخلی پایتون آشنا شوید deque و queue مدول. بیشتر اوقات، آنها طیف گسترده ای از نیازها را برآورده می کنند و باعث صرفه جویی در زمان و کاهش خطاهای احتمالی می شوند.
Dive Deeper: مفاهیم صف پیشرفته در پایتون
برای کسانی که مکانیک های اولیه صف ها را درک کرده اند و مشتاق هستند عمیق تر شوند، پایتون مجموعه ای از مفاهیم و تکنیک های پیشرفته را برای اصلاح و بهینه سازی عملیات مبتنی بر صف ارائه می دهد. بیایید برخی از این جنبه های پیچیده را کشف کنیم و زرادخانه ای از ابزارها را برای مقابله با سناریوهای پیچیده تر در اختیار شما قرار دهیم.
صف های دو طرفه با دکه
در حالی که قبلاً بررسی کرده بودیم deque به عنوان یک صف FIFO، از عملیات LIFO (Last-In-First-Out) نیز پشتیبانی می کند. این به شما امکان می دهد عناصر را از هر دو طرف با پیچیدگی O(1) اضافه یا پاپ کنید:
from collections import deque
dq = deque()
dq.appendleft('A') # add to the front
dq.append('B') # add to the rear
dq.pop() # remove from the rear
dq.popleft() # remove from the front
PriorityQueu در عمل
استفاده از یک صف ساده FIFO زمانی که ترتیب پردازش وابسته به اولویت است میتواند منجر به ناکارآمدی یا نتایج نامطلوب شود، بنابراین، اگر درخواست شما مستلزم این است که برخی از عناصر قبل از سایرین بر اساس برخی معیارها پردازش شوند، از یک PriorityQueue. این تضمین می کند که عناصر بر اساس اولویت های تعیین شده آنها پردازش می شوند.
به نحوه تعیین اولویت برای عناصری که به صف اضافه می کنیم نگاهی بیندازید. این مستلزم آن است که یک تاپل را به عنوان آرگومان از آن پاس کنیم put() روش. تاپل باید اولویت را به عنوان اولین عنصر و مقدار واقعی را به عنوان عنصر دوم داشته باشد:
import queue
pq = queue.PriorityQueue()
pq.put((2, "Task B"))
pq.put((1, "Task A")) # Lower numbers denote higher priority
pq.put((3, "Task C"))
while not pq.empty():
_, task = pq.get()
print(f"Processing: {task}")
این موارد زیر را به ما می دهد:
Processing: Task A
Processing: Task B
Processing: Task C
توجه داشته باشید که چگونه عناصر را به ترتیبی متفاوت از آنچه در صف ذخیره شده است اضافه کردیم. این به دلیل اولویت هایی است که ما در آن تعیین کرده ایم put() روش هنگام افزودن عناصر به صف اولویت.
اجرای صف دایره ای
یک صف دایره ای (یا بافر حلقه) یک ساختار داده پیشرفته است که در آن آخرین عنصر به اولین عنصر متصل می شود و جریان دایره ای را تضمین می کند. deque می تواند این رفتار را با استفاده از آن تقلید کند maxlen ویژگی:
from collections import deque
circular_queue = deque(maxlen=3)
circular_queue.append(1)
circular_queue.append(2)
circular_queue.append(3)
# Now the queue is full, adding another element will remove the oldest one
circular_queue.append(4)
print(circular_queue) # Output: deque((2, 3, 4), maxlen=3)
نتیجه
صف ها، اساسی و در عین حال قدرتمند، جوهر خود را در انواع برنامه های کاربردی دنیای واقعی و مشکلات محاسباتی می یابند. از زمانبندی وظایف در سیستمهای عامل گرفته تا مدیریت جریان داده در اسپولرهای چاپی یا درخواستهای وب سرور، پیامدهای صفها بسیار گسترده است.
پایتون یک پالت غنی از ابزارها و کتابخانه ها را برای کار با صف ها به جدول می آورد. از صفهای ساده مبتنی بر فهرست برای اسکریپتهای سریع گرفته تا موارد بسیار کارآمد deque برای برنامه های کاربردی حیاتی، زبان واقعاً طیفی از نیازها را برآورده می کند.
منتشر شده در 1402-12-26 03:18:45
