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

קהל: אנחנו יכולים באופן דינמי לשנות את גודלו. 

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

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

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

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

קהל: זה עושה את זה לעבור אחד. 

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

אני הולך קדימה ו להצהיר על משתנה זמני ש באמנה היא רק הולך להיקרא מצביע, או PTR, אבל אתה יכול לקרוא לזה מה שאתה רוצה. ואני הולך לאתחל זה לתחילת הרשימה. אז אתה סוג של יכול לחשוב על זה כ מורה היום האחר, סוג של מצביע על מישהו בקרב בני האדם כמתנדבים. אז אני משתנה זמני זה רק מצביע על אותו הדבר ש בשם במקרה מתנדב דוד גם היה מצביע. עכשיו בזמן שמצביע הוא לא ריק, כי כזכור null שהוא ערך כלשהו זקיף מיוחד תוחם את סוף הרשימה, אז בזמן שאני לא מצביע ב קרקע כמו מתנדב האחרון שלנו היה, בואו נלך קדימה ולבצע את הפעולות הבאות. אם pointer-- ועכשיו אני סוג של הרצון לעשות את מה שעשינו עם התלמיד structure-- אם נקודת המצביע הבאה equals-- ולא, אם נקודת מצביע N שווה שווה N משתנה, טיעון שכבר עבר ב, אז אני רוצה ללכת קדימה ואומרים לחזור אמיתי. מצאתי N המספר פנימי של אחד הצמתים של הרשימה המקושרת שלי. אבל הנקודה כבר לא עובד בהקשר זה, כי מצביע, PTR, הוא אכן מצביע, כתובת, אנחנו באמת יכולים להפליא להשתמש סוף סוף פיסת התחביר זה סוג של גורם תחושה אינטואיטיבית ולמעשה להשתמש חץ כאן, מה שאומר שהולכים מ שכתובת למספר השלם יש ב. אז זה דומה מאוד ב רוח למפעיל הנקודה, אלא משום שהמצביע אינו מצביע ולא struct בפועל עצמו, אנחנו פשוט להשתמש בחץ. 

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

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

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

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

אז אם אני רוצה לדחוף משהו על הערימה, מניח שאני מכנה את דחיפת הפונקציה, ו אני אומר לדחוף 50, כמו המספר 50, איפה אתה מציע אני מצייר אותו במערך הזה? יש חמש תשובות אפשריות שונות. איפה אתה רוצה לדחוף את המספר 50? אם המטרה כאן, שוב, קוראים דחיפת פונקציה, לעבור בטענה של 50, שבו אין אני שם את זה? חמישה סיכוי של 20% possible-- ניחוש נכון. כן? 

קהל: ימין קיצוני. 

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

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

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

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

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

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

אז עכשיו יש לנו את היכולת בקוד. אם כי, זה הולך לקחת אותנו יותר זמן לכתוב את זה, אנחנו יכולים עכשיו להקצות מחדש זיכרון שעל ידי רק אחסון כתובת אחרת יש אם אנחנו רוצים יותר גדולים או אפילו נתח קטן יותר של זיכרון. אז הנה ממסחר. עכשיו אנחנו מקבלים דינמיות. עדיין יש לנו contiguousness אני טוען. בגלל malloc ייתן לנו נתח רציף של זיכרון. אבל זה הולך להיות כאב ב צווארנו, מתכנת, למעשה קוד למעלה. זה פשוט יותר עבודה. אנחנו צריכים קוד דומה למה שהייתי דופק את רק לפני רגע. מאוד אפשרי, אבל זה מוסיף מורכבות. וכך זמן מפתח, מתכנת זמן הוא משאב אחר עדיין שאולי אנחנו צריכים להשקיע קצת זמן כדי לקבל תכונות חדשות. ואז כמובן יש תור. אנחנו לא נכנסנו לזה אחד בפירוט רב. אבל זה דומה מאוד ברוחו. אני יכול ליישם תור, ו הפעילות המקבילה שלה, Enqueue או dequeue, כמו להוסיף או להסיר, זה רק דרך מהודרת לומר את זה, Enqueue או dequeue, כדלקמן. אני יכול רק לתת לעצמי struct יש מערך של מספר ששוב, יש ששוב גודל, אבל למה לעשות עכשיו אני צריך כדי לעקוב אחר מול תור? אני לא צריך לדעת מול הערימה שלי. ובכן, אם אני שוב ל queue-- בואו פשוט קשה קוד זה כבעל כמו חמש מספרים שלמים בכאן פוטנציאל. אז זה הוא אפס, אחת, שתיים, שלוש, ארבעה. זה הולך להיות מספרים התקשרו שוב. וזה ייקרא גודל. 

