DAVID مالان: حسنا. لقد عدنا. حتى في هذا القطاع على برمجة ما اعتقد اننا كنا نفعله هو مزيج من الأشياء. واحدة، لا قليلا شيء التدريب العملي على، وإن كان ذلك باستخدام أكثر لعوب environment-- البرمجة واحد هو أن بيانية لل بالضبط ذلك النوع من الأفكار كنا نتحدث عنها، ولكن أكثر من ذلك بقليل رسميا. اثنين، نلقي نظرة على بعض أكثر الطرق التقنية أن مبرمجا من شأنه أن يحل في الواقع مشاكل مثل مشكلة البحث أن ننظر في قبل و أيضا بشكل أساسي مشكلة مثيرة للاهتمام من الفرز. 

افترضنا فقط من الحصول على الذهاب أن تم فرز هذا الكتاب الهاتف، لكن هذا وحده هو في الواقع نوع من مشكلة صعبة مع العديد من الطرق المختلفة من أجل حلها. ولذا فإننا سوف تستخدم هذه كما فئة من المشاكل ممثل الأشياء التي يمكن حلها بشكل عام. ثم سنتحدث حول بشيء من التفصيل ما تسمى البيانات structures-- طرق مربي الحيوانات مثل القوائم المرتبطة والجداول التجزئة والأشجار التي سيكون مبرمجا في الواقع استخدام وعموما استخدام على لوحة بيضاء لرسم صورة ما هو أو هي تتصور لتنفيذ بعض قطعة من البرمجيات. 

لذلك دعونا نفعل التدريب العملي على جزء أول. حتى مجرد الحصول على يديك القذرة مع البيئة يسمى scratch.mit.edu. هذا هو الأداة التي نستخدمها في الدرجة الجامعية لدينا. على الرغم من انها مصممة لأعمار 12 سنة فما فوق، نستخدمها لتصل جزء من ذلك قليلا جدا حيث أنها لطيفة وممتعة طريقة رسومية من التعلم شيئا قليلا عن البرمجة. لذا توجه إلى هذا العنوان، حيث كنت يجب أن نرى صفحة تماما مثل هذا، والمضي قدما وانقر تاريخ خدش في الحق الأعلى واختيار اسم مستخدم و كلمة المرور و في نهاية المطاف الحصول على نفسك وscratch.mit.edu سبب-. اعتقدت أن استخدام هذا باعتباره الفرصة الأولى لإظهار هذا. وجاء السؤال حتى خلال العطلة حول رمز ما يبدو في الواقع مثل. وكنا نتحدث خلال فترة الاستراحة عن C، في particular-- ولا سيما في أقل مستوى في اللغة القديمة. وأنا فقط لم سريعة بحث Google للعثور على رمز C للبحث ثنائي، الخوارزمية التي نحن تستخدم لبحث هذا الكتاب الهاتف في وقت سابق. هذا مثال معين، بالطبع، لا يتم البحث في دليل الهاتف. هو فقط بالبحث في مجمله مجموعة من الأرقام في ذاكرة الكمبيوتر. ولكن إذا كنت ترغب في مجرد الحصول على البصرية شعور ما في البرمجة الفعلية لغة تبدو، يبدو شيئا قليلا من هذا القبيل. لذلك فمن حوالي 20 زائد، 30 أو حتى خطوط للقانون، ولكن محادثة نحن وجود أكثر من العطلة وحول كيفية هذا الواقع يحصل تحولت إلى أصفار ومنها وإذا كنت لا يمكن أن تعود أن معالجة والذهاب من الآحاد والأصفار و نسخ إلى رمز. 

وللأسف، فإن عملية غير التحويلية ذلك أنه من الأسهل كثيرا من القيام به. ذهبت إلى الأمام وتحولت فعلا هذا البرنامج، ثنائي البحث، في الآحاد والأصفار وعن طريق ل دعا برنامج ومترجم بأنني يحدث لدينا هنا حق على بلدي ماك. وإذا نظرت إلى الشاشة هنا، مع التركيز بشكل خاص على هذه ستة أعمدة المتوسطة فقط، سترى الوحيدة الآحاد والأصفار و. وتلك هي الأصفار وتلك التي يؤلف بالضبط هذا البرنامج البحث. 

وهكذا كل قطعة من خمسة أجزاء، كل بايت من الآحاد والأصفار وهنا، تمثل بعض التعليمات عادة داخل جهاز الكمبيوتر. وفي الواقع، إذا كنت قد سمعت تسويق شعار "إنتل في الداخل" - التي، وبطبيعة الحال، مجرد وسيلة لديك وحدة المعالجة المركزية إنتل أو الدماغ داخل الكمبيوتر. وماذا يعني أن تكون وحدة المعالجة المركزية أن يكون لديك مجموعة التعليمات، إذا جاز التعبير. 

كل وحدة المعالجة المركزية في العالم، والعديد من منهم أدلى بها إنتل في هذه الأيام، يفهم محدود عدد من التعليمات. وهذه التعليمات هي مستوى منخفض للغاية كما تضيف هذين الرقمين معا، تتضاعف هذه الأرقام معا، نقل هذه القطعة من البيانات من هنا إلى هنا في الذاكرة، حفظ هذا معلومات من هنا إلى هنا في الذاكرة، وهكذا forth-- ذلك جدا، جدا على مستوى منخفض، تفاصيل الإلكترونية تقريبا. ولكن مع تلك الرياضي العمليات إلى جانب مع ما ناقشناه في وقت سابق، تمثيل البيانات كما الأصفار ومنها، يمكن يمكنك بناء كل شيء أن الكمبيوتر يمكن القيام به اليوم، سواء انها النصية، الرسوم البيانية والموسيقية، او غير ذلك. 

لذلك هذا هو السهل جدا الحصول على خسر في الأعشاب الضارة من على وجه السرعة. وهناك الكثير من التحديات النحوية حيث إذا قمت بإجراء أبسط، أغبى من الأخطاء المطبعية أيا من البرنامج ستعمل على الإطلاق. وذلك بدلا من استخدام لغة مثل C هذا الصباح، اعتقدت انه سيكون أكثر متعة القيام به في الواقع شيء أكثر البصرية، التي في حين صممت للأطفال هو في الواقع مظهر الكمال من البرمجة الفعلية language-- يحدث لمجرد أن استخدام الصور بدلا من النص لتمثيل تلك الأفكار. 

ذلك مرة واحدة لديك في الواقع الحساب على scratch.mit.edu، انقر فوق الزر إنشاء في أعلى يسار الموقع. ويجب أن تشاهد بيئة مثل واحد أنا على وشك أن نرى على الشاشة هنا. ونحن سوف ينفق قليلا قليلا من الوقت يلعب هنا. دعونا نرى ما اذا كنا لا يمكن أن تحل جميع بعض المشاكل معا على النحو التالي. 

وذلك ما سترى في هذا environment-- وفعلا مجرد السماح لي وقفة. وأي شخص ليس هنا؟ ليس هنا؟ حسنا. لذلك اسمحوا لي أن أشير إلى عدد قليل خصائص هذه البيئة. 

حتى في أعلى يسار الشاشة، ل لدينا مرحلة الصفر، وإذا جاز التعبير. الصفر ليس فقط اسم هذه لغة البرمجة. كما انها اسم القط الذي ترى افتراضيا هناك في البرتقال. وهو على خشبة المسرح، لذلك مثل الكثير وصفت سلحفاة في وقت سابق بأنه في مستطيلة البيئة وحة بيضاء. يقتصر العالم هذا القط تماما لهذا المستطيل حتى أعلى هناك. 

وفي الوقت نفسه، على اليمين الجانب هنا، انها مجرد منطقة مخطوطات، وهو لائحة بيضاء اذا صح التعبير. هذا هو المكان الذي كنت أريد أن أكتب برامجنا في مجرد لحظة. ولبنات البناء على أننا يجب استخدامها لكتابة هذا program-- اللغز قطعة، إذا كنت will-- هي تلك هنا في الوسط، وانهم تصنيفها من وظائف. لذلك، على سبيل المثال، انا ذاهب الى المضي قدما وتظهر واحدة على الأقل من هذه. انا ذاهب الى المضي قدما وانقر فئة تحكم حتى أعلى. 

لذا فان هذه الفئات حتى أعلى. أنا ذاهب إلى انقر فوق الفئة التحكم. بدلا من ذلك، انا ذاهب فوق الأحداث الفئة، واحد حتى أول قمة. وإذا كنت ترغب في متابعة على طول حتى كما نفعل هذا، وكنت موضع ترحيب للغاية ل. أنا ذاهب إلى انقر واسحب هذا أول واحد، "عندما ينقر العلم الأخضر". ثم انا ذاهب لإسقاطه فقط تقريبا في الجزء العلوي من بلدي القوائم فارغة. 

وما هو جميل عن سكراتش غير أن هذا اللغز قطعة، عندما متشابكة مع اللغز الآخر قطعة، سيفعل حرفيا ما تقول تلك القطع لغز للقيام به. لذلك، على سبيل المثال، خدش هو الصحيح الآن في منتصف عالمه. انا ذاهب الى المضي قدما واختيار الآن، دعنا نقول، فئة الحركة، إذا كنت ترغب في القيام same-- فئة الحركة. وتلاحظ الآن لدي ككل مجموعة من قطع اللغز هنا هذا، مرة أخرى، من نوع يفعلون ما يقولون. وانا ذاهب الى المضي قدما وسحب و إسقاط كتلة حركة حق أكثر من هنا. 

وتلاحظ أن بمجرد الحصول على على مقربة من الجزء السفلي من "العلم الأخضر النقر "زر، لاحظ كيفية ظهور خط أبيض، كما لو انها تقريبا المغناطيسي، انها تريد الذهاب الى هناك. مجرد ترك، وسوف المفاجئة معا والأشكال وستكون مباراة. والآن يمكنك ربما تقريبا تخمين أين نحن ذاهبون مع هذا. 

إذا نظرتم الى مرحلة الصفر أكثر من هنا وننظر إلى الجزء العلوي منه، سترى الضوء الأحمر، و وقف علامة، والعلم الأخضر. وانا ذاهب الى المضي قدما ومشاهدة screen-- بلدي لمجرد لحظة، إذا كنت تستطيع. انا ذاهب الى فوق العلم الأخضر في الوقت الراهن، وانتقل على ما يبدو 10 خطوات أو 10 بكسل، 10 نقطة، على الشاشة. 

وهكذا لا أن مثيرة، ولكن اسمحوا لي أن أقترح دون أن يعلم هذا، فقط باستخدام تلقاء اسمحوا intuition-- الخاصة بك لي أن أقترح أن لك معرفة كيفية جعل خدش المشي الحق قبالة المرحلة. وعليه إفساح المجال للجانب الأيمن من الشاشة، على طول الطريق إلى اليمين. واسمحوا لي أن أقدم لكم لحظة أو نحو ذلك ليتصارع مع ذلك. قد ترغب في إلقاء نظرة في فئات أخرى من لبنات. حسنا. وذلك فقط من أجل التذكير، عندما يكون لدينا النقر على العلم الأخضر هنا ونقل 10 خطوات هي تعليمات الوحيد، في كل مرة أنا انقر العلم الأخضر، ما الذي يحدث؟ حسنا، هذا هو تشغيل برنامجي. حتى أتمكن من القيام بذلك ربما 10 مرات يدويا، ولكن هذا يشعر قليلا الشيء hackish، إذا جاز التعبير، حيث أنا لست حقا حل هذه المشكلة. أنا فقط أحاول مرة أخرى و مرة أخرى، ومرة ​​أخرى ومرة ​​أخرى حتى أنا من النوع عن طريق الخطأ تحقيق التوجيه التي أخذت على عاتقي أن يحقق في وقت سابق. 

ولكننا نعرف من وجهة نظرنا شبة الكود في وقت سابق أن هناك هذه الفكرة في برمجة حلقات، تفعل شيئا مرارا وتكرارا. وهكذا رأيت أن حفنة منكم وصلت لقطعة ما اللغز؟ كرر حتى. حتى أننا يمكن أن نفعل شيئا كما كرر حتى. وماذا كنت أكرر حتى بالضبط؟ 

حسنا. واسمحوا لي ان اذهب مع احد وهذا إلى حد ما أكثر بساطة لمجرد لحظة. اسمحوا لي أن نمضي قدما ونفعل هذا. لاحظ أنه، كما قد تكون لديكم اكتشف تحت السيطرة، هناك هذا تكرار كتلة، التي لا يبدو انها بهذا الحجم. هناك غرفة ليس كثيرا في بين هذين خطوط صفراء. ولكن بما أن بعض من قد يكون لديك لاحظت، إذا قمت بسحب وإسقاط، لاحظ كيف أنها تنمو لتعبئة الشكل. 

ويمكنك حتى الالزام أكثر. انها سوف تبقي فقط المتنامية اذا قمت بسحب وتحوم فوقها. وأنا لا أعرف ما هو أفضل هنا، لذلك اسمحوا لي على الأقل تكرار خمس مرات، ل مثلا، ثم انتقل إلى مرحلة وانقر على العلم الأخضر. وتلاحظ الآن أنه ليس هناك تماما. 

الآن بعضكم المقترحة، كما فيكتوريا فقط لم، كرر 10 مرات. وأن يفعل عموما الحصول عليه على طول الطريق، ولكن لن يكون هناك أكثر قوة الطريق من كشف تعسفية خارج عدد من الاجراءات لدفع؟ ما قد يكون كتلة أفضل من تكرار 10 مرات تكون؟ 

نعم، فلماذا لا تفعل شيئا إلى الأبد؟ والآن اسمحوا لي أن أنتقل هذا اللغز قطعة داخل هناك، والتخلص من هذه واحدة. لاحظ الآن لا يهم أين خدش يبدأ، بل يذهب إلى الحافة. ولله الحمد معهد ماساتشوستس للتكنولوجيا، الذي يجعل من خدش، فقط يتأكد أنه أبدا يختفي تماما. يمكنك دائما انتزاع ذيله. 

وفقط بشكل حدسي، لماذا هو الحفاظ على التحرك؟ ما الذي يجري هنا؟ ويبدو أنه قد توقف، ولكن ثم إذا أنا التقاط وسحب وقال انه يحتفظ الرغبة في الذهاب إلى هناك. لماذا هذا؟ حقا، جهاز كمبيوتر هو حرفيا تنوي القيام به ما كنت أقول أن تفعله. حتى لو قلت في وقت سابق قيام الشيء التالي إلى الأبد، نقل 10 خطوات، انها سوف تستمر وسوف حتى أنا ضربت علامة التوقف الحمراء ووقف البرنامج تماما. 

