איטרציה

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

תוכן עניינים 1 דוגמאות לאיטרציות 2 גודל האיטרציה 3 מספר האיטרציות 4 שיקולי תכנות של איטרציה 5 מושגים קשורים

[עריכה] דוגמאות לאיטרציות

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

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

[עריכה] גודל האיטרציה

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

[עריכה] מספר האיטרציות

מספר האיטרציות בתהליך מסוים יכול לנוע בין אפס לאינסוף. בדרך כלל מספר האיטרציות הוא פונקציה של הקלט לתוכנית או לאלגוריתם, ושל יעילות האלגוריתם. דוגמה: לחיפוש איבר מבוקש ברשימה ממוינת בת 1,024 איברים יידרשו לכל היותר 1,024 איטרציות (ובממוצע 512 איטרציות) כאשר החיפוש נעשה באמצעות סריקה סדרתית של הרשימה. אבל כאשר מבוצע חיפוש בינארי, שהוא יעיל יותר, יידרשו לכל היותר 10 איטרציות בלבד.

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

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

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

1. זמן קצר ככל האפשר לכל איטרציה. חיסכון של מעט זמן בכל איטרציה עשוי להסתכם בחיסכון של זמן רב מאוד, כאשר הוא מוכפל במספר האיטרציות.
2. הספק רב ככל האפשר בכל איטרציה בודדת, כך שמספר האיטרציות הכללי יפחת.
3. באיטרציות המשמשות תוכניות מחשב יש חשיבות לכך שכל איטרציה 'תתפוס' מינימום מזיכרון המחשב, מהסיבות הבאות:
   1. מניעת גלישת זיכרון.
   2. מניעת גלישת מחסנית (stack overflow), שעשויה להתרחש במקרה של שימוש ברקורסיה עמוקה מידי.
   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), שהיא סוג של מבנה נתונים.
• דילמת האסיר האיטרטיבית.