פורסם ב זה רק קוד, מתכוננות לראיונות

זה לא התור, זה הסיבוכיות

זמן קריאה: 8 דקות

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

הפונקציה pop(i) היא פונקציית ספרייה בפייתון לטיפול ברשימות, שמוציאה איבר מרשימה באינדקס נתון. הפונקציה ממומשת בסיבוכיות o(n) במקרה הממוצע, כאשר יוצאת הדופן היא הוצאת איבר מסוף הרשימה שהסיבוכיות שלה היא o(1). אחרי ההרצאה התפתח בטוויטר דיון סביב נושא הסיבוכיות של הפונקציה הזו, והאם היא מפתיעה או לא. במהלך הדיון נשאלה שאלה מאוד הגיונית – איך היינו מבצעות את אותה הפעולה בלי להשתמש ב-pop? אז חשבתי שיהיה מעניין לדון באלטרנטיבות.

לפני שאנחנו רצות קדימה בואו נתחיל מההתחלה, מהו המימוש של (i)pop בפייתון?

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

ה״בשר״ של האלגוריתם נראה בערך ככה

pop(self, index):
	item = self.list[index]
	if (index < self.list_size - 1):
		j = 0
		while index + j < list_size - 1:
			self.list[index + j] = self.list[index + j + 1]  
			j += 1
	self.list_size = list_size - 1
	return item

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

כולם לזוז מקום אחד שמאלה בבקשה

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

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

האם אפשר לשפר את המימוש

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

מה היא רוצה מאיתנו?

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

האם נוכל לעשות זאת בלי לשלם בסיבוכיות o(n) בכל פעולה? כן, אנחנו יכולות, אבל חשוב לזכור שלכל מימוש שכזה יהיו מחירים משלו. כמו כן, שימו לב שנתתי לנו פה הנחה משמעותית – בחרתי בעיה שהפתרון שלה דורש הוצאה של איברים מתחילת התור והוספה של איברים לסוף התור בלבד. המימוש של ()pop בפייתון מאפשר הוצאה והכנסה מכל מיקום במערך, שזו בעיה מסובכת יותר.

איך נממש תור בפייתון?

מימוש בעזרת אינדקסים

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

class IndexedQueue:
   def __init__(self):
       self.queue = list()
       self.__queue_size = 0
       self.start_index = 0

def pop_first(self):
   if self.__queue_size == 0:
       return None

   if self.start_index == self__.queue_size - 1:
       return None

   else:
       first_item = self.queue[self.start_index]
       self.__queue_size -= 1
       self.start_index += 1
       return first_item

אמרו לא לצפיפות!

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

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

כדי להתגבר על בעיית המקום, אפשר להחליט שאנחנו כן משחררות איברים מהתור, אבל לא בכל פעולה אלא רק לפעמים. בערך פעם אחת בכל n פעולות.
למשל, אני יכולה להוסיף פונקציה שבודקת בכל הוצאה את מספר האיברים שכבר ״הוצאו״ מהתור. אם החלק הריק של הרשימה מגיע לאחוז כלשהו, נגיד 3/4 מגודל הרשימה, אנחנו נעתיק את כל האיברים שנותרו לרשימה חדשה בגודל n/2, ונשחרר את הרשימה הקודמת.

העתקת כל המספרים הנותרים לרשימה חדשה מתבצעת בסיבוכיות o(n). מכיוון שאני אוציא אותה לפועל רק פעם ב-n פעולות הוצאה, הסיבוכיות המשוערכת (amortized) שלי תהיה – o(1) לכל פעולת הוצאה. אני לא אכנס כאן יותר מדי לעומק ההסבר על סיבוכיות משוערכת אבל אם אתן לא מכירות שווה לקרוא.

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

מימוש בעזרת רשימה מקושרת

דרך אחרת לממש את pop באופן אלטרנטיבי היא ללכת צעד אחד אחורה ולשאול את עצמנו למה אנחנו בכלל צריכות להשתמש במערך? אם במקום להשתמש במערך נשתמש ברשימה מקושרת נוכל לייצר מימוש שמכניס ומוציא לקוחות מהתור בסיבוכיות o(1).

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

class LinkedListQueue:
   def __init__(self):
       self.__queue_size = 0
       self.first_node = NullNode()
       self.last_node = NullNode()

   def size(self):
       return self.__queue_size

   def add(self, value):
       if self.__queue_size == 0:
           self.first_node = LinkedListNode(value)
           self.first_node.set_next(NullNode())
           self.last_node = self.first_node
       else:
           new_last_node = LinkedListNode(value)
           self.last_node.set_next(new_last_node)
           self.last_node = new_last_node
       self.__queue_size += 1

   def pop_first(self):
       if self.__queue_size == 0:
           return None
       else:
           first_value = self.first_node.value()
           self.first_node = self.first_node.get_next()
           self.__queue_size -= 1
           return first_value

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


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


unsplash-logoHeader photo by Daniel K Cheung Vector image by VectorStockDucks photo by Vectorstock

8 תגובות בנושא “זה לא התור, זה הסיבוכיות

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

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

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

    לגבי המימוש הראשון – אולי פספסתי אבל אני לא מוצא את המונח "חוצץ מעגלי", וזה צריך להיות השם של המחלקה:
    https://en.wikipedia.org/wiki/Circular_buffer
    (נשמטה במימוש הזחה אחת בטעות, עבור המתודה השניה)

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

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

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

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

  4. הי מאיה, פוסט מצוין!
    מעניין לראות שגם בעולם של NodeJS אין מימוש מספק (מבחינת ביצועים) של תור, כחלק מה standard library של השפה עצמה.
    מנצל את ההזדמנות ומרים לעצמי בלי בושה: באפריל האחרון הצגתי במיטאפ של NodeJS IL את המימושים שכתבתי לתור, והם זמינים גם ב package בשם lite-fifo.

  5. שימי לב שיש הבדל מהותי בין O(n) ובין o(n) – זה קצת כמו ההבדל בין ״קטן/שווה״ ל־״קטן ממש״.

השאר תגובה