لذلك حتى لو كنت لا تفعل هذا، كيف يمكن لي جعل هذه الخطوة خدش أسرع عبر الشاشة؟ المزيد من الخطوات، أليس كذلك؟ وذلك بدلا من القيام 10 في وقت واحد، لماذا لا نفعل نحن المضي قدما وتغييره ل-- ماذا كنت propose-- 50؟ حتى الآن أنا ذاهب إلى انقر الأخضر العلم، والواقع، وقال انه يذهب بسرعة كبيرة. 

وهذا، بطبيعة الحال، هو فقط مظهر من مظاهر حيوية. ما هي الرسوم المتحركة؟ انها مجرد يظهر لك على الإنسان مجموعة كاملة من الصور الثابتة حقا، حقا، حقا بسرعة. وهكذا إذا نحن فقط نقول له بالتحرك المزيد من الخطوات، نحن مجرد وجود التأثير سيكون ل التغيير حيث انه على الشاشة كل وحدة بشكل أسرع في الوقت. 

الآن التحدي المقبل الذي اقترحه وكان أن يكون له ترتد قبالة الحافة. ودون أن يعرفوا ما لغز قطع exist-- لأنه على ما يرام إذا كنت لا تحصل على مرحلة من مراحل challenge-- ما هل تريد أن تفعل بشكل حدسي؟ كيف لنا أن يكون له ارتداد و إيابا، بين اليسار واليمين؟ 

بلى. لذلك نحن بحاجة إلى نوع من الشرط، ونحن يبدو أن لديها الشرطية، وذلك ل الكلام، وضمن فئة التحكم. أي من هذه الكتل هل نحن ربما تريد؟ نعم، ربما "إذا، بعد ذلك." لذلك نلاحظ أن من بين كتل صفراء لدينا هنا، هناك هذا "لو" أو هذا "إذا، آخر" الكتلة التي سوف تسمح لنا لاتخاذ قرار للقيام بذلك أو أن نفعل ذلك. ويمكنك حتى عش لهم أن تفعل أشياء متعددة. أو إذا كنت لم ذهبت هنا بعد، المضي قدما إلى فئة الاستشعار and-- دعونا نرى ما اذا كان هنا. 

وماذا في ذلك كتلة قد يكون من المفيد هنا للكشف عن ما اذا كان بعيدا عن المسرح؟ نعم، لاحظ أن بعض هذه الكتل يمكن parametrized، إذا جاز التعبير. ويمكن الفرز حسب الطلب، وليس على عكس HTML أمس مع الصفات، حيث هذه الصفات نوع من تخصيص سلوك علامة. وبالمثل هنا، يمكنني أن الاستيلاء على هذه لمس كتلة والتغيير ونطرح هذا السؤال: هل لمس الماوس مؤشر مثل مؤشر أم أنك لمس حافة؟ 

لذلك اسمحوا لي أن أذهب في وقيام بذلك. انا ذاهب للتصغير لحظة. اسمحوا لي أن الاستيلاء على هذه قطعة اللغز هنا، هذا اللغز قطعة هذا، وانا ذاهب الى الخليط لهم حتى لمجرد لحظة. انا ذاهب الى نقل هذا، تغيير هذا إلى حافة مؤثرة، وانا ذاهب الى اقتراح قيام بذلك. حتى هنا بعض المكونات. أعتقد أنني قد حصلت على كل ما تريد. 

شخص ما من شأنه أن تقترح كيف ويمكن ربط هذه ربما أعلى إلى أسفل من أجل حل مشكلة وجود الصفر الخطوة اليمين إلى اليسار إلى اليمين ل من اليسار إلى اليمين إلى اليسار، كل الوقت فقط كذاب قبالة الجدار؟ ماذا تريد أن تفعل؟ التي كتلة يجب أن الاتصال "العلم عندما الأخضر النقر أولا"؟ 

حسنا، دعونا نبدأ مع "الى الابد". ما يدور داخل المقبل؟ شخص اخر. موافق، والانتقال الخطوات. حسنا. ثم ماذا؟ حتى ذلك الحين وإذا. ولاحظ، على الرغم من أنها تبدو تقع معا بإحكام، انها سوف تنمو فقط لملء الفراغ. وسوف تقفز فقط في المكان الذي أريد ذلك. 

وماذا أضع بين وإذا وبعد ذلك؟ ربما "إذا لمس الحافة." والإشعار، مرة أخرى، انها كبيرة جدا لذلك، ولكنها سوف تنمو لملء الفراغ. ثم قم بتشغيل 15 درجة؟ كم درجه؟ نعم، لذلك 180 سوف تدور لي على طول الطريق حول. لذلك دعونا نرى إذا حصلت على هذا الحق. اسمحوا لي أن التصغير. 

اسمحوا لي أن سحب خدش تصل. حتى انه قليلا مشوهة الآن، ولكن هذا شيء طيب. كيف يمكنني إعادة عليه بسهولة؟ أنا ذاهب للغش قليلا. لذلك أنا آخر إضافة كتلة، لمجرد أن يكون واضحا. أريده أن نشير 90 درجة إلى اليمين بشكل افتراضي، لذلك أنا فقط أريد أن أقول له للقيام بذلك برمجيا. وها قد بدأنا. يبدو أننا قد فعلت ذلك. انها غريبة بعض الشيء، ل انه المشي رأسا على عقب. دعونا نسمي ذلك الخلل. وهذا خطأ. والخطأ هو خطأ في البرنامج، ل خطأ منطقي أنني، والإنسان، جعلت. لماذا يذهب رأسا على عقب؟ لم MIT المسمار أو فعلت؟ 

نعم، أعني، انها ليست معهد ماساتشوستس للتكنولوجيا خطا. أعطوني قطعة اللغز تقول تحويل بعض عدد من الدرجات. وبناء على اقتراح فيكتوريا، أنا تحول 180 درجة، وهو الحدس الصحيح. ولكن تحول 180 درجة حرفيا يعني تحول 180 درجة، وهذا ليس حقا ما أريد، وعلى ما يبدو. لأنه على الأقل انه في هذا العالم ثنائي الأبعاد، هكذا تحول يحدث في الواقع على الوجه له رأسا على عقب. 

أنا ربما تريد استخدام ما كتلة بدلا من ذلك، بناء على ما تراه هنا؟ كيف يمكن أن نصلح هذا؟ نعم، لذلك يمكن أن نشير في الاتجاه المعاكس. والواقع حتى هذا لن يكون كافيا، لأننا لا نستطيع رمز القرص الثابت فقط لافتا اليسار أو اليمين. 

أنت تعرف ماذا يمكن أن نفعل؟ يبدو أن لدينا الراحة كتلة هنا. إذا كنت في التكبير، انظر شيء نحب هنا؟ بحيث يبدو مثل معهد ماساتشوستس للتكنولوجيا لديه التجريد بنيت هنا. يبدو هذه الكتلة ليكون معادلا التي الكتل الأخرى، بصيغة الجمع؟ 

ويبدو أن هذا كتلة واحدة ليكون معادلا لهذا الثلاثي كاملة من كتل ان لدينا هنا. لذلك تبين لي يمكن تبسيط بلدي البرنامج من خلال التخلص من كل ذلك وضعت للتو هذا هنا. والآن انه لا يزال قليلا عربات التي تجرها الدواب، وهذا شيء طيب في الوقت الراهن. سنترك أن يكون. ولكن برنامجي هو حتى أبسط، وهذا، أيضا، سيكون ممثل من هدف في programming-- هو جعل مثالي التعليمات البرمجية كما بسيطة، كما ضغط ممكن، في حين لا تزال كما قراءة وقت ممكن. كنت لا تريد أن تجعل من مقتضبة جدا أنه من الصعب أن نفهم. 

ولكن لاحظ لقد استبدلت ثلاث كتل واحد، وهذا القول شيء جيد. لقد المستخرجة بعيدا عن فكرة للتحقق ما إذا كنت على حافة مع كتلة واحدة فقط. ونحن الآن يمكن أن يكون متعة مع هذا، في الواقع. هذا لا يضيف كثيرا القيمة الفكرية ولكن قيمة لعوب. انا ذاهب الى المضي قدما والاستيلاء على هذا الصوت هنا. لذلك اسمحوا لي المضي قدما، واسمحوا لي وقف برنامج لحظة. أنا ذاهب لتسجيل ما يلي، مما يتيح الوصول إلى الميكروفون. 

ها نحن ذا. أوتش. دعونا نحاول هذا مرة أخرى. ها نحن ذا. حسنا، أنا سجلت الشيء الخطأ. ها نحن ذا. أوتش. أوتش. حسنا. الآن أنا بحاجة للتخلص من ذلك. حسنا. 

وحتى الآن لدي تسجيل فقط "أوتش". حتى الآن أنا ذاهب للذهاب قبل ونسمي هذا "أوتش". انا ذاهب الى العودة لكتاباتي، والآن إشعار هناك هذه الكتلة وهذا يسمى تشغيل الصوت "مواء" أو تشغيل الصوت "أوتش". انا ذاهب الى سحب هذا، وأين يجب أن أضع هذا لتأثير هزلية؟ نعم، وحتى الآن انها نوع من عربات التي تجرها الدواب، لأنه الآن هذا block-- لاحظ كيف هذا "إذا كان على الحافة، ارتداد "هو نوع من الاكتفاء الذاتي. لذلك أنا بحاجة إلى إصلاح هذا. اسمحوا لي أن نمضي قدما ونفعل هذا. اسمحوا لي أن نتخلص من هذا والعودة لدينا الأصلي، وأكثر متعمد وظائف. "إذا كانت لمس الحافة، ثم" أريد لتحويل، كما اقترح فيكتوريا، 180 درجة. والقيام أريد أن ألعب صوت "أوتش" هناك؟ 

نعم، لاحظ انها خارج أن الكتلة الصفراء. لذلك هذا، أيضا، سيكون علة، ولكن لقد لاحظت ذلك. لذلك أنا ذاهب لجرها إلى هنا، وإشعار الآن حان داخل "إذا". حتى "لو" هو هذا النوع شبيه مثل الذراع وصمة عار وهذا ما لن يؤدي الا الى تفعل ما هو داخل منه. حتى الآن إذا كنت التصغير في خطر annoying-- 

COMPUTER: أوتش، أوتش، أوتش. 

DAVID مالان: وذلك سوف تذهب فقط إلى الأبد. الآن فقط لتسريع الامور هنا، اسمحوا لي أن المضي قدما وفتح، دعونا say-- السماح لي بالذهاب إلى بعض من أشيائي الخاصة من الصف. واسمحوا لي أن تفتح، دعنا نقول، هذا قدم واحدا تلو الآخر من زملاء التدريس لدينا بضع سنوات مضت. وحتى بعض من تذكرون هذه اللعبة من الأمس، وانها ملحوظا في الواقع. على الرغم من أننا قد فعلت أبسط البرامج في الوقت الحالي، دعونا نتأمل ما هذا في الواقع يبدو مثل. اسمحوا لي أن ضرب اللعب. 

حتى في هذه اللعبة، لدينا الضفدع، وباستخدام السهم keys-- ويأخذ خطوات أكبر مما كنت remember-- لدي السيطرة على هذا الضفدع. والهدف من ذلك هو الحصول على جميع أنحاء مشغول الطريق دون الوقوع في السيارات. ودعونا see-- إذا ذهبت إلى هنا، وأنا يجب أن ننتظر لسجل للتمرير من قبل. هذا يبدو وكأنه علة. هذا هو نوع من الخلل. حسنا. أنا على هذا هنا، هناك، ثم عليك أن تبقي الذهاب حتى تحصل على كل الضفادع لمنصات زنبق. الآن هذا قد يبدو جميع أكثر تعقيدا، ولكن دعونا نحاول كسر هذه أسفل عقليا وشفهيا إلى كتل عنصرها. لذلك هناك على الارجح هو لغز قطعة أننا لم نر حتى الآن ولكن هذا ردا على ضربات المفاتيح، إلى أشياء أنا ضربت على لوحة المفاتيح. 

ولذلك لا يوجد ربما نوع من كتلة أن يقول، إذا كان المفتاح يساوي حتى، ثم تفعل شيئا مع Scratch-- ربما تحريكه 10 خطوات هذا الطريق. إذا لم تضغط على مفتاح لأسفل، نقل 10 خطوات بهذه الطريقة، أو مفتاح اليسار، نقل 10 خطوات بهذه الطريقة، 10 خطوات ذلك. لقد تحولت بوضوح القط إلى ضفدع. ولهذا فقط حيث زي، عن مكالمات خدش it-- نحن فقط المستوردة صورة من الضفادع. 

ولكن ماذا يحدث؟ ما الخطوط الأخرى للقانون، ما غيرها من قطع اللغز لم بليك، لدينا تدريس زميل، استخدامها في هذا البرنامج، على ما يبدو؟ ما جعل كل شيء move-- ما البرمجة بناء؟ 

الحركة، sure-- ذلك نقل كتلة، لعلى يقين. وما هو أن كتلة حركة داخل، وعلى الأرجح؟ نعم، نوعا من حلقة، وربما منع إلى الأبد، وربما تكرار block-- كرر حتى كتلة. وهذا ما جعل سجلات و منصات زنبق وكل شيء تحرك آخر ذهابا وايابا. انها مجرد يحدث ما لا نهاية. 

لماذا بعض السيارات تتحرك بشكل أسرع من الآخرين؟ ما هو مختلف عن تلك البرامج؟ نعم، ربما البعض منهم أخذ المزيد من الخطوات دفعة واحدة وبعض منهم خطوات أقل في وقت واحد. والمؤثرات البصرية سريع مقابل بطيئة. 

ما رأيك حدث؟ عندما حصلت على ضفدع على طول الطريق عبر الشارع والنهر على لوحة الزنبق، شيء حدث يذكر. ما حدث في أقرب وقت كما فعلت ذلك؟ توقفت. توقف هذا الضفدع، و حصلت على الضفدع الثاني. وماذا في ذلك بناء يجب أن يكون المستخدمة هناك، ما الميزة؟ 

