Посібник із черг у Python

Перевидано Платоном

читають: 0

Вступ

Від зберігання простих цілих чисел до керування складними робочими процесами, структури даних закладають основу для надійних програм. Серед них, чергу часто виявляється одночасно інтригуючим і всюдисущим. Подумайте про це – а чергу в банку, очікування своєї черги біля прилавка швидкого харчування чи буферизація завдань у комп’ютерній системі — усі ці сценарії перегукуються з механізмом черги.

Перша людина в черзі обслуговується першою, а нові прибувають у кінці. Це реальний приклад черги в дії!

Для розробників, особливо в Python, черги — це не просто теоретичні побудови з підручника з інформатики. Вони формують базову архітектуру багатьох програм. Черги відіграють незамінну роль, починаючи від керування завданнями на принтері й закінчуючи безперебійним потоком даних під час прямих трансляцій.

У цьому посібнику ми глибше заглибимося в концепцію черг, дослідимо їхні характеристики, реальні програми та, що найважливіше, як їх ефективно реалізувати та використовувати в Python.

Що таке структура даних черги?

Переміщаючись серед структур даних, ми часто стикаємося з контейнерами, які мають чіткі правила для введення та пошуку даних. Серед них, чергу виділяється своєю елегантністю і прямолінійністю.

Принцип FIFO

За своєю суттю черга — це лінійна структура даних, яка дотримується Перший прийшов першим вийшов (FIFO) принцип. Це означає, що перший елемент, доданий до черги, буде першим видалений. Щоб порівняти це зі схожим сценарієм: розглянемо чергу клієнтів біля квиткової каси. Людина, яка прибуває першою, отримує квиток першою, а всі наступні прибувають у чергу в кінці, чекаючи своєї черги.

Примітка: У черги два кінці – задній і передній. Передня частина вказує, звідки елементи будуть видалені, а задня частина вказує, де будуть додані нові елементи.

Основні операції з чергою

У чергу – Акт додати елемент до кінця (задній) черги.
Зняти чергу – Акт видалення елемент від перед черги.
Peek або Front – У багатьох ситуаціях корисно просто спостерігати за переднім елементом, не знімаючи його. Ця операція дозволяє нам це зробити.
Пусто – Операція, яка допомагає визначити, чи є в черзі елементи. Це може бути вирішальним у сценаріях, коли дії залежать від черги, що містить дані.

Примітка: У той час як деякі черги мають обмежений розмір (обмежені черги), інші потенційно можуть збільшуватися до тих пір, поки дозволяє пам’ять системи (необмежені черги).

Простота черг і їх чіткі правила роботи роблять їх ідеальними для різноманітних застосувань у розробці програмного забезпечення, особливо в сценаріях, які вимагають упорядкованої та систематичної обробки.

Однак розуміння теорії – лише перший крок. Просуваючись вперед, ми заглибимося в практичні аспекти, ілюструючи, як реалізувати черги в Python.

Як реалізувати черги в Python – Списки проти Deque проти модуля черги

Python зі своєю багатою стандартною бібліотекою та зручним синтаксисом надає кілька механізмів для впровадження та роботи з чергами. Хоча всі вони служать основній меті керування чергами, вони мають свої нюанси, переваги та потенційні підводні камені. Давайте розберемо кожен підхід, проілюструвавши його механіку та найкращі випадки використання.

Примітка: Завжди перевіряйте статус своєї черги перед виконанням операцій. Наприклад, перед видаленням з черги перевірте, чи черга порожня, щоб уникнути помилок. Подібним чином для обмежених черг переконайтеся, що є вільний простір, перш ніж ставити в чергу.

Використання списків Python для реалізації черг

Використання вбудованих списків Python для реалізації черг є інтуїтивно зрозумілим і простим. Немає потреби у зовнішніх бібліотеках або складних структурах даних. Однак цей підхід може бути неефективним для великих наборів даних. Видалення елемента з початку списку (pop(0)) займає лінійний час, що може спричинити проблеми з продуктивністю.

Примітка: Для програм, які потребують високої продуктивності або мають справу зі значним обсягом даних, перейдіть на collections.deque для постійної складності часу як для постановки в чергу, так і для вилучення з черги.