למה זה לא מספיק יש רק גודל? ובכן, בואו לדחוף אותם מספרים ב. אז אני pushed-- אני בעלות מוצבת בתור, או דחפתי. עכשיו אני Enqueue 50, ולאחר מכן 51, ולאחר מכן 61, ושלוש נקודות. אז זה Enqueue. אני בעלות מוצבות בתור 50, אז 51, אז 61. וזה נראה זהה לערימה עד כה, מלבד אני צריך לעשות שינוי אחד. אני צריך לעדכן את הגודל הזה, אז אני הולך מאפס לאחד, ל02:58 עכשיו. איך אני dequeue? מה קורה עם dequeue? מי צריך לבוא מרשימה זו ראשונה אם זה בתור בחנות אפל? אז 50. אז זה סוג של יותר מסובך הפעם. ואילו בפעם האחרונה זה היה סופר קל רק כדי לעשות מינוס גודל אחד, אני מגיע לסוף המערך שלי ביעילות שבו המספרים, הוא מסיר 61. אבל אני לא רוצה להסיר 61. אני רוצה לקחת את 50, ש היה שם שעה 5:00 בבוקר בשורה ל iPhone או מה שלא חדשים. וכך להיפטר של 50, אני לא יכול פשוט לעשות את זה, נכון? אני יכול לעבור את 50. אבל אנחנו פשוט אמרתי שאנחנו לא צריך להיות כל כך אנאלי כלגרד החוצה או להסתיר את הנתונים. אנחנו יכולים פשוט לשכוח איפה זה. 

אבל אם אני משנה את הגודל שלי עכשיו ל שני, הוא מספיק מידע זה לדעת מה קורה בתור שלי? לא באמת. כמו הגודל שלי הוא שתיים, אבל שבו התור אינו מתחיל, במיוחד אם עדיין יש לי אותם מספרים בזיכרון. 50, 51, 61. אז אני צריך לזכור עכשיו איפה החזית. וכך כפי שהצעתי עד שם, אנחנו פשוט נקראים מול המי יודע כמה, שראשוני ערך צריך להיות מה? אפס, רק ההתחלה של הרשימה. אבל עכשיו, בנוסף לdecrementing הגודל, אנחנו פשוט להגדיל את החזית. עכשיו הנה בעיה נוספת. אז ברגע שאני כל הזמן הולך. מניח שזה הוא מספר כמו 121, 124, ולאחר מכן, לכל הרוחות, אני מתוך שטח. אבל חכה רגע, אני לא. כך שבנקודה זו של הסיפור, נניח שהגודל הוא אחד, שתי, שלוש, ארבעה, כך מניח ש גודל הוא ארבעה, החזית היא אחד, כך 51 הוא בחזית. אני רוצה לשים את מספר אחר כאן, אבל, לעזאזל, אני לא בשטח. אבל אני לא ממש, נכון? איפה אני יכול לשים כמה ערך נוסף, כמו 171? רק כן, אני יכול סוג של לחזור לשם, נכון? ואז לחצות את 50, או רק להחליף אותו עם 171. ואם אתם תוהים למה המספרים שלנו יש כל כך אקראיים, אלה נלקחים מחשב נפוץ קורסי מדע באוניברסיטת הרווארד לאחר CS50. אבל זה היה אופטימיזציה טובה, כי עכשיו אני לא מבזבז שטח. אני עדיין צריך לזכור כמה גדול הדבר הזה הוא מוחלט. זה חמש כולל. כי אני לא רוצה תתחיל להחליף 51. אז עכשיו אני עדיין מחוץ למרחב, כך את אותה הבעיה כמו קודם. אבל אתה יכול לראות איך עכשיו בקוד שלך, אתה כנראה צריך לכתוב קצת יותר מורכבות כדי שזה יקרה. ולמעשה, מה שמפעיל בC כנראה מאפשר לי אתה קסם לעשות את זה מעגלי? כן מפעיל מודולו, אחוזים הסימן. אז מה סוג של מגניב על תור, למרות שאנחנו ממשיכים מערכי ציור כקווים ישרים כמו אלה, אם אתה סוג של לחשוב על זה כמתעקל סביב כעיגול, ואז פשוט באופן אינטואיטיבי אותו סוג של עובד נפשי אני חושב שקצת יותר נקי. אתה עדיין תצטרך ליישם שמודל המנטלי בקוד. אז לא כל כך קשה, סופו של דבר, ליישום, אבל אנחנו עדיין מאבדים size-- ולא, היכולת לשנות את הגודל, אלא אם כן אנחנו עושים את זה. 

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

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

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

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