نعم، لذلك هناك نوع من "إذا" الحالة هناك، أيضا. ويتحول out-- لم نر this-- ولكن هناك كتل أخرى في ان هناك يمكن القول، إذا كنت لمس شيء آخر على الشاشة، إذا كنت لمس لوحة الزنبق "، ثم". ثم هذا عندما كنا تجعل الضفدع الثاني تظهر. ذلك على الرغم من هذه اللعبة هو بالتأكيد بتاريخ جدا، على الرغم من النظرة الأولى هناك الكثير الذهاب بليك on-- و لم سوط هذا الأمر في دقيقتين، وربما أخذته عدة ساعات لخلق هذه اللعبة بناء على ذاكرته أو أشرطة الفيديو النسخة الأمس منه. ولكن كل هذه الأشياء الصغيرة الذهاب على الشاشة في عزلة تختزل إلى هذه بسيطة جدا الحركات constructs-- أو بيانات كما ناقشناه، والحلقات الظروف، وذلك حول هذا الموضوع. هناك عدد قليل من السمات الأخرى مربي الحيوانات. بعض منهم بحتة جمالية أو الصوتية، مثل الأصوات لعبت فقط مع. ولكن بالنسبة للجزء الأكبر، كنت لدينا في هذه اللغة، خدش، كل الأساسية اللبنات التي تقوم يكون في C، جافا، جافا سكريبت، PHP، روبي، بيثون، وأي عدد من اللغات الأخرى. أي أسئلة حول الصفر؟ حسنا. لذلك نحن لن الغوص في أعمق للخدش، لو كنت موضع ترحيب في نهاية هذا الاسبوع، وخاصة إذا كان لديك أطفال أو بنات وأبناء وكذا، لتعريفهم خدش. انها في الواقع لعوب رائعة البيئة مع، كما يقول أصحابها، السقوف العالية جدا. على الرغم من أننا بدأنا مع جدا من التفاصيل على مستوى منخفض، يمكنك القيام به حقا لا بأس به مع ذلك، وهذا هو ربما مظاهرة من ذلك تماما. 

ولكن دعونا الآن ننتقل لبعض أكثر مشاكل معقدة، إذا صح التعبير، المعروفة باسم "البحث" و "الفرز،" بشكل عام. كان لدينا هذا الكتاب الهاتف earlier-- هنا واحد آخر فقط لdiscussion-- أننا كنا قادرين على البحث أكثر كفاءة ل من افتراض كبير. ومجرد أن يكون واضحا، ما كان الافتراض الأول جعل عند البحث من خلال هذا الكتاب الهاتف؟ أن كان مايك سميث في دفتر الهاتف، على الرغم من أنني سوف تكون قادرة على التعامل مع السيناريو بدونه هناك إذا أنا مجرد توقف قبل الأوان. هذا الكتاب هو الأبجدي. وهذا سخية جدا الافتراض، لأن ذلك يعني someone-- انا من النوع قطع زاوية، مثل أنا أسرع لشخص ما آخر فعل الكثير من العمل الشاق بالنسبة لي. 

ولكن ما إذا كان الهاتف تم فرزها الكتاب؟ ربما حصلت فيريزون كسول، ورمى فقط الجميع أسماء والأرقام في هناك ربما في الترتيب الذي وقعت لخدمة الهاتف. وكم من الوقت يستغرق لي للعثور على شخص مثل مايك سميث؟ book-- 1000 الهاتف الصفحة كم صفحات لا بد لي من البحث عن طريق؟ 

كل منهم. كنت نوعا من الخروج من الحظ. لديك حرفيا للنظر في كل الصفحة إذا كان الكتاب الهاتف فقط مرتبة بشكل عشوائي. قد تحصل على الحظ وتجد مايك على الصفحة الأولى للغاية، لأنه كان أول زبون لطلب خدمة الهاتف. لكنه قد يكون الأخير أيضا. 

لذلك بترتيب عشوائي ليست جيدة. لذلك نفترض أن لدينا لفرز دليل الهاتف أو في البيانات النوع العام أننا قد أعطيت. كيف يمكننا فعل ذلك؟ 

حسنا، اسمحوا لي أن مجرد محاولة مثال بسيط هنا. اسمحوا لي أن نمضي قدما وإرم أرقام قليلة على متن الطائرة. لنفترض أن الأرقام لدينا هي، دعنا نقول، أربعة، اثنان، واحد، وثلاثة. و، بن، فرز هذه الأرقام بالنسبة لنا. 

موافق، وحسن. كيف فعلت ذلك؟ حسنا. بحيث تبدأ مع أصغر قيمة وأعلى، وهذا هو حقا الحدس الجيد. وندرك أننا البشر هم جميلة فعلا جيدة في حل المشاكل مثل هذا، على الأقل عندما تكون البيانات صغير نسبيا. بمجرد البدء في الحصول على مئات من الأرقام، الآلاف من الأرقام، الملايين من الأرقام، بن ربما لا يمكن أن يفعل ذلك تماما بهذه السرعة، على افتراض أن هناك الفجوات في الأرقام. من السهل جدا أن العد إلى مليون خلاف ذلك، والوقت فقط المستهلكة. 

ولذلك فإن خوارزمية يشعرك مثل بن تستخدم فقط الآن كان البحث عن أصغر رقم. حتى على الرغم من أننا يمكن للانسان ان يأخذ في الكثير من المعلومات بصريا، جهاز كمبيوتر هو في الواقع أكثر من ذلك بقليل محدودة. الكمبيوتر لا يمكن إلا أن ننظر بايت واحد في وقت واحد أو ربما أربعة بايت في time-- في هذه الأيام ربما 8 بايت في time-- ولكن عدد قليل جدا بايت من في وقت معين. 

ذلك بالنظر إلى أن لدينا حقا أربع قيم منفصلة here-- ويمكن ان يخطر لك من بن وجود غمامات على لو كان جهاز الكمبيوتر هذا انه لا يستطيع رؤية أي شيء آخر من رقم واحد في time-- لذلك نحن عموما سوف نفترض، كما هو الحال في اللغة الإنجليزية، فإننا سوف تقرأ من اليمين إلى اليسار. وبالتالي فإن الرقم الأول بن ربما بدا في كان أربعة ثم بسرعة كبيرة أدركت هذا هو كبير جدا number-- اسمحوا لي أن مواصلة البحث. 

هناك اثنان. انتظر دقيقة. الثاني هو أصغر من أربعة. انا ذاهب الى تذكر. الثاني هو الآن أصغر. الآن احدا-- هذا أفضل. هذا هو أصغر من ذلك. انا ذاهب الى نسيان اثنين وتذكر فقط واحد الآن. 

ويمكنه التوقف عن النظر؟ حسنا، يمكن أن يستند على هذه المعلومات، ولكن عنيدا أفضل بحث بقية القائمة. لأن ما إذا الصفر كانت في القائمة؟ ماذا لو كانت سلبية واحدة في القائمة؟ انه يعرف فقط أن جوابه هو الصحيح اذا كان باستفاضة فحص اللائحة بأكملها. لذلك نحن ننظر في بقية هذا. Three-- التي كانت مضيعة للوقت. حصلت سيئ الحظ، لكني لم اكن لا تزال صحيحة للقيام بذلك. وحتى الآن كان يفترض اختيار أقل عدد ومجرد وضعها في بداية من القائمة، كما سأفعل هنا. الآن ماذا فعلتم بعد ذلك، على الرغم من أنك لم تفكر في ذلك ما يقرب من إلى هذا الحد؟ كرر هذه العملية، هكذا نوع من الحلقة. هناك فكرة مألوفة. حتى هنا هو أربعة. هذا هو حاليا أصغر. هذا المرشح. ليس بعد الآن. الآن رأيت اثنين. هذا هو التالي أصغر عنصر. Three-- هذا ليس أصغر، لذلك الآن بن يمكن أن أقتلع اثنين. 

والآن نكرر هذه العملية، و بالطبع يحصل سحبت ثلاثة من القادم. تكرار هذه العملية. يحصل سحبت أربعة من. والآن نحن من الأرقام، لذا يجب أن يتم فرز القائمة. 

وبالفعل، هذا هو خوارزمية الرسمية. عالم الكمبيوتر سوف نسمي هذا "نوع الاختيار، و" والفكرة هي نوع من قائمة iteratively-- مرة أخرى ومرارا وتكرارا اختيار أصغر رقم. وما هو لطيف عن ذلك هو انها فقط حتى بديهية الرتق. في غاية البساطة. ويمكنك تكرار نفس العملية مرة أخرى ومرة ​​أخرى. انه سهل. 

في هذه الحالة كان سريع، ولكن وكم من الوقت تأخذ في الواقع؟ دعونا جعل الأمر يبدو و يشعر أكثر قليلا مملة. حتى واحد، اثنان، ثلاثة، أربعة، خمسة ستة، سبعة، ثمانية، تسعة، 10، 11، 12، 13، 14، 15، 16-- عدد التعسفي. أردت فقط أكثر هذه الوقت من مجرد أربعة. حتى لو كنت قد حصلت على العموم مجموعة من الأرقام الآن-- ذلك حتى لا يهم ما are-- في السماح التفكير في ما هذا الخوارزمية هو مثل حقا. 

لنفترض أن هناك أعدادا هناك. مرة أخرى، لا يهم ما هم، لكنهم عشوائي. وأنا على تطبيق الخوارزمية بن ل. ولست بحاجة لتحديد أقل عدد. ماذا أفعل؟ وانا ذاهب الى جسديا تفعل ذلك هذه المرة للعمل بها. أبحث، أبحث، تبحث، وتبحث، وتبحث. فقط في الوقت أحصل على في نهاية القائمة يمكن وأنا أدرك أصغر كان عدد اثنين من هذا الوقت. واحد ليس في القائمة. لذلك أنا وضعت أسفل اثنين. 

ماذا أفعل بعد ذلك؟ أبحث، أبحث، أبحث، أبحث. الآن وجدت الرقم سبعة، ل هناك ثغرات في هذه numbers-- ولكن فقط تعسفية. حسنا. حتى الآن أستطيع اخماد سبعة. أبحث تبحث، وتبحث. 

الآن أفترض، من بطبيعة الحال، أن بن لا لديها ذاكرة إضافية، خارج الذاكرة، لأنه، بطبيعة الحال، أنا أبحث في نفس العدد. بالتأكيد كان يمكن أن تذكر كل من هذه الأرقام، وهذا صحيح تماما. ولكن إذا بن يتذكر كل الأرقام رآه، وقال انه لم تصدر حقا تقدم أساسي لأن لديه بالفعل القدرة على البحث من خلال الأرقام الموجودة على متنها. تذكر كل من الأرقام لا يساعد، لأنه يمكن لا يزال كجهاز كمبيوتر ننظر فقط في، قلنا، رقم واحد في وقت واحد. لذلك ليس هناك نوع من الغش هناك والتي يمكنك الاستفادة. 

حتى في واقع الأمر، وأنا إبقاء البحث في قائمة، لدي حرفيا للحفاظ على مجرد الذهاب ذهابا وإيابا من خلال ذلك، ونتف من في اليوم التالي أصغر رقم. وكما يمكنك النوع من الاستدلال من تحركاتي سخيفة، هذا يحصل فقط جدا مملة بشكل سريع جدا، ويبدو لي أن يذهب إلى الخلف و إيابا، ذهابا وإيابا لا بأس به. الآن لكي نكون منصفين، أنا لم يكن لديك للذهاب تماما كما، حسنا، دعونا see-- لكي نكون منصفين، أنا لم يكن لديك على المشي تماما العديد من الخطوات كما في كل مرة. لأنه، بطبيعة الحال، كما أنا اختيار الأرقام من القائمة، قائمة المتبقية هو الحصول على أقصر. 

وهكذا دعونا نفكر في عدد الخطوات وأنا فعلا التمشي من خلال كل الوقت. في الحالة الأولى جدا كان لدينا 16 أرقام، وهكذا maximally-- دعونا فقط تفعل هذا لdiscussion-- كان لي أن ننظر من خلال 16 أرقام للعثور على أصغر. ولكن مرة واحدة أنا وقلعوا أقل عدد، كيف وكان لفترة طويلة قائمة المتبقية، وبطبيعة الحال؟ فقط 15. فعلت ذلك عدد الأرقام بن أو لدي لننظر من خلال المرة الثانية؟ 15، لمجرد الذهاب والعثور على أصغر. ولكن الآن، وبطبيعة الحال، فإن القائمة، جدا، أصغر مما كان عليه من قبل. فكيف العديد من الخطوات فعلت أنا يجب أن تأخذ في المرة القادمة؟ 14 ثم 13 ثم 12، بالإضافة إلى نقطة، نقطة، نقطة، حتى أنا تركت مع واحد فقط. وحتى الآن من شأنه عالم الكمبيوتر نسأل، حسنا، ماذا يفعل ذلك جميعا على قدم المساواة؟ فإنه يساوي فعلا بعض الخرسانة الرقم الذي يمكننا بالتأكيد به حسابيا، ولكن نريد أن نتحدث حول كفاءة الخوارزميات أكثر من ذلك بقليل formulaically، بغض النظر عن متى القائمة. 

وحتى تعرف ماذا؟ هذا هو 16، ولكن كما قلت من قبل، دعونا مجرد دعوة حجم المشكلة n، حيث n هو عدد بعض. ربما حان 16، وربما انها ثلاثة، وربما انها المليون. انا لا اعرف. لا أهتم. ما أريد حقا هو صيغة يمكنني استخدامها لمقارنة هذه الخوارزمية ضد خوارزميات أخرى أن شخصا ما قد يدعي هي أفضل أو أسوأ من ذلك. 

لذلك تبين، وأنا فقط أعرف هذا من المدارس الابتدائية، أن هذا يعمل فعلا لنفسه شيء كما ن على ن زائد واحد أكثر من اثنين. ويحدث هذا على قدم المساواة، من بالطبع، ن تربيع زائد ن أكثر من اثنين. لذلك إذا أردت صيغة لكيفية العديد من الخطوات وشارك في النظر في جميع من هذه الأرقام مرة أخرى ومرة ​​أخرى ومرة أخرى، ومرة ​​أخرى، أود أن أقول انها المربعة ن بالإضافة إلى ن أكثر من اثنين. ولكن هل تعرف لماذا؟ هذا يبدو مجرد فوضى. أنا فقط حقا تريد الشعور العام من الأشياء. وتذكرون من المدرسة الثانوية أن هناك هو مفهوم الدرجة الأولى المدى. أي من هذه الشروط، ن مربع، ن، أو النصف، له أكبر الأثر على مر الزمن؟ ن أكبر يحصل، التي من هذه المسائل أكثر؟ 

وبعبارة أخرى، إذا كنت سد العجز في المليون، ن تربيع سيكون على الأرجح العامل المهيمن، لمليون مرة في حد ذاته هو أكبر بكثير من زائد واحد إضافي مليون. لذلك أنت تعرف لماذا؟ هذا هو مثل هذا الرتق كبيرة عدد إذا كنت تربيع عدد. هذا لا يهم حقا. نحن ذاهبون فقط عبر هذا من ونسيانها. وهكذا فإن عالم الكمبيوتر ويقول أن كفاءة هذه الخوارزمية هو بناء على أمر من ن squared-- أعني حقا تقريبي. والمربعة نوع تقريبا ن ذلك. مع مرور الوقت، وأكبر وأكبر ن يحصل، وهذا هو تقدير جيد لما كفاءة أو عدم كفاءة هذه الخوارزمية في الواقع. وأنا اشتقاق هذا، بطبيعة الحال، من فعل فعلا الرياضيات. ولكن الآن أنا مجرد التلويح يدي، لأنني فقط تريد الشعور العام من هذه الخوارزمية. 