Почнемо зі створення списку для представлення нашої черги:

queue = []

Процес додавання елементів у кінець черги (постановка в чергу) є нічим іншим, як додаванням їх до списку:


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

Крім того, видалення елемента з початку черги (вилучення з черги) еквівалентно простому видаленню першого елемента списку:


queue.pop(0)
print(queue)

використання колекції.deque для впровадження черг

Цей підхід є високоефективним, оскільки deque реалізується за допомогою a подвійний список. Він підтримує швидке O(1) додавання та видалення з обох кінців. Недоліком цього підходу є те, що він трохи менш інтуїтивно зрозумілий для початківців.

Перш за все, ми будемо імпортувати deque об'єкт з collections модуль і ініціалізуємо нашу чергу:

from collections import deque queue = deque()

Тепер ми можемо використовувати append() метод постановки елементів у чергу та popleft() метод видалення елементів із черги:

Ознайомтеся з нашим практичним практичним посібником із вивчення Git з передовими методами, прийнятими в галузі стандартами та включеною шпаргалкою. Припиніть гуглити команди Git і фактично вчитися це!


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

Використання Python чергу Модуль для впровадження черг

Команда queue модуль у стандартній бібліотеці Python забезпечує більш спеціалізований підхід до керування чергами, обслуговуючи різні випадки використання:

SimpleQueue – Основна черга FIFO
LifoQueue – Черга LIFO, по суті стек
Пріоритетна черга – Елементи вилучаються з черги на основі їхнього призначеного пріоритету

Примітка: Виберіть queue модуль, який призначений для того, щоб бути різьбові. Це гарантує, що одночасні операції в черзі не призведуть до непередбачуваних результатів.

Цей підхід чудовий, оскільки він явно розроблений для операцій у черзі. Але, чесно кажучи, це може бути надмірним для простих сценаріїв.

Тепер почнемо використовувати queue модуль, імпортувавши його в наш проект:

import queue

Оскільки ми реалізуємо просту чергу FIFO, ми ініціалізуємо її за допомогою SimpleQueue() конструктор:

q = queue.SimpleQueue()

Операції постановки та вилучення з черги реалізовані за допомогою 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!")

Яку реалізацію вибрати?

Ваш вибір реалізації черги в Python має відповідати вимогам вашої програми. Якщо ви обробляєте великий обсяг даних або вам потрібна оптимізована продуктивність, collections.deque є переконливим вибором. Однак для багатопоточних програм або коли в гру вступають пріоритети, queue модуль пропонує надійні рішення. Для швидких сценаріїв або коли ви тільки починаєте, списків Python може бути достатньо, але завжди будьте обережні щодо потенційних пасток продуктивності.

Примітка: Повторне винайдення колеса шляхом індивідуальної реалізації операцій черги, коли Python уже надає потужні вбудовані рішення.
Перш ніж створювати спеціальні рішення, ознайомтеся з вбудованими пропозиціями Python, наприклад deque і queue модуль. Найчастіше вони задовольняють широкий спектр вимог, заощаджуючи час і зменшуючи можливі помилки.

Зануртеся глибше: розширені концепції черги в Python

Для тих, хто осягнув основну механіку черг і прагне заглибитися глибше, Python пропонує безліч передових концепцій і методів для вдосконалення й оптимізації операцій на основі черги. Давайте розкриємо деякі з цих складних аспектів, даючи вам арсенал інструментів для вирішення більш складних сценаріїв.

Двосторонні черги с деке

Поки ми вже досліджували deque будучи чергою FIFO, він також підтримує операції LIFO (останній прийшов-перший вийшов). Це дозволяє вам додавати або висувати елементи з обох кінців зі складністю 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)

Висновок

Черги, фундаментальні, але потужні, знаходять свою суть у різноманітних реальних програмах і обчислювальних проблемах. Від планування завдань в операційних системах до керування потоком даних у спулерах друку чи запитах веб-сервера, наслідки черг є далекосяжними.

Python пропонує багату палітру інструментів і бібліотек для роботи з чергами. Від простих спискових черг для швидких сценаріїв до високоефективних deque для критично важливих для продуктивності додатків мова справді задовольняє широкий спектр потреб.