לפני כמה שבועות העברתי הרצאה בכנס 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). 

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