איטרציה

אִיטֵרַצְיָה (באנגלית: Iteration; על פי האקדמיה ללשון העברית: חִזְרוּר) היא פעולה החוזרת על עצמה במהלך פתרון של בעיה, בדרך כלל בעיה כמותית. כל חזרה נקראת איטרציה. תהליך המורכב מאיטרציות קרוי תהליך איטרטיבי (או תהליך חזרור). כאשר מדובר בבעיה כמותית, ניתן לבצע את האיטרציות הן באופן ידני והן בעזרת מחשב. בדרך כלל משמשים מושגים אלה לתיאור תהליך במסגרת תוכנית מחשב, ובאופן כללי יותר לתיאור אלגוריתמים.

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

דוגמאות לאיטרציות

• ביצוע גוף לולאה (Loop) באלגוריתם המשמש לכתיבת תוכניות מחשב באמצעות שפת תכנות.
• מחזור של רקורסיה. במובן מסוים של המונח איטרציה קיימת הבחנה בין אלגוריתם איטרטיבי המתייחס ללולאה בלבד, לבין אלגוריתם רקורסיבי.
• בפרשת עכן, המתוארת בספר יהושע, נלכד עכן בתהליך איטרטיבי בן ארבעה שלבים: ”וַיַּשְׁכֵּם יְהוֹשֻׁעַ בַּבֹּקֶר וַיַּקְרֵב אֶת יִשְׂרָאֵל לִשְׁבָטָיו, וַיִּלָּכֵד שֵׁבֶט יְהוּדָה. וַיַּקְרֵב אֶת מִשְׁפַּחַת יְהוּדָה וַיִּלְכֹּד אֵת מִשְׁפַּחַת הַזַּרְחִי, וַיַּקְרֵב אֶת מִשְׁפַּחַת הַזַּרְחִי לַגְּבָרִים וַיִּלָּכֵד זַבְדִּי. וַיַּקְרֵב אֶת בֵּיתוֹ לַגְּבָרִים, וַיִּלָּכֵד עָכָן בֶּן כַּרְמִי בֶן זַבְדִּי בֶּן זֶרַח לְמַטֵּה יְהוּדָה.” (ספר יהושע, פרק ז', פסוקים ט"ז–י"ח) תהליך איטרטיבי דומה מופיע בתיאור המלכתו של שאול: ”וַיַּקְרֵב שְׁמוּאֵל אֵת כָּל שִׁבְטֵי יִשְׂרָאֵל, וַיִּלָּכֵד שֵׁבֶט בִּנְיָמִן. וַיַּקְרֵב אֶת שֵׁבֶט בִּנְיָמִן לְמִשְׁפְּחֹתָיו וַתִּלָּכֵד מִשְׁפַּחַת הַמַּטְרִי, וַיִּלָּכֵד שָׁאוּל בֶּן קִישׁ וַיְבַקְשֻׁהוּ וְלֹא נִמְצָא.” (ספר שמואל א', פרק י', פסוקים כ'–כ"א)
• הפעלה פונקציה על אובייקט מספר פעמים בזו אחר זו. למשל, עבור הפונקציה ${\displaystyle f(x)=2x}$, ‏${\displaystyle f^{2}(x)=f(f(x))=2(2x)=2^{2}x=4x}$ ו־${\displaystyle f^{n}(x)=2\cdot \cdot \cdot 2\cdot 2x=2^{n}x}$, הן איטרציות של הפעלת הפונקציה ${\displaystyle f(x)}$ פעמיים או מספר מסוים של פעמים על אובייקט כלשהו.

גודל האיטרציה

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

מספר האיטרציות

מספר האיטרציות בתהליך מסוים יכול לנוע בין אפס לאינסוף. בדרך כלל מספר האיטרציות הוא פונקציה של הקלט לתוכנית או לאלגוריתם, ושל יעילות האלגוריתם. דוגמה: לחיפוש איבר מבוקש ברשימה ממוינת בת 1,024 איברים יידרשו לכל היותר 1,024 איטרציות (ובממוצע 512 איטרציות) כאשר החיפוש נעשה באמצעות סריקה סדרתית של הרשימה. אבל כאשר מבוצע חיפוש בינארי, שהוא יעיל יותר, יידרשו לכל היותר 10 איטרציות, משום ש- ${\displaystyle \ \log _{2}1024=10}$, או בניסוח אחר ${\displaystyle \ 1024=2^{10}}$.

שיקולי תכנות של איטרציה

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

מתכנתים מתייחסים ליעילות של איטרציה בהבטים אחדים:

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

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

ישנם מספר אמצעים, בעזרתם ניתן 'לשחרר' את המחשב:

1. מִקבול משימות התוכנית, באמצעות שימוש במספר תהליכונים (Threads).
2. קביעת עדיפות (Priority) נכונה עבור התהליכון המהווה 'צוואר בקבוק'.
3. תזמון הפעולה, המהווה 'צוואר בקבוק', לעיתוי נוח יותר. לפעמים מעבירים פעולות כאלו לשעת טעינת התוכנית.

אמצעים אחרים נועדו לשתף את המשתמש בידע על המתרחש:

1. הצגת הודעה מילולית המסבירה למשתמש את פשר העיכוב והמידעת אותו על המתרחש.
2. הצגת מד־התקדמות (Progress bar), בעזרתו יכול המשתמש לדעת בכל רגע כמה אחוזים מהתהליך כבר התבצעו.
3. הצגת סרטון וידאו המייצג את המתרחש.
4. שינוי צורת סמן העכבר לצורת שעון חול.

דרך השימוש באמצעים שהוזכרו שונה משפת מחשב אחת לשפת מחשב אחרת. מומלץ להשתמש בכמה מהאמצעים יחדיו.

מושגים קשורים

• משפטי איטרציה (Iteration statements) – כגון while ו־for, הם סוג של משפטי בקרה על זרימת תוכנית מחשב שמאפשרים חזרה על קוד. משפטי איטרציה נבדלים ממשפטי בחירה (Selection statements), כגון if ו־switch, שגם הם סוג של משפטי בקרה שמאפשרים לבצע קטעי קוד נבחרים.
• בקרת איטרציות (Iteration controls) – קובעת את מספר האיטרציות שיתקיימו.
• איטרטור – מחלקה המאפשרת מעבר באיטרציות במבנה נתונים כלשהו. בשפת ++C, איטרטורים הם חלק נכבד מהספרייה התקנית STL.
• מעבר על פני רשימה (Iterate over a list), שהיא סוג של מבנה נתונים.
• דילמת האסיר האיטרטיבית
• משחק החיים - משחק מסוג אוטומט תאי המשוחק באיטרציות.

קישורים חיצוניים

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: איטרציה
ערך מילוני בוויקימילון: חזרור