דרך ארץ. » אני רק כרטיסיה לבאר שבע; ראייה תרבותית של מבני נתונים

אני רק כרטיסיה לבאר שבע; ראייה תרבותית של מבני נתונים

26 11 2007

ובכן.

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

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

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

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



מצד שמאל נמצא העוגן, שמצביע תמיד אל האיבר הראשון ברשימה. כל תא מורכב משני חלקים: אחד הוא תוכן התא, והאחר הוא מצביע לתא הבא ברשימה. המצביע בתא האחרון הוא אפס (null), דהיינו, לא מצביע לתא תקני בזיכרון, וכל נסיון להשתמש בו עלול להוביל למלחמת עולם שלישית, או חלילה להשתמטות מצה"ל. הוצאת איברים מתבצעת מראש התור: מספר 1 יוצא מהתור, ואז העוגן מצביע למספר 2 הנוכחי, שהופך להיות הראשון. בדומה לכך, איברים חדשים נכנסים לסוף התור: אחרי השאלה "מי אחרון" יגלה האיבר החדש, מספר 7, שמדובר במספר 6, יכריז שהוא אחריו, וכך המצביע של מספר 6 יעבור להצביע על מספר 7, והמצביע של מספר 7 יצביע על האפס. (זכרו, כמובן, שמדובר רק בייצוג; הוא איננו מספר, הוא אדם חופשי.)

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

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



העוגן מצביע על האיבר הראשון בתור, וכל איבר מורכב מתוכן ומשני מצביעים, ימני ושמאלי. הוצאת איברים – כניסה לאוטובוס – מתבצעת מהתא הראשון, 1; ואז מתפנה המקום 1, ומי שזוכה בו הוא החזק מבין מספרי 2 ו־3; בה"כ מתפנה המקום 3, ומי שזוכה בו הוא החזק מבין מספרי 5 ו־6; וכן הלאה. כניסת איברים לתור היא במקום הריק הקדמי ביותר – אם, למשל, תפוסים רק תאים 1 ו־3, יעדיף איבר חדש להכנס לתא 2 ולא לתא 6 – ובמקרה שאיננו מוגדר היטב, למשל כזה שבו תאים 4 ו־5 פנויים, נראה לי להעדיף את התא הקרוב יותר למרכז השורה.

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

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


פעולות

מידע על הקטע



12 תגובות על הקטע ”אני רק כרטיסיה לבאר שבע; ראייה תרבותית של מבני נתונים“

26 11 2007
שגיאB(14:12:42) :

גדול, ולא בגלל השיר. :mrgreen:

28 11 2007
החתול של שרדינגר(09:28:58) :

מצוין!:).
תור עדיפויות זה השם העברי ל skip list? ורסיה מעט אלימה שלה בהחלט יכולה לשקף את התור הישראלי.

28 11 2007
אורי(11:52:29) :

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

28 11 2007
צביקה(21:15:26) :

מילא מבנה הנתונים הנודע "תור ישראלי" – תאר לך איזה פוסטים אפשר לכתוב על מבני הנתונים "מחסנית ישראלית" ו"מפה ישראלית"…

29 11 2007
יניב(05:21:04) :

די, תמשיכו. 8) החתול וגו': אני חושב שבגויית קוראים לזה priority queue. מהי skip list?
אורי: תעשיית ההזנק העברית למוד־תלמד לעמוד בתור לאוטובוס, אם אך תיושם רפורמת המיסוי. מה שכן, יהיה מעניין לראות תור לשטיפת מכוניות מתנהל בצורה דומה, ואולי זה אפילו יגרור נזק רב לכלי רכב כבדים, לשמחת כולנו.
צביקה: קדימה, כתוב! :)

5 12 2007
יואב(15:36:08) :

אני חושב שאפשר לקרוא למבנה הזה: "זינוק בעלייה" (ואולי להוסיף: בסוברו-פשע).

מעניין למדוד לחץ דם ממוצע ומספר אינטראקציות חברתיות לדקה בתור הישראלי מול הפיפו/פיפ"א האירופאי.

5 12 2007
יואב(15:39:19) :

אני חושב שאפשר לקרוא למבנה הזה זינוק בעלייה (ואולי להוסיף: בסוברו-פשע).
מעניין למדוד לחץ דם ממוצע ומספר אינטראקציות חברתיות לדקה בתור הישראלי מול הפיפו האירופאי.

5 12 2007
יניב(23:11:53) :

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

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

13 01 2008
דוברמן(19:45:15) :

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

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

13 01 2008
יניב(21:00:13) :

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

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

20 01 2008
ערן בילינסקי(23:57:42) :

Skip List זה מבנה מאוד דומה לעצי B (שמוכרים בדרך כלל יותר כ"עצי 2-3") שמאפשר פעולות רבות יחסית בסיבוכיות זמן לוגריתמית ובסיבוכיות מקום לינארית. ראה עוד בוויקיפדיה: http://en.wikipedia.org/wiki/Skip_list

ובכל מקרה, לשאלתו של החתול, התשובה היא "לא".

21 01 2008
יניב(00:35:58) :

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

השאר תגובה

באפשרותך להשתמש בתגים אלה :

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>