מדריך לתורים בפייתון

הועלה מחדש על ידי אפלטון

עוקב: 0

מבוא

מאחסון מספרים שלמים פשוטים ועד לניהול זרימות עבודה מורכבות, מבני נתונים מניחים את הבסיס ליישומים חזקים. ביניהם, ה תור לעתים קרובות מתגלה כמסקרן ונמצא בכל מקום. תחשוב על זה - א קו בבנק, המתנה לתורך ליד דלפק מזון מהיר, או משימות חציצה במערכת מחשב - כל התרחישים האלה מהדהדים עם המכניקה של תור.

האדם הראשון בתור מקבל שירות ראשון, ומגיעים חדשים מצטרפים בסוף. זוהי דוגמה מהחיים האמיתיים של תור בפעולה!

עבור מפתחים, במיוחד ב-Python, תורים הם לא רק מבנים תיאורטיים מתוך ספר לימוד במדעי המחשב. הם מהווים את הארכיטקטורה הבסיסית ביישומים רבים. מניהול משימות במדפסת ועד הבטחת זרימת נתונים בצורה חלקה בשידורים חיים, לתורים יש תפקיד הכרחי.

במדריך זה, נעמיק במושג התורים, נחקור את המאפיינים שלהם, יישומים בעולם האמיתי, והכי חשוב, כיצד ליישם אותם ולהשתמש בהם ביעילות ב-Python.

מהו מבנה נתוני תור?

בניווט בנוף של מבני נתונים, אנו נתקלים לעתים קרובות במכולות שיש להם כללים ברורים להזנת נתונים ואחזורם. בין אלה, ה תור בולט באלגנטיות והישירות שלו.

עקרון ה-FIFO

בבסיסו, תור הוא מבנה נתונים ליניארי שדבק ב- ראשון נכנס ראשון החוצה (FIFO) עִקָרוֹן. המשמעות היא שהאלמנט הראשון שנוסף לתור יהיה הראשון שיוסר. כדי להשוות את זה לתרחיש שאפשר להתייחס אליו: שקול שורה של לקוחות בדלפק כרטיסים. האדם שמגיע ראשון מקבל את הכרטיס ראשון, וכל הגעות הבאות עומדות בתור בסוף, ומחכות לתורן.

הערה: לתור יש שני קצוות - מאחור ומלפנים. החזית מציינת מהיכן יוסרו אלמנטים, והחלק האחורי מציין היכן יתווספו אלמנטים חדשים.

פעולות תור בסיסיות

תור - המעשה של מוסיף אלמנט עד הסוף (אחורי) של התור.
דקו - המעשה של הסרת אלמנט מה חזית של התור.
הצצה או חזית - במצבים רבים, זה מועיל פשוט לצפות באלמנט הקדמי מבלי להסיר אותו. הפעולה הזו מאפשרת לנו לעשות בדיוק את זה.
IsEmpty – פעולה שעוזרת לקבוע אם התור מכיל אלמנטים כלשהם. זה יכול להיות חיוני בתרחישים שבהם פעולות מותנות בכך שהתור מכיל נתונים.

הערה: בעוד שלחלק מהתורים יש גודל מוגבל (תורים מוגבלים), אחרים יכולים לגדול כל עוד זיכרון המערכת מאפשר זאת (תורים לא מוגבלים).

הפשטות של התורים וכללי הפעולה הברורים שלהם הופכים אותם לאידיאליים עבור מגוון יישומים בפיתוח תוכנה, במיוחד בתרחישים הדורשים עיבוד מסודר ושיטתי.

עם זאת, הבנת התיאוריה היא רק הצעד הראשון. ככל שנתקדם, נעמיק בהיבטים המעשיים, ונמחיש כיצד ליישם תורים ב-Python.

כיצד ליישם תורים ב-Python - רשימות מול Deque vs. Queue Module

Python, עם ספריית סטנדרטים עשירה ותחביר ידידותי למשתמש, מספקת מספר מנגנונים ליישום ועבודה עם תורים. בעוד שכולם משרתים את המטרה הבסיסית של ניהול תורים, הם מגיעים עם הניואנסים, היתרונות והמלכודות הפוטנציאליות שלהם. בואו ננתח כל גישה, ונמחיש את המכניקה שלה ואת מקרי השימוש הטובים ביותר.

הערה: בדוק תמיד את מצב התור שלך לפני ביצוע פעולות. לדוגמה, לפני יציאה מהתור, ודא אם התור ריק כדי למנוע שגיאות. כמו כן, עבור תורים מוגבלים, ודא שיש מקום לפני עמידה בתור.

שימוש ברשימות Python ליישום תורים

השימוש ברשימות המובנות של Python ליישום תורים הוא אינטואיטיבי ופשוט. אין צורך בספריות חיצוניות או במבני נתונים מורכבים. עם זאת, ייתכן שגישה זו לא תהיה יעילה עבור מערכי נתונים גדולים. הסרת רכיב מתחילת רשימה (pop(0)) לוקח זמן ליניארי, מה שעלול לגרום לבעיות ביצועים.

הערה: עבור יישומים הדורשים ביצועים גבוהים או כאלו העוסקים בנפח משמעותי של נתונים, עבור אל collections.deque למורכבות זמן מתמדת עבור עמידה בתור ויציאה בתור.

נתחיל ביצירת רשימה שתייצג את התור שלנו:

queue = []

התהליך של הוספת אלמנטים לסוף התור (תור) אינו אלא הוספתם לרשימה:


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

כמו כן, הסרת האלמנט מחזית התור (יציאה מהתור) שווה ערך להסרה בלבד של האלמנט הראשון ברשימה:


queue.pop(0)
print(queue)

שימוש collection.deque ליישם תורים

גישה זו היא יעילה ביותר כמו deque מיושם באמצעות רשימה מקושרת כפולה. הוא תומך בהוספה מהירה של 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)

שימוש בפייתון תור מודול ליישום תורים

השמיים queue מודול בספרייה הסטנדרטית של Python מספק גישה מיוחדת יותר לניהול תורים, המספקת מקרי שימוש שונים:

SimpleQueue – תור FIFO בסיסי
LifoQueue - תור LIFO, בעצם מחסנית
PriorityQueue – אלמנטים מוציאים בתור על סמך העדיפות שהוקצתה להם

הערה: בחר ב 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 (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. זה מבטיח שאלמנטים מעובדים על סמך סדרי העדיפויות שנקבעו.

תסתכל כיצד אנו קובעים סדרי עדיפויות עבור האלמנטים שאנו מוסיפים לתור. זה דורש שנעביר tuple כטיעון של put() שיטה. ה-tuple צריך להכיל את העדיפות כאלמנט הראשון שלו ואת הערך בפועל כאלמנט השני:

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)

סיכום

תורים, בסיסיים אך חזקים, מוצאים את המהות שלהם במגוון יישומים ובעיות חישוביות בעולם האמיתי. מתזמון משימות במערכות הפעלה ועד לניהול זרימת נתונים ב-printspoolers או בקשות שרת אינטרנט, ההשלכות של תורים הן מרחיקות לכת.

Python מביאה לשולחן פלטה עשירה של כלים וספריות לעבודה עם תורים. מהתורים הפשוטים המבוססים על רשימות לתסריטים מהירים ועד לתורים היעילים ביותר deque עבור יישומים קריטיים לביצועים, השפה באמת עונה על קשת של צרכים.