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

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

אז בוא נעשה את הידיים על החלק הראשון. אז פשוט לקבל את הידות מלוכלכות עם בסביבה קרא scratch.mit.edu. זהו כלים שאנו משתמשים בכיתה הראשונה שלנו. למרות שהוא מתוכנן לגילאי 12 ומעלה, אנו משתמשים בו עבור למעלה חלק למדי כי קצת כיוון שזה כיף, נחמד בצורה גרפית של למידה משהו קטן על תכנות. אז לכו ל- URL כי, שבו אתה צריך לראות דף בצורה כזאת, וללכת קדימה ולחץ הצטרף Scratch בצד ימין למעלה ולבחור את שם המשתמש ואת סיסמא ובסופו של דבר לקבל את עצמך scratch.mit.edu account--. חשבתי שאשתמש בזה בתור ההזדמנות הראשונה להראות זאת. שאלה שהתעוררה במהלך ההפסקה על מה קוד באמת נראה כמו. ואנחנו מדברים במהלך ההפסקה על C, ב particular-- ובמיוחד רמה נמוכה ב שפה קדומה. ואני רק עשיתי מהיר החיפוש של גוגל כדי למצוא קוד C עבור חיפוש בינארי, האלגוריתם שאנחנו המשמש לחיפוש שספר טלפון קודם לכן. בדוגמה זו בפרט, כמובן, אינו מחפש ספר טלפונים. זה פשוט מחפש חבורה שלמה של מספרים בזיכרון המחשב. אבל אם אתה רוצה רק לקבל חזותי תחושת איזה תכנות בפועל שפה נראית, זה נראה משהו קטן כזה. אז זה בערך 20 פלוס, שורות קוד 30 או משהו כזה, אבל השיחה אנחנו נהלו בחופשה היה על איך זה בעצם מקבל נהפך אפסים ואחדים ואם אתה לא יכול פשוט לחזור כי לעבד וללכת אפסים ואחדים לגבות לקוד. 

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

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

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

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

אז פעם אכן יש לך חשבון על scratch.mit.edu, לחץ על לחצן צור בחלק העליון השמאלי של האתר. ואתה צריך לראות בסביבה כמו אחד אני עומד לראות על המסך שלי כאן. ונבלה קצת קצת זמן לשחק כאן. בוא נראה אם ​​אנחנו לא יכולים כל לפתור חלק בעיות ביחד באופן הבא. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

COMPUTER: אאוץ ', אאוץ', אאוץ '. 

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

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

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

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

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

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

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

כן, אז יש איזשהו "אם" להתנות שם למעלה, מדי. וזה הופך out-- לא ראינו זה- אבל יש בלוקים אחרים שם ניתן לומר, אם אתה נוגע ללב עוד דבר על המסך, אם אתה נוגע כרית שושן, "אז." ואז זה כשאנחנו להפוך את הצפרדע השנייה להופיע. אז למרות המשחק הזה הוא בהחלט מאוד מיום, למרות שבמבט ראשון יש כל כך הרבה קורה on-- ובלייק לא להלהיב זאת בשתי דקות, זה בטח לקח לו כמה שעות כדי ליצור את המשחק הזה מבוסס על זיכרון או סרטי הווידאו שלו גרסה של פעם ממנו. אבל כל הדברים הקטנים האלה הולך על המסך בבידוד להרתיח עד מאוד אלה פשוט תנועות או הצהרות constructs-- כמו שאמרנו, לולאות תנאים, וזה על זה. יש כמה תכונות מגדלת אחרות. חלקם גרידא אסתטי או אקוסטי, כמו הצלילים פשוט שיחקתי עם. אבל על פי רוב, אתה יש ב Scratch השפה, זה, כל יסוד אבני הבניין שאתה יש ב- C, Java, JavaScript, PHP, Ruby, Python, וכל מספר בשפות אחרות. בכל שאלה אודות Scratch? בסדר. אז אנחנו לא לצלול עמוק יותר אל Scratch, אם אתה מוזמן בסוף השבוע, במיוחד אם יש לך ילדים או אחיינים כזה, כדי להציג בפניהם את Scratch. זהו בעצם להפליא שובבה סביבה עם, כמו מחבריו לומר, תקרות גבוהות מאוד. למרות שהתחלנו עם מאוד פרטים ברמה נמוכה, אתה באמת יכול לעשות לא מעט עם זה, וזה אולי הפגנה של בדיוק את זה. 

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

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

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

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

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

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

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

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

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

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

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

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

