סריקת מידע בזיכרון

ד"ר שמואל אבן-זהר

מתוך מחשבים בחינוך מס' 38 - קיץ תשנ"ו


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

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

זמן-תגובה:
המדד המשותף הנפוץ לבדיקת יעילות מערכת כל שהיא הוא זמן תגובה 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.

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

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

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

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