راهنمای صف ها در پایتون

بازنشر افلاطون

دنبال: 0

معرفی

از ذخیره اعداد صحیح ساده گرفته تا مدیریت گردش‌های کاری پیچیده، ساختارهای داده زمینه را برای برنامه‌های کاربردی قوی فراهم می‌کنند. در میان آنها، صف اغلب به عنوان جذاب و همه جا ظاهر می شود. در مورد آن فکر کنید - الف خط در بانک، منتظر نوبت شما در یک پیشخوان فست فود، یا بافر کردن وظایف در یک سیستم کامپیوتری - همه این سناریوها با مکانیک یک صف طنین انداز می شوند.

اولین نفر در صف ابتدا خدمات دریافت می کند و افراد جدید در پایان به آن ها می پیوندند. این یک نمونه واقعی از یک صف در عمل است!

برای توسعه دهندگان، به خصوص در پایتون، صف ها فقط ساختارهای نظری از یک کتاب درسی علوم کامپیوتر نیستند. آنها معماری اساسی را در بسیاری از کاربردها تشکیل می دهند. از مدیریت وظایف در چاپگر گرفته تا اطمینان از پخش یکپارچه داده ها در پخش زنده، صف ها نقش مهمی دارند.

در این راهنما، ما عمیقاً در مفهوم صف، بررسی ویژگی‌های آنها، برنامه‌های کاربردی دنیای واقعی، و مهم‌تر از همه، نحوه پیاده‌سازی و استفاده مؤثر از آنها در پایتون خواهیم بود.

ساختار داده صف چیست؟

با گشت و گذار در چشم انداز ساختارهای داده، ما اغلب با کانتینرهایی مواجه می شویم که قوانین مجزایی برای ورود و بازیابی داده ها دارند. در این میان، صف به دلیل ظرافت و صراحت خود متمایز است.

اصل FIFO

در هسته خود، صف یک ساختار داده خطی است که به آن پایبند است اولین-در-اولین-بیرون (FIFO) اصل این بدان معنی است که اولین عنصر اضافه شده به صف اولین عنصری است که حذف می شود. برای تشبیه آن به یک سناریوی مرتبط: یک صف از مشتریان را در پیشخوان بلیط در نظر بگیرید. فردی که اولین بار وارد می شود، ابتدا بلیط خود را دریافت می کند و هر ورودی بعدی در پایان صف می کشد و منتظر نوبت خود است.

توجه داشته باشید: یک صف دو سر دارد - عقب و جلو. قسمت جلو نشان می دهد که عناصر از کجا حذف می شوند و قسمت عقب نشان می دهد که عناصر جدید در کجا اضافه می شوند.

عملیات صف اولیه

نوبت دهی - عمل از اضافه کردن یک عنصر تا انتها (عقب) از صف.
کاهش - عمل از از بین بردن یک عنصر از جلو از صف
زیرچشمی یا جلو - در بسیاری از موقعیت ها، صرفاً مشاهده عنصر جلو بدون برداشتن آن سودمند است. این عملیات به ما این امکان را می دهد که این کار را انجام دهیم.
خالی است - عملیاتی که به تعیین اینکه آیا صف دارای عناصری است یا خیر کمک می کند. این می تواند در سناریوهایی که اقدامات مشروط به داشتن داده در صف است، بسیار مهم باشد.

توجه داشته باشید: در حالی که برخی از صف ها اندازه محدودی دارند (صف های محدود)، برخی دیگر به طور بالقوه می توانند تا زمانی که حافظه سیستم اجازه می دهد رشد کنند (صف های نامحدود).

سادگی صف ها و قوانین کارکرد واضح آنها، آنها را برای انواع برنامه های کاربردی در توسعه نرم افزار، به ویژه در سناریوهایی که نیاز به پردازش منظم و سیستماتیک دارند، ایده آل می کند.

با این حال، درک نظریه فقط اولین قدم است. همانطور که به جلو می رویم، به جنبه های عملی می پردازیم و نحوه پیاده سازی صف ها در پایتون را نشان می دهیم.

نحوه پیاده‌سازی صف‌ها در پایتون – لیست‌ها در مقابل Deque در مقابل ماژول صف

پایتون با کتابخانه استاندارد غنی و سینتکس کاربر پسند خود، مکانیسم های مختلفی را برای پیاده سازی و کار با صف ها ارائه می دهد. در حالی که همه در خدمت هدف اساسی مدیریت صف هستند، آنها با تفاوت های ظریف، مزایا و مشکلات احتمالی خود همراه هستند. بیایید هر رویکرد را تشریح کنیم، مکانیک و بهترین موارد استفاده آن را نشان دهیم.

توجه داشته باشید: همیشه قبل از انجام عملیات وضعیت صف خود را بررسی کنید. به عنوان مثال، قبل از حذف صف، بررسی کنید که آیا صف خالی است تا از خطا جلوگیری شود. به همین ترتیب، برای صف های محدود، قبل از قرار گرفتن در صف، از وجود فضای خالی اطمینان حاصل کنید.

استفاده از لیست های پایتون برای پیاده سازی صف ها

استفاده از لیست های داخلی پایتون برای پیاده سازی صف ها بصری و ساده است. نیازی به کتابخانه های خارجی یا ساختارهای داده پیچیده نیست. با این حال، این رویکرد ممکن است برای مجموعه داده های بزرگ کارآمد نباشد. حذف یک عنصر از ابتدای لیست (pop(0)) زمان خطی می گیرد که می تواند باعث مشکلات عملکرد شود.