وذلك باستخدام نفس المنطق، وفي الوقت نفسه، دعونا النظر خوارزمية أخرى نظرنا بالفعل at-- البحث الخطي. عندما كنت تبحث لbook-- الهاتف لا فرز ذلك، البحث من خلال book-- الهاتف حافظنا قائلا انه كان 1000 خطوات، أو 500 خطوة. ولكن دعونا تعميم ذلك. إذا كان هناك ن الصفحات في دفتر الهاتف، ما هو إدارة الوقت أو كفاءة البحث الخطي؟ انها على ترتيب عدد الخطوات لإيجاد مايك سميث باستخدام البحث الخطي، و الخوارزمية الأولى، أو حتى الثانية؟ 

في أسوأ الحالات، مايك هو في نهاية الكتاب. حتى إذا كان الكتاب يحتوي الهاتف على 1000 صفحة، قلنا آخر مرة، في أسوأ الأحوال، قد يستغرق ما يقرب كيف العديد من الصفحات للعثور مايك؟ مثل 1000. انها الحد الأعلى. إنها أسوأ حالة ممكنة. ولكن مرة أخرى، نحن نبتعد من أرقام مثل 1000 الآن. انها مجرد ن. 

فما هي النتيجة المنطقية؟ العثور مايك في الهاتف كتاب يتضمن صفحات ن قد تتخذ، في أسوأ حالة جدا، عدد الخطوات بناء على أمر من ن؟ وبالفعل جهاز كمبيوتر ان عالم يقول أن الوقت يعمل، أو أداء أو كفاءة أو عدم الكفاءة، خوارزمية مثل بحث الخطي هو بناء على أمر من ن. ويمكن أن نطبق نفس منطق عبور شيء كما فعلت في الثانية الخوارزمية التي أجريناها مع دفتر الهاتف، حيث ذهبنا صفحتين في وقت واحد. 

لذلك قد 1000 صفحة دليل الهاتف تأخذنا 500 المنعطفات صفحة، زائد واحد إذا ضاعفنا الى الوراء قليلا. حتى إذا كان الكتاب يحتوي الهاتف على صفحات ن، ولكن نقوم به صفحتين في وقت واحد، وهذا تقريبا ما؟ N على اثنين، ذلك أن مثل ن على اثنين. لكني اتخذت مطالبة لحظة قبل أن ن على two-- هذا النوع من نفس فقط ن. انها مجرد عاملا ثابتا، سوف يقول علماء الكمبيوتر. دعونا نركز فقط على المتغيرات، really-- أكبر المتغيرات في المعادلة. 

البحث الخطي لذلك، سواء فعل ذلك واحد الصفحة في وقت واحد أو صفحتين في وقت واحد، هو نوع من الأساس نفسه. انها لا تزال في حدود ن. لكن ادعيت مع صورة بلدي في وقت سابق أن الخوارزمية الثالثة لم تكن خطي. لم يكن خط مستقيم. كان عليه أن الخط المنحني، و وكان جبري صيغة هناك ما؟ سجل n-- ذلك تسجيل قاعدة اثنين من ن. ونحن لم يكن لديك للذهاب إلى غاية الكثير من التفاصيل على اللوغاريتمات اليوم، ولكن معظم علماء الكمبيوتر لن حتى ان اقول لكم ما هي القاعدة. لأن كل شيء فقط عوامل ثابتة، إذا جاز التعبير، مجرد اختلافات رقمية طفيفة. وهكذا سيكون هذا شائع جدا طريقة لجهاز رسمي ولا سيما العلماء في لوحة أو المبرمجين في لوحة بيضاء بحجة الواقع الذي خوارزمية أنهم سيستخدمون أو ما كفاءة من خوارزمية هي. 

وهذا ليس بالضرورة شيئا أن تناقش في أي بقدر كبير من التفصيل، لكن مبرمج الجيد هو شخص الذي لديه، الخلفية رسمية الصلبة. انه قادر على التحدث إلى كنت في هذا النوع من الطريق وجعل الواقع الحجج النوعية كما لماذا خوارزمية واحدة أو قطعة واحدة من البرمجيات متفوقة في بعض الطريق إلى أخرى. لأنك يمكن بالتأكيد فقط تشغيل البرنامج شخص واحد والاعتماد على عدد الثواني ما يلزم لفرز بعض الأرقام، ويمكنك تشغيل بعض برنامج الشخص الآخر وحساب عدد من الثواني الذي يستغرقه. ولكن هذا هو وسيلة أكثر العامة التي يمكنك استخدامها لتحليل الخوارزميات، اذا صح التعبير، فقط على ورق أو مجرد لفظيا. دون حتى تشغيله، دون حتى محاولة المدخلات العينة، يمكنك التفكير فقط من خلال ذلك. وحتى مع التعاقد مع المطور أو إذا وجود له أو لها نوعا من يقول لك لماذا خوارزمية، سرهم صلصة للبحث مليارات من صفحات الويب الخاصة بك الشركة هي أفضل، هذه هي أنواع الحجج التي يجب أن يكون مثاليا قادرا على القيام بها. أو هذه على الأقل هي أنواع الأشياء التي من شأنها أن تطرح في المناقشة، في الأقل في مناقشة رسمية جدا. حسنا. لذلك اقترح بن شيئا دعا اختيار نوع. ولكن انا ذاهب الى أقترح أن هناك طرق أخرى للقيام بذلك أيضا. ما لم يعجبني حقا حول خوارزمية بن ل غير أنه أبقى المشي، أو بعد أن لي المشي، ذهابا وإيابا وذهابا وإيابا وذهابا وإيابا. ماذا لو بدلا من ذلك كان علي أن أفعل شيء من هذا القبيل هذه الأرقام هنا وكان لي أن مجرد التعامل مع كل عدد بدورها كما أنا أعطيت ذلك؟ 

وبعبارة أخرى، من هنا قائمتي من الأرقام. أربعة، واحد، ثلاثة، اثنان. وانا ذاهب الى القيام بما يلي. أنا ذاهب لإدراج أرقام حيث تنتمي بالأحرى من اختيار واحد في وقت واحد. وبعبارة أخرى، وهنا رقم أربعة. 

وهنا قال لي القائمة الأصلية. وانا ذاهب للحفاظ على في الأساس قائمة جديدة هنا. لذلك هذا هو القائمة القديمة. هذه لائحة جديدة. أرى رقم أربعة لأول مرة. قائمتي جديدة في البداية فارغة، هكذا هو الحال بشكل مسلي أن أربعة من قائمة متنوعة الآن. أنا مجرد أخذ عدد انا معين، وأنا أضع في بلدي قائمة جديدة. 

يتم فرز هذه القائمة الجديدة؟ بلى. انه من الغباء لأنه لا يوجد واحد فقط عنصر، لكنها مرتبة على الاطلاق. لا يوجد شيء للخروج من المكان. انها أكثر إثارة للاهتمام، هذه الخوارزمية، عندما أنتقل إلى الخطوة التالية. 

الآن لدي واحدة. حتى واحد، وبطبيعة الحال، وينتمي في بداية أو نهاية لهذه القائمة الجديدة؟ البداية. لذلك لا بد لي من القيام ببعض الأعمال الآن. لقد تم اتخاذ بعض الحريات مع بلدي علامة فقط عن طريق رسم الأشياء حيث أريد لها، ولكن هذا ليس حقا دقيقة في جهاز الكمبيوتر. كمبيوتر، كما نعلم، لديها ذاكرة الوصول العشوائي، أو ذاكرة الوصول العشوائي، وهذا بايت واحد و البايت آخر والبايت آخر. وإذا كان لديك غيغا بايت من ذاكرة الوصول العشوائي، لديك مليار بايت، ولكنهم فعليا في مكان واحد. لا يمكنك فقط نقل الاشياء حول من خلال الاعتماد على لوحة أينما تريد. حتى إذا قائمتي الجديدة لديها أربعة مواقع في الذاكرة، للأسف الأربعة هو بالفعل في المكان الخطأ. 

لذلك لإدراج رقم واحد لا أستطيع مجرد رسم من هنا. عدم وجود هذا الموقع الذاكرة. من شأنه أن يكون الغش، ولقد كنت الغش بالصور لبضع دقائق هنا. ذلك حقا، إذا كنت ترغب في وضع واحد هنا، لدي نسخ أربعة مؤقتا ومن ثم وضع واحد هناك. 

هذا شيء طيب، وهذا هو الصحيح، أن من الممكن من الناحية الفنية، ولكن ندرك أن هذا العمل الإضافي. لم أكن مجرد وضع الرقم في المكان. كان أول من نقل عدد، ثم وضعها في المكان، لذلك النوع من الضعف مبلغ عملي. حتى أن تبقي في الاعتبار. 

ولكن أنا الآن القيام به مع هذا العنصر. الآن أريد أن انتزاع المركز الثالث. حيث، بطبيعة الحال، وأنها لا تنتمي؟ ما بين أثنين. لا أستطيع خداع بعد الآن ومجرد وضعها هناك، لأنه، مرة أخرى، هذه الذاكرة في المواقع المادية. لذلك لا بد لي من نسخ الأربعة ووضع ثلاثة أكثر من هنا. لا صفقة كبيرة. انها مجرد خطوة واحدة اضافية يشعر again-- غير مكلفة للغاية. 

ولكن الآن أن أنتقل إلى اثنين. وهما، بالطبع، وينتمي هنا. الآن أن تبدأ في رؤية كيف العمل يمكن أن تتراكم. الآن ماذا علي أن أفعل؟ نعم، لا بد لي من نقل أربعة، وبعد ذلك يكون لنسخ الثلاث، والآن أستطيع أن إدراج اثنين. والصيد مع هذا الخوارزمية، ومن المثير للاهتمام، هو أن نفترض أن لدينا أكثر تطرفا الحالة حيث انها دعنا نقول ثمانية، سبعة، ستة، خمسة، أربعة، ثلاثة، اثنان، واحد. وهذا هو، في العديد من السياقات، أسوأ سيناريو، لأن الشيء الرتق هو حرفيا إلى الوراء. 

أنه لا حقا تؤثر خوارزمية بن ل، لأنه في اختيار بن ل نوع انه ذاهب للحفاظ على ذهابا وإيابا من خلال القائمة. ولأنه كان يبحث دائما من خلال قائمة الباقية كلها، لا يهم حيث العناصر. ولكن في هذه الحالة مع بلدي ادخال approach-- دعونا نحاول هذا. 

حتى واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة، ثمانية. واحد إثنان ثلاثة أربعة، خمسة، ستة، سبعة، ثمانية. انا ذاهب الى اتخاذ الثمانية، وأين وضعه؟ حسنا، في بداية قائمتي، لأنه يتم فرز هذه القائمة الجديدة. وأعبر بها. 

أين أضع السبعة؟ الرتق ذلك. فإنه يحتاج إلى الذهاب إلى هناك، لذلك لا بد لي من القيام ببعض النسخ. والآن سبعة يذهب هنا. الآن أن أنتقل إلى ستة. الآن حان المزيد من العمل. 

ثمانية ديه للذهاب هنا. سبعة أن يذهب هنا. الآن الست يمكن أن تذهب هنا. الآن أنا الاستيلاء على خمسة. الآن ثمانية ديه للذهاب هنا، سبعة أن يذهب هنا، ستة أن يذهب هنا، و الآن خمسة وتكرار. وأنا الى حد كبير تحريكه باستمرار. 

لذلك في النهاية، هذا algorithm-- سنقوم نسميها الإدراج sort-- الواقع لديه الكثير من العمل أيضا. انها مختلفة تماما النوع من العمل من وبن. وكان لعمل بن لذهابي ذهابا وإيابا في كل وقت، اختيار بجوار أصغر العنصر مرة أخرى ومرة ​​أخرى. لذلك كان هذا النوع البصري جدا من العمل. 

هذه الخوارزمية الأخرى، التي لا تزال correct-- أنها سوف تحصل على وظيفة done-- مجرد تغييرات كمية العمل. يبدو في البداية كنت إنقاذ، لأنك فقط التعامل مع كل عنصر في خط الهجوم دون المشي كل كانت الطريق من خلال قائمة مثل بن. ولكن المشكلة هي، لا سيما في هذه الحالات مجنون حيث كل شيء الى الوراء، كنت مجرد نوع من تأجيل العمل الشاق حتى يكون لديك لتصحيح أخطائك. 

وحتى إذا كان يمكنك أن تتخيل هذا ثمانية وسبعة وستة وخمسة وبعد أربعة وثلاثة واثنين تتحرك في طريقهم من خلال القائمة، لقد غيرت فقط نوع من العمل الذي نقوم به. بدلا من القيام بذلك في ابتداء من بلدي التكرار، أنا فقط أفعل ذلك في نهاية كل التكرار. لذلك تبين أن هذه الخوارزمية، أيضا، وتسمى عادة الإدراج النوع، هو أيضا بناء على أمر من ن المربعة. انها في الواقع ليست أفضل، ليست أفضل على الإطلاق. 

ومع ذلك، هناك نهج ثالث وأود أن أشجع منا أن نفكر: وهو هذا. لذلك نفترض قائمتي، عن البساطة مرة أخرى، أربعة، واحد، ثلاثة، two-- أربعة أرقام فقط. وكان بن حدس جيد، الحدس البشري جيد من قبل، ونحن هنا الثابتة كلها قائمة eventually-- الإدراج الفرز. أنا أقنع لنا على طول. ولكن دعونا النظر في أبسط طريقة لإصلاح هذه القائمة. 

لا يتم فرز هذه القائمة. لماذا؟ في اللغة الإنجليزية، وشرح لماذا انها ليست مرتبة في الواقع. ما لا يعني أن مرتبة؟ 

الطالب: انها ليست متسلسلة. 

DAVID مالان: غير متسلسلة. اعطني مثال. 

الطالب: وضعها في النظام. 

DAVID مالان: موافق. أعطني مثالا أكثر تحديدا. 

الطالب: تصاعدي ترتيب. DAVID مالان: غير ترتيب تصاعدي. أن تكون أكثر دقة. أنا لا أعرف ماذا تقصد ب تصاعدي. ماالخطب؟ 

الطالب: أصغر من الأرقام ليست في الفضاء الأول. 

DAVID مالان: أصغر عدد من وليس في الفضاء الأول. كن أكثر تحديدا. أنا بدأت للقبض على. نحن كنت أعول، ولكن ما هو خارج الترتيب هنا؟ 