ואז הוא אמר, עכשיו ג'ק, בסוף היום, לשים את הבגדים שלך בצד השמאל כאשר אתה שם אותם משם. אז מחר בבוקר כשאתה לראות את אור השמש, את הבגדים שלך מימין, מסוף השורה. אתה לא רואה? אמר לו. זה יהיה כל כך נחמד. אתה לובש כל מה שפעם לפני שאתה לובש משהו פעמיים. ועם כל דבר בתורים בארון והמדף שלו, ג'ק התחיל להרגיש די בטוח בעצמו. הכל בזכות לו ו תורו הנפלא. 1 SPEAKER: בסדר, זה מקסים. אז מה באמת כבר הולך במתחת למכסת המנוע עכשיו? שיש לנו עצות, שיש לנו malloc, שיש לנו את היכולת ליצור נתחי זיכרון לעצמנו באופן דינמי. אז זה אנחנו תמונה ראיתי רק לפני כמה הימים. אנחנו לא באמת להתעכב על זה, אבל התמונה הזאת כבר קורה מתחת מכסה המנוע לשבועות. וכך זה מייצג, רק מלבן שאנחנו כבר נמשכים, הזיכרון של המחשב שלך. ואולי המחשב שלך, או CS50 זיהוי, יש ג'יגה זיכרון או זיכרון RAM או שתי ג'יגה-בייט או ארבעה. זה לא משנה באמת. מערכת ההפעלה שלך Windows או Mac OS או לינוקס, בעצם מאפשר התכנית שלך לחשוב שיש לו גישה למכלול הזיכרון של המחשב שלך, למרות שאתה יכול להיות ריצה תוכניות מרובות בבת אחת. אז במציאות, שלא ממש עובד. אבל זה סוג של אשליה נתתי לכל התוכניות שלך. אז אם היה לך שתי הופעות של זיכרון RAM, זה איך ייתכן שהמחשב חושב על זה. 

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

וזוכר עכשיו שזה חשוב. כי אם יש לנו משהו כמו החלפה ושני משתנים מקומיים כמו A ו- B ו אנחנו משנים את הערכים האלה מאחד ושתי לשתיים ואחד, כזכור כי כאשר החלפה חוזרת, זה כאילו פרוסה זה זיכרון הוא פשוט נעלם. במציאות, זה עדיין בחינה משפטית יש. ומשהו עדיין ממש שם. אבל מבחינה רעיונית, זה כ למרות שהוא נעלם לחלוטין. וכך עיקרי אינו יודע את כל העבודה שנעשה שבפונקצית swap, אלא אם כן זה ממש עבר באלה טיעונים על ידי מצביע או על ידי התייחסות. עכשיו, הפתרון היסודי לבעיה שעם החלפה עובר דברים בכתובת. אבל מתברר, גם, מה נמשך מעל כי חלק של המלבן כל הזמן הזה הוא עדיין יש יותר זיכרון עד לשם. וכאשר אתה באופן דינמי להקצות זיכרון, בין אם זה בתוך GetString, ש אנחנו כבר עושים בשבילך בCS50 ספרייה, או אם אתם קורא malloc ולשאול מערכת ההפעלה לנתח של זיכרון, זה לא בא מהערימה. זה בא ממקום אחר בזיכרון של המחשב שלך זה נקרא הגל. וזה לא שונה. זה אותו זיכרון RAM. זה אותו הזיכרון. זה רק זיכרון RAM זה עד שם במקום כאן למטה. 

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

