בעיה י"א

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

age = input(‘Insert age; -1 to stop: ‘)

while age != ‘-1’:

    print(age)

    age = input(‘Insert age; -1 to stop: ‘)

 

יש לכתוב את הפונקציה digitsAndNums2  –

def digitsAndNums2(nums):

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

[33, 13, 913]

הפונקציה תחזיר את המילון הזה –

{3: (33, 13, 913), 1: (13, 913), 9: (913,)}

הזוגות לא יופיעו במילון בהכרח בסדר הזה.

פתרון

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

{3: (33, 13), 1: (13)}

עד סוף הפתרון נוסיף נוסיף רשומה חדשה למילון, וגם נגדיל את הרשומות הפנימיות שאליהם ממופים המפתחות 3 ו-1 –

{3: (33, 13, 913), 1: (13, 913), 9: (913,)}

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

def digitsAndNums(nums):    

    d = {} 

    for num in nums: 

        digits = set(str(num))

        for digit in digits:             

            intDigit = int(digit)

            if intDigit not in d: 

                d[intDigit] = 1 

            else: 

                d[intDigit] += 1

    return d

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

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

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

אם כן הנה הצעה לפתרון המבוססת על האבחנה הנ”ל –

def digitsAndNums2(nums):    

    d = {} 

    for num in nums: 

        digits = set(str(num))

        for digit in digits:             

            intDigit = int(digit)

            if intDigit not in d: 

                d[intDigit] = (num,)

            else: 

                d[intDigit] += (num,)

    return d 

        

print(digitsAndNums2([33, 13, 913]))

>>>

{3: (33, 13, 913), 1: (13, 913), 9: (913,)}

נבחן את יצירת המילון עבור הרשימה המועברת אליה בזימון כאן –

[33, 13, 913]

בסיבוב הראשון של הלולאה החיצונית num == 33, וללולאה הפנימית יש סיבוב אחד בלבד – עבור הספרה 3. בתחילת סיבוב יחיד זה של הלולאה הפנימית המילון ריק. בייחוד אין בו זוג שהמפתח בו הוא הספרה 3. לכן יש להוסיף אליו את הזוג הזה –

{3: (33,)}

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

d[intDigit] = (num,)

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

בסיבוב השני של הלולאה החיצונית num = 13, וללולאה הפנימית יש שני סיבובים: האחד עבור הספרה 1 והשני עבור הספרה 3. נניח שלמילון מיתוסף ראשית הזוג שבו המפתח הוא הספרה 1. כיוון שספרה זו עדיין אינה מפתח במילון, מתבצעת שוב הכנסת זוג חדש למילון, ולאחריה המילון יהיה זה –

{3: (33,) 1: (13,)}

בסיבוב השני של הלולאה הפנימית, עבור הספרה 3, נמצא שכבר יש במילון זוג שהמפתח בו הוא 3. פירוש הדבר כי הפעולה שיש לבצע אינה הכנסת זוג חדש, אלא עדכון זוג במילון, באמצעות האופרטור =+

d[intDigit] += (num,)

d[intDigit] הוא הרשומה שאליה ממופה הספרה intDigit, ובמקרה המסוים הנבחן כאן, הכוונה היא לרשומה שאליה ממופה הספרה 3, כלומר לרשומה (33,). האופרטור += מוסיף לרשומה הזאת רשומה המכילה את המספר הנסרק הנוכחי, כלומר את הרשומה (13,). כך מתעדכנת הרשומה שאליה ממופה המפתח 3: העדכון החלפת הרשומה הנוכחית, (33,), ברשומה היא תוצאה של הפעולה הזאת –

(33,) + (13,)

וכך לאחר העדכון תוכן המילון הוא זה –

{3: (33, 13) 1: (13,)}

ניתן מבט נוסף בהוראה הזאת –

d[intDigit] = d[intDigit] + (num,)

האופרטור + פועל כאן על אוסף – ספציפית: רצף – מסוג שאי אפשר לשנות אותו במקום. לכן מצד ימין של ההוראה כאן נוצרת רשומה חדשה, וההוראה מחליפה בה את הרשומה שאליה ממופה כרגע הספרה intDigits במילון. למשל אם הספרה 3 ממופה כרגע לרשומה (33,), ו- num == 13, הוראת ההשמה תיצור רשומה חדשה זו –

(33,) + (13,)  → (33, 13)

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

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

d[intDigit] += (num,)

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

{3: [33, 13, 913], 1: [13, 913], 9: [913]}

בפתרון, בשלב הוספת זוג חדש למילון, היינו ממפים ספרה לרשימה שיש בה מספר יחיד, כך –

d[intDigit] = [num]

בשלב שבו היינו מעדכנים זוג היינו יכולים לכתוב כך –

d[intDigit] = d[intDigit] + [num]

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

d[intDigit] += [num]

אין נוצרת רשימה חדשה! למשל אם intDigit == 3, num = 13, והספרה 3 ממופה כרגע לרשימה [33], הרשימה הזאת עצמה תגדל: המספר 13 ייתוסף לסופה, והרשימה [33, 13] שתתקבל לא תהיה רשימה חדשה. 

היוצא מזה הוא שהשימוש באופרטור =+ על רשימות מאפשר לחסוך במשאבי זכרון. לאור זאת עיינו בשכתוב של הפתרון שהוצע למעלה –

def digitsAndNums2(nums):    

    d = {} 

    for num in nums: 

        digits = set(str(num))

        for digit in digits:             

            intDigit = int(digit)

            if intDigit not in d: 

                d[intDigit] = [num,]

            else: 

                d[intDigit] += [num]

    for k in d: 

        d[k] = tuple(d[k])    

    return d 

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