الطالب: التسلسل العددي. DAVID مالان: التسلسل العددي. نوع الجميع من حفظ ذلك here-- مستوى عال جدا. قل لي حرفيا ما هو خطأ مثل القوة البالغ من العمر خمس سنوات. 

الطالب: زائد واحد. 

DAVID مالان: ما هذا؟ 

الطالب: زائد واحد. 

DAVID مالان: ماذا تقصد زائد واحد؟ أعطني مختلفة البالغ من العمر خمس سنوات. ما هو الخطأ، أمي؟ ما هو الخطأ، يا أبي؟ ماذا يعني هذا غير مصنفة؟ 

الطالب: انها ليست المكان المناسب. 

DAVID مالان: ما هو ليس في المكان المناسب؟ 

الطالب: أربعة. DAVID مالان: موافق، وحسن. حتى أربعة ليس حيث ينبغي أن يكون. على وجه الخصوص، هل هذا صحيح؟ أربعة واحد، الأول رقمين أرى. هل هذا صحيح؟ لا، انهم خارج الترتيب، أليس كذلك؟ في الواقع، أعتقد الآن حول جهاز كمبيوتر، أيضا. ويمكن أن ننظر فقط في ربما واحدة، ربما شيئين في once-- والواقع شيء واحد فقط في وقت واحد، ولكن يمكن على الأقل ننظر في شيء واحد ثم الشيء التالي الحق بجانبه. 

هكذا هي هذه في النظام؟ بالطبع لا. لذلك أنت تعرف لماذا؟ لماذا لا نأخذ الطفل خطوات إصلاح هذه المشكلة بدلا من القيام بهذه الهوى خوارزميات مثل بن، حيث انه نوع من تحديد ذلك من قبل حلقات عبر قائمة بدلا من أن يفعل ما فعلت، حيث أنا مجرد نوع من أنها ثابتة ونحن نمضي؟ دعونا فقط كسر حرفيا أسفل فكرة الترتيب العددي order--، يطلق عليه مهما كنت want-- في هذه المقارنات البشرى. 

أربعة واحد. هل هذا هو الترتيب الصحيح؟ لذلك دعونا تحديد ذلك. واحد وأربعة، ثم سنقوم مجرد نسخ ذلك. كل الحق، وحسن. أنا ثابت واحد وأربعة. ثلاثة واثنين؟ لا. السماح كلماتي تطابق أصابعي. أربعة وثلاثة؟ 

انها ليست في النظام، لذلك أنا ذاهب لفعل واحد، ثلاثة، أربعة، اثنين. موافق، وحسن. الآن أربعة واثنان؟ نحن بحاجة إلى إصلاح هذا أيضا. حتى واحد، ثلاثة، اثنان، أربعة. لذلك فإنه مرتبة؟ لا، ولكن هل هو أقرب إلى مرتبة؟ 

هو عليه، لأننا إصلاح هذا خطأ، ونحن إصلاح هذا الخطأ، ونحن إصلاح هذا الخطأ. لذلك نحن الثابتة ثلاثة أخطاء يمكن القول. لا يزال لا تبدو حقا فرزها، ولكن هو أقرب موضوعية فرزها لأننا إصلاح بعض من تلك الأخطاء. 

الآن ماذا أفعل بعد ذلك؟ النوع الأول من وصل إلى نهاية القائمة. وبدا لي أن الثابتة كل الأخطاء، ولكن لا. لأنه في هذه الحالة، بعض الأرقام قد انفجر حتى أقرب إلى أرقام أخرى لا تزال خارج الترتيب. لذلك دعونا نفعل ذلك مرة أخرى، وسوف أكون مجرد القيام بذلك في المكان هذه المرة. واحد وثلاثة؟ أنها على ما يرام. ثلاثة واثنين؟ بالطبع لا، لذلك دعونا تغيير ذلك. حتى سنتين أو ثلاث. ثلاثة وأربعة؟ والآن دعونا نكون فقط متحذلق هنا بشكل خاص. هل مرتبة؟ كنت البشر يعرفون كل شيء فرزها. 

أود أن حاول مرة أخرى. حتى أوليفيا يقترح أحاول مرة أخرى. لماذا؟ بسبب عدم توفر جهاز كمبيوتر ترف العين البشرية لدينا من نظرة عابرة فقط موافق back--، أنا فعلت. كيف يحدد الكمبيوتر أن يتم فرز القائمة الآن؟ ميكانيكيا. 

أود أن تذهب من خلال مرة أخرى، وإلا إذا أنا لا تجعل / العثور على أي أخطاء يمكنني ثم تختتم في الكمبيوتر، نعم، نحن على ما يرام. حتى واحد واثنين، واثنين و ثلاثة، ثلاثة وأربعة. الآن أستطيع أن أقول بشكل قاطع هذا هو فرزها، لأنني إجراء أية تغييرات. الآن سيكون خطأ وفقط أحمق لو كنت، الكمبيوتر، سألت هذه الأسئلة نفسها مرة أخرى تتوقع إجابات مختلفة. لا ينبغي أن يحدث. 

وحتى الآن يتم فرز القائمة. للأسف، تشغيل وقت وN أيضا تربيع هذه الخوارزمية. لماذا؟ لأن لديك أرقام ن، وفي أسوأ حال كان لديك لنقل أعداد ن ن مرات لأنه لديك على الاستمرار العودة إلى تحقق وربما إصلاح هذه الأرقام. ويمكننا أن نفعل أكثر تحليل رسمي أيضا. 

لذلك هذا هو كل شيء أن أقول لقد اتخذنا ثلاثة مناهج مختلفة، واحدة منهم بديهية فورا قبالة الخفافيش من بن إلى بلدي الإدراج المقترح الفرز لهذا واحد أين أنت نوع من فقدان البصر الغابة للأشجار في البداية. ولكن بعد ذلك إذا كنت تأخذ خطوة إلى الوراء، فويلا، لقد حددت فكرة الفرز. لذلك هذا هو، أجرؤ على القول، مستوى أدنى ربما من بعض الأشخاص الذين لا الخوارزميات، ولكن دعونا نرى ما اذا كنا لا يمكن تصور هذه عن طريق هذا. 

لذلك هذا هو بعض لطيفة البرامج التي شخص كتب باستخدام قضبان الملونة هذا الذهاب إلى القيام بما يلي بالنسبة لنا. كل من هذه القضبان يمثل عددا. أطول شريط، وأكبر عدد وأصغر شريط، أصغر رقم. حتى من الناحية المثالية نريد الهرم لطيفة حيث يبدأ صغيرا ويحصل كبيرة، وهذا يعني أن يتم فرز هذه القضبان. لذلك أنا ذاهب إلى المضي قدما واختيار، على سبيل المثال، خوارزمية بن ل first-- نوع الاختيار. 

وتلاحظ ما تقوم به. الطريقة التي اخترتها لل تصور هذه الخوارزمية غير أنه، مثلما كنت المشي من خلال قائمتي، هذا البرنامج هو المشي من خلال قائمتها للأرقام، تسليط الضوء باللون الوردي كل الرقم الذي كان يبحث في. وما هو على وشك أن يحدث الآن؟ 

أصغر رقم أنا أو بن جدت فجأة يحصل انتقل إلى بداية القائمة. ولاحظ فعلوا نزع الرقم الذي كان هناك، وهذا على ما يرام تماما. أنا لم نصل إلى ذلك المستوى من التفصيل. ولكن نحن بحاجة إلى وضع هذا العدد في مكان ما، لذلك نحن مجرد نقله إلى بقعة المفتوحة التي تم إنشاؤها. لذلك أنا ذاهب لتسريع هذه يصل، لأن خلاف ذلك يصبح مملة جدا بسرعة. الرسوم المتحركة speed-- هناك نذهب. وحتى الآن نفس المبدأ كنت تطبيق، ولكنك يمكن أن تبدأ في الشعور الخوارزمية، إذا كنت صح التعبير، أو ترى أنها أكثر قليلا بشكل واضح. وهذه الخوارزمية لديه تأثير اختيار أصغر عنصر المقبل، حتى وأنت تسير لبدء ل نرى ذلك تكثيف الناحية اليسرى. وعلى كل التكرار، وأنا المقترح، فإنه لا أقل قليلا العمل. فإنه ليس من الضروري أن يذهب كل في طريقه العودة إلى الطرف الأيسر من القائمة، لأنه بالفعل يعرف يتم فرز تلك. لذلك النوع من يشعر وكأنه انها تسريع، على الرغم من كل خطوة أخذ نفس المقدار من الوقت. هناك فقط عدد أقل من الخطوات المتبقية. والآن يمكنك نوع من الشعور الخوارزمية تنظيف نهاية لها، والواقع الآن هو فرزه. 

لذلك الإدراج النوع هو كل ذلك. أنا بحاجة إلى إعادة عشوائية-المصفوفة. وتلاحظ يمكنني فقط الحفاظ التعشءه ذلك، وسوف نحصل على شكل تقريبي ل نفس النهج، إدراج النوع. اسمحوا لي أن تبطئ خطاها إلى هنا. دعونا نبدأ أن أكثر. توقف. 

دعونا تخطي الأربعة. هناك نذهب. بطريقة عشوائية أنها مجموعة. وهنا نحن go-- الإدراج الفرز. لعب. لاحظ أنه يتعامل مع كل العنصر أنه واجه على الفور، ولكن إذا كان ينتمي في والخطأ إشعار مكان كل من العمل الذي يجب أن يحدث. علينا أن نحافظ على تحويل المزيد والمزيد من العناصر لجعل الغرفة لواحد ونحن نريد أن نضع في المكان. 

لذلك نحن نركز على الطرف الأيسر من القائمة فقط. لاحظ أننا لم حتى بدا at-- نحن لم سلط عليها الضوء في أي شيء وردي إلى اليمين. نحن فقط التعامل مع المشاكل ونحن نمضي، ولكننا خلق الكثير من العمل من أجل أنفسنا لا يزال. وحتى إذا كنا إسراع بهذا، الآن للذهاب إلى الانتهاء، لديها شعورا مختلفا لأنه في الواقع. انها مجرد التركيز على الطرف الأيسر ولكن القيام بمزيد من العمل أقل قدر needed-- نوع من الأشياء تمهيد على، وتحديد الأشياء، لكن التعامل في نهاية المطاف مع كل عنصر واحد في وقت واحد حتى نصل الى the-- جيدا، ونحن نعلم جميعا كيف أن هذا سوف ينتهي، لذلك فمن مخيب قليلا ربما. 

لكن القائمة في end-- spoiler-- سوف يتم فرزها. لذلك دعونا ننظر في واحد واحد آخر. لا يمكننا تخطي ذلك الآن. كدنا نصل. اثنين للذهاب، واحدة للذهاب. وفويلا. ممتاز. 

حتى الآن دعونا نفعل واحدة واحدة الماضي، إعادة العشوائي مع نوع فقاعة. ويلاحظ هنا، وخاصة إذا أنا بطيء عليه أسفل، وهذا لا تبقي الإنقضاض من خلال. ولكن لاحظ أنه يجعل من مجرد زوجيا نوع comparisons-- الحلول المحلية. ولكن بمجرد أن نصل إلى في نهاية القائمة باللون الوردي، ما يحدث لدينا أن يحدث مرة أخرى؟ نعم، انها ستكون لدينا ل البدء من جديد، لأنه فقط الأخطاء البشرى ثابتة. والتي قد يكشف بعد عن الآخرين. وحتى إذا كنت تسريع هذا الأمر، عليك نرى أنه، بقدر ما يوحي الاسم، أصغر elements-- أو بالأحرى، وelements-- أكبر بدأت إلى فقاعة تصل إلى أعلى، إذا صح التعبير. والعناصر الأصغر بدأت فقاعة أسفل إلى اليسار. والواقع، أن هذا النوع من المؤثرات البصرية أيضا. وحتى هذا سوف ينتهي الانتهاء بطريقة مماثلة جدا، جدا. 

ليس لدينا ليسكن على هذا واحد بعينه. اسمحوا لي أن فتح هذا الآن، أيضا. هناك عدد قليل من خوارزميات الفرز أخرى في العالم، وعدد قليل منها يتم التقاطها هنا. وخصوصا للمتعلمين الذين ليسوا بالضرورة البصرية أو الرياضية، كما فعلنا من قبل، نستطيع أيضا القيام بذلك audially إذا كان لنا أن ربط الصوت مع هذا. وفقط من أجل المتعة، وهنا بعض خوارزميات مختلفة، واحد منهم على وجه الخصوص كنت الذهاب يسمى إشعار "دمج النوع". 

هو في الواقع متعصبون لجوهر أفضل الخوارزمية، مثل أن دمج النوع، واحدة من تلك التي على وشك أن نرى، ليس ترتيب ن المربعة. انها على ترتيب n مرة سجل ن، الذي هو في الواقع أصغر، وبالتالي أسرع من هؤلاء الثلاثة الأخرى. وهناك اثنين آخرين سخيفة تلك التي سنرى. 

حتى هنا نذهب مع بعض الصوت. هذا هو ترتيب بالإدراج، لذلك مرة أخرى انها مجرد التعامل مع العناصر كما أنها تأتي. هذا هو فقاعة النوع، لذلك فمن معتبرة إياها أزواج في وقت واحد. ومرة أخرى، أكبر عناصر وظهرت على السطح تصل إلى أعلى. 

اختيار المقبل حتى الفرز. هذا هو خوارزمية بن، حيث مرة أخرى انه اختيار تكراري في اليوم التالي أصغر عنصر. ومرة أخرى، الآن يمكنك سماع حقا أن انها تسريع ولكن فقط بقدر ما كما يفعل أقل وأقل العمل على كل التكرار. هذا هو أسرع واحد، ودمج النوع، وهو فرز مجموعات من أرقام معا ومن ثم الجمع بينهما. حتى look-- اليسار يتم فرز نصف بالفعل. 

الآن انها فرز النصف الأيمن، و الآن انها سوف الجمع بينهما في واحد. وهذا هو ما يسمى "غنوم النوع." ويمكنك نوع من يرى أن انها تسير ذهابا وإيابا، تحديد العمل هنا قليلا و هناك قبل أن يشرع في عمل جديد. وهذا كل شيء. هناك نوع آخر، وهو حقا فقط للأغراض الأكاديمية، ودعا "نوع من الغباء"، والذي يأخذ البيانات الخاصة بك، يفرز بشكل عشوائي، ومن ثم يتحقق إذا تم فرزه. وإذا لم يكن، فإنه re-يفرز ذلك عشوائيا، يتحقق إذا هو فرزه، وإذا لم يكرر. ونظريا، احتماليا سيكتمل، ولكن بعد قدرا كبيرا من الوقت. انها ليست أكثر كفاءة الخوارزميات. لذلك أي أسئلة على تلك خوارزميات أو أي شيء خاصة المرتبطة هناك، أيضا؟ 