ומתברר שהבחור רע, אנשים ש טובים במיוחד עם תכנות, ומנסה לפרוץ למחשבים, יכול לנצל את המציאות הזאת. למעשה, הבה נבחן קטע קטן. אז זו דוגמא שאתה יכול לקרוא על בפירוט רב יותר בויקיפדיה. אנחנו נצביע עליך מאמר אם סקרן. אבל יש התקפה בדרך ידוע כהצפת מאגר ש קיים כל עוד בני אדם יש לי היכולת לתפעל הזיכרון של המחשב, במיוחד בג אז זה הוא תכנית מאוד שרירותית, אבל בואו לקרוא אותו מלמטה למעלה. ראשי לכוכב char argc argv. אז מדוברים בתכנית שלוקחת שורת פקודת טיעונים. וכל זה, ככל הנראה, היא עיקרי שיחה פונקציה, קוראת לזה F לפשטות. והוא עובר במה? Argv של אחד. אז הוא עובר לF מה המילה היא שהמשתמש הקליד בשורת אחרי שמו של תכנית בכל. כל כך הרבה כמו קיסר או Vigenere, ש אולי אתה זוכר עושה עם argv. 

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

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

ואז מה היא תכנית זו הולך לעשות הוא פשוט עיוור להעתיק דבר אחד למשנהו. ולכן אם אנו מפנים את זה כתמונה, הנה רק רסיס של מרחב הזיכרון. אז שמנו לב בתחתית, אנחנו יש בר משתנה המקומי. כך שהמצביע שהולך store-- ולא שהטיעון מקומי זה הולך לחנות בר המחרוזת. ואז שם לב רק מעליה בערימה, כי בכל פעם שאתה שואל לזיכרון במחסנית, זה הולך קצת מעליו ציורי, הודעה שיש לנו 12 בתים שם. שמאל אחד העליון היא תושבת C אפס ו את האדם הנכון התחתון הוא תושבת C 11. זה בדיוק איך המחשבים הולך להוציא אותו. אז רק באופן אינטואיטיבי, אם בר יש יותר מ -12 תווים בסך הכל, כוללים הקו הנטוי אפס, שבו הוא 12 או את תושבת C 12 הולכים? או לייתר דיוק שבו הוא ה -12 אופי או הדמות -13, האופי מאית הולך בסופו של בתמונה? מעל או מתחת? 

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

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

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

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

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

אז זה סתם חבורה של מילות והגדרות למשהו שנקרא עץ במחשב מדע, כמו עץ ​​משפחה. אבל יש גלגולים להשתכלל עצים, שאחד מהם נקרא עץ חיפוש בינארי. ואתה יכול סוג של להקניט מלבד מה שעושה את הדבר הזה. ובכן, זה בינארי באיזה מובן? איפה ינארי מגיע מכאן? מצטער? זה לא כל כך הרבה או או. זה יותר שכל אחד מהצמתים אין יותר משני ילדים, כפי שאנו רואים כאן. באופן כללי, וtree-- ההורים והסבים שלך יכול להיות כמה שיותר ילדים או נכדים כפי שהם באמת רוצים, וכך למשל יש לנו שלוש ילדים שמיד ימין הצומת, אבל בעץ בינארי, יש צומת אפס, אחד, או שני ילדים מקסימאלי. וזה נכס נחמד, כי אם זה כתרים על ידי שתי, אנחנו הולכים להיות מסוגלים לקבל בסיס יומן קטן שני פעולה קורה כאן סופו של דבר. אז יש לנו משהו לוגריתמית. אבל עוד על כך ברגע. עץ חיפוש משמעות הדבר היא כי המספרים מסודר כך שהילד השמאלי של הערך גדול מהשורש. והילד שלה הנכון הוא גדול יותר מהשורש. במילים אחרות, אם אתה לוקח את כל צמתים, חוגים בתמונה הזאת, ומסתכל על השמאל שלה ילד והילד שלה תקין, הראשון צריך להיות פחות מ, השני צריכים להיות גדול מ. אז שפיות לבדוק 55. זה שנשאר ילד הוא 33. זה פחות מ. 55, הילד שלה תקין הוא 77. זה גדול יותר מ. וזה הגדרה רקורסיבית. אנחנו יכולים לבדוק כל אחד מאותם בלוטות ואת אותו הדפוס יחזיק. 

