הפונקציות שיצרנו עד כה נבנו כך שיחזירו ערך אחד בכל קריאה.
הערך הזה יכול היה להיות מכל טיפוס שהוא: בוליאני, מחרוזת, tuple וכדומה.
אם נרצה להחזיר כמה ערכים יחד, תמיד נוכל להחזיר אותם כרשימה או כ־tuple.
אבל מה קורה כשאנחנו רוצים להחזיר סדרת ערכים גדולה מאוד או אפילו אין־סופית?
למשל:
בכלים שיש בידינו כרגע, נמצא שיש בעיה ליצור רשימות כאלו.
עבור רשימות גדולות מאוד – לא יהיה למחשב די זיכרון ולבסוף הוא ייכשל בשמירת ערכים חדשים.
ומה בנוגע לרשימות אין־סופיות? הן... ובכן... אין־סופיות, ולכן מלכתחילה לא נוכל ליצור אותן.
פתרון שמעניין לחשוב עליו הוא "פונקציה עצלנית".
אם אנחנו בשום שלב לא יכולים להחזיק בזיכרון המחשב את כל האיברים (כי יש יותר מדי מהם, או כי זו סדרה אין־סופית),
אולי נוכל לשלוח תחילה את הערך הראשון – ואת הערכים שבאים אחריו נשלח רק כשיבקשו אותם מאיתנו.
פונקציה עצלנית שכזו נקראת generator, ובכל פעם שנבקש ממנה, היא תחזיר לנו איבר יחיד מתוך סדרת ערכים.
תחילה – היא תחזיר רק את הערך הראשון, בלי לחשב את שאר האיברים. אחר כך, באותו אופן, רק את השני, אחר כך רק את השלישי וכן הלאה.
ההבדל העיקרי בין generator לבין פונקציה רגילה, הוא שב־generator נבחר להחזיר את הערכים אחד־אחד ולא תחת מבנה מאוגד.
נסכם: generator היא פונקציה שיוצרת עבורנו בכל פעם ערך אחד, מחזירה אותו, ומחכה עד שנבקש את האיבר הבא.
נתחיל בהגדרת generator מטופש למדי:
In [ ]:
def silly_generator():
a = 1
yield a
b = a + 1
yield b
c = [1, 2, 3]
yield c
מעניין! זה נראה ממש כמו פונקציה. נקרא למבנה הזה שיצרנו "פונקציית ה־generator".
אבל מהו ה־yield המוזר הזה שנמצא שם?
לפני שנתהה על קנקנו, בואו ננסה לקרוא לפונקציה ונראה מה היא מחזירה:
In [ ]:
print(silly_generator())
אומנם למדנו שלא אומרים איכס על פונקציות, אבל מה קורה פה?
בניגוד לפונקציות רגילות, קריאה ל־generator לא מחזירה ערך מייד.
במקום ערך היא מחזירה מעין סמן, כמו בקובץ, שאפשר לדמיין כחץ שמצביע על השורה הראשונה של הפונקציה.
נשמור את הסמן על משתנה:
In [ ]:
our_generator = silly_generator()
בעקבות הקריאה ל־silly_generator נוצר לנו סמן שמצביע כרגע על השורה a = 1.
המינוח המקצועי לסמן הזה הוא generator iterator.
אחרי שהרצנו את השורה our_generator = silly_generator(), הסמן המדובר נשמר במשתנה בשם our_generator.
זה זמן מצוין לבקש מה־generator להחזיר ערך.
נעשה זאת בעזרת הפונקציה הפייתונית next:
In [ ]:
next_value = next(our_generator)
print(next_value)
כדי להבין מה התרחש נצטרך להבין שני דברים חשובים שקשורים ל־generators:
next היא כמו לחיצה על "נגן" (Play) – היא גורמת לסמן לרוץ עד שהוא מגיע לשורה של החזרת ערך.yield דומה למילת המפתח return – היא מפסיקה את ריצת הסמן, ומחזירה את הערך שמופיע אחריה.
אז היה לנו סמן שהצביע על השורה הראשונה. לחצנו Play, והוא הריץ את הקוד עד שהוא הגיע לנקודה שבה מחזירים ערך.
ההבדל בין פונקציה לבין generator, הוא שכשאנחנו מחזירים ערך בעזרת yield אנחנו "מקפיאים" את המצב שבו
יצאנו מהפונקציה.
ממש כמו ללחוץ על "Pause".
כשנקרא ל־next בפעם הבאה – הפונקציה תמשיך לרוץ מאותו המקום שבו השארנו את הסמן, עם אותם ערכי משתנים.
עכשיו הסמן מצביע על השורה b = a + 1, ומחכה שמישהו יקרא שוב ל־next כדי שהפונקציה תוכל להמשיך לרוץ:
In [ ]:
print(next(our_generator))
נסכם מה קרה עד עכשיו:
next על ה־generator iterator, הרצנו את הסמן עד שה־generator החזיר ערך.next על ה־generator iterator, וראינו שהוא ממשיך מהמקום שבו ה־generator הפסיק לרוץ פעם קודמת.
תוכלו לחזות מה יקרה אם נקרא שוב ל־next(our_generator)?
חשוב!
פתרו לפני שתמשיכו!
ננסה:
In [ ]:
print(next(our_generator))
יופי! הכל הלך כמצופה.
אבל מה צופן לנו העתיד?
בפעם הבאה שנבקש ערך מהפונקציה, הסמן שלנו ירוץ הלאה ולא ייתקל ב־yield.
במקרה כזה, נקבל שגיאת StopIteration, שמבשרת לנו ש־next לא הצליח לחלץ מה־generator את הערך הבא.
In [ ]:
print(next(our_generator))
מובן שאין סיבה להילחץ.
במקרה הזה אפילו לא מדובר במשהו רע – פשוט כילינו את כל הערכים מה־generator iterator שלנו.
פונקציית ה־generator עדיין קיימת!
אפשר ליצור עוד generator iterator אם נרצה, ולקבל את כל הערכים שנמצאים בו באותה צורה:
In [ ]:
our_generator = silly_generator()
print(next(our_generator))
print(next(our_generator))
print(next(our_generator))
אבל כשחושבים על זה, זה קצת מגוחך.
בכל פעם שנרצה להשיג את הערך הבא נצטרך לרשום next?
חייבת להיות דרך טובה יותר!
אז למעשה, יש יותר מדרך טובה אחת להשיג את כל הערכים שיוצאים מ־generator מסוים.
כהקדמה, נניח פה עובדה שלא תשאיר אתכם אדישים: ה־generator iterator הוא... iterable! הפתעת השנה, אני יודע!
אמנם אי אפשר לפנות לאיברים שלו לפי מיקום, אך בהחלט אפשר לעבור עליהם בעזרת לולאת for, לדוגמה:
In [ ]:
our_generator = silly_generator()
for item in our_generator:
print(item)
מה מתרחש כאן?
אנחנו מבקשים מלולאת ה־for לעבור על ה־generator iterator שלנו.
ה־for עושה עבורנו את העבודה אוטומטית:
next.next. כך עד שייגמרו האיברים ב־generator iterator.
שימו לב שהעובדות שלמדנו בנוגע לאותו "סמן" יבואו לידי ביטוי גם כאן.
הרצה נוספת של הלולאה על אותו סמן לא תדפיס יותר איברים, כיוון שהסמן מצביע כעת על סוף פונקציית ה־generator:
In [ ]:
for item in our_generator:
print(item)
למזלנו, לולאות for יודעות לטפל בעצמן בשגיאת StopIteration, ולכן שגיאה שכזו לא תקפוץ לנו במקרה הזה.
דרך אחרת, לדוגמה, היא לבקש להמיר את ה־generator iterator לסוג משתנה אחר שהוא גם iterable:
In [ ]:
our_generator = silly_generator()
items = list(our_generator)
print(items)
בקוד שלמעלה, השתמשנו בפונקציה list שיודעת להמיר ערכים iterable־ים לרשימות.
שימו לב שמה שלמדנו בנוגע ל"סמן" יבוא לידי ביטוי גם בהמרות:
In [ ]:
print(list(our_generator))
נכתוב פונקציה רגילה שמקבלת מספר שלם, ומחזירה רשימה של כל המספרים השלמים מ־0 ועד אותו מספר (נשמע לכם מוכר?):
In [ ]:
def my_range(upper_limit):
numbers = []
current_number = 0
while current_number < upper_limit:
numbers.append(current_number)
current_number = current_number + 1
return numbers
for number in my_range(1000):
print(number)
בפונקציה הזו אנחנו יוצרים רשימת מספרים חדשה, המכילה את כל המספרים בין 0 לבין המספר שהועבר לפרמטר upper_limit.
אך ישנה בעיה חמורה – הפעלת הפונקציה גורמת לניצול משאבים רבים!
אם נכניס כארגומנט 1,000 – נצטרך להחזיק רשימה המכילה 1,000 איברים שונים, ואם נכניס מספר גדול מדי – עלול להיגמר לנו הזיכרון.
אבל איזו סיבה יש לנו להחזיק בזיכרון את רשימת כל המספרים?
אם לא עולה צורך מובהק שכזה, ייתכן שעדיף להחזיק בזיכרון מספר אחד בלבד בכל פעם, ולהחזירו מייד בעזרת generator:
In [ ]:
def my_range(upper_limit):
current_number = 0
while current_number < upper_limit:
yield current_number
current_number = current_number + 1
our_generator = my_range(1000)
for number in our_generator:
print(number)
שימו לב כמה הגרסה הזו אלגנטית יותר!
בכל פעם אנחנו פשוט שולחים את ערכו של מספר אחד (current_number) החוצה.
כשמבקשים את הערך הבא מה־generator iterator, פונקציית ה־generator חוזרת לעבוד מהנקודה שבה היא עצרה:
היא מעלה את ערכו של המספר הנוכחי, בודקת אם הוא נמוך מ־upper_limit, ושולחת גם אותו החוצה.
בשיטה הזו, my_range(numbers) לא מחזירה לנו רשימה של התוצאות – אלא generator iterator שמחזיר ערך אחד בכל פעם.
כך אנחנו לעולם לא מחזיקים בזיכרון 1,000 מספרים בו־זמנית.
לפניכם פונקציה שמקבלת רשימה, ומחזירה עבור כל מספר ברשימה את ערכו בריבוע.
זוהי גרסה מעט בזבזנית שמשתמשת בהרבה זיכרון. תוכלו להמיר אותה להיות generator?
חשוב!
פתרו לפני שתמשיכו!
In [ ]:
def square_numbers(numbers):
squared_numbers = []
for number in numbers:
squared_numbers.append(number ** 2)
return squared_numbers
for number in square_numbers(my_range(1000)):
print(number)
לעיתים ניאלץ לבצע חישוב ארוך, שהשלמתו תימשך זמן רב מאוד.
במקרה כזה, נוכל להשתמש ב־generator כדי לקבל חלק מהתוצאה בזמן אמת,
בזמן שבפונקציה "רגילה" נצטרך להמתין עד סיום החישוב כולו.
שלשה פיתגורית, לדוגמה, היא שלישיית מספרים שלמים וחיוביים, $a$, $b$ ו־$c$, שעונים על הדרישה $a^2 + b^2 = c^2$.
אם כך, כדי ששלושה מספרים שאנחנו בוחרים ייחשבו שלשה פיתגורית,
הסכום של ריבוע המספר הראשון וריבוע המספר השני, אמור להיות שווה לערכו של המספר השלישי בריבוע.
אלו דוגמאות לשלשות פיתגוריות:
ננסה למצוא את כל השלשות הפיתגוריות מתחת ל־10,000 בעזרת קוד שרץ על כל השלשות האפשריות:
In [ ]:
def find_pythagorean_triples(upper_bound=10_000):
pythagorean_triples = []
for c in range(3, upper_bound):
for b in range(2, c):
for a in range(1, b):
if a ** 2 + b **2 == c ** 2:
pythagorean_triples.append((a, b, c))
return pythagorean_triples
for triple in find_pythagorean_triples():
print(triple)
הרצת התא הקודם תתקע את המחברת (חישוב התוצאה יימשך זמן רב).
כדי להיות מסוגלים להריץ את התאים הבאים, לחצו 00 לאחר הרצת התא, ובחרו Restart.
אל דאגה – האתחול יתבצע אך ורק עבור המחברת, ולא עבור מחשב.
יו, כמה זמן נמשכת הרצת הקוד הזה... 😴
הלוואי שעד שהקוד הזה היה מסיים היינו מקבלים לפחות חלק מהתוצאות!
נפנה ל־generator־ים לעזרה:
In [ ]:
def find_pythagorean_triples(upper_bound=10_000):
for c in range(3, upper_bound):
for b in range(2, c):
for a in range(1, b):
if a ** 2 + b **2 == c ** 2:
yield a, b, c
for triple in find_pythagorean_triples():
print(triple)
איך זה קרה? קיבלנו את התשובה בתוך שבריר שנייה!
ובכן, זה לא מדויק – קיבלנו חלק מהתשובות. שימו לב שהקוד ממשיך להדפיס :)
להזכירכם, ה־generator שולח את התוצאה החוצה מייד כשהוא מוצא שלשה אחת,
וה־for מקבל מה־generator iterable כל שלשה ברגע שהיא נמצאה.
ברגע שה־for מקבל שלשה, הוא מבצע את גוף הלולאה עבור אותה שלשה, ורק אז מבקש מ־generator את האיבר הבא.
בגלל האופי של generators, הקוד בתא האחרון מדפיס לנו כל שלשה ברגע שהוא מצא אותה, ולא מחכה עד שיימצאו כל השלשות.
"פירוק לגורמים של מספר שלם" היא בעיה שחישוב פתרונה נמשך זמן רב במחשבים מודרניים.
עליכם לכתוב פונקציה שמקבלת מספר חיובי שלם $n$, ומחזירה קבוצת מספרים שמכפלתם (תוצאת הכפל ביניהם) היא $n$.
לדוגמה, המספר 1,386 בנוי מהמכפלה של קבוצת המספרים $2 \cdot 3 \cdot 3 \cdot 7 \cdot 11$.
כל מספר בקבוצת המספרים הזו חייב להיות ראשוני.
להזכירכם: מספר ראשוני הוא מספר שאין לו מחלקים חוץ מעצמו ומ־1.
הניחו שהמספר שהתקבל אינו ראשוני.
מה היתרון של generator על פני פונקציה רגילה שעושה אותו דבר?
רמז: אם תנסו לחלק את המספר ב־2, ואז ב־3 (וכן הלאה), בסופו של דבר תגיעו למחלק ראשוני של המספר.
רמז עבה: בכל פעם שמצאתם מחלק אחד למספר, חלקו את המספר במחלק, והתחילו את החיפוש מחדש. מתי עליכם לעצור?
עבור בעיות מסוימות, נרצה להיות מסוגלים להחזיר אין־סוף תוצאות.
ניקח כדוגמה לסדרה אין־סופית את סדרת פיבונאצ'י, שבה כל איבר הוא סכום זוג האיברים הקודמים לו:
$1, 1, 2, 3, 5, 8, \ldots$
נממש פונקציה שמחזירה לנו את סדרת פיבונאצ'י.
בפונקציה רגילה אין לנו אפשרות להחזיר מספר אין־סופי של איברים, ולכן נצטרך להחליט על מספר האיברים המרבי שנרצה להחזיר:
In [ ]:
def fibonacci(max_items):
a = 1
b = 1
numbers = [1, 1]
while len(numbers) < max_items:
a, b = b, a + b # Unpacking
numbers.append(b)
return numbers
for number in fibonacci(10):
print(number)
לעומת זאת, ל־generators לא חייב להיות סוף מוגדר.
נשתמש ב־while True שתמיד מתקיים, כדי שבסופו של דבר – תמיד נגיע ל־yield:
In [ ]:
def fibonacci():
a = 1
b = 1
numbers = [1, 1]
while True: # תמיד מתקיים
yield a
a, b = b, a + b
generator_iterator = fibonacci()
for number in range(10):
print(next(generator_iterator))
# אני יכול לבקש בקלות רבה את 10 האיברים הבאים בסדרה
for number in range(10):
print(next(generator_iterator))
generators אין־סופיים יכולים לגרום בקלות ללולאות אין־סופיות, גם בלולאות for.
שימו לב לצורת ההתעסקות העדינה בדוגמאות למעלה.
הרצת לולאת for ישירות על ה־generator iterator הייתה מכניסה אותנו ללולאה אין־סופית.
כתבו generator שמחזיר את כל המספרים השלמים הגדולים מ־0.
חשוב!
פתרו לפני שתמשיכו!
נגדיר generator פשוט שמחזיר את האיברים 1, 2 ו־3:
In [ ]:
def simple_generator():
yield 1
yield 2
yield 3
ניצור שני generator iterators ("סמנים") שונים שמצביעים לשורה הראשונה של ה־generator שמופיע למעלה:
In [ ]:
first_gen = simple_generator()
second_gen = simple_generator()
בעניין זה, חשוב להבין שכל אחד מה־generator iterators הוא "חץ" נפרד שמצביע לשורה הראשונה ב־simple_generator.
אם נבקש מכל אחד מהם להחזיר ערך, נקבל משניהם את 1, ואותו חץ דמיוני יעבור בשני ה־generator iterators להמתין בשורה השנייה:
In [ ]:
print(next(first_gen))
print(next(second_gen))
נוכל לקדם את first_gen, לדוגמה, לסוף הפונקציה:
In [ ]:
print(next(first_gen))
print(next(first_gen))
אבל second_gen הוא חץ נפרד, שעדיין מצביע לשורה השנייה של פונקציית ה־generator.
אם נבקש ממנו את הערך הבא, הוא ימשיך את המסע מהערך 2:
In [ ]:
print(next(second_gen))
ממצב זה נוכל להסיק שאפשר ליצור יותר מ־generator iterator אחד עבור כל פונקציית generator.
כל אחד מה־generator iterators יחזיק תמונת מצב עצמאית של המקום שבו עצר הסמן ושל ערכי המשתנים.
ההתנהלות של כל generator iterator תקרה בנפרד, ולא תושפע בשום צורה מה־generator iterators האחרים.
בשלב זה יש לנו הרבה מבנים שאפשר לרוץ עליהם, וכל המינוח סביב עניין האיטרביליות נעשה מעט מבלבל.
ננסה לעשות סדר בדברים:
next().iterable[0]), כמו מחרוזות, רשימות ו־tuple־ים.yield ומגדירה אילו ערכים יוחזרו מה־generator.
Generators הם פונקציות שמאפשרות לנו להחזיר סדרות ערכים באופן מדורג.
כשנקרא לפונקציית generator, היא תחזיר לנו generator iterator שישמש מעין "סמן".
הסמן ישמור "מצב" שמתאר את המקום שבו אנחנו שוהים בתוך הפונקציה, ואת הערכים שחושבו במהלך ריצתה עד כה.
בכל שלב, נוכל לבקש את הערך הבא ב־generator בעזרת קריאה לפונקציה next על ה־generator iterator.
נוכל גם להשתמש במבנים שיזיזו עבורנו את הסמן, כמו for או המרה לסוג נתונים אחר שגם הוא iterable.
ל־generators יתרונות רבים:
קראו בוויקיפדיה על דרך החישוב של ספרת הביקורת במספרי הזהות בישראל.
אפשר לחלק רול סושי של 6 יחידות לאדם אחד, ל־2 אנשים, ל־3 אנשים ול־6 אנשים.
נתעלם ממצבים שבהם כל אדם מקבל רק חתיכת סושי אחת. זה נשמע לי עצוב.
נגדיר "מנה מושלמת לחלוקה" כמנה שאם נסכום את כל הצורות לחלק אותה, נקבל את גודל המנה עצמה.
לדוגמה:
כתבו תוכנית שמדפיסה באופן אין־סופי את כל גודלי המנות שנחשבים מושלמים לחלוקה.
בקובץ resources/logo.jpg מופיע לוגו הקורס, ובתוכו מוכמנים מסרים סודיים אחדים.
המסרים הם מחרוזות באורך 5 אותיות לפחות, כתובים באותיות אנגליות קטנות בלבד ומסתיימים בסימן קריאה.
פתחו את הלוגו לקריאה בתצורה בינארית, וחלצו ממנו את המסרים הסודיים.
זכרו שהקובץ עלול להיות גדול מאוד, ועדיף שלא לקרוא את כולו במכה אחת.
מצאו באינטרנט עזרה בנוגע לפתיחת קבצים בצורה בינארית ולקריאה מדורגת של הקובץ.
הקפידו שלא להשתמש בטכניקות שלא למדנו (או להוסיף אותן רק בנוסף לפתרון שכזה).