حسنا، دعونا ندف الآن باستثناء ما كل هذه الخطوط هي التي كنت رسم وما أفترض الكمبيوتر يمكن القيام به تحت غطاء محرك السيارة. أنا أزعم أن كل هذه الأرقام وأظل drawing-- ما يحتاجونه للوصول تخزينها في مكان ما في الذاكرة. سنقوم نتخلص من هذا الرجل الآن، أيضا. 

حتى قطعة من الذاكرة في computer-- ذلك RAM DIMM غير ما بحثنا عن أمس، مزدوج ذاكرة مضمنة module-- يشبه هذا. ولكل من هذه الرقائق السوداء الصغيرة هو بعض عدد من وحدات البايت، وعادة. ثم دبابيس الذهب هي مثل الأسلاك التي توصيله إلى جهاز الكمبيوتر، ومجلس السيليكون الأخضر هو فقط ما يبقي كل شيء معا. فماذا يعني هذا حقا؟ إذا أنا نوع من رسم هذه الصورة نفسها، دعونا نفترض لبساطة أن هذا DIMM، مزدوج وحدة الذاكرة المضمنة، هو واحد غيغا بايت من ذاكرة الوصول العشوائي، واحد غيغا بايت من الذاكرة، والذي هو كيف كثير من مجموع بايت؟ واحد غيغا بايت المهم هو كم بايت؟ اكثر من ذلك. 1124 هو كيلو، 1000. ميجا هو مليون. جيجا هو مليار. 

أنا الكذب؟ حتى يمكننا قراءة الملصق؟ هذا هو في الواقع 128 غيغا بايت، لذلك هو أكثر من ذلك. ولكننا سوف نتظاهر هذا هو واحد غيغا بايت فقط. وهذا يعني هناك مليار بايت من الذاكرة المتاحة لي أو 8000000000 بت، ولكن نحن في طريقنا في الحديث من حيث بايت الآن، التحرك إلى الأمام. 

ذلك ما يعنيه ذلك هو هذا بايت واحد، وهذا هو البايت آخر، هذا هو البايت آخر، وإذا كنا نريد حقا أن تكون محددة سيكون لدينا ل رسم قليلا مليار الساحات. ولكن ماذا يعني ذلك؟ حسنا، اسمحوا لي أن التكبير في على هذه الصورة. إذا كنت قد حصلت على شيء يبدو مثل هذا الآن، وهذا هو أربعة بايت. 

وحتى أتمكن من وضع أربعة أرقام هنا. واحد إثنان ثلاثة أربعة. أو يمكن أن أضع أربعة أحرف أو رموز. "مهلا!" يمكن أن تذهب هناك حق، لأن كل من الحروف، ناقشنا في وقت سابق، يمكن أن تكون ممثلة مع ثمانية بت أو ASCII أو بايت. لذلك وبعبارة أخرى، يمكنك وضع 8000000000 الأشياء داخل من هذه عصا واحدة من الذاكرة. الآن ماذا يعني ذلك لوضع الأمور مرة أخرى إلى العودة إلى الوراء في الذاكرة مثل هذا؟ هذا هو ما مبرمج سيدعو الى "مجموعة". في برنامج كمبيوتر، كنت لا أعتقد حول الأجهزة الأساسية، في حد ذاته. كنت مجرد التفكير في نفسك وجود الوصول إلى ما مجموعه مليار بايت، ويمكنك أي شيء تريده معها. ولكن للراحة انها مفيدة بشكل عام للحفاظ على حق الذاكرة الخاصة بك بجانب بعضها البعض مثل هذا. حتى لو كنت التكبير في this-- لأننا بالتأكيد لن رسم قليلا مليار squares-- دعونا نفترض أن هذا المنتدى يمثل أن عصا الذاكرة الآن. وأنا مجرد رسم ما يصل الى بلدي علامة ينتهي إعطائي هنا. حتى الآن لدينا عصا من الذاكرة على متن الطائرة وهذا ما حصل واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، seven-- حتى 42 بايت الذاكرة على مجموعه الشاشة. شكرا. نعم، فعلت بلدي الحساب حق. حتى 42 بايت من الذاكرة هنا. فماذا يعني ذلك في الواقع؟ حسنا، وهو مبرمج كمبيوتر لو فعلا عموما التفكير في هذه الذاكرة كما عنونة. وبعبارة أخرى، كل واحد من هؤلاء مواقع في الذاكرة، في الأجهزة، لديه عنوان فريد. 

انها ليست معقدة كما واحدة براتل مربع، كامبريدج، ماساشوستس، 02138. بدلا من ذلك، انها مجرد عدد. هذا هو بايت الرقم صفر، وهذا هو واحد، وهذا هو اثنين، وهذا هو ثلاثة، وهذا هو 41. انتظر دقيقة. فكرت قلت 42 قبل لحظة. أنا بدأت العد من الصفر، ذلك أن الصحيح في الواقع. الآن ليس لدينا لاستدراجه في الواقع على شكل شبكة، وإذا كنت استدراجه كشبكة أعتقد أن الأمور في الواقع الحصول على مضللة بعض الشيء. ما من شأنه مبرمج، في عقله أو عقلها الخاص، أعتقد عموما من هذا الذاكرة كما هو تماما مثل الشريط، مثل قطعة من اخفاء الشريط الذي يذهب فقط وإلى الأبد أو حتى نفاد الذاكرة. ولذلك فإن الطريقة الأكثر شيوعا لرسم ومجرد التفكير في الذاكرة سوف يكون هذا هو صفر بايت، واحد، اثنان، ثلاثة، ثم نقطة، نقطة، نقطة. وكان لديك 42 هذه بايت الكلي، حتى على الرغم من جسديا قد فعلا يكون شيئا أكثر من هذا القبيل. 

لذلك إذا كنت تعتقد الآن من الخاصة بك الذاكرة عن هذا، تماما مثل الشريط، هذا هو ما مبرمج جديد سيدعو مجموعة من الذاكرة. وعندما تريد تخزين الواقع شيء ما في ذاكرة جهاز الكمبيوتر، كنت عادة تفعل أشياء مخزن ، ظهر إلى ظهر إلى ظهر إلى ظهر. لذلك كنا نتحدث عن الأرقام. وعندما أردت أن حل المشاكل مثل أربعة، واحد، ثلاثة، اثنان، على الرغم من أنني كنت مجرد رسم فقط الأرقام أربعة، واحد، ثلاثة، اثنين على متن الطائرة، من شأنه الكمبيوتر حقا هذا الإعداد في الذاكرة. 

وماذا سيكون بجانب اثنين في ذاكرة الكمبيوتر؟ حسنا، ليس هناك إجابة على ذلك. نحن لا نعرف حقا. وطالما أن الكمبيوتر لا حاجة إليها، لم يكن لديك لرعاية ما هو القادم إلى أرقام فإنه لا يهتمون. وعندما قلت في وقت سابق ان الكمبيوتر يمكن أن ننظر فقط في عنوان واحد في وقت واحد، هذا هو نوع من السبب. 

لا يختلف رقما قياسيا لاعب ورأس القراءة القدرة على النظر في بعض فقط الأخدود في سجل المدرسة القديمة البدني في وقت واحد، وبالمثل يمكن لجهاز الكمبيوتر بفضل إلى وحدة المعالجة المركزية، ولها مجموعة التعليمات إنتل، بين الذين تعليمات قراءة من الذاكرة أو حفظ لmemory-- ل الكمبيوتر يمكن أن ننظر فقط في مكان واحد في time-- أحيانا مزيجا منها، ولكن الموقع في الحقيقة مجرد واحد في وقت واحد. حتى عندما كنا نفعل هذه الخوارزميات المختلفة، أنا لست مجرد الكتابة في vacuum-- أربعة، واحد، ثلاثة، اثنان. هذه الأرقام ينتمون فعلا في مكان ما المادي في الذاكرة. لذلك هناك القليل الصغير الترانزستورات أو نوع من الالكترونيات تحت غطاء تخزين هذه القيم. 

وبشكل إجمالي، كم من البتات تشارك في الوقت الراهن، لمجرد أن يكون واضحا؟ لذلك هذا هو أربعة بايت، أو الآن حان مجموعه 32 بت. لذلك هناك في الواقع 32 الأصفار و منها تتكون هذه الأمور الأربعة. هناك أكثر حتى هنا، ولكن مرة أخرى نحن لا يهمني ذلك. 

لذلك اسمحوا الآن نسأل أخرى السؤال باستخدام الذاكرة، لأنه في نهاية اليوم في التباين. بغض النظر عن ما يمكن أن تفعله مع على جهاز الكمبيوتر، في نهاية اليوم الأجهزة لا تزال نفسه تحت غطاء محرك السيارة. كيف يمكنني تخزين كلمة هنا؟ حسنا، كلمة في الكمبيوتر مثل "مهلا!" سيتم تخزينها فقط من هذا القبيل. وإذا أردت أطول كلمة، يمكنك ببساطة الكتابة التي وأقول شيئا مثل "مرحبا" وتخزين ذلك هنا. 

وحتى هنا، أيضا، هذا التلامس هو في الواقع ميزة، لأنه يمكن لجهاز الكمبيوتر فقط قراءتها من اليمين إلى اليسار. ولكن هنا سؤال. في سياق هذه الكلمة، ح-ل-ه-ل-س، تعجب، كيف يمكن معرفة الكمبيوتر حيث كلمة تبدأ وأين تنتهي الكلمة؟ في سياق الأرقام، كيف يمكن للكمبيوتر أعرف كم من الوقت تسلسل الأرقام هي أو أين يبدأ ذلك؟ حسنا، فإنه يتحول out-- ونحن لن نذهب كثيرا إلى هذا المستوى من detail-- أجهزة الكمبيوتر تتحرك الاشياء حولها في الذاكرة حرفيا عن طريق هذه العناوين. حتى في الكمبيوتر، وإذا كنت كتابة التعليمات البرمجية لتخزين الأشياء مثل الكلمات، ما كنت به حقا هو كتابة التعبيرات التي نتذكر فيها في ذاكرة الكمبيوتر هذه الكلمات. لذلك اسمحوا لي أن تفعل جدا، مثال بسيط جدا. 

انا ذاهب الى المضي قدما و فتح برنامج نصي، وانا ذاهب الى خلق ملف يسمى hello.c. معظم هذه المعلومات نحن لن أخوض في بقدر كبير من التفصيل، ولكن انا ذاهب لكتابة برنامج في تلك اللغة نفسها، C. وهذا أبعد ما يكون أكثر ترهيبا، أنا أزعم، من الصفر، لكنه مشابه جدا في الروح. في الواقع، هذه مجعد braces-- يمكنك نوع من التفكير في ما أنا فقط كما فعل هذا. 

دعونا نفعل ذلك، في الواقع. وعندما ينقر العلم الأخضر، اعمل كالآتي. أريد أن طباعة "مرحبا". لذلك هذا هو الآن شبة الكود. انا من النوع طمس الخطوط. في C، هذه اللغة أنا أتحدث حول، هذا الخط طباعة مرحبا يصبح في الواقع "printf" مع بعض الأقواس ومنقوطة. 

ولكن انها نفس الفكرة بالضبط. وهذا جدا سهل الاستعمال "عندما ينقر العلم الأخضر" يصبح أكثر غامضة كثيرا "الفراغ الرئيسي كثافة العمليات." وهذا في الحقيقة لا رسم الخرائط، لذلك أنا ذاهب لمجرد تجاهل ذلك. لكن الأقواس المعقوفة هي مثل قطع اللغز المنحنية مثل هذا. 

حتى تتمكن من نوع من التخمين. حتى لو كنت قد برمجت لم يحدث من قبل، ماذا يعني هذا البرنامج ربما تفعل؟ يطبع ربما مرحبا مع علامة تعجب. 

لذلك دعونا نحاول ذلك. أنا ذاهب لحفظه. وهذا هو، مرة أخرى، جدا البيئة المدرسية القديمة. لا أستطيع انقر، وأنا لا يمكن سحب. ولا بد لي من كتابة الأوامر. لذلك أريد أن تشغيل برنامج بلدي، لذلك وأود أن تفعل هذا، مثل hello.c. هذا الملف ركضت. ولكن مهلا، أنا في عداد المفقودين خطوة. ما فعله نقوله هو ضروري خطوة للغة مثل C؟ لقد كتبت للتو مصدر الرمز، ولكن ما الذي أحتاجه؟ نعم، أنا بحاجة إلى مترجم. لذلك على بلدي ماك هنا، ولدي برنامج يسمى دول مجلس التعاون الخليجي، GNU C مترجم، والذي يسمح لي أن تفعل this-- بدوره قانون بلدي المصدر إلى، ونحن سوف يطلق عليه، كود الآلة. 

وأستطيع أن أرى ذلك، مرة أخرى، على النحو التالي، هذه هي الآحاد والأصفار وأنا فقط التي تم إنشاؤها من شفرة المصدر الخاص بي، كل من الآحاد والأصفار و. وإذا كنت ترغب في تشغيل بلدي program-- يحدث ليتم استدعاؤها a.out ل reasons-- التاريخية "مرحبا". يمكنني تشغيله مرة أخرى. اهلا اهلا اهلا. ويبدو أن العمل. 

ولكن هذا يعني في مكان ما في بلدي ذاكرة الكمبيوتر هي عبارة ح-ه-ل-ل-س، تعجب. وكما تبين، تماما كما جانبا، ما من شأنه كمبيوتر عادة ذلك أنه يعرف أين تبدأ الامور وend-- انها الذهاب لوضع رمز خاص هنا. والاتفاقية هي لوضع الرقم صفر في نهاية الكلمة حتى يتسنى لك معرفة أين ينتهي في الواقع، حتى يتسنى لك لا تبقي طبع أكثر وأكثر شخصيات من كنت تنوي فعلا. 

ولكن الوجبات الجاهزة هنا، حتى وإن كان هذا هو غامضة إلى حد ما، غير أنه في نهاية المطاف بسيط نسبيا. أعطيت لك نوعا من الشريط، فارغة الفضاء الذي يمكنك كتابة الرسائل. لديك لمجرد أن يكون رمز خاص، مثل تعسفا الرقم صفر، لوضع نهاية لل كلماتك بحيث يعرف الكمبيوتر، أوه، يجب أن إيقاف الطباعة بعد أرى أن تعجب. لأن الشيء القادم هناك هي قيمة ASCII من الصفر، أو حرف خالية كما شخص ما من شأنه يطلق عليه. ولكن هناك نوع من مشكلة هنا، ودعونا تعود مرة أخرى إلى أرقام لحظة. لنفترض أن أفعل، في الواقع، لدينا مجموعة من الأرقام، ونفترض أن برنامج أنا أكتب هو مثل كتاب الصف للمعلم والفصول الدراسية المعلمين. وهذا البرنامج يسمح له أو لها لكتابة عشرات طلابهم على الاختبارات. ونفترض أن الطالب يحصل 100 في أول اختبار، وربما مثل 80 على واحد القادم، ثم 75، ثم 90 في مسابقة الرابعة. 

