סריקת מידע בזיכרון
מחבר: ד"ר שמואל אבן-זהר
מחשבים בחינוך, גיליון 38, 1996
בעיות רבות בתחום של עיבוד מידע בזיכרון משותפים לאדם ולמחשב. הדבר אינו מפליא שכןלשתי המערכות הללו - מערכת המחשב ומערכת האדם תהליכים משותפים: שתי המערכות קולטותאינפורמציה ממקורות חיצוניים באמצעות "ציוד" המוקדש למטרה זו, האינפורמציה עוברתקידוד מצורתה החיצונית הפיזיקלית לקודים פנימיים של המערכת והיא מאוחסנת זמניתבזיכרון, נערך עיבוד כל-שהוא על הנתונים, ומופקת "תגובה" חיצונית, שנועדה לפתורבעיה כל-שהיא.
בחרתי להציג כאן בעיה ספציפית משותפת, המראה עד כמה שתימערכות השונות לחלוטין מבחינת החומרה - חומר מתכתי לעומת חומר אורגני, דומותפונקציונלית בתהליך פתרון בעיה.
זמן-תגובה:
המדד המשותף הנפוץ לבדיקת יעילותמערכת כל שהיא הוא זמן תגובה Reaction Time - RT)). זמן תגובה מוגדר כזמן העוברמרגע הצגת הגירוי או הנתונים לערוץ הקלט, ועד לגמר ביצוע התגובה על-ידי ערוץ הפלט. זמן תגובה משמש לבדיקת יעילות המערכת הן במערכת האנושית והן במערכת המחשב. אצל האדםמושפע זמן זה, כמובן, מטיב "החומרה" (מהירות ההולכה העצבית תלויה בין השארבמצב-בריאותי, גיל ועוד), אך מושפע גם מ"תוכניות" קבועות וזמניות הקיימות במערכת, כמו "עירות", "קשב" ו"מוטיבציה". זמן תגובה הוא מדד מורכב המייצג הבחנה, תהליךבחירה ותגובה. ואכן, רוב הניסויים הפסיכולוגיים בזמן תגובה בדקו אותו במצבי בחירה. בכל ניסיון ((TRIAL בודקים זמן תגובה בודדת להצגת תבנית גירוי יחידה, למשל, לחיצהעל מתג. הנבדק מקבל הוראות להגיב מהר ככל האפשר מיד עם הופעת הגירוי. כאמור, במדדהפיזיקלי הפשוט הזה, מעורבים פעולות רקע רבות (כמו קשב, מוטיבציה, תפיסה וכדומה). בהנחה של רציפות זמן תגובה, ניתן לחלקו לשלושה שלבים עיקריים:
1. זמן קידוד - הזמן העוברמרגע הצגת הגירוי ועד לקידודו הפנימי במוח - בזיכרון קצר-הטווח. במחשב זהו הזמן שלקריאת נתון ממקור חיצוני אל הזיכרון הפעיל.
2. זמן השוואה והחלטה - הזמןהעובר מרגע ייצוגו הפנימי של הגירוי במוח ועד להחלטה אם וכיצד להגיב. במחשב זהו זמןעיבוד הנתון, חישוב מסוים, השוואתו עם נתון אחר.
3. זמן ביצוע - הזמן העוברמרגע ההחלטה להגיב ועד לגמר ביצוע התגובה. במחשב זהו הזמן מגמר העיבוד ועד להצגתהתוצאה על המסך או הדפסתה.
במחשב, ישנן תוכניות שירות שונות הבודקות זמניתגובה של השלבים השונים. התפתחויות טכנולוגיות במחשב משמען (בין השאר) קיצור שלזמנים אלו. בדיקת יעילות המערכת פשוטה יותר מאשר אצל האדם, אך גם במחשב נעזריםבניתוחים סטטיסטיים. לדוגמה, מבוצעות 1000 קריאות וכתיבות למקומות אקראיים בדיסקהקשיח, ומחושבים ממוצע זמן הקריאה של הראש קורא-כותב, וסטיית-התקן.
לגביהאדם, ישנה בעיה למדוד תהליכים פנימיים אלו. ההפרדה בין מרכיבי זמן התגובה איננהמתקבלת ישירות בניסוי, ויש צורך בניסיונות רבים, ובתהליכי ניפוי וניתוח הנתונים.
ב. מדידת מרכיבי זמן-תגובה אנושי
כדי לבדוקאת יעילות מערכת הזיכרון במהלך מעבר המידע מהגירוי ועד התגובה, יש צורך לזהות אתמשך השלבים השונים. במצב של זמן תגובה פשוט (כאשר קיים גירוי אחד ותגובה אחתויחידה), זמן ההשוואה אינו קיים, למעשה, וזמן ההחלטה קצר ביותר. דוגמה מעשית: זמןהלחיצה על בלם המכונית מיד עם זיהוי
האובייקט בכביש.
במצב של זמן תגובהמורכב (כאשר קיימות מספר אלטרנטיבות של תגובות לכל גירוי), או במצב של זמן תגובהמסובך (כאשר קיימות כמה אלטרנטיבות של תגובות למספר אלטרנטיבות של גירויים), עלהנבדק לבחור בין מספר תגובות אפשריות, ולכן זמן ההשוואה וההחלטה גדל.
בהנחהשל רציפות השלבים ניתן למצוא את משך הזמן של שלב מסוים בשיטת ההחסרה, לדוגמה, אםנמצא שני תפקידים לביצוע של הנבדק, שאחד מהם אינו מכיל שלב מסוים, אזי על-ידי החסרהפשוטה ביניהם, ניתן למצוא את משך אותו שלב. כך למשל, זמן תגובה למצב מורכב (כאשרמספר פריטים מוצגים בזה אחר זה, ויש להחליט כיצד להגיב) פחות זמן תגובה למצב פשוט (כשפריט אחד מוצג - מגיבים מיד), מייצג את סך זמן הסריקה וההשוואה. אם נחלק זמן זהלמספר הפריטים המוצגים, נקבל את זמן הסריקה וההשוואה לפריט בודד.
שיטתהחסרה זו הוחלפה על ידי שיטות סטטיסטיות מתוחכמות, כמו רגרסיה, ניתוח סדרות עיתיותוטכניקות לא פרמטריות.
פרדיגמת ניסוי של שטרנברג (משנת 1969) המתוארת להלן, מאפשרת לבודד את מרכיבי זמן התגובה העיקריים - זמן השוואה, וזמן קידוד וביצוע, באמצעות ביצוע ניתוח רגרסיה על הנתונים.
סריקת מידע בזיכרון קצר הטווח
כמו במחשב שםקיימים מספר סוגי זיכרונות - זיכרון מטמון ראשוני CACHE) MEMORY), הזיכרון בפועל (RAM) של המחשב, שהוא זמני ומוגבל, וזיכרון חיצוני הקבוע לאורך זמן - אחסון בדיסק. גם אצל האדם קיימים מספר סוגי זיכרונות - הזיכרון המיידי (IMMEDIATE MEMORY) הנמשךשבריר שנייה, הזיכרון קצר- הטווח (SHORT TERM MEMORY), העכשוי, וזיכרון ארוךטווח(LONG TERM) MEMORY הנמשך למשך כל החיים. אתייחס כאן לזיכרון קצר הטווח בלבד.
הזיכרון קצר הטווח מוגבל למספר מועט של פריטים, והוא נמשך ממספר שניות ועדדקה או שתיים. לדוגמה - זמן זכירת מספר הטלפון של רופא השיניים (שאין כל-כךמוטיבציה לזוכרו באופן קבוע), הנמשך מזמן קריאתו מפנקס הטלפונים ועד לגמר החיוג.
ישנם מודלים אחדים לשאלה איך מתבצע אחזור המידע מהזיכרון קצר הטווח. אתייחסכאן למודל אחד בלבד - מודל החיפוש המקיף של שטרנברג. מודל זה מתאר תהליך המתרחשבמשך זמן התגובה מהגירוי ועד התגובה. לשיטתו, זמן התגובה מורכב מארבעה שלבים - קידוד הגירוי, השוואה סדרתית, החלטה בינרית, ותרגום התגובה וארגונה.
פרדיגמת ניסוי של שטרנברג מאפשרת לבודד את מרכיבי זמן התגובה - זמן הקידודוהביצוע, וזמן ההשוואה. לפי אחת השיטות מציגים לנבדק מספר מסוים של פריטים, בקצבקבוע, ולאחר הפסקה קצרה וסימן אזהרה מופיע פריט-מבחן. על הנבדק ללחוץ, מהר ככלהאפשר, על מתג אחד מבין שניים, לציון אם פריט המבחן הופיע בסדרה הקודמת, ועל המתגהשני - אם לא הופיע. שטרנברג מצא שזמן התגובה לפריט המבחן הוא פונקציה ליניארית שלמספר הפריטים בסדרה המופיעה קודם לכן.
הנוסחה המתארת פונקציה זו היא : , RT = a + bN
כאשר: RT - זמן תגובה לפריט המבחן
a - זמן קידוד וביצועהתגובה (נקודת החיתוך)
b - זמן השוואה לפריט (השיפוע)
N - מספר הפריטיםבסדרה
למעשה הנוסחה היא RT = a + bN + c
כאשר a מייצג את זמן הקידודבלבד
ו-c - את זמן הביצוע.
אולם מאחר ו-c הינו זמן קבוע (הנבדק התבקש תמידלהגיב מהר ככל האפשר, ולכן זהו הזמן השרירי המינימלי), ניתן להוסיפו ל-a ולהתעלםממנו.
מהנוסחה הליניארית ניתן להבין, שפריט המבחן עובר השוואה רציפה עםפריטי הסדרה. הללו מושווים בזה אחר זה, בסדר עולה או יורד, עד ההתאמה או אי-ההתאמהעם פריט המבחן, הגוררת החלטה כיצד להגיב, ולכן, זמן התגובה גדל באופן ליניארי ככלשהסדרה גדלה.
על-ידי הצגת סדרות רבות בגדלים שונים, ניתן למצוא את קוהרגרסיה ולבודד את המדדים a ו-a . b הוא נקודת החיתוך עם ציר ה-RT, והוא מייצג אתזמן התפיסה והקידוד פלוס זמן ההחלטה והביצוע (זמן הקלט והפלט), כלומר, זהו מצב של "גודל סדרה 0". הוא שונה מחוש לחוש, אך קבוע בתוך כל חוש ולכל סוג פריט. bN - הואסך כל זמן ההשוואה (העיבוד המרכזי), והוא תלוי, אם כן, בגודל הסדרה - b . N הואשיפוע הקו, והוא מייצג את התוספת הקבועה לזמן התגובה עם כל גידול נוסף בפריטיהסדרה. ישנם משתנים שונים המשפיעים על נקודת החיתוך והשיפוע, ולא כאן המקום לפרטם.
סדרה חיובית ושלילית
הסדרות נקראות: סדרהחיובית (Positive Set - Ps) כשפריט המבחן היה בסדרה המוקדמת, וסדרה שלילית (Negative Set- NS), כשפריט המבחן לא היה בה.
שטרנברג מצא בניסויים רביםשערך ממצא מדהים: אין הבדל מובהק בזמן התגובה הממוצע בין סדרות חיוביות ובין סדרותשליליות! ומדוע, הרי כשהסדרה חיובית צריך להפסיק את הסריקה מיד עם מציאת הפריטהזהה? המסקנה היא שבכל מקרה, גם בסדרות חיוביות הסריקה היא מקיפה (עד גמר הסדרה). דבר זה מעורר את השאלה, מדוע? הנבדק התבקש להגיב "מהר ככל האפשר", ואם הסריקהממשיכה, הרי המערכת לא עובדת בצורה יעילה?
מסתבר שבמערכות מסוימות לעתיםיעיל יותר להמשיך ולסרוק את הסדרה גם לאחר ההתאמה, ורק אז להחליט על התגובההמתאימה.
נתאר לעצמנו מערכת בה תהליך הסריקה מורכב משתי פעולות:
א.השוואה בין פריט הסדרה ובין פריט המבחן.
ב.החלטהאם היתה התאמה או לא.
אם פעולתההחלטה נמשכת זמן מסוים בנוסף לזמן ההשוואה, אזי אם החיפוש נפסק מיד עם ההתאמה, הרילאחר כל פעולת השוואה צריכה להיות פעולת החלטה אשר קובעת אם להמשיך את הסריקה אולהפסיקה, שהרי מראש לא ידוע באיזה פריט תהיה ההתאמה, אם בכלל. כלומר, קיימות מספרהחלטות כמספר הפריטים המושווים. לפי תיאורית החיפוש המקיף אין צורך בהחלטה מיידיתלאחר כל פעולת השוואה, שהרי הסריקה ממשיכה בכל מקרה. פעולת ההחלטה קימת רק פעם אחת - בגמר הסריקה, בהתאם למידע אם היתה התאמה באיזה שהוא שלב בסריקה או לא. לפיכךמערכת של השוואה מקיפה חסכונית ממערכת של הפסקת הסריקה, בעיקר כשזמן ההחלטה ארוךיחסית לזמן ההשוואה.
השוואה לסריקת מחשב
מודל זה תואם שיטות חיפושממוחשבות אחדות, בעיקר בסדרות קצרות: נניח שקיים מערך חד ממדי בן 7 איברים המכילמספרים, ועלינו למצוא אם המספר 3 נמצא ביניהם. תוכנית המחשב מכילה לולאה המתבצעת 7פעמים. בכל פעם נסרק איבר אחר של המערך ומושווה אל הספרה 3, ואם התגובה חיובית, משתנה S מקבל ערך "כן". בתוך הלולאה ישנה פקודה נוספת האומרת: אם ערך S הוא "כן" הפסק סריקה, צא מהלולאה החוצה והדפס את ערך S - "כן".
נניח, שסריקת כל איברבלולאה נמשך 10 מיליוניות השנייה, וגם הבדיקה אם ערך S הוא "כן", נמשך זמן זהה - סך-הכול 20 מיליוניות השנייה לכל "סיבוב" בלולאה. אם הספרה 3 אכן הייתה בלולאה, (סדרה חיובית - PS) ומיקומה הוא אקראי, בממוצע היא נמצאת במקום האמצעי - הרביעי זמןהסריקה הממוצע אם כן הוא (20*4) 80 מיליוניות השנייה. במקרה והספרה לא היתה ביןאיברי הסדרה (סדרה שלילית-NS), הלולאה תבוצע עד תומה, ותימשך לכן (20*7) 140מיליוניות השנייה. אם נניח שההסתברות להמצאות או אי-המצאות הספרה 3 בסדרה הוא 50%, ממוצע זמן החיפוש בתוכנית כזו הוא 110 מיליוניות השנייה.
נבדוק אלגוריתםאחר לביצוע חיפוש כזה: הבדיקה אם ערך S הוא "כן" לא נעשית בתוך "הלולאה", אלא מחוץהלולאה, בתום סריקת כל 7 האיברים. סך זמן הסריקה בלולאה נמשך 70 מיליוניות השנייה, והבדיקה אם ערך S הוא "כן" נעשית רק פעם אחת בתום הלולאה ותימשך 10 מיליוניותהשנייה. במצב זה תתבצע תמיד סריקה מלאה, אך היא תימשך 80 מיליוניות השנייה בלבד. תכנית זו אם כן, יעילה יותר מקודמתה!
ניתוח המצבים של סוגי הסדרות
אם N - גודלהסדרה (מספר הפריטים),
K - זמן השוואה לפריט (והצבת ערך "כן")
L - זמןבדיקה אם היתה התאמה
אזי זמן הסריקה לסדרה חיובית הוא: (PS=N(K+L
וזמןהסריקה לסדרה שלילית הוא כמחציתו: (NS=N/2(K+L
בהנחת הסתברות של 50% להופעתסדרה חיובית או שלילית, נוסחת זמן הסריקה
לפי השיטה הראשונה הנ"ל היא בקירוב:
(N(K+L)+N/2(K+L
------------------------
2
וזמן הסריקה לפי השיטה השנייה הוא: NK+L
אם נניח שקיים שוויוןבין זמן השוואה וזמן בדיקה, כלומר, K=L
(מה שסביר בהחלט), אזי אם נפתח את שתיהנוסחאות הנ"ל בהנחה של שוויון ביניהם (או שזמן התגובה לפי הנוסחה הראשונה גדולמאשר לפי הנוסחה השנייה), נקבל:
(N(K+L)+N/2(K+L) = > 2(NK+L
N(K+L) = > 2NK+2L3/2
NK+ 3/2 NL = > 2NK+2L3/2
NL = > 1/2 NK+2L3/2
ואם K=L נחלק בהם את המשוואה ונקבל: 3/2 N = > 1/2 N+2
N = > 2
כלומר, במצב של שוויון בין זמן ההשוואה וזמן הבדיקה, החל מגודל סדרה בתלמעלה משני פריטים, עדיפה הנוסחה הראשונה, והיא נותנת זמן תגובה קצר יותר.
אם נציב ערכי N שונים במשוואה הראשונה הנ"ל (בלי הנחה של שוויון בין K ל-L) ונפתח את המשוואה, נראה שהיחס בין L ל-K הולך ומתקרב ל-1/3
כלומר:
אם N=2 אזי L >=K, יחס של 100%,
אם N=3 אזי L >=3/5 K, יחס של 60%,
אם N=4 אזי L >=2/4 K, יחס של 50%,
אם N=5 אזי L >=5/11 K, יחס של 45.45%,
אם N=6 אזי L >=3/7 K, יחס של 42.86%,
אם N=7 אזי L >=7/17 K, יחס של 41.18%,
אם N=8 אזי L >=4/10 K, יחס של 40%,
אם N=9 אזי L >=9/23 K, יחס של 39.13%,
אם N=10 אזי L >=5/13 K, יחס של 38.46%,
אם N=20 אזי L >=10/28 K, יחס של 35.71%,
אם N=100 אזי L >=50/148 K, יחס של 33.7%8.
המשמעות היא, שככל שהסדרה גדלה, אפילו אם זמן הבדיקה מגיע רק לשליש מזמןההשוואה, עדיין עדיפה שיטת הסריקה המלאה על-פני הסריקה החלקית.
סוף דבר
בניסויים נוספים וממושכים שנערכולגבי סריקת מידע בזיכרון האנושי לא תמיד נמצאה תמיכה ברעיון הסריקה המקיפה כפתרוןחסכוני. מסתבר שהדבר נכון בסדרות קצרות ולפריטים פשוטים, כמו סדרת אותיות, ואזאסטרטגית הנבדק היא לסרוק בכל מקרה עד תום הסדרה, ורק אז להגיב. בסדרות ארוכותיותר, ובגירויים מורכבים, אין הסריקה מקיפה את כל הסדרה אלא מסתיימת עם מציאת פריטהמבחן, ולכן זמן התגובה קצר יותר בסדרות חיוביות מאשר בסדרות שליליות. אולם, ככלשהסדרות ארוכות יותר, כבר לא מדובר בזיכרון קצר הטווח, אלא בזיכרון ארוך הטווח, ואזאין מבנה הנתונים סדרתי, אלא מבנה אחר, היררכי או אסוציאטיבי, ושיטת אחזור המידעשונה לחלוטין. לדוגמה, כשפוגשים חבר מוכר ברחוב, לא סורקים בזיכרון את כל החבריםהידועים לפי סדר מסוים עד לזיהוי, אלא הזיהוי הוא מיידי. תהליך אחזור המידע דומהיותר לניפוי וסריקה של רשת מידע, או בגישה ישירה כמו בבסיסי נתונים.
ובסריקת זיכרון במחשב? החישוב של האלגוריתם הנ"ל נכון לכל גודל סדרה, אלאשגם במחשב, בסדרות ארוכות אין אחסון המידע הסדרתי חסכוני במיוחד. מבנה בסיס הנתוניםהחסכוני יותר הוא טבלאי, או רשת של צמתים וקשרים ביניהם, והגישה היא ישירה לפיאינדקסים. לעולם לא היו מצליחים לבצע שליפה מהירה מבסיס נתונים טכסטואלי אפילו בסדרגודל של התנ"ך, ללא אחסון הנתונים במבנה מיוחד, לא סדרתי, אלא טבלאי.
ישנםכמובן מודלים שונים משל שטרנברג, לחיפוש מידע בזיכרון קצר הטווח (מודלים של עוצמתזיכרון קבועה, סריקה לא ליניארית, הפסקת הסריקה מיד עם ההתאמה, השוואות מקבילותועוד), אולם התיאוריה הפשוטה והחסכונית עדיפה תמיד, בעיקר אם היא מנבאת ממצאיםניסויים רבים, ובעיקר כשהיא מקבלת תימוכין ממערכת אחרת הדומה לה פונקציונלית, מערכתהמחשב.