6. תורים (Queues)

מבנה נתונים ואלגוריתמים

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

ביצועים

ניתוח שתי השיטות ליצירת תורים מראה כי בשתיהן הזמן הדרוש להוספה או מחיקה של פריט הינו קבוע ואינו תלוי במספר הפריטים שבתור. לכן, נסווג הן את ההוספה והן את המחיקה כפעולות של O(1). עבור כל שילוב של מחשב, מערכת הפעלה ושפה, הוספה עשויה לארוך C₁ שניות ומחיקה C₂ שניות, אך אנו איננו מעונינים בערכו של הקבוע, אשר משתנה ממחשב למחשב, משפה לשפה וכד'. העיקרון בהקשר זה הוא כי זמן הריצה איננו תלוי ב-n ולכן יוצר אלגוריתם של O(1).

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

המחשב ועוד, עשויים לגרום לשיפור. בכל אופן, שיטות של O(1) הינן מהירות, ולא סביר כי מאמץ לשיפורן יפיק רווח ניכר.

6.1 תורי קדימויות (Priority Queues)

לרוב קיימת קדימות הקשורה לפריטים המתווספים לתור: קדימות זו קובעת את הסדר שבה יצאו הפריטים מהתור - הפריט בעל הקדימות הגבוהה ביותר יוסר ראשון.

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

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

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

בנוסף

הרוב הגדול של מערכות מחשב נכנסים לקטגוריה של מערכות מידע, אשר תפקידם הוא פשוט לאחסן ולעבד מידע לתועלת המשתמשים, שמחליטים החלטות על סמך מידע זה. ברור שבמערכות שכאלה לרוב אין זה משנה אם פרק הזמן שנדרש לשליפת המידע הוא שניה אחת או מאה שניות - ההשלכה עשויה להיות האם אתה יוצא להפסקת קפה עכשיו או אחר כך. אולם כפי שנראה בהמשך, השימוש באלגוריתמים הידועים הטובים ביותר הוא לרוב קל ופשוט: הם נמצאים בספריות ובספרים. אין צורך אפילו לבדוק ולברר את הקוד שלהם ואת אופן פעולתם! במקרה כזה רק המוניטין שלך עשוי להינזק אם מישהו (שלמד את אותו טקסט של האלגוריתם) יגיע ויאמר: "מדוע לעזאזל השתמשת בשיטה של O(n²) כשיש שיטה ידועה אחרת של O(n) בלבד". כמובן שיצרני חומרה ישמחו מאוד אם תשתמש באלגוריתם לא יעיל - זה מגביר את הדרישה לחומרה חדשה מהירה יותר - דבר המגדיל את רווחיהם.

יש מבנה אשר מספק ביצועים מובטחים של O(logn) הן עבור הוספה והן עבור מחיקה. מבנה זה נקרא ערמה.

מושגים

תור FIFO

תור שבו הפריט הראשון שנכנס הוא תמיד הראשון שיוצא.

תור LIFO

תור שבו הפריט שנכנס אחרון הוא תמיד הראשון שיוצא.

תור קדימויות

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

מערכות תומכות חיים

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

מערכות זמן אמת

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

המשך ל: ערמות חזור ל: תוכן עניינים