אז מה נחמד ב עץ החיפוש בינארי, הוא כי אחד, אנחנו יכולים ליישם את זה עם struct, בדיוק כמו זה. ואף על פי שאנחנו זורקים הרבה מבנים בך, הם במידה מסוימת אינטואיטיבי עכשיו בתקווה. התחביר הוא עדיין מסתורי בודאות, אבל התוכן של צומת בזה context-- ואנחנו שומרים שימוש במילה צומת, בין אם זה מלבן על המסך או מעגל, זה רק חלק מיכל גנריות, במקרה זה של עץ, כמו אחד ראינו, אנחנו צריכים שלמים בכל אחד מהצמתים ואז אני צריך הצבעה שני מצביעים לילד השמאלי והילד תקין, בהתאמה. אז זה כיצד תוכל ליישם את זה בstruct. ואיך אני יכול ליישם את זה בקוד? ובכן, בואו ניקח מהיר תתבונן בדוגמה קטנה זו. זה לא פונקציונלי, אבל יש לי להעתיק ולהדביק מבנה ש. ואם הפונקציה שלי לינארי עץ חיפוש נקרא חיפוש, וזה לוקח שני טיעונים, N מספר שלם ומצביע לצומת, ולכן מצביע לעץ או מצביע לשורש של עץ, איך אני הולך על חיפוש עבור N? ובכן, ראשית, כי אני התמודדות עם מצביעים, אני הולך לעשות בדיקת שפיות. אם שווים עץ שווים null, הוא N בעץ הזה או לא בעץ הזה? זה לא יכול להיות, נכון? אם אני האחרון null, אין שם כלום. אני יכול גם פשוט עיוור אומרים לחזור שווא. אם אתה נותן לי שום דבר, אני לא יכול ללא ספק למצוא כל מספר נ 'אז מה עוד יכול אני בדוק עכשיו? אני הולך לומר גם אחר, אם N הוא פחות מכל מה שהוא בצומת העץ כי אני כבר מסרתי ערך N. במילים אחרות, אם אני המספר מחפש, N, הוא פחות מהצומת שאני מסתכל. והצומת אני מחפש בנקרא עץ, וזוכר מהדוגמא הקודמת כדי להגיע לערך במצביע, אני משתמש בסימון החץ. אז אם N הוא פחות מחץ עץ N, אני רוצה ללכת שמאל מושגית. איך אני מביע גששתי ימינה? כדי להיות ברור, אם זה התמונה בשאלה, וכבר עבר לי כי עליון חץ שמצביע למטה. זה מצביע העץ שלי. אני מצביע על השורש של העץ. ואני מחפש למשל, ל המספר 44, באופן שרירותי. האם 44 פחות או יותר מ -55 ברור? אז זה פחות מ. וכך זה אם המצב חל. אז מבחינה רעיונית, מה אני רוצה חיפוש הבא אם אני מחפש 44? כן? 

בדיוק, אני רוצה לחפש את הילד השמאלי, או תת-העץ השמאלי של תמונה זו. ולמעשה, תן לי דרך התמונה כאן למטה רק לרגע, שכן אני לא יכול לגרד את זה. אם אני אתחיל כאן בגיל 55, ו אני יודע שהערך 44 אני מחפש ל השמאל, שזה סוג כמו קורע את ספר טלפונים ב מחצית או קורע את העץ במחצית. אני כבר לא צריך לדאוג מחצית שלמה זה של העץ. ובכל זאת, בסקרנות במונחים של מבנה, הדבר הזה כאן ש מתחיל עם 33, שעצמו הוא עץ חיפוש בינארי. אמרתי את המילה רקורסיבית לפני כי אכן זה הוא מבנה נתונים ש על פי הגדרה הוא רקורסיבית. אולי יש לך עץ זה זה גדול, אבל כל אחד מילדיה מייצג עץ רק קצת יותר קטן. במקום שזה יהיה סבא או סבתא, עכשיו זה רק אמא or-- אני לא יכול say-- לא אמא או אבא, זה יהיה מוזר. במקום שני הילדים יש היה כמו אחות ואח להיות. דור חדש של עץ המשפחה. אבל מבחינה מבנית, זה אותו הרעיון. ומתברר שיש לי פונקציה עם שאני יכול לחפש בחיפוש בינארי עץ. זה נקרא חיפוש. אני מחפש את N בשמאל חץ עץ אחר אם N הוא גדול מהערך כי אני כרגע ב. 55 בסיפור לפני רגע. יש לי פונקציה שנקראת חיפוש שאני רק יכול לעבור N זה ואופן רקורסיבי חיפוש תת-העץ ורק תמורה מה תשובה ש. אחר יש לי כמה מקרה בסיס סופי כאן. 

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

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