توجه داشته باشید: برای برنامه‌هایی که نیاز به عملکرد بالا دارند یا آن‌هایی که با حجم قابل‌توجهی از داده‌ها سروکار دارند، به آن بروید collections.deque برای پیچیدگی زمانی ثابت برای هر دو صف و در صف.

بیایید با ایجاد یک لیست برای نشان دادن صف خود شروع کنیم:

queue = []

فرآیند افزودن عناصر به انتهای صف (صف بندی) چیزی جز الحاق آنها به لیست نیست:


queue.append('A')
queue.append('B')
queue.append('C')
print(queue)

همچنین، حذف عنصر از جلوی صف (dequeuing) معادل حذف تنها عنصر اول لیست است:


queue.pop(0)
print(queue)

با استفاده از collections.deque برای پیاده سازی صف ها

این رویکرد بسیار کارآمد است به عنوان deque با استفاده از a اجرا می شود لیست دوگانه پیوند خورده. از ضمیمه های سریع O(1) پشتیبانی می کند و از هر دو انتها باز می شود. نقطه ضعف این رویکرد این است که اینطور است کمی برای مبتدیان کمتر بصری است.

اول از همه، ما وارد می کنیم deque شی از collections ماژول و صف ما را مقداردهی اولیه کنید:

from collections import deque queue = deque()

در حال حاضر، ما می توانیم استفاده کنید append() روش صف بندی عناصر و popleft() روش حذف عناصر از صف:

راهنمای عملی و عملی ما برای یادگیری Git را با بهترین روش ها، استانداردهای پذیرفته شده در صنعت و برگه تقلب شامل بررسی کنید. دستورات Google Git را متوقف کنید و در واقع یاد گرفتن آی تی!


queue.append('A')
queue.append('B')
queue.append('C')
print(queue) queue.popleft()
print(queue)

با استفاده از پایتون صف ماژول برای پیاده سازی صف

La queue ماژول در کتابخانه استاندارد پایتون رویکرد تخصصی تری را برای مدیریت صف ارائه می دهد و موارد استفاده مختلف را ارائه می دهد:

SimpleQueue - یک صف اولیه FIFO
LifoQueue - یک صف LIFO، در اصل یک پشته
اولویت - عناصر بر اساس اولویت اختصاص داده شده در صف قرار می گیرند

توجه داشته باشید: را انتخاب کنید queue ماژول، که طراحی شده است نخ ایمن. این تضمین می کند که عملیات همزمان در صف منجر به نتایج غیرقابل پیش بینی نمی شود.

این رویکرد عالی است زیرا به صراحت برای عملیات صف طراحی شده است. اما، اگر بخواهیم کاملاً صادق باشیم، ممکن است برای سناریوهای ساده بیش از حد باشد.

حالا بیایید شروع به استفاده از queue ماژول با وارد کردن آن به پروژه ما:

import queue

از آنجایی که ما یک صف ساده FIFO را پیاده سازی می کنیم، آن را با استفاده از آن مقداردهی اولیه می کنیم SimpleQueue() سازنده:

q = queue.SimpleQueue()

عملیات Enqueue و Dequeue با استفاده از آن اجرا می شوند put() و get() روش های از queue مدول:


q.put('A')
q.put('B')
q.put('C')
print(q.queue) q.get()
print(q.queue)

توجه داشته باشید: عملیات صف می تواند استثناهایی را ایجاد کند که در صورت عدم کنترل، می تواند جریان برنامه شما را مختل کند. برای جلوگیری از آن، عملیات صف خود را در آن بپیچید 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') dq.append('B') dq.pop() dq.popleft()

PriorityQueu در عمل

استفاده از یک صف ساده FIFO زمانی که ترتیب پردازش وابسته به اولویت است می تواند منجر به ناکارآمدی یا نتایج نامطلوب شود، بنابراین، اگر درخواست شما نیاز دارد که برخی از عناصر قبل از سایرین بر اساس برخی معیارها پردازش شوند، از یک PriorityQueue. این تضمین می کند که عناصر بر اساس اولویت های تعیین شده آنها پردازش می شوند.

به نحوه تعیین اولویت برای عناصری که به صف اضافه می کنیم نگاهی بیندازید. این مستلزم آن است که یک تاپل را به عنوان آرگومان از آن پاس کنیم put() روش. تاپل باید اولویت را به عنوان اولین عنصر و مقدار واقعی را به عنوان عنصر دوم داشته باشد:

import queue pq = queue.PriorityQueue()
pq.put((2, "Task B"))
pq.put((1, "Task A")) 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) circular_queue.append(4)
print(circular_queue)

نتیجه

صف ها، اساسی و در عین حال قدرتمند، جوهر خود را در انواع برنامه های کاربردی دنیای واقعی و مشکلات محاسباتی می یابند. از زمان‌بندی کار در سیستم‌های عامل گرفته تا مدیریت جریان داده در اسپولرهای چاپی یا درخواست‌های وب سرور، پیامدهای صف‌ها بسیار گسترده است.

پایتون یک پالت غنی از ابزارها و کتابخانه ها را برای کار با صف ها به جدول می آورد. از صف‌های ساده مبتنی بر فهرست برای اسکریپت‌های سریع گرفته تا موارد بسیار کارآمد deque برای برنامه های کاربردی حیاتی، زبان واقعاً طیفی از نیازها را برآورده می کند.