حتى في هذه النقطة في القصة، مجموعة ذات حجم الأربعة. هناك المزيد من الاطلاق الذاكرة في الكمبيوتر، ولكن مجموعة، إذا جاز التعبير، هي من الحجم الأربعة. لنفترض الآن أن المعلم يريد تعيين مسابقة الخامسة إلى الفئة. حسنا، واحدة من الأشياء التي كان أو أنها في طريقها إلى القيام به هو الآن تخزين قيمة إضافية هنا. ولكن إذا كان مجموعة من المعلمين لديها التي تم إنشاؤها في هذا البرنامج هو من حجم، واحد من المشكلة مع مجموعة هو أن لا يمكنك فقط الحفاظ على إضافة إلى الذاكرة. لأن ما إذا كان جزء آخر من البرنامج لديه كلمة "يا" هناك حق؟ 

وبعبارة أخرى، يمكن أن ذاكرتي يكون استخدامها في أي شيء في هذا البرنامج. وإذا مقدما أنا كتبته في، مهلا، أريد لإدخال أربع درجات المسابقة، أنها قد تذهب هنا وهنا. وإذا كنت فجأة غيرت رأيك في وقت لاحق، ويقول أريد مسابقة الخامسة النتيجة، لا يمكنك فقط وضعه في أي مكان تريد، لأن ما إذا كان هذا ويجري استخدام الذاكرة عن شيء else-- بعض البرامج الأخرى أو بعض ميزة أخرى من البرنامج ان كنت تستخدم؟ ولذلك عليك أن تفكر مقدما كيف تريد لتخزين البيانات الخاصة بك، لأنه الآن كنت قد رسمت نفسك في زاوية الرقمية. 

حتى يمكن المعلم بدلا من ذلك يقول عند كتابة برنامج لتخزين له أو لها الدرجات، وانت تعرف ماذا؟ وانا ذاهب لطلب، عند كتابة برنامجي، الذي أريد صفر، واحد، اثنان، ثلاثة، مجموع أربعة، خمسة، ستة، ثمانية درجات. حتى واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة، ثمانية. يمكن للمدرس أن ما يزيد قليلا عن تخصص الذاكرة عند الكتابة له أو لها برنامج وأقول، أنت تعرف لماذا؟ أنا أبدا لتعيين أكثر من ثماني مسابقات في الفصل الدراسي. هذا مجرد مجنون. أنا لن تخصيص ذلك. ذلك أن هذه الطريقة هو أو هي لديه المرونة لعشرات مخزن طالب، مثل 75، 90، وربما واحد إضافي حيث حصل الطالب رصيد إضافي و 105. 

ولكن إذا كان المعلم أبدا يستخدم هذه المساحات الثلاث، هناك على الوجبات الجاهزة بديهية هنا. هو أو هي مجرد إضاعة الفضاء. لذلك وبعبارة أخرى، هناك هذا المقايضة مشتركة في البرمجة حيث يمكنك تخصيص إما بالضبط قدر الذاكرة كما تريد، الاتجاه الصعودي الذي هو أنك السوبر efficient-- كنت عدم الإسراف في all-- ولكن الجانب السلبي منها هو ما إذا غيرت رأيك عندما باستخدام البرنامج الذي تريد تخزين المزيد من البيانات مما كنت أصلا. 

ولذلك ربما يكون الحل هو، إذن، كتابة البرامج الخاصة بك في مثل هذه الطريقة التي يستخدمونها المزيد من الذاكرة مما يحتاجون فعلا. بهذه الطريقة أنت لن لتشغيل إلى هذه المشكلة، ولكن كنت يجري الإسراف. والمزيد من الذاكرة يستخدم البرنامج الخاص بك، كما ناقشنا أمس، وأقل الذاكرة التي تتوفر لغيرها من البرامج، وكلما قد يبطئ جهاز الكمبيوتر الخاص بك أسفل بسبب الذاكرة الظاهرية. وبالتالي فإن الحل الأمثل قد يكون ماذا؟ 

تحت تخصيص يبدو سيئا. الإفراط في تخصيص يبدو سيئا. وذلك ما قد يكون أفضل حل؟ إعادة تخصيص. تكون أكثر ديناميكية. لا تجبر نفسك على اختيار بداهة، في البداية، ما تريد. وبالتأكيد لا الإفراط في تخصيص، لئلا يكون الإسراف. 

وذلك لتحقيق هذا الهدف، ونحن تحتاج إلى رمي هذه البنية البيانات، إذا جاز التعبير، بعيدا. وماذا في ذلك مبرمجا وعادة ما تستخدم وما يسمى يست مجموعة ولكن قائمة مرتبطة. وبعبارة أخرى، وقال انه أو انها سوف البدء في التفكير في ذاكرتهم بأنها نوع من الشكل الذي كانوا يمكن رسم على النحو التالي. إذا أريد لتخزين رقم واحد في وprogram-- لذلك فمن سبتمبر لقد منحت طلابي مسابقة. انا اريد لتخزين مسابقة الأولى للطلاب، وأنها حصلت على 100 على it-- أنا انا ذاهب الى طرح جهاز الكمبيوتر الخاص بي، عن طريق برنامج عندي مكتوب لقطعة واحدة من الذاكرة. وانا ذاهب لتخزين عدد 100 في ذلك، وهذا كل شيء. 

بعد أسابيع ثم بضع عندما أحصل على بلدي مسابقة الثانية، وحان الوقت لكتابة في ذلك 90٪، وانا ذاهب أن تطلب من جهاز الكمبيوتر، مهلا، الكمبيوتر، يمكن أن لدي قطعة أخرى من الذاكرة؟ انها سوف تعطيني هذا قطعة فارغة من الذاكرة. أنا ذاهب لوضعها في عدد 90، ولكن في برنامجي بطريقة أو بأخرى أو other-- ونحن لن تقلق بناء الجملة من أجل this-- أحتاج إلى حد ما سلسلة هذه الأشياء معا. وسوف سلسلة معا مع ما يشبه السهم هنا. 

هذه المسابقة الثالثة التي تأتي، انا ذاهب الى القول، مهلا، الكمبيوتر، تعطيني قطعة أخرى من الذاكرة. وانا ذاهب الى اخماد مهما كان، مثل 75، ولقد لسلسلة هذه معا الآن بطريقة أو بأخرى. مسابقة الرابعة تأتي جنبا إلى جنب، وربما هذا هو في نهاية الفصل الدراسي. وهذه النقطة برنامجي قد يكون استخدام الذاكرة في كل مكان، في جميع أنحاء جسديا. وذلك فقط لركلات، وأنا الذهاب إلى رسم هذا إيابا quiz-- أنسى ما كان عليه. أنا أعتقد ربما 80 أو something-- طريقة أكثر من هنا. 

لكن لا بأس، لأن بالصور انا ذاهب الى رسم هذا الخط. وبعبارة أخرى، في الواقع، في جهاز الكمبيوتر الخاص بك، النتيجة الأولى قد ينتهي الأمر هنا لأنه الحق في بداية الفصل الدراسي. قد تنتهي المرحلة التالية هنا لأن قليلا من الوقت قد مر والبرنامج يبقى قيد التشغيل. النتيجة التالية، التي كانت 75، قد يكون أكثر من هنا. والنتيجة الأخيرة قد تكون 80، والتي هي أكثر من هنا. 

حتى في واقع الأمر، جسديا، وهذا قد يكون ما تبدو ذاكرة الكمبيوتر الخاص بك مثل. ولكن هذه ليست عقلية مفيدة نموذج لمبرمج كمبيوتر. لماذا يجب أن يهمك فيها هيك بياناتك ينتهي بهم المطاف؟ كنت ترغب فقط لتخزين البيانات. 

هذا هو نوع من مثل مناقشتنا في وقت سابق من رسم مكعب. لماذا يهمني ما كانت الزاوية من المكعب وكيف يجب أن تتحول لاستدراجه؟ كنت ترغب فقط في المكعب. وبالمثل هنا، فقط أريد أن كتاب الصف. كنت ترغب فقط في التفكير في هذا كقائمة من الأرقام. من يهتم كيف أنها تنفذ في الأجهزة؟ 

لذا فإن التجريد الآن هي هذه الصورة هنا. هذا هو قائمة مرتبطة، كما سيكون مبرمجا يطلق عليه، بقدر ما لديك قائمة، من الواضح من الأرقام. لكنها مرتبطة بالصور عن طريق هذه الأسهم، وجميع هذه الأسهم are-- تحت غطاء محرك السيارة، إذا كنت غريبة، نذكر أن لدينا الأجهزة الفعلي له عناوين صفر، واحد، اثنان، ثلاثة، أربعة. كل هذه السهام هي أشبه خريطة أو الاتجاهات، حيث إن 90 أعرف، الآن حصلت على الاعتماد. 

صفر، واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة. يبدو أن 90 هو في ذاكرة عنوان الرقم سبعة. كل هذه السهام هي هي مثل قصاصة صغيرة من الورق وهذا ما يعطي توجيهات لل البرنامج الذي تقول اتبع هذه الخريطة للوصول الى موقع سبعة. وهناك سوف تجد نتيجة مسابقة الثانية الطالب. وفي الوقت نفسه، 75-- إذا ما زلت هذا، هذا هو سبعة، ثمانية، تسعة، 10، 11، 12، 13، 14، 15. 

هذا السهم الآخر يمثل فقط خريطة لموقع الذاكرة 15. ولكن مرة أخرى، مبرمج لا عادة لا يهمني هذا المستوى من التفصيل. وفي معظم كل البرمجة لغة اليوم، مبرمج لن تعرف حتى مكان في الذاكرة هذه الأرقام هي في الواقع. كل ديه أو لديها إلى يهمني هو أنها ترتبط بطريقة أو بأخرى معا في بنية بيانات من هذا القبيل. 

ولكن تبين عدم للحصول على التقنية أيضا. ولكن فقط لأننا يمكن ربما تحمل أن يكون هذا النقاش هنا، لنفترض أن نعيد النظر هذه المسألة هنا من صفيف. دعونا نرى ما اذا كنا نأسف الذهاب هنا. هذه هي 100، 90، 75، و 80. 

اسمحوا لي أن فترة وجيزة هذا الادعاء. هذا هو مجموعة، ومرة ​​أخرى، السمة البارزة لمجموعة غير أن جميع البيانات الخاصة بك عاد ل العودة إلى الوراء في memory-- حرفيا بايت واحد أو ربما أربعة بايت، بعض عدد محدد من وحدات البايت بعيدا. في قائمة مرتبطة، ونحن قد رسم مثل هذا، تحت غطاء محرك السيارة الذي يعرف أين هذه الأشياء هو؟ بل لا تحتاج إلى تدفق مثل هذا. بعض البيانات يمكن أن يكون إلى اليسار هناك. حتى أنك لا تعرف. 

وذلك مع مجموعة، لديك ميزة يعرف الوصول العشوائي. وما وسائل الوصول العشوائي غير أن الكمبيوتر يمكن القفز على الفور إلى أي مكان في صفيف. لماذا؟ لأنه يعرف الكمبيوتر أن الموقع الأول صفر، واحد، اثنان، وثلاثة. 

وحتى إذا كنت تريد أن تذهب من هذا العنصر إلى العنصر التالي، لكم حرفيا، في عقل الكمبيوتر، فقط إضافة واحد. إذا كنت ترغب في الذهاب إلى العنصر الثالث، فقط إضافة احدا-- العنصر التالي، فقط أضف واحدا. ومع ذلك، في هذا الإصدار من القصة، لنفترض تبحث حاليا الكمبيوتر في أو التعامل مع عدد 100. كيف تحصل على التالي الصف في كتاب الصف؟ 

عليك أن تأخذ سبع الخطوات، التي هي تعسفية. للوصول الى المرحلة التالية، لديك ل اتخاذ ثماني خطوات أخرى للوصول الى 15. وبعبارة أخرى، انها ليست الفجوة المستمرة بين الأرقام، وهكذا فإنه يأخذ فقط الكمبيوتر مزيدا من الوقت هو نقطة. يحتوي جهاز الكمبيوتر للبحث من خلال الذاكرة من أجل للعثور على ما كنت أبحث عنه. 

ذلك في حين أن مجموعة يميل إلى أن يكون ل structure-- البيانات بسرعة لأنك يمكن حرفيا مجرد القيام بعملية حسابية بسيطة ونصل الى حيث تريد عن طريق إضافة واحدة، لinstance-- قائمة مرتبطة، تضحي هذه الميزة. لا يمكنك الذهاب فقط من البداية الى المركز الثاني إلى المركز الثالث الى المركز الرابع. عليك أن تتبع الخريطة. لديك لاتخاذ المزيد من الخطوات للوصول الى تلك القيم، التي يبدو أن إضافة تكلفة. لذلك نحن ندفع الثمن، ولكن ما كان الميزة التي دان كان يسعى هنا؟ ماذا قائمة مرتبطة على ما يبدو تسمح لنا القيام به، الذي كان أصل هذه القصة؟ 

بالضبط. وحجم الديناميكي لذلك. ويمكننا أن نضيف إلى هذه القائمة. حتى يمكننا تقليص قائمة، لذلك أننا فقط باستخدام قدر الذاكرة كما نريد فعلا وهكذا نحن أبدا الإفراط في تخصيص. 

الآن لمجرد أن يكون أحمق من الصعب إرضاءه حقا، هناك تكاليف خفية. لذلك يجب أن لا فقط اسمحوا لي أن يقنع لك أن هذا هو المقايضة مقنعة. هناك تكاليف خفية أخرى هنا. صالح، أن تكون واضحة، غير أن نحصل على ديناميكية. إذا كنت تريد عنصر آخر، يمكنني فقط استدراجه ووضع عدد من هناك. وبعد ذلك يمكن ربطه مع صورة هنا، في حين أن أكثر من هنا، مرة أخرى، إذا كنت قد حوصرت في زاوية، إذا كان هناك شيء آخر يستخدم بالفعل الذاكرة هنا، وأنا من الحظ. لقد رسمت نفسي في الزاوية. 