במקרה זה היה מהיר, אך כמה זמן לוקח באמת? בואו נעשה את זה נראה ו מרגיש קצת יותר משעמם. אז אחת, שתיים, שלוש, ארבע, חמש ושש, שבע, שמונה, תשע, 10, 11, 12, 13, 14, 15, 16-- מספר שרירותי. רציתי פשוט יותר זה זמן מאשר רק ארבע. אז אם יש לי כל חבורה של מספרים now-- זה אפילו לא משנה מה הוא שהן-- בואו לחשוב על מה זה האלגוריתם באמת כמו. 

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

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

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

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

וכך בואו נחשוב על כמה צעדים אני בעצם לשוטט דרך בכל פעם. במצב הראשון היו לנו 16 מספרים, וכך maximally-- בואו פשוט עושה את זה בשביל discussion-- הייתי צריך לחפש דרך 16 מספרים כדי למצוא את הקטן. אבל ברגע שאני ותלשתי המספר הקטן ביותר, איך ארוכה היא רשימת הנותרים, כמובן? רק 15. אז כמה מספרים עשו בן או שאני צריך להסתכל דרך בפעם השנייה? 15, רק כדי ללכת ולמצוא את הקטן. אבל עכשיו, כמובן, הרשימה היא, גם קטן ממה שהוא היה לפני. אז כמה צעדים עשו לי יש לקחת בפעם הבאה? 14 ואז 13 ואז 12, פלוס נקודה, נקודה, נקודה, עד שאני נשאר רק עם אחד. אז עכשיו מדען מחשב היה לשאול, ובכן, מה עושה את זה כולם שווה? זה בעצם מסתכם ב כ בטון מספר שאנחנו יכולים בהחלט אריתמטית לעשות, אבל אנחנו רוצים לדבר על היעילות של אלגוריתמים קצת יותר formulaically, עצמאי של כמה זמן והרשימה. 

אז אתה יודע מה? זהו 16, אבל כמו שאמרתי קודם, בואו פשוט נקרא את גודל הבעיה n, כאשר n הוא מספר כלשהו. אולי זה 16, אולי זה שלושה, אולי זה מיליון. אֲנִי לֹא יוֹדֵעַ. לא אכפת לי. מה שאני באמת רוצה זה נוסחה שאני יכול להשתמש בו כדי להשוות אלגוריתם זה נגד אלגוריתמים אחרים כי מישהו עלול לטעון הם לטוב ולרע. 

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

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

אז עם אותו ההיגיון, בינתיים, הבה נבחן אלגוריתם אחר אנחנו כבר נראינו at-- חיפוש ליניארי. כאשר חיפשתי עבור הטלפון book-- לא מיון, חיפוש דרך הטלפון book-- אנחנו כל הזמן אמר שזה היה 1,000 צעדים, או 500 צעדים. אבל בואו להכליל את זה. אם יש n עמודים בספר הטלפונים, מה הזמן רץ או היעילות של חיפוש ליניארי? זה בסדר גודל של כמה צעדים כדי למצוא מייק סמית באמצעות חיפוש ליניארי, אלגוריתם ראשון, או אפילו שני? 

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

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

אז 1,000 דף בספר טלפונים אולי לקחת אותנו 500 פניות דף, ועוד אחד אם נכפיל קצת אחורה. אז אם בספר טלפונים יש דפי n, אבל אנחנו עושים שני עמודים בכל פעם, זה פחות או יותר מה? N מעל השנייה, אז זה כמו n מעל השנייה. אבל אני עשיתי את התביעה רגע לפני כי n מעל two-- זה סוג של זהה רק n. זה פשוט גורם קבוע, מדעני מחשב יגידו. בואו רק להתמקד המשתנים, באמת-- המשתנים הגדולים במשוואה. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

רשימה זו אינה מסודרת. למה? באנגלית, להסביר מדוע זה לא מסודר למעשה. מה זה אומר להיות מסודר לא? 

סטודנט: זה לא רציף. 

DAVID מלאן: לא רציף. תן לי דוגמה. 

סטודנט: שים אותם לפי סדר. 

DAVID מלאן: אישור. תן לי דוגמה ספציפית יותר. 

סטודנט: עולה סדר. DAVID מלאן: לא עולה. ליתר דיוק. אני לא יודע למה אתה מתכוון על ידי עולה. מה לא בסדר? 

סטודנט: הקטן של מספרים לא במרחב הראשון. 

DAVID מלאן: המספר הקטן ביותר של לא במרחב הראשון. תהיה יותר ספציפי. אני מתחיל לתפוס. אנו אתה סומך, אבל מה מקולקל כאן? 

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

סטודנט: פלוס אחד. 

DAVID מלאן: מה זה? 

סטודנט: פלוס אחד. 

DAVID מלאן: למה אתה מתכוון אחד ועוד? תן לי חמש-בת שונה. מה לא בסדר, אמא? מה לא בסדר, אבא? למה אתה מתכוון זה לא מסודר? 

סטודנט: זה לא המקום הנכון. 