יש חוסר יעילות כזו כאן. איך היית באופן אינטואיטיבי לדחוס את הדגל הגרמני אם יישומו כקובץ? כמו איזה מידע יכול שלא מפריע אחסון בדיסק כדי כדי להקטין את גודל הקובץ שלנו כמ מגה לקילובייט, משהו קטן יותר? היכן טמונה היתירות כאן צריך להיות ברור? מה אתה יכול לעשות? כן? בדיוק. למה לא ולא זוכר הצבע של כל פיקסל לעזאזל בדיוק כמו שאתה עושה בPSET4 עם פורמט קובץ מפת הסיביות, למה אתה לא רק מייצג את העמודה השמאלית ביותר של פיקסלים, למשל חבורה של פיקסלים שחורים, חבורה של אדום, וחבורה של צהוב, ואז פשוט איכשהו לקודד רעיון של חזרה 100 פעמים או לחזור על 1,000 פעמים זה? איפה 100 או 1,000 הוא רק מספר שלם, כך ש יכול לברוח עם רק מספר בודד במקום מאות או אלפים פיקסלים של נוספים. ואכן, זה איך אנחנו יכול לדחוס את הדגל הגרמני. ו עכשיו מה לגבי הדגל הצרפתי? וקצת סוג של תרגיל מחשבי, שדגל יכול להיות דחוס יותר בדיסק? הדגל הגרמני או צרפתית דגל, אם תיקח גישה ש? הדגל הגרמני, משום שיש יתירות אופקית יותר. ועל ידי עיצוב, קובץ גרפי רב פורמטים אכן עובדים קווי סריקה כ אופקי. הם יכולים לעבוד אנכי, אנושות רק לפני שנים החליטו שנוסיף ל בדרך כלל חושב על שורת דברים על ידי שורה במקום טור על ידי טור. אז אכן אם היית להסתכל על הקובץ גודל של דגל גרמני וצרפתית דגל, כל עוד ההחלטה היא אותו הדבר, באותו הרוחב וגובה, זה אחד כאן הולך להיות גדול יותר, כי אתה צריך לחזור על עצמך שלוש פעמים. אתה צריך לציין כחול, חזור את עצמך, לבן, לחזור על עצמך, אדום, לחזור על עצמך. אתה לא יכול פשוט ללכת כל בדרך לימין. וכמו בצד, לעשות לנקות את הדחיסה נמצא בכל מקום, אם אלה הם ארבע מסגרות מvideo-- אולי זוכר שסרט או וידאו הוא בדרך כלל כמו 29 או 30 פריימים לשניה. זה כמו ספר להעיף קטן שבו אתה רק לראות את התמונה, תמונה, תמונה, תמונה, תמונה רק סופר מהיר כל כך שזה נראה כמו השחקנים על המסך נעים. הנה דבורה ב העליון של זר פרחים. ואף על פי שזה יכול להיות סוג של קשה לראות במבט ראשון, הדבר היחיד שנע ב הסרט הזה הוא הדבורה. 

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

אבל איך אתה לדחוס טקסט? איך אתה הולך על דחיסת טקסט? ובכן, כל אחת מהדמויות ב ASCII הוא בית אחד, או שמונה סיביות. וזה סוג של מטומטם, נכון? מכיוון שאתה כנראה להקליד ו- E ואני וO וU הרבה לעתים קרובות יותר מאשר כמו W או Q או Z, בהתאם לשפה שבי אתה כותב בהחלט. ואז למה אנחנו משתמשים ב שמונה סיביות לכל אות, כולל לפחות אותיות פופולריות, נכון? למה לא להשתמש פחות סיביות ל מכתבי סופר הפופולריים, כמו E, הדברים שאתה מניח ראשון בגלגל המזל, ולהשתמש יותר ביטים ל האותיות פחות פופולריות? למה? כי אנחנו פשוט הולכים להשתמש בם בתדירות נמוכה יותר. 

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

אני? אני? או מה על-- או אני? אולי זה היה רק ​​שתי תקין של E? אז יש את הבעיה הזאת של decodability עם מורס קוד, לפיו, אלא אם כן אדם שולח לך הודעה עוצר למעשה, כך שאתה יכול למיין של לראות או לשמוע את הפערים בין אותיות, זה לא מספיק רק ל לשלוח זרם של אפסים ואחדים, או נקודות ומקפים, כי יש עמימות. E היא נקודה אחת, כך שאם אתה רואה שתי נקודות או לשמוע שתי נקודות, אולי זה שתי E של או אולי זה I. אחד אז אנחנו צריכים מערכת זה קצת יותר חכם מזה. שנות האפמן אז אדם בשם לפני באתי עם זה בדיוק. אז אנחנו פשוט הולכים לקחת מבט מהיר בכמה עצים רלוונטיים לזה. נניח שזה חלק הודעה טיפשית שאתה רוצה לשלוח, מורכב מרק A, B, של ד 'של C ו- E של, אבל יש הרבה יתירות כאן. זה לא אמור להיות באנגלית. זה לא מוצפן. זה פשוט טיפשי הודעה עם הרבה חזרות. אז אם אתה באמת לספור את כל של, B של, C של, D's, ו- E של, הנה התדירות. 20% מהאותיות של, 45% מהאותיות הם E של, ושלושה תדרים אחרים. ספרנו שם למעלה באופן ידני ורק עשיתי את החשבון. 

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

ששני צמתים אני משלב הבא? זה קצת מעורפל. אז יש כמה מקרי פינה ל לשקול, אלא כדי לשמור על דברים יפים, אני הולך לבחור 20% - עכשיו אני מתעלם הילדים. אני הולך לבחור 20% ו 15% ולצייר שני קצוות חדשים. ועכשיו ששני צמתים אני לוגי לשלב? להתעלם מכל הילדים, כל נכדים, רק להסתכל על השורשים עכשיו. ששני צמתים אני קושר יחד? נקודה שתיים ו0.35. אז תן לי לצייר שני קצוות חדשים. ואז יש לי רק אחד שמאלה. אז הנה עץ. וזה נמשך במכוון לחפש סוג של די, אבל שמתי לב שיש לי הקצוות גם כותרתו אפס ואחד. אז כל הקצוות השמאלי הוא אפס באופן שרירותי, אלא באופן עקבי. כל הקצוות ימני הם אלה. 

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

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

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

עכשיו הערימות גדלו, ש זה דבר עיצוב מכוון כאן. אבל מה עוד אני יכול לעשות? אז בעצם יש לנו כאן חבורה של ספרי בחינה בבית הספר ישנים. נניח שחבורה של שמות תלמידים על כאן. הנה טבלת חשיש גדולה יותר. במקום ארבעה דליים, יש לי, נניח 26. ואנחנו לא רוצים ללכת ללוות 26 דברים מ[ בחוץ? אננברג?], ולכן הנה חמש שמייצגים דרך ז 'ואם אני לראות תלמיד ששמו מתחיל ב, אני הולך לשים אותו או חידונה שם. אם מישהו מתחיל עם C, שם, זה-- למעשה, לא רוצה לעשות את זה. B הולך כאן. אז יש לי A ו- B ו- C. ו עכשיו הנה תלמיד אחר. אבל אם שולחן חשיש זה מיושם עם מערך, אני סוג של דפוק בשלב זה, נכון? אני סוג של צריך לשים איפשהו זה. 

אז דרך יחידה שאני יכול לפתור את זה, כולו נכון, הוא עסוק, B הוא עסוק, C הוא עסוק. אני הולך לשים אותו בד אז ב הראשון, יש לי גישה מיידית אקראית לכל אחד מהדליים לתלמידים. אבל עכשיו זה סוג של devolved ליניארי משהו, כי אם אני רוצה לחפש מישהו השם שלהם מתחיל עם, אני בודק כאן. אבל אם זה לא סטודנט אני מחפש, אני סוג של יש להתחיל לבדוק הדליים, כי מה שעשיתי היה סוג של ליניארי לחקור את מבנה הנתונים. דרך מטופשת לומר רק להסתכל לפתיחה זמינה הראשונה, ולשים כתכנית ב ', כביכול, או D תכנית במקרה זה, הערך במיקום שבמקום. זה פשוט כל כך שאם יש לך קיבלתי 26 מקומות ולא תלמידים עם שם Q או Z, או משהו כזה כי, לפחות אתה משתמש בחלל. 

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

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

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

אז יש את המבנה הזה. וזה אחרון שלנו מבנה להיום, וזה משהו שנקרא איירי. T-R-אני-E, שמשום מה היא קצר לאחזור, אבל זה נקרא איירי. אז איירי היא עוד מעניינת תערובת של הרבה מהרעיונות האלה. זה עץ, שראינו בעבר. זה לא עץ חיפוש בינארי. זה עץ עם כל מספר של ילדים, אבל כל אחד מהילדים באיירי הוא מערך. מערך של גודל, אומר, 26 או אולי 27 אם אתה רוצה לתמוך בשמות מקף או גרשיים בשמות של אנשים. 

ואז זה מבנה נתונים. ואם אתה מסתכל מלמעלה למטה, כמו אם מסתכל על הצומת העליונה שם, M, הוא מצביע על הדבר השמאלי ביותר שם, שלאחר מכן, X, W, E, L, ל 'זה הוא רק מבנה נתונים שבאופן שרירותי הוא אחסון השמות של אנשים. ומקסוול מאוחסן רק על ידי הבא דרכו של מערך למערך למערך. אבל מה מדהים על איירי היא ש, ואילו רשימה מקושרת ואפילו מערך, את הטוב ביותר שאי פעם קיבלו הוא זמן ליניארי או לוגריתמי זמן מחפש מישהו שם למעלה. במבנה זה נתונים של איירי, אם יש מבנה הנתונים שלי שם אחד בזה ואני מחפש מקסוול, אני הולך למצוא אותו די מהר. אני רק מחפש M-X-W-E-L-L. אם מבנה נתונים זה, לעומת זאת, אם N הוא מיליון, אם יש מיליון שמות במבנה נתונים זה, מקסוול עדיין הולך להיות לגילוי רק לאחר M-X-W-E-L-L צעדים. וצעדי David-- D-A-V-אני-D. במילים אחרות, על ידי בנייה מבנה נתונים זה קיבלתי את כל מערכים אלה, אשר כולם עצמם לתמוך בגישה אקראית, אני יכול להתחיל לחפש את האנשים של שם באמצעות כמות הזמן זה לא פרופורציונאלי למספר דברים במבנה נתונים, כמו מיליון שמות קיימים. משך זמן שלוקח לי למצוא M-X-W-E-L-L במבנה נתונים זה מידתי שלא גודלו של מבנה הנתונים, אבל לאורכו של השם. ומציאותי שמות שאנחנו מחפשים את אף פעם לא הולכים להיות מטורף עוד. אולי למישהו יש 10 דמות שם, 20 שם דמות. זה בהחלט סופי, נכון? יש אדם על פני כדור הארץ ש יש שם הארוך ביותר האפשריים, אבל השם שהוא קבוע אורך ערך, נכון? זה לא ישתנה בכל מובן. אז בדרך זו, יש לנו השיג מבנה נתונים שהוא להסתכל למעלה בזמן קבוע. זה לוקח מספר הצעדים בהתאם לאורכו של הקלט, אבל לא את מספר שם במבנה נתונים. אז אם אנחנו להכפיל את מספר השמות בשנה הבאה ממליארד לשני מיליארדים, ממצא מקסוול הולך לקחת בדיוק את אותו המספר של שבעה צעדים כדי למצוא אותו. וכך אנו נראים שהשגנו הגביע הקדוש שלנו של זמן ריצה. 

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

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

1 SPEAKER: בסדר, זהו זה לעת עתה. נתראה בשבוע הבא. 

דאג: כדי לראות אותו בפעולה. אז בואו נסתכל על זה עכשיו. אז הנה, יש לנו מערך לא ממוינת. 

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

איאן: וואו, וואו, וואו, לחתוך, לחתוך, לחתוך, לחתוך. דאג, אתה פשוט לא יכול יה-דה, יא-דה, יה-דה, דרכך סוג המיזוג. 

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

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

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

דאג: אבל יש לנו כבר הסביר כיצד שני sides-- 

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

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

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

איאן: בסדר. אתה מוכן? גדול. פעולה.