ولكن ما هو المستور تكلف في هذه الصورة؟ انها ليست مجرد مبلغ من الوقت الذي يستغرقه للانتقال من هنا إلى هنا، وهي سبع خطوات، ثم ثماني خطوات، التي هي أكثر من واحد. ما هي تكاليف خفية أخرى؟ لا وقت فقط. المعلومات الإضافية ضروري لتحقيق هذه الصورة. 

نعم، تلك الخريطة، تلك قصاصات صغيرة من ورقة، وأظل اصفا إياها ب. هذه arrows-- تلك ليست حرة. وcomputer-- تعلمون ما لديه جهاز كمبيوتر. لديها الآحاد والأصفار و. إذا كنت تريد أن تمثل سهم أو خريطة أو عدد، كنت بحاجة الى بعض الذاكرة. وبالتالي فإن السعر الأخرى التي دفع للحصول على قائمة مرتبط، علم الكمبيوتر المشتركة الموارد، هو أيضا الفضاء. 

والواقع جدا، لذلك عادة، بين المفاضلات في تصميم هندسة البرمجيات نظم وقتا وspace-- وهما من المكونات الخاصة بك، وهما من المكونات الأكثر تكلفة. هذا يكلف لي المزيد من الوقت لاني اريد ان اتبع هذه الخريطة، ولكن هذا يكلف لي أيضا مساحة أكبر لأن لدي للحفاظ على هذه الخريطة حولها. لذلك الأمل، كما قمنا نوع من ناقش خلال أمس واليوم، غير أن الفوائد سوف تفوق التكاليف. 

ولكن ليس هناك حل واضح هنا. ربما هو better-- سريع لوس انجليس وقذرة، كما اقترح كريم earlier-- لرمي الذاكرة في المشكلة. مجرد شراء المزيد من الذاكرة، والتفكير أقل مليا حل المشكلة، وحلها بطريقة أسهل. وبالفعل في وقت سابق، عندما تحدثنا عن المفاضلات، لم يكن الفضاء في الكمبيوتر والوقت. كان الوقت قد حان المطور، الذي هو بعد مورد آخر. 

ذلك مرة أخرى، هو هذا التوازن تحاول أن تقرر أي من تلك الأشياء هل أنت على استعداد لقضاء؟ وهو أقل تكلفة؟ التي تعطي نتائج أفضل؟ بلى؟ 

في الواقع. في هذه الحالة، إذا كنت تمثل الأرقام في maps-- وتسمى هذه في العديد من اللغات "مؤشرات" أو "عناوين" - انها ضعف مساحة. أن لا يلزم أن يكون سيئا كما ضعف إذا الآن نحن فقط تخزين الأرقام. لنفترض أننا كنا تخزين سجلات المرضى في hospital-- حتى أسماء بيرسون، وأرقام الهواتف، أرقام الضمان الاجتماعي، الطبيب التاريخ. قد يكون هذا المربع الكثير، أكبر من ذلك بكثير، في هذه الحالة مؤشر الصغير للغاية، عنوان element-- المقبل انها ليست صفقة كبيرة. انها مثل هامشية تكلفة لا يهم. ولكن في هذه الحالة، نعم، انها مضاعفة. سؤال جيد. 

دعونا نتحدث عن وقت ل قليلا أكثر تحديدا. ما هي إدارة الوقت من البحث في هذه القائمة؟ لنفترض أنني أريد أن ابحث من خلال جميع الدرجات للطلاب، وهناك درجات ن في هذا الهيكل البيانات. هنا، أيضا، يمكننا أن الاقتراض مفردات في وقت سابق. هذا هو هيكل البيانات الخطية. 

يا كبير من ن غير ما هو مطلوب للحصول على في نهاية هذا الهيكل البيانات، whereas-- ولم نر هذا before-- مجموعة يعطيك ما يسمى وقت ثابت، وهو ما يعني خطوة واحدة أو خطوتين أو 10 steps-- لا يهم. إنه رقم ثابت. عليها أن تفعل مع أي شيء حجم المصفوفة. والسبب في ذلك، مرة أخرى، هو الوصول العشوائي. الكمبيوتر يمكن فقط على الفور القفز إلى موقع آخر، لأنهم كل نفس المسافة من كل شيء آخر. ليس هناك تفكير المعنية. حسنا. حتى لو كنت تستطيع، واسمحوا لي أن أحاول ل ترسم صورتين النهائية. واحد شائع جدا تعرف باسم جدول تجزئة. وذلك لتحفيز هذه المناقشة، اسمحوا لي أن التفكير في كيفية القيام بذلك. 

فكيف هذا؟ لنفترض أن المشكلة نريد أن نحل الآن تنفذ في dictionary-- حتى في مجمله مجموعة من الكلمات الإنجليزية أو أيا كان. والهدف هو أن تكون قادرا على الإجابة أسئلة النموذج هو هذا الكلمة؟ لذلك كنت ترغب في تنفيذ المدقق الإملائي، فقط مثل القاموس البدني التي يمكن أن ننظر الامور في. أفترض أن نفعل هذا مع صفيف. يمكنني أن أفعل هذا. 

وافترض أن الكلمات هي التفاح والموز والشمام. وأنا لا أستطيع التفكير في الفواكه التي تبدأ مع د، لذلك نحن فقط ستكون لدينا ثلاثة الفواكه. لذلك هذا هو صفيف، ونحن تخزين كل هذه الكلمات في هذا القاموس كما صفيف. والسؤال إذن هو كيف آخر هل يمكن تخزين هذه المعلومات؟ 

حسنا، أنا نوع من الغش هنا، ل كل من هذه الحروف في كلمة هو في حقيقة الأمر بايت الفردية. لذلك إذا أردت حقا أن تكون أحمق من الصعب إرضاءه، ينبغي لي حقا يتم تقسيم هذا الأمر في كثير قطع أصغر من الذاكرة، ونحن يمكن ان نفعل ذلك بالضبط. ولكن ونحن في طريقنا لتصل الى نفس المشكلة كما كان من قبل. ماذا لو، وميريام وبستر أو أكسفورد يفعل كل year-- يضيفون كلمات إلى dictionary-- نحن لا نريد بالضرورة أن ترسم أنفسنا في زاوية مع مجموعة؟ 

بدلا من ذلك، ربما نهجا أكثر ذكاء هو وضع التفاح في العقدة الخاصة أو مربع، كما نقول، والموز، و ثم لدينا هنا الشمام. ونحن سلسلة هذه الأشياء معا. لذلك هذا هو مجموعة، و هذه هي قائمة مرتبطة. إذا كنت لا تستطيع رؤية جدا، هو فقط وتقول "مجموعة"، وهذا يقول "قائمة". 

لذلك لدينا نفس قضايا بالضبط كما كان من قبل، حيث لدينا الآن ديناميكية في قائمة مرتبطة لدينا. ولكن لدينا قاموس بطيئة إلى حد ما. لنفترض أنني أريد للبحث عن كلمة واحدة. قد يستغرق لي يا كبير من ن الخطوات، لأن الكلمة قد يكون كل وسيلة في نهاية القائمة، مثل الشمام. واتضح أن في البرمجة، نوع من الكأس المقدسة من البيانات الهياكل، شيء والتي تمنحك ثابت الوقت مثل مجموعة ولكن هذا لا يزال يمنحك الحيوية. 

بحيث يمكن لدينا أفضل من كلا العالمين؟ وبالفعل، هناك شيء دعا جدول التجزئة هذا يسمح لك أن تفعل بالضبط هذا، وإن كان ما يقرب من. جدول التجزئة هو مربي الحيوانات هيكل البيانات التي لدينا يمكن التفكير في مثل مزيج من array-- وانا ذاهب لاستدراجه مثل this-- والقوائم المرتبطة أنني سوف يوجه مثل هذا أكثر من هنا. 

وطريقة هذا الشيء يعمل هو على النحو التالي. إذا كانت هذه الآن-- تجزئة table-- هو بلدي بنية بيانات الثالث، وأريد أن تخزين كلام في هذا، وأنا لا تريد فقط تخزين جميع الكلمات العودة إلى الوراء إلى العودة إلى الوراء. أريد أن الاستفادة من بعض جزء من معلومة حول الكلمات التي سوف تسمح لي الحصول عليها حيث أنها أسرع. 

ذلك نظرا لكلمات التفاح والموز والشمام، أنا اختار عمدا تلك الكلمات. لماذا؟ ما هو نوع من الأساس مختلف عن الثلاثة؟ ما هو واضح؟ وهي تبدأ بأحرف مختلفة. 

لذلك أنت تعرف لماذا؟ بدلا من وضع كل كلامي في نفس دلو، إذا جاز التعبير، كما هو الحال في لائحة واحدة كبيرة، لماذا لا أنا على الأقل في محاولة لتحسين وجعل القوائم بلدي 1/26 طالما. والأمثل مقنعة قد يكون السبب لا I-- عند إدخال كلمة في هذا الهيكل البيانات، في ذاكرة الكمبيوتر، لماذا لا أضع كل "أ" الكلمات هنا، جميع 'ب' الكلمات هنا، وجميع 'ج' الكلمات هنا؟ لذلك هذا ينتهي وضع تفاحة هنا، الموز هنا والشمام هنا، وهكذا دواليك. 

وإذا كان لدي مبلغ إضافي كلمة like-- ما هو آخر؟ التفاح والموز والكمثرى. أي شخص يفكر في الفاكهة الذي يبدأ ب أ، ب، أو ج؟ الكمال Blueberry--. الذي لن ينتهي هنا. وهكذا يبدو لنا أن لديها هامشي أفضل حل، لأنه الآن إذا كنت تريد للبحث عن التفاح، وأنا first-- أنا فقط لا الغوص في بنية البيانات الخاصة بي. أنا لا يغوص في ذاكرة جهاز الكمبيوتر الخاص بي. أنا أولا ننظر إلى الحرف الأول. 

وهذا هو ما كمبيوتر ان عالم يقول. يمكنك تجزئة في بنية البيانات الخاصة بك. كنت تأخذ المدخلات الخاصة بك، والتي في هذه الحالة هي كلمة مثل التفاح. كنت نحللها، وتبحث في أول حرف في هذه الحالة، وبالتالي تجزئة عليه. التجزئة هو حيث العام المدى كنت تأخذ شيئا كمدخل وكنت تنتج بعض الانتاج. وخرج في ذلك القضية هي المكان تريد البحث، الأول المكان، والمكان الثاني، الثالث. لذلك المدخل هو التفاح، الإخراج هو أولا. المدخل هو الموز، و يجب أن يكون الناتج الثاني. المدخل هو الشمام، يجب أن يكون الإخراج الثالث. المدخل هو عنبية، ل الناتج ينبغي أن تكون مرة أخرى الثانية. وهذا ما يساعدك على اتخاذ اختصارات من خلال الذاكرة الخاصة بك من أجل الحصول على كلمات أو البيانات بشكل أكثر فعالية. 

الآن هذه التخفيضات عصرنا يحتمل بنسبة تصل إلى واحد من أصل 26، لأنه إذا افترض أن ل لدينا العديد من "أ" كلمات ب "ض" كلمات ككلمات "س"، التي لا realistic-- حقا وأنت تسير أن يكون الانحراف عبر رسائل معينة من alphabet-- ولكن هذا سيكون بشكل تدريجي، النهج الذي لا تسمح لك للحصول على الكلمات بسرعة أكثر من ذلك بكثير. وفي الواقع، متطورة برنامج، وغوغل من العالم، وFacebooks من world-- انها ستستخدم جدول تجزئة لكثير من الأغراض المختلفة. لكنها لن تكون السذاجة بحيث لمجرد إلقاء نظرة على الحرف الأول في التفاح أو الموز أو الكمثرى أو الشمام، لأنه كما ترون هذه قوائم يمكن الحصول على ما زالت طويلة. 

وحتى هذا قد يكون لا يزال الفرز من linear-- ذلك نوع من البطء، كما هو الحال مع يا كبير من ن أن ناقشنا في وقت سابق. ذلك ما سوف طاولة الحقيقي التجزئة جيدة do-- سيكون لها مجموعة أكبر من ذلك بكثير. وسوف تستخدم أكثر من ذلك بكثير وظيفة التجزئة متطورة، بحيث لا مجرد إلقاء نظرة على "أ." ربما يبدو في "لف ف-ل-ه" و بطريقة ما يحول تلك الأحرف الخمسة إلى الموقع حيث يجب أن يتم تخزين التفاح. نحن فقط بسذاجة باستخدام حرف "أ" وحده، لأنه لطيف وبسيط. 

لكن جدول تجزئة، في في النهاية، يمكنك التفكير من حيث أن مجموعة مجموعة، كل واحدة منها لديه قائمة مرتبط بشكل مثالي يجب أن تكون قصيرة قدر الإمكان. وهذه ليست الحل واضح. في الواقع، فإن الكثير من ضبط ما يدور تحت غطاء محرك السيارة عندما تنفيذ هذه الأنواع من هياكل البيانات المتطورة ما هو الحق طول المصفوفة؟ ما هي وظيفة تجزئة الصحيحة؟ كيف يمكنك تخزين الأشياء في الذاكرة؟ 

ولكن ندرك مدى سرعة هذا النوع من النقاش تصاعدت، إما حتى الآن أنه من نوع أكثر من واحد في الرأس عند هذه النقطة، التي على ما يرام. ولكن بدأنا، أذكر، مع حقا شيء على مستوى منخفض والإلكترونية. وحتى هذا مرة أخرى هذا موضوع التجريد، حيث بمجرد البدء في اتخاذ ل منح، حسنا، لقد حصلت على it-- هناك الذاكرة الفعلية، موافق، وحصلت عليه، كل الموقع الجغرافي لديه عنوان، حسنا، أنا حصلت عليه، ويمكن أن تمثل هذه العناوين كما arrows-- يمكنك البدء بسرعة جدا أن يكون محادثات أكثر تطورا أن في النهاية يبدو أن يسمح لنا لحل مشاكل مثل البحث والفرز بشكل أكثر فعالية. وتطمئن، too-- لأنني أعتقد أن هذا هو أعمق انتقلنا إلى بعض من هذه المواضيع CS proper-- قمنا يتم في يوم واحد ونصف في هذا نقطة ما قد تفعل عادة على خلال ثمانية أسابيع في فصل دراسي. 

أي أسئلة حول هذه؟ لا؟ حسنا. حسنا، لماذا لا نتوقف هناك، بدء الغداء بضع دقائق في وقت مبكر، استئناف في غضون ساعة تقريبا؟ وسوف إغلاقه ل قليلا مع الأسئلة. ثم انا ذاهب لدينا للذهاب تأخذ المكالمات الزوجين إذا كان هذا هو موافق. أنا تشغيل بعض الموسيقى في هذه الأثناء، ولكن الغداء ينبغي أن يكون قاب قوسين أو أدنى.