DAVID מלאן: מה לא במקום הנכון? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אבל הרשימה end-- spoiler-- הולך להיות מסודר. אז בואו נסתכל על איזה אחד אחרון. אנחנו לא יכולים פשוט לדלג כעת. אנחנו כמעט שם. נשארו לנו עוד שניים, אחד ללכת. וזהו. מְעוּלֶה. 

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

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

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

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

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

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

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

אז פיסת זיכרון בבית computer-- כך RAM DIMM הוא מה שחיפשנו אתמול, כפול זיכרון פנימי module-- נראה כך. וכל אחד שבבי השחורים הקטנים האלה כמה מספר הבתים הוא, בדרך כלל. ואז פיני הזהב הם כמו חוטים שמחברים אותו למחשב, ואת לוח סיליקון הירוק הוא רק מה שמחזיק הכל הכל ביחד. אז מה זה באמת אומר? אם אני סוג של לצייר תמונה ממש, הבה נניח לפשטות כי DIMM זה, כפול מודול זיכרון פנימי, ג'יגה של זיכרון RAM אחד הוא, אחד ג'יגה של הזיכרון, וכך הכולל בתים רבים? ג'יגה אחת היא כמה בתים? יותר מזה. 1,124 הוא קילו, 1,000. מגה מיליון. גיגה הוא מיליארדים. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ואני יכול לראות את זה, שוב, כדלקמן, אלה הם אפסים ואחדות אני פשוט נוצר מקוד המקור שלי, כל האפסים ואחדים. ואם אני רוצה לרוץ שלי program-- זה קורה להיקרא a.out עבור reasons-- ההיסטורית "שלום." אני יכול להפעיל אותו שוב. שלום שלום שלום. וזה נראה שזה עובד. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אפס, אחת, שתיים, שלוש, ארבע, חמש, שש, שבע. זה נראה כמו 90 הוא ב כתובת זיכרון מספר שבע. כל החצים האלה הם הוא כמו פיסת נייר קטנה כי נותן הנחיות כיצד להגיע אל תוכנית שאומרת לפי המפה זה כדי להגיע למיקום שבע. ויש תמצא את ציון החידון השני של התלמיד. בינתיים, 75-- אם אני ממשיך זה, זה שבעה, שמונה, תשע, 10, 11, 12, 13, 14, 15. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O ביג של n הוא מה נדרש כדי לקבל עד הסוף של מבנה נתונים זה, whereas-- ולא ראינו זה before-- מערך נותן לך מה שנקרא זמן קבוע, כלומר צעד אחד או שני צעדים או 10 steps-- לא משנה. זה מספר קבוע. יש לזה שום קשר עם את גודל המערך. והסיבה לכך, שוב, היא גישה אקראית. המחשב יכול רק מיד לקפוץ למקום אחר, כי הם כולם אותו הדבר המרחק בין כל דבר אחר. אין מחשבה שהושקעה. בסדר. אז אם אני יכול, תן לי לנסות לצייר שתי תמונות סופיות. אחד נפוץ מאוד המכונה טבלת גיבוב. אז כדי להניע את הדיון הזה, תן לי לחשוב על איך לעשות את זה. 

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

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

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

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

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

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

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

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

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

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

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

עכשיו זה יצמצם זמננו פוטנציאלי על ידי ככל אחד מתוך 26, כי אם אתה מניח שאתה יש כמה "a" מילים כמו "z" מילים כמילים "q", אשר הוא לא ממש realistic-- אתה הולך יש להטות פני אותיות מסוימות של alphabet-- אבל זה יהיה מצטבר הגישה כי אין לאפשר לך להגיע מילים הרבה יותר מהר. וגם במציאות, מתוחכם התוכנית, גוגל של העולם, Facebooks של בעולם-- הם ישתמשו טבלת גיבוב עבור הרבה מטרות שונות. אבל הם לא יהיו עד כדי כך נאיבי רק להסתכל על האות הראשונה תפוח או בננה או אגס או מלון, כי כפי שאתה יכול לראות אותם רשימות עדיין יכולות לקבל ארוכה. 

וכך זה עדיין עשוי להיות מעין של linear-- כך מעין איטית, כמו עם O הגדולה של n כי שהזכרנו קודם לכן. אז מה טבלת גיבוב ממש טובה תהיה לבצע-- יהיה לו מערך הרבה יותר גדול. וזה ישתמש הרבה יותר פונקצית hashing מתוחכמת, כך שזה לא רק להסתכל על "א." אולי זה נראה ב "א-p-p-l-e" ו איכשהו ממירה אותם חמישה מכתבים אל המיקום שבו יש לאחסן תפוחים. אנחנו רק בתמימות באמצעות מכתב א ' לבד, כי זה נחמד ופשוט. 

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

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

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