ייצוג סדרות
סידרה היא פשוט רצף של ערכים ויש מספר דרכים לייצג סדרות בתוכניות מחשב. כשאנחנו מדברים על רצף ערכים סופי ולא גדול אפשר להשתמש בזיכרון ולשמור את הסידרה כולה במערך, למשל רשימת כל הסימניות שאני שומר לאתרי אינטרנט:
bookmarks = [
'https://www.tocode.co.il',
'https://www.google.com',
]
וכשאנחנו מדברים על סדרות יותר מעניין לדבר על סדרות ארוכות מאוד או אפילו אין סופיות. דרך אחת לייצג סדרות ארוכות היא פונקציה שמקבלת אינדקס ומחזירה את האיבר המתאים בסידרה. למשל סידרת המספרים הזוגיים היא אין סופית (0, 2, 4, 6, ... ), ואין בעיה לייצג את כולה באמצעות הפונקציה:
def even(index):
return index * 2
עבור כל "מקום בסידרה" שנעביר לפונקציה נקבל את האיבר שיושב במקום הזה.
אבל הסדרות המעניינות באמת הן סדרות שאי אפשר לייצג אותן עם פונקציה. למשל סידרת המספרים שמשתמש מסוים יקליד לתוכנית, או רצף השורות בקובץ. בשני המקרים אי אפשר לדלג על ערכים, כלומר כדי לדעת מה המספר החמישי שמשתמש הכניס לתוכנית צריך יהיה לקבל את ה-4 שקדמו לו. בשביל למצוא את השורה החמישית בקובץ צריך יהיה לחפש את ה-4 שקדמו לה.
ייצוג סדרות מסוג זה בתוכנית מחשב יאפשר לנו להפריד בין הקוד שמטפל בסידרה לקוד שמגדיר אותה כך שאפשר להשתמש שוב ושוב בקוד שמגדיר את הסידרה בהקשרים שונים.
אני חושב שדוגמא תעזור כאן ונתחיל מאיפה שאנחנו מכירים בעבודה עם קבצים. התוכנית הבאה בשפת פייתון מדפיסה את כל השורות בקובץ עם מספרי שורה:
import sys
with open(sys.argv[1]) as f:
for index, line in enumerate(f):
sys.stdout.write(f"{index}: {line}")
print()
והנה גירסא נוספת הפעם שמדפיסה רק את השורות שארוכות מ-10 תווים מתוך הקובץ:
import sys
with open(sys.argv[1]) as f:
for index, line in enumerate(f):
if len(line) <= 10: continue
sys.stdout.write(f"{index}: {line}")
print()
מעניין להסתכל על המשותף בין שתי התוכניות- בשתיהן לא היינו צריכים לכתוב קוד שקורא את התווים מהקובץ ומזהה מתי שורה חדשה מתחילה. המבנה הזה של "סידרת השורות בקובץ" שחוזר על עצמו בשתי התוכניות הוא משהו שקיבלנו מהשפה עצמה. רשימת הקלטים מהמשתמש לתוכנית זה עוד מבנה שאנחנו מקבלים במתנה מהשפה.
ופייתון כמו גם שפות רבות אחרות מאפשרת למתכנתים גם להגדיר מבנים כאלה בעצמנו, ואז להשתמש בהם שוב ושוב בתוכניות. קחו לדוגמא את סידרת מספרי פיבונאצ'י, הלא היא הסידרה בה כל ערך מורכב מסכום שניה ערכים שלפניו:
1, 1, 2, 3, 5, 8, 13, 21
אפשר היה לייצג אותה באמצעות פונקציה רגילה שנראית כך:
def fib(n):
x, y = 0, 1
for i in range(n):
x, y = y, x + y
return x
אבל הייצוג הזה מערבב את "מה שאני רוצה לעשות" עם "איך אני מקבל את הערך". קל לראות את הערבוב כשאנחנו מנסים להשתמש בפונקציה למטרות שונות, למשל קל להשתמש בפונקציה כדי להדפיס את המספר השמיני בסידרת פיבונאצ'י:
print(fib(8))
אבל הרבה יותר קשה להשתמש בה כדי לגלות מה הערך הראשון בסידרה שגדול מ-200. כי בשביל זה נצטרך להפעיל אותה שוב ושוב ולבדוק כל ערך בנפרד:
i = 0
while fib(i) < 200:
i += 1
print(f"fib({i}) == {fib(i)}")
ומה כל כך רע בקטע הקוד האחרון אתם שואלים? שימו לב כמה פעמים הוא צריך לחשב את המספר השלישי או הרביעי בסידרה כדי לענות על השאלה. למעשה כל איטרציה של הלולאה אנחנו מחשבים שוב את כל הערכים שהיו לפני. באנלוגיה לקובץ זה קצת כמו שהיינו צריכים לקרוא את הקובץ מההתחלה כל פעם שרוצים להדפיס שורה נוספת.
לכן שפת פייתון תומכת בכתיב נוסף שנקרא Generators ומטרתו לייצג את הסידרה, בלי להגיד כלום על מה אתם רוצים לעשות עם הערכים. מילת הקסם בפייתון לכתוב Generator היא yield ואת הסידרה נכתוב כך:
def fib():
x, y = 0, 1
while True:
yield x
x, y = y, x + y
לוגיקת החישוב לא השתנתה מה שכן השתנה זה מה עושים עם הערך. במקום לחשב את הערך ה-n בסידרה אנחנו עושים yield לכל ערך בנפרד. כך קוד שמגיע מבחוץ יכול לקבל את הסידרה ערך אחרי ערך ולהחליט מה הוא עושה עם הערכים. בדיוק כמו שהקוד שלנו שקורא קובץ שורה-אחר-שורה החליט מה הוא עושה עם השורות ואז המשיך לקרוא את השורה הבאה מאותה נקודה בה עצר.
כך נראה קוד שמשתמש בסידרה החדשה שלנו כדי להדפיס את המספר השמיני בסידרת פיבונאצ'י:
for index, val in enumerate(fib()):
if index == 8:
print(val)
break
וזה הקוד שיגלה מהו הערך הראשון שגדול מ-200:
for index, val in enumerate(fib()):
if val > 200:
print(val)
break
ואגב המנגנון של הגדרת סדרות קיים בהרבה מאוד שפות תכנות. הנה אותה תוכנית פיבונאצ'י בתרגום לרובי ו JavaScript - נסו למצוא את ההבדלים:
fib = Enumerator.new do |yielder|
x, y = 0, 1
loop do
yielder << x
x, y = y, x + y
end
end
fib.lazy.each_with_index do |val, index|
if index == 8
puts val
break
end
end
fib.lazy.each_with_index do |val, index|
if val > 200
puts val
break
end
end
function *enumerate(it, start=0) {
for(let x of it) {
yield [start++, x];
}
}
function *fib() {
[x, y] = [0, 1];
while(true) {
yield x;
[x, y] = [y, x + y];
}
}
for ([index, val] of enumerate(fib())) {
if (index == 8) {
console.log(val);
break;
}
}
for ([index, val] of enumerate(fib())) {
if (val > 200) {
console.log(val);
break;
}
}
שימו לב איך ב JavaScript גם המבנה של enumerate לא קיים בשפה ואנחנו בונים אותו באותו תחביר בניית סדרות איתו בנינו את סידרת פיבונאצ'י.