>> DAVID ลัน: สิทธิทั้งหมด
พวกเรากลับมาแล้ว.
ดังนั้นในส่วนนี้ในการเขียนโปรแกรมสิ่งที่ ผมคิดว่าเราจะทำคือการผสมผสานของสิ่งต่างๆ
หนึ่งทำนิ​​ด ๆ หน่อย บางสิ่งบางอย่าง Hands-on,
แม้จะใช้ขี้เล่นมากขึ้น environment-- การเขียนโปรแกรม
หนึ่งที่บ่งชี้ของ ตรงชนิดของความคิด
เราได้รับการพูดคุยเกี่ยวกับ แต่เล็ก ๆ น้อย ๆ อย่างเป็นทางการ
สองดูที่บางส่วนของ วิธีการทางเทคนิคเพิ่มเติม
ที่เป็นโปรแกรมเมอร์จริงจะแก้ ปัญหาเช่นปัญหาในการค้นหา
ที่เรามองที่ก่อนและ นอกจากนี้ยังมีพื้นฐานมากขึ้น
ปัญหาที่น่าสนใจของการเรียงลำดับ
>> เราเพียง แต่สันนิษฐานว่าจากที่ได้รับไป ว่าหนังสือเล่มโทรศัพท์ที่ได้รับการจัดเรียง
แต่ที่อยู่คนเดียวเป็นจริงชนิดของ ปัญหาหนักด้วยวิธีการที่แตกต่างกัน
จะแก้ปัญหาได้
ดังนั้นเราจะใช้เหล่านี้เป็น ระดับของปัญหา
ตัวแทนของสิ่งที่ อาจได้รับการแก้ไขโดยทั่วไป
และจากนั้นเราจะพูดคุย เกี่ยวกับในรายละเอียดบางสิ่ง
จะเรียกว่าข้อมูล structures-- วิธีที่นักเล่นเช่นรายการเชื่อมโยง
และตารางแฮชและต้นไม้ที่ โปรแกรมเมอร์จะจริง
การใช้งานและโดยทั่วไปใช้ บนไวท์บอร์ดในการวาด
ภาพของสิ่งที่เขาหรือเธอ วาดภาพสำหรับการดำเนินการ
ชิ้นส่วนของซอฟต์แวร์บาง
>> เพื่อขอทำมือในส่วนแรก
ดังนั้นเพียงแค่ได้รับในมือของคุณสกปรกกับ สภาพแวดล้อมที่เรียกว่า scratch.mit.edu
นี้เป็นเครื่องมือที่เราใช้ ในชั้นเรียนระดับปริญญาตรีของเรา
แม้ว่าจะได้รับการออกแบบ สำหรับทุกวัย 12 ขึ้นไป
เราใช้มันสำหรับขึ้น ส่วนหนึ่งของที่ไม่น้อย
เพราะมันเป็นความสุขสนุกสนาน ทางกราฟิกของการเรียนรู้
บางสิ่งบางอย่างเล็ก ๆ น้อย ๆ เกี่ยวกับการเขียนโปรแกรม
ดังนั้นมุ่งหน้าไปยัง URL ที่ที่คุณ จะเห็นหน้ามากเช่นนี้
และไปข้างหน้าและคลิก เข้าร่วมกับรอยขีดข่วนที่มุมขวาบน
และเลือกชื่อผู้ใช้และ รหัสผ่านและในที่สุดได้รับตัวเอง
account-- scratch.mit.edu
ฉันคิดว่าฉันใช้นี้เป็น โอกาสแรกที่แสดงนี้
คำถามขึ้นมาในช่วงพัก เกี่ยวกับสิ่งที่รหัสจริงดูเหมือน
และเราได้พูดคุย ในช่วงพักเกี่ยวกับ C ที่
ใน particular-- โดยเฉพาะอย่างยิ่ง ระดับที่ต่ำกว่าในภาษาที่เก่า
และผมก็ไม่ได้อย่างรวดเร็ว ค้นหาของ Google เพื่อค้นหารหัส C
สำหรับการค้นหาไบนารีขั้นตอนวิธีการที่เรา ใช้ในการค้นหาสมุดโทรศัพท์ว่าก่อนหน้านี้
ตัวอย่างนี้โดยเฉพาะอย่างยิ่งของหลักสูตร ไม่ได้ค้นหาสมุดโทรศัพท์
มันเป็นเพียงแค่การค้นหาทั้งกลุ่ม ตัวเลขในหน่วยความจำของคอมพิวเตอร์
แต่ถ้าคุณต้องการเพียงแค่ได้รับภาพ ความรู้สึกของสิ่งที่เกิดขึ้นจริงในการเขียนโปรแกรม
ภาษาดูเหมือนว่ามันดู บางสิ่งบางอย่างเล็ก ๆ น้อย ๆ เช่นนี้
ดังนั้นจึงเป็นประมาณ 20 บวก 30 หรือดังนั้นสายรหัส
แต่การสนทนาเรา ได้มีการแบ่งมากกว่า
เป็นเรื่องเกี่ยวกับวิธีการนี​​้จริง ได้รับการปรับเปลี่ยนไปศูนย์และคน
และถ้าคุณไม่สามารถย้อนกลับไปเพียงว่า ประมวลผลและไปจากศูนย์และคน
กลับไปที่รหัส
>> แต่น่าเสียดายที่กระบวนการ เป็นกระแสเพื่อให้
ว่ามันเป็นจำนวนมากพูดง่ายกว่าทำ
ฉันเดินไปข้างหน้าและหันจริง โปรแกรมที่ไบนารีค้นหา
เข้ามาในศูนย์และคนโดยวิธีการ โปรแกรมที่เรียกว่าคอมไพเลอร์ที่ผม
เกิดขึ้นจะมีที่นี่ตอนบน Mac ของฉัน
และถ้าคุณดูที่หน้าจอ ที่นี่เน้นเฉพาะ
เหล่านี้กลางหกคอลัมน์เท่านั้น คุณจะเห็นศูนย์เท่านั้นและคน
และผู้ที่มีเลขศูนย์และคนที่ เขียนตรงที่โปรแกรมการค้นหา
>> และเพื่อให้ก้อนห้าบิตแต่ละ แต่ละไบต์ของศูนย์และคนที่นี่
แทนคำแนะนำบางอย่าง โดยทั่วไปภายในของคอมพิวเตอร์
และในความเป็นจริงถ้าคุณเคยได้ยิน สโลแกนการตลาด "อินเทลภายใน" - ว่า
แน่นอนก็หมายความว่าคุณมี Intel CPU หรือสมองภายในเครื่องคอมพิวเตอร์
และสิ่งที่หมายถึงการเป็นซีพียู ว่าคุณมีชุดคำสั่ง
เพื่อที่จะพูด
>> ทุก CPU ในโลกหลายแห่ง พวกเขาทำโดย Intel วันนี้
เข้าใจแน่นอน จำนวนคำแนะนำ
และคำแนะนำผู้ที่มีระดับต่ำดังนั้น ทั้งเพิ่มจำนวนทั้งสองเข้าด้วยกัน
คูณจำนวนทั้งสองเข้าด้วยกัน ย้ายชิ้นส่วนของข้อมูลนี้จากที่นี่
เดินทางมาที่นี่ในหน่วยความจำบันทึกนี้ ข้อมูลจากที่นี่ไปที่นี่ในหน่วยความจำ
และอื่น ๆ เพื่อให้ forth-- มาก ระดับต่ำรายละเอียดอิเล็กทรอนิกส์เกือบ
แต่กับคนทางคณิตศาสตร์ การดำเนินงานควบคู่
กับสิ่งที่เรากล่าวก่อนหน้านี้ เป็นตัวแทนของข้อมูล
เป็นศูนย์และคนสามารถ คุณสร้างขึ้นมาทุกอย่าง
ที่คอมพิวเตอร์สามารถทำวันนี้ไม่ว่าจะเป็น มันเป็นต้นฉบับกราฟิกดนตรี
หรือมิฉะนั้น
>> ดังนั้นนี่เป็นเรื่องง่ายมากที่จะได้รับ หายไปในวัชพืชได้อย่างรวดเร็ว
และมีจำนวนมาก ความท้าทายกับการสร้างประโยค
โดยถ้าคุณทำที่ง่าย โง่ของความผิดพลาดไม่มีโปรแกรม
จะทำงานใด ๆ
และอื่น ๆ แทนการใช้ ภาษาเช่น C เช้านี้
ฉันคิดว่ามันจะเป็น สนุกมากขึ้นที่จะทำจริง
บางสิ่งบางอย่างที่มองเห็นได้มากขึ้นซึ่ง ในขณะที่ออกแบบมาสำหรับเด็ก
เป็นจริงการแสดงออกที่สมบูรณ์แบบ ของการเขียนโปรแกรมที่เกิดขึ้นจริง
language-- เพิ่งเกิดขึ้น ใช้ภาพแทนข้อความ
เพื่อเป็นตัวแทนของความคิดเหล่านั้น
>> ดังนั้นเมื่อคุณมีแน่นอน บัญชีผู้ใช้บน scratch.mit.edu,
คลิกที่ปุ่มสร้าง ที่ด้านซ้ายบนของเว็บไซต์
และคุณจะเห็นสภาพแวดล้อมเช่น หนึ่งฉันจะเห็นบนหน้าจอของฉัน
ที่นี่
และเราจะใช้จ่ายเพียงเล็กน้อย บิตของเวลาในการเล่นที่นี่
ลองมาดูว่าเราจะไม่สามารถแก้ปัญหาทั้งหมด ปัญหาที่เกิดขึ้นร่วมกันในวิธีการดังต่อไปนี้
>> ดังนั้นสิ่งที่คุณจะได้เห็นภายในนี้ environment-- และที่จริงเพียงแค่ให้
ฉันหยุดการทำงานชั่วคราว
มีใครไม่ได้ที่นี่?
ไม่อยู่ที่นี่?
ตกลง.
เพื่อให้ฉันชี้ให้เห็นไม่กี่ ลักษณะของสภาพแวดล้อมเช่นนี้
>> ดังนั้นที่ด้านบนซ้ายของหน้าจอเรา มีรอยขีดข่วนของเวทีเพื่อที่จะพูด
รอยขีดข่วนไม่ได้เป็นเพียงชื่อ ของการเขียนโปรแกรมภาษานี้
ก็ยังเป็นชื่อของแมวที่ คุณเห็นโดยค่าเริ่มต้นมีสีส้ม
เขาอยู่บนเวทีเพื่อให้ เหมือนฉันอธิบาย
เต่าก่อนหน้านี้เป็นอยู่ใน สภาพแวดล้อมบอร์ดสีขาวเป็นรูปสี่เหลี่ยมผืนผ้า
โลกของแมวตัวนี้ถูกกักขังอยู่ทั้งหมด ที่ด้านบนสี่เหลี่ยมผืนผ้ามีขึ้น
>> ในขณะเดียวกันทางด้านขวา ด้านที่นี่มันเป็น
เพียงแค่พื้นที่สคริปต์เป็น กระดานชนวนว่างเปล่าถ้าคุณจะ
นี่คือที่เรากำลังจะเขียน โปรแกรมของเราในเวลาเพียงสักครู่
และการก่อสร้างตึกหรือว่าเราจะ ใช้ในการเขียนนี้ program-- ปริศนา
ชิ้นถ้าคุณมี will-- ผู้ขวาที่นี่อยู่ตรงกลาง
และพวกเขากำลังอยู่ในหมวดหมู่ โดยการทำงาน
ดังนั้นสำหรับตัวอย่างเช่นฉันจะไปข้างหน้า และแสดงให้เห็นอย่างน้อยหนึ่งของเหล่านี้
ฉันจะไปข้างหน้าและคลิก ด้านบนประเภทการควบคุมขึ้น
>> ดังนั้นเหล่านี้เป็นประเภทขึ้นด้านบน
ฉันจะคลิกประเภทการควบคุม
แต่ฉันจะไปคลิกเหตุการณ์ ประเภทหนึ่งขึ้นเป็นครั้งแรกบนมาก
และถ้าคุณต้องการที่จะทำตามแม้กระทั่ง ในขณะที่เราทำเช่นนี้คุณค่อนข้างยินดีต้อนรับสู่
ฉันจะคลิกและลากนี้ คนแรก "เมื่อธงสีเขียวคลิก."
แล้วฉันจะวางมันเป็นเพียงแค่ ประมาณที่ด้านบนของหลังคาว่างเปล่าของฉัน
>> และสิ่งที่ดีเกี่ยวกับการรอยขีดข่วน คือว่าปริศนาชิ้นนี้เมื่อ
ประสานกับปริศนาอื่น ๆ ชิ้นจะไปทำอย่างแท้จริง
สิ่งเหล่านั้นชิ้นส่วนปริศนาบอกว่าจะทำอย่างไร
ดังนั้นสำหรับตัวอย่างเช่นรอยขีดข่วนเป็นสิทธิ ขณะนี้อยู่ในช่วงกลางของโลกของเขา
ฉันจะไปข้างหน้าและเลือก ตอนนี้ขอบอกว่าหมวดหมู่ Motion,
หากคุณต้องการที่จะทำ หมวดหมู่ same-- เคลื่อนไหว
และตอนนี้ฉันมีแจ้งให้ทราบทั้งหมด พวงของชิ้นส่วนปริศนาที่นี่
ว่าอีกชนิดของการทำในสิ่งที่พวกเขากล่าวว่า
และฉันจะไปข้างหน้าและลากและ วางบล็อกย้ายขวามากกว่าที่นี่
>> และแจ้งให้ทราบว่าทันทีที่คุณได้รับ ใกล้กับด้านล่างของ "ธงสีเขียว
คลิกปุ่ม "แจ้งให้ทราบล่วงหน้า วิธีเส้นสีขาวปรากฏขึ้น
ราวกับว่ามันเกือบจะ แม่เหล็กก็ต้องการที่จะไปที่นั่น
เพียงแค่ปล่อยให้ไปและมันจะสแนป ร่วมกันและรูปร่างจะตรงกับ
บางทีอาจจะเป็นและตอนนี้คุณเกือบจะสามารถ คาดเดาที่เรากำลังจะมีนี้
>> ถ้าคุณดูที่เวทีรอยขีดข่วน มากกว่าที่นี่และมองไปที่ด้านบนของมัน
คุณจะเห็นแสงสีแดง เข้าสู่ระบบหยุดและธงสีเขียว
และฉันจะไปข้างหน้า และดู screen-- ของฉัน
เพื่อรอสักครู่ถ้าคุณสามารถ
ฉันจะคลิก ธงสีเขียวในขณะนี้
และเขาย้ายสิ่งที่ปรากฏเป็น 10 ขั้นตอน หรือ 10 พิกเซล, 10 จุดบนหน้าจอ
>> และอื่น ๆ ไม่ได้เป็นที่น่าตื่นเต้น แต่ให้ฉันเสนอ
โดยไม่ได้เรียนการสอนนี้เพียง โดยใช้ตัวเอง Let intuition-- ของคุณเอง
ผมเสนอว่าคุณคิดออกว่าจะ ทำให้ใช้เวลาเดินเพียงรอยขีดข่วนขวาปิดเวที
มีเขาทำให้ทางด้านขวาของ หน้าจอไปทางขวา
ผมขอให้คุณสักครู่ หรือเพื่อที่จะต่อสู้กับว่า
คุณอาจต้องการที่จะดู ในประเภทอื่น ๆ ของบล็อก
ก็ดี
ดังนั้นเพียงแค่สรุปเมื่อเรามี ธงสีเขียวคลิกที่นี่
และย้ายไป 10 ขั้นตอนคือ การเรียนการสอนเท่านั้นในแต่ละครั้งที่ผม
คลิกธงสีเขียว, สิ่งที่เกิดขึ้น?
ดีที่ใช้โปรแกรมของฉัน
ดังนั้นผมจึงสามารถทำเช่นนี้ อาจจะ 10 ครั้งด้วยตนเอง
แต่ตอนนี้รู้สึกเล็ก ๆ น้อย ๆ บิต hackish, เพื่อที่จะพูด
ด้วยเหตุนี้ฉันไม่ได้จริงๆ การแก้ปัญหาที่เกิดขึ้น
ฉันแค่พยายามอีกครั้งและ อีกครั้งและอีกครั้งและอีกครั้ง
จนกว่าฉันจะเรียงลำดับของการตั้งใจ บรรลุสั่ง
ที่ผมออกไปก่อนหน้านี้ประสบความสำเร็จ
>> แต่เรารู้จากเรา pseudocode ก่อนหน้านี้ที่มี
ความคิดนี้ในการเขียนโปรแกรมของบ่วง ทำอะไรบางอย่างอีกครั้งและอีกครั้ง
และดังนั้นผมจึงเห็นว่าพวงของคุณ ถึงสิ่งที่สำหรับชิ้นส่วนปริศนา?
ทำซ้ำจนกว่า
ดังนั้นเราจึงสามารถทำบางสิ่งบางอย่าง เช่นการทำซ้ำจนกว่า
และสิ่งที่คุณทำซ้ำจนกว่าว่า?
>> ตกลง.
และแจ้งให้เราไปกับคนที่ ค่อนข้างง่ายสำหรับรอสักครู่
ให้ฉันไปข้างหน้าและทำเช่นนี้
ขอให้สังเกตว่าในขณะที่คุณอาจจะมี ค้นพบภายใต้การควบคุม
มีบล็อกซ้ำนี้ซึ่ง ดูไม่เหมือนมันเป็นเรื่องที่ใหญ่
มีห้องพักไม่มากในการเป็น ระหว่างทั้งสองเส้นสีเหลือง
แต่ในขณะที่บางท่านอาจจะมี สังเกตเห็นถ้าคุณลากและวาง
แจ้งให้ทราบว่ามันจะเติบโตเพื่อเติมเต็มรูปร่าง
>> และคุณยังสามารถอัดมากขึ้น
มันก็จะทำให้การเจริญเติบโตถ้า คุณลากและวางเมาส์เหนือมัน
และผมก็ไม่ทราบว่ามีอะไร ดีที่สุดที่นี่เพื่อให้
ฉันอย่างน้อยทำซ้ำห้าครั้งสำหรับ อินสแตนซ์และจากนั้นกลับไปที่เวที
และคลิกที่ธงสีเขียว
และตอนนี้แจ้งให้ทราบก็ไม่มาก
>> ตอนนี้บางท่านเสนอเป็น วิกตอเรียก็ไม่ทำซ้ำ 10 ครั้ง
และโดยทั่วไปจะ ได้รับเขาตลอดทาง
แต่จะไม่ได้มีประสิทธิภาพมากขึ้น วิธีที่ดีกว่าโดยพลการหา
วิธีการหลายย้ายเพื่อให้?
สิ่งที่อาจจะเป็นบล็อกที่ดีกว่า กว่า 10 ครั้งทำซ้ำจะเป็นอย่างไร
>> ใช่ดังนั้นทำไมไม่ทำอะไรบางอย่างถาวรหรือไม่
และตอนนี้ให้ฉันย้ายชิ้นส่วนปริศนานี้ ภายในมีและกำจัดคนนี้
ตอนนี้ทราบว่าที่ไม่มีรอยขีดข่วน เริ่มต้นเขาจะไปที่ขอบ
และโชคดีที่เอ็มไอที ผู้ที่จะทำให้รอยขีดข่วนเพียง
ทำให้แน่ใจว่าเขาไม่เคย หายไปอย่างสมบูรณ์
คุณสามารถคว้าหางของเขา
>> และเพียงแค่สังหรณ์ใจ ทำไมเขาไม่ให้ย้าย?
เกิดขึ้นที่นี่คืออะไร?
ดูเหมือนว่าเขาจะหยุด แต่ แล้วถ้าผมรับและลาก
เขาช่วยให้ความต้องการที่จะไปที่นั่น
ทำไมเป็นเช่นนั้น?
แท้จริงคอมพิวเตอร์เป็นตัวอักษร จะทำในสิ่งที่คุณบอกว่าจะทำอย่างไร
ดังนั้นถ้าคุณบอกว่ามันทำก่อนหน้านี้ สิ่งต่อไปนี้ตลอดไปย้าย 10 ขั้นตอน
ก็จะเก็บไปและไป จนกว่าฉันจะตีป้ายแดง
และหยุดโปรแกรมทั้งหมด
>> ดังนั้นแม้ว่าคุณจะไม่ได้ ทำเช่นนี้ฉันจะทำอย่างไร
ให้ย้ายรอยขีดข่วนได้เร็วขึ้น ผ่านหน้าจอ?
ขั้นตอนมากขึ้นใช่ไหม?
ดังนั้นแทนที่จะทำ 10 ในเวลาที่ทำไมเราไม่
ไปข้างหน้าและเปลี่ยน to-- สิ่งที่คุณจะ propose-- 50?
ดังนั้นตอนนี้ฉันกำลังจะไปคลิกสีเขียว ธงและแน่นอนเขาจะไปได้อย่างรวดเร็วจริงๆ
>> และนี้แน่นอนเป็นเพียง เป็นการรวมตัวกันของการเคลื่อนไหว
นิเมชั่นคืออะไร?
มันเป็นเพียงแค่แสดงให้คุณเห็นมนุษย์ ทั้งกลุ่มของภาพนิ่งจริงๆ
จริงๆอย่างรวดเร็วจริงๆ
และดังนั้นถ้าเราเพียงแค่บอก เขาย้ายขั้นตอนมากขึ้น
เราเพียงแค่มีผลกระทบที่จะมีการ การเปลี่ยนแปลงที่เขาอยู่บนหน้าจอ
ทั้งหมดที่มากขึ้นอย่างรวดเร็วต่อหน่วยของเวลา
>> ตอนนี้ความท้าทายต่อไปที่ผมเสนอ ก็จะมีเขากระเด็นขอบ
และไม่ทราบว่าสิ่งที่จิ๊กซอว์ ชิ้น exist-- เพราะมันเป็นเรื่องที่ดี
ถ้าคุณไม่ได้รับการ ขั้นตอนของการ challenge-- สิ่งที่
คุณต้องการที่จะทำอย่างสังหรณ์ใจ?
วิธีการที่เราจะได้เขากลับมาและ มาระหว่างซ้ายและขวา?
>> ใช่.
ดังนั้นเราจึงจำเป็นบางชนิด สภาพและเรา
ดูเหมือนจะมีเงื่อนไขเพื่อที่จะ พูดภายใต้หมวดหมู่การควบคุม
ซึ่งบล็อกเหล่านี้ เราไม่อาจจะต้องการได้หรือไม่
ใช่อาจจะ "ถ้าแล้ว."
ดังนั้นสังเกตเห็นว่าในหมู่บล็อกสีเหลือง เรามีที่นี่มีเป็นแบบนี้ "ถ้า"
หรือนี้ "ถ้าอื่น" บล็อกที่จะ ช่วยให้เราสามารถทำให้การตัดสินใจที่จะทำเช่นนี้
หรือจะทำอย่างนั้น
แม้และคุณสามารถให้พวกเขารัง จะทำสิ่งที่หลาย ๆ
หรือถ้าคุณไม่ได้ไปที่นี่เลย ไปข้างหน้าไปที่หมวดหมู่การตรวจจับ
and-- ขอดูว่ามันนี่
>> ดังนั้นสิ่งที่บล็อกอาจจะเป็นประโยชน์ที่นี่ การตรวจสอบถ้าเขาออกเวที?
ใช่สังเกตเห็นบางส่วนของบล็อกเหล่านี้ว่า สามารถ parametrized เพื่อที่จะพูด
พวกเขาสามารถปรับแต่งการจัดเรียงของไม่ได้ ซึ่งแตกต่างจาก HTML เมื่อวานนี้มีคุณลักษณะ
ซึ่งคุณลักษณะเหล่านั้นชนิดของ ปรับแต่งการทำงานของแท็กที่
ในทำนองเดียวกันที่นี่ผมสามารถคว้าสัมผัสนี้ บล็อกและการเปลี่ยนแปลงและถามคำถาม
คุณกำลังสัมผัสเมาส์ ชี้เหมือนเคอร์เซอร์
หรือคุณสัมผัสขอบ?
>> เพื่อให้ฉันไปในและทำเช่นนี้
ฉันจะซูมออกสักครู่
ให้ฉันคว้าชิ้นส่วนปริศนานี้ ที่นี่ชิ้นส่วนปริศนานี้นี้
และฉันจะสับสน พวกเขาขึ้นเพื่อรอสักครู่
ผมจะย้ายไปนี้ เปลี่ยนเป็นขอบสัมผัส
และฉันจะเคลื่อนไหวทำเช่นนี้
ดังนั้นนี่คือส่วนผสมบาง
ฉันคิดว่าฉันมีทุกอย่างที่ฉันต้องการ
>> คนที่ต้องการที่จะนำเสนอวิธีการที่ฉัน สามารถเชื่อมต่อเหล่านี้อาจจะบนลงล่าง
เพื่อที่จะแก้ปัญหาของการมี รอยขีดข่วนย้ายขวาไปซ้ายไปขวาเพื่อ
จากซ้ายไปขวาไปซ้ายแต่ละ เวลาเพียงไม่ใหญ่ปิดผนังหรือไม่
อะไรที่ฉันต้องการจะทำอย่างไร?
ซึ่งบล็อกที่ฉันควรจะเชื่อมต่อไปยัง "ธงสีเขียวเมื่อคลิกแรก"?
>> ตกลงดังนั้นขอเริ่มต้นด้วย "ตลอดไป."
สิ่งที่จะไปภายในต่อไปหรือไม่
คนอื่น
ตกลงย้ายไปตามขั้นตอน
ก็ดี
แล้วไง?
ดังนั้นแล้วหาก
และแจ้งให้ทราบถึงแม้ว่ามันจะมีลักษณะ แซนวิชด้วยกันแน่น
มันก็จะเติบโตในการกรอกข้อมูล
มันก็จะกระโดดในที่ที่ฉันต้องการ
>> และสิ่งที่ผมใส่ระหว่าง ถ้าและแล้ว?
อาจจะ "ถ้าสัมผัสขอบ."
และแจ้งให้ทราบอีกครั้งก็ใหญ่เกินไป สำหรับมัน แต่มันจะเติบโตในการกรอกข้อมูล
แล้วเปิด 15 องศา?
กี่องศา?
ใช่ดังนั้น 180 จะหมุน ฉันทุกทางรอบ
ดังนั้นเรามาดูว่าผมได้รับสิทธินี้
ผมขอซูมออก
>> ผมขอลาก Scratch ขึ้น
ดังนั้นเขาจึงเป็นเพียงเล็กน้อยบิดเบี้ยว ตอนนี้ แต่ที่ดี
ฉันจะรีเซ็ตเขาได้อย่างง่ายดาย?
ฉันจะโกงเล็กน้อย
ดังนั้นฉันเพิ่มอีก บล็อกเพียงเพื่อให้มีความชัดเจน
ผมต้องการให้เขาจะชี้ 90 องศา ไปทางขวาโดยเริ่มต้นที่
ดังนั้นฉันเพียงแค่จะบอกเขา ที่จะทำโปรแกรม
และที่นี่เราไป
ดูเหมือนว่าเราได้ทำมัน
มันแปลกเล็กน้อยเพราะ เขาเดินคว่ำ
ขอเรียกว่าข้อผิดพลาด
นั่นเป็นความผิดพลาด
ข้อผิดพลาดเป็นข้อผิดพลาดในโปรแกรมเป็น ข้อผิดพลาดที่ผมตรรกะของมนุษย์ที่ทำ
ทำไมเขาจะคว่ำลง?
ไม่ MIT กรูขึ้นหรือไม่ฉัน?
>> ใช่ฉันหมายความว่ามันไม่ได้เป็นของเอ็มไอที ความผิด พวกเขาให้ฉันชิ้นส่วนจิ๊กซอว์
ที่บอกว่าเปิดจำนวนองศาบาง
และข้อเสนอแนะของวิกตอเรีย ฉันหัน 180 องศา
ซึ่งเป็นสัญชาตญาณที่เหมาะสม
แต่หัน 180 องศาอย่างแท้จริง หมายถึงการหัน 180 องศา
และที่ไม่ได้จริงๆ สิ่งที่ผมอยากเห็นได้ชัด
เพราะอย่างน้อยเขาอยู่ใน โลกนี้สองมิติ
เพื่อเปลี่ยนเป็นจริงที่เกิด เขาจะพลิกคว่ำ
>> ฉันอาจต้องการที่จะใช้สิ่งที่บล็อก แต่ขึ้นอยู่กับสิ่งที่คุณเห็นนี่?
วิธีการที่เราอาจจะแก้ไขปัญหานี้อย่างไร
ใช่ดังนั้นเราจึงสามารถชี้ ในทิศทางตรงกันข้าม
และที่จริงแม้กระทั่งว่า ไม่ได้ไปจะพอ
เพราะเราสามารถยากรหัส เพื่อชี้ทางซ้ายหรือขวา
>> คุณจะรู้ว่าสิ่งที่เราสามารถทำอะไรได้บ้าง
ดูเหมือนว่าเรามี ความสะดวกสบายที่นี่บล็อก
ถ้าฉันซูมเข้าดูที่ บางสิ่งบางอย่างที่เราชอบที่นี่?
เพื่อให้ดูเหมือนว่ามีเอ็มไอที นามธรรมที่สร้างขึ้นในที่นี่
บล็อกนี้ดูเหมือนว่าจะเทียบเท่า ที่บล็อกอื่น ๆ พหูพจน์?
>> หนึ่งบล็อกนี้ดูเหมือนว่าจะเทียบเท่า ทั้งสามคนไปทั้งหมดนี้ของบล็อก
ที่เรามีที่นี่
ดังนั้นมันจะเปิดออกผมสามารถลดความซับซ้อนของฉัน โปรแกรมโดยการกำจัดทุกที่
และเพียงแค่ใส่นี้ที่นี่
และตอนนี้เขาก็ยังคงเป็นเพียงเล็กน้อย รถและที่ดีสำหรับตอนนี้
เราจะออกจากที่เป็น
แต่โปรแกรมของฉันคือแม้ ที่เรียบง่ายและนี้มากเกินไป
จะเป็นตัวแทน ของเป้าหมายในการ programming--
คือการทำให้ความนึกคิดของคุณเป็นรหัส เรียบง่ายเป็นขนาดเล็กที่สุดเท่าที่ทำได้
ในขณะที่ยังคงความเป็น สามารถอ่านได้ที่เป็นไปได้
คุณไม่ต้องการที่จะให้มันรวบรัดเพื่อ ว่ามันเป็นเรื่องยากที่จะเข้าใจ
>> แต่สังเกตเห็นฉันได้แทนที่ สามบล็อกที่มีหนึ่ง
และนั่นคือเนื้อหาที่เป็นสิ่งที่ดี
ฉันได้แยกออกไปความคิด ของการตรวจสอบไม่ว่าคุณจะ
บนขอบที่มีเพียงหนึ่งช่วงตึก
ตอนนี้เราสามารถมีความสุขกับเรื่องนี้ในความเป็นจริง
นี้ไม่ได้เพิ่มมาก มูลค่าทางปัญญา แต่ค่าขี้เล่น
ฉันจะไปข้างหน้า และคว้าเสียงที่นี่
เพื่อให้ฉันไปข้างหน้าและแจ้งให้เรา หยุดโปรแกรมสักครู่
ฉันจะบันทึกต่อไปนี้ ช่วยให้เข้าถึงไมโครโฟนของฉัน
>> ไปเลย.
อุ๊ย
ลองนี้อีกครั้ง
ไปเลย.
ตกลงฉันบันทึกสิ่งที่ผิด
ไปเลย.
อุ๊ย
ก็ดี
ตอนนี้ผมต้องกำจัดที่
ก็ดี
>> ดังนั้นตอนนี้ผมมี การบันทึกเพียงแค่ "อุ๊ย."
ดังนั้นตอนนี้ฉันกำลังจะไป ข้างหน้าและเรียกสิ่งนี้ว่า "อุ๊ย."
ฉันจะกลับไป สคริปต์ฉันและตอนนี้
แจ้งให้ทราบล่วงหน้ามีบล็อกที่เรียกว่า เล่นเสียง "Meow" หรือเล่นเสียง "อุ๊ย."
ฉันจะลากนี้และที่ ฉันควรใส่นี้สำหรับผลตลก?
ใช่ดังนั้นตอนนี้มันเป็นชนิดของ รถเพราะตอนนี้ block--
แจ้งให้ทราบว่าเรื่องนี้ "ถ้าในขอบ ตีกลับ "เป็นชนิดของตนเองมี
ดังนั้นผมจึงจำเป็นต้องแก้ไขปัญหานี้
ให้ฉันไปข้างหน้าและทำเช่นนี้
ให้ฉันได้รับการกำจัดนี้และกลับไป ไปที่เดิมของเรามากขึ้นโดยเจตนา
ฟังก์ชั่น
ดังนั้น "ถ้าสัมผัสขอบแล้ว" ฉันต้องการ เพื่อเปิดเป็นวิกตอเรียเสนอ
180 องศา
และฉันต้องการที่จะเล่น เสียง "อุ๊ย" มี?
>> ใช่แจ้งให้ทราบก็ออกไปข้างนอก ที่บล็อกสีเหลือง
ดังนั้นนี้มากเกินไปจะเป็น ข้อผิดพลาด แต่ฉันได้สังเกตเห็นมัน
ดังนั้นฉันจะลากขึ้นที่นี่ และแจ้งให้ทราบตอนนี้ก็ภายใน "ถ้า".
ดังนั้น "ถ้า" เป็นประเภทนี้ เช่น blot แขนเหมือน
ที่เพียงไป ทำในสิ่งที่ภายในของมัน
ดังนั้นตอนนี้ถ้าผมซูมออกที่ ความเสี่ยงของการ annoying--
>> คอมพิวเตอร์: อุ๊ยอุ๊ยอุ๊ย
>> DAVID ลัน: และมัน ก็จะอยู่กับคุณตลอดไป
ตอนนี้เพียงแค่สิ่งที่จะเร่ง ที่นี่ให้ฉันไปข้างหน้าและเปิดขึ้น
ขอ say-- ให้ฉันไปบางส่วน ของสิ่งที่เป็นของตัวเองจากชั้นเรียน
และแจ้งให้เราเปิดขึ้นสมมติว่านี้ หนึ่งที่ทำโดยหนึ่งในการเรียนการสอนพวกเรา
สองสามปีที่ผ่านมา
ดังนั้นบางท่านอาจจะจำได้ เกมนี้จากปีกลาย
และมันเป็นเรื่องที่น่าทึ่งจริง
แม้ว่าเราจะได้ทำ ที่ง่ายที่สุดของโปรแกรมในขณะนี้
ลองพิจารณาสิ่งนี้ ดูเหมือนจริง
ผมขอตีเล่น
>> ดังนั้นในเกมนี้เรามี กบและการใช้ลูกศร keys--
เขาใช้ขั้นตอนที่มีขนาดใหญ่กว่าฉัน remember-- ฉันมีการควบคุมมากกว่ากบ
และมีเป้าหมายที่จะได้รับในไม่ว่าง ถนนโดยไม่ต้องวิ่งเข้าไปในรถ
และขอ see-- ถ้าผมขึ้นไปนี่ผม ต้องรอให้เข้าสู่ระบบเพื่อเลื่อนโดย
นี้รู้สึกเหมือนข้อผิดพลาด
นี้เป็นชนิดของข้อผิดพลาด
ก็ดี
ฉันเกี่ยวกับเรื่องนี้ที่นี่ มีแล้วคุณเก็บ
ไปจนกว่าคุณจะได้รับทั้งหมด กบแผ่นลิลลี่
ตอนนี้อาจจะดู ทั้งหมดที่ซับซ้อนมากขึ้น
แต่ให้พยายามที่จะทำลาย ลงจิตใจ
และด้วยวาจาเป็นบล็อกที่เป็นส่วนประกอบของ
ดังนั้นอาจมีปริศนา ชิ้นส่วนที่เรายังไม่ได้เห็น
แต่ที่ตอบสนองต่อการกดแป้นพิมพ์ สิ่งที่ฉันกดบนแป้นพิมพ์
>> ดังนั้นอาจมีบางชนิด บล็อกที่บอกว่าถ้าคีย์เท่ากับขึ้น
แล้วทำอะไรกับ Scratch-- อาจจะย้ายไป 10 ขั้นตอนวิธีนี้
ถ้าคีย์ถูกกดลงย้าย 10 ขั้นตอน วิธีนี้หรือคีย์ซ้ายย้าย 10 ขั้นตอน
วิธีนี้ 10 ขั้นตอนที่
ผมได้เปิดอย่างชัดเจนแมวลงในกบ
เพื่อให้เป็นเพียงที่ เครื่องแต่งกายและโทรศัพท์ Scratch it-- เรา
เพียงแค่นำเข้าภาพของกบที่
>> แต่สิ่งที่คนอื่นจะเกิดขึ้น?
สิ่งที่สายอื่น ๆ ของรหัส สิ่งที่ชิ้นส่วนปริศนาอื่น ๆ
ได้เบลคเพื่อนการเรียนการสอนของเรา ใช้ในโปรแกรมนี้เห็นได้ชัด?
สิ่งที่ทำให้ทุกอย่าง move-- สิ่งที่เขียนโปรแกรมสร้าง?
>> การเคลื่อนไหว sure-- ดังนั้น ย้ายบล็อกเพื่อตรวจสอบว่า
และสิ่งที่บล็อกย้าย ภายในของส่วนใหญ่?
ใช่ชนิดของห่วงบางอย่างอาจจะเป็น ตลอดไปป้องกันอาจจะซ้ำ block--
ทำซ้ำจนกว่าบล็อก
และนั่นคือสิ่งที่ทำให้ล็อกและ แผ่นลิลลี่และทุกสิ่งทุกอย่างที่ย้าย
ไปมา.
มันเป็นเพียงแค่สิ่งที่เกิดขึ้นอย่างไม่มีที่สิ้นสุด
>> ทำไมบางส่วนของรถยนต์ ย้ายได้เร็วขึ้นกว่าคนอื่น ๆ ?
คืออะไรที่แตกต่างกันเกี่ยวกับโปรแกรมเหล่านั้นหรือไม่
ใช่อาจจะเป็นบางส่วนของพวกเขาจะพา ขั้นตอนมากขึ้นในครั้งเดียวและบางส่วนของพวกเขา
ขั้นตอนน้อยลงในครั้งเดียว
และผลภาพ เป็นไปอย่างรวดเร็วเมื่อเทียบกับช้า
>> คุณคิดว่าอะไรที่เกิดขึ้น?
เมื่อฉันได้กบของฉันตลอดทาง ฝั่งตรงข้ามถนนและแม่น้ำ
ลงบนแผ่นลิลลี่บางสิ่งบางอย่าง ที่สำคัญเกิดขึ้น
สิ่งที่เกิดขึ้นเร็วที่สุดเท่าที่ฉันไม่ว่า?
มันหยุด
กบที่หยุดและ ผมได้กบที่สอง
ดังนั้นสิ่งที่จะต้องสร้าง ใช้มีสิ่งที่คุณสมบัติ?
>> ใช่เพื่อให้มีชนิดของ "ถ้า" เงื่อนไขขึ้นมีมากเกินไป
และมันจะเปิด out-- เราไม่เห็น this-- แต่มีบล็อกอื่น ๆ ในที่นั่น
สามารถพูดได้ว่าถ้าคุณสัมผัส อีกสิ่งหนึ่งบนหน้าจอ
ถ้าคุณกำลังสัมผัสแผ่นลิลลี่ "แล้ว."
แล้วที่ว่าเมื่อเรา ทำให้กบสองปรากฏ
ดังนั้นแม้ว่าเกมนี้อย่างแน่นอน ลงวันที่มากถึงแม้ว่าได้อย่างรวดเร็วก่อน
มีมากไป on-- และเบลค ไม่ได้ชักนี้ขึ้นมาในสองนาที
มันอาจจะพาเขาหลาย ชั่วโมงในการสร้างเกมนี้
ขึ้นอยู่กับหน่วยความจำหรือวิดีโอของเขา รุ่นปีกลายของมัน
แต่ทุกสิ่งเล็ก ๆ น้อย ๆ เหล่านี้ ไปบนหน้าจอในการแยก
ต้มลงไปเหล่านี้ง่ายมาก การเคลื่อนไหว constructs-- หรืองบ
เหมือนอย่างที่เราได้กล่าวถึงห่วงและ เงื่อนไขและที่เกี่ยวกับมัน
มีไม่กี่คนชอบเล่นคุณลักษณะอื่น ๆ
บางส่วนของพวกเขาเป็นอย่างหมดจด ความงามหรืออะคูสติก
เช่นเสียงที่ผมเพียงแค่เล่นกับ
แต่ส่วนใหญ่คุณ มีในภาษานี้รอยขีดข่วน
ทั้งหมดของพื้นฐาน ก่อสร้างตึกที่คุณ
มีใน C, Java, JavaScript PHP, Ruby, Python,
และจำนวนของภาษาอื่น ๆ
คำถามใด ๆ เกี่ยวกับ Scratch?
ก็ดี
ดังนั้นเราจะไม่ดำน้ำในลึกรอยขีดข่วน แม้ว่าคุณจะยินดีต้อนรับวันหยุดสุดสัปดาห์นี้
โดยเฉพาะอย่างยิ่งถ้าคุณมีเด็กหรือ หลานสาวและหลานชายและเช่น
ที่จะแนะนำให้พวกเขาที่จะเกา
เป็นจริงขี้เล่นที่เยี่ยมยอด สภาพแวดล้อมที่มีในขณะที่ผู้เขียนบอกว่า
เพดานสูงมาก
แม้ว่าเราจะเริ่มต้นด้วย รายละเอียดมากในระดับต่ำ
คุณสามารถทำได้จริงๆไม่น้อย กับมันและนี้อาจจะ
การสาธิตของว่าที่
>> แต่ตอนนี้ขอเปลี่ยนไปบางมากขึ้น ปัญหาที่มีความซับซ้อนถ้าคุณจะ
ที่เรียกว่า "ค้นหา" และ "เรียงลำดับ" มากขึ้นโดยทั่วไป
เรามีสมุดโทรศัพท์นี้ earlier-- นี่ อีกคนหนึ่งเพียงเพื่อ discussion--
ว่าเรามีความสามารถในการค้นหา ได้อย่างมีประสิทธิภาพมากขึ้นเพราะ
ของสมมติฐานอย่างมีนัยสำคัญ
และเพียงแค่ต้องมีความชัดเจนในสิ่งที่ สมมติฐานคือผมทำ
เมื่อค้นหาผ่านสมุดโทรศัพท์นี้หรือไม่?
ว่าไมค์สมิ ธ อยู่ใน สมุดโทรศัพท์ แต่ฉัน
จะสามารถที่จะจัดการกับ สถานการณ์โดยไม่ต้องให้เขา
มีถ้าฉันเพียงแค่หยุดก่อนเวลาอันควร
หนังสือเล่มนี้เป็นตัวอักษร
และที่เป็นคนใจกว้างมาก สมมติฐานเนื่องจากว่า
หมายความ someone-- ผมชนิด ของการตัดมุม
เหมือนฉันได้เร็วขึ้นเพราะใครบางคน อื่น ๆ ไม่มากของการทำงานอย่างหนักสำหรับผม
>> แต่สิ่งที่ถ้าโทรศัพท์ หนังสือที่ได้รับไม่ได้เรียงลำดับ?
บางที Verizon ได้ขี้เกียจเพียงแค่โยน ชื่อของทุกคนและตัวเลขในการมี
อาจจะอยู่ในลำดับที่พวกเขา สมัครใช้บริการโทรศัพท์
และเวลาเท่าไรไม่ก็พาฉัน ที่จะหาคนที่ชอบไมค์สมิ ธ
โทรศัพท์หน้า 1,000 book-- หลายวิธี หน้าฉันจะต้องมองผ่าน?
>> ทั้งหมด.
คุณเรียงลำดับของการออกจากโชค
คุณอย่างแท้จริงต้องมองไปที่ทุก หน้าถ้าสมุดโทรศัพท์เป็นเพียง
เรียงแบบสุ่ม
คุณอาจได้รับโชคดีและหาไมค์ ในหน้าแรกมากเพราะเขา
เป็นลูกค้ารายแรก การสั่งซื้อบริการโทรศัพท์
แต่เขาอาจจะเป็นครั้งสุดท้ายเกินไป
>> เพื่อสุ่มดังนั้นไม่ดี
ดังนั้นสมมติว่าเรามีการจัดเรียง สมุดโทรศัพท์หรือในการเรียงลำดับข้อมูลทั่วไป
ที่เราได้รับ
วิธีที่เราสามารถทำเช่นนั้น?
>> ดีให้ฉันเพียงแค่พยายาม ตัวอย่างง่ายๆที่นี่
ให้ฉันไปข้างหน้าและโยน จำนวนน้อยบนกระดาน
สมมติว่าตัวเลขที่เรามีอยู่ สมมติว่าสี่สองหนึ่งและสาม
และเบนเรียงลำดับตัวเลขเหล่านี้สำหรับเรา
>> OK ดี.
คุณทำได้อย่างไร?
ก็ดี
ดังนั้นการเริ่มต้นมีขนาดเล็กที่สุด และค่าสูงสุด
และนั่นคือสัญชาตญาณที่ดีจริงๆ
และตระหนักถึงเราที่ มนุษย์จะสวยจริง
ที่ดีในการแก้ปัญหา เช่นนี้อย่างน้อย
เมื่อข้อมูลมีขนาดค่อนข้างเล็ก
เร็วที่สุดเท่าที่คุณจะเริ่มมีหลายร้อย ของจำนวนหลายพันคนของตัวเลข
ล้านหมายเลขเบนอาจจะ ไม่สามารถทำมันค่อนข้างรวดเร็ว
สมมติว่ามี ช่องว่างในตัวเลข
สวยง่ายที่จะนับล้าน เวลาเพียงแค่มิฉะนั้นบริโภค
>> ดังนั้นขั้นตอนวิธีที่มันฟัง เช่นเบนใช้เพียงแค่ตอนนี้
คือการค้นหาสำหรับจำนวนที่น้อยที่สุด
ดังนั้นแม้ว่ามนุษย์เราสามารถใช้ ในข้อมูลจำนวนมากสายตา
คอมพิวเตอร์เป็นจริง เล็ก ๆ น้อย ๆ ที่ จำกัด มากขึ้น
คอมพิวเตอร์สามารถเท่านั้น มองไปที่หนึ่งไบต์ในเวลา
หรืออาจจะสี่ไบต์ที่ time-- วันนี้อาจจะ 8 ไบต​​์ที่ time--
แต่จำนวนน้อยมาก ไบต์ในเวลาที่กำหนด
>> ดังนั้นให้ที่เราจริงๆมี สี่ค่าแยกต่างหาก here--
และคุณอาจจะคิดว่าเบนที่มี blinders บนว่าเขาเป็นเช่นคอมพิวเตอร์
ว่าเขาไม่สามารถมองเห็นอะไรอื่น ๆ กว่าหนึ่งในจำนวนที่ time--
ดังนั้นเรามักจะถือว่าเหมือนใน ภาษาอังกฤษเราจะอ่านจากขวาไปซ้าย
ดังนั้นจำนวนแรกเบนอาจจะมอง ที่สี่แล้วอย่างรวดเร็ว
ตระหนักว่าเป็นใหญ่สวย number-- ให้ฉันให้มอง
>> มีสองเรื่อง
เดี๋ยวก่อน.
สองมีขนาดเล็กกว่าสี่
ฉันจะจำ
สองคือตอนนี้มีขนาดเล็กที่สุด
ตอนนี้ one-- ที่ดียิ่งขึ้น
นั่นคือแม้มีขนาดเล็ก
ฉันจะลืมเกี่ยวกับสอง และเพียงแค่จำได้ในขณะนี้
>> และเขาสามารถหยุดมอง?
ดีที่เขาจะได้ตาม ข้อมูลนี้
แต่เขาต้องการค้นหาที่ดีขึ้น ส่วนที่เหลือของรายการ
เพราะสิ่งที่ถ้าศูนย์อยู่ในรายการหรือไม่
เกิดอะไรขึ้นถ้าคนใดคนหนึ่งในเชิงลบในรายการ?
เขารู้ดีว่าคำตอบของเขา ถูกต้องถ้าเขาอย่างละเอียดถี่ถ้วน
ตรวจสอบรายชื่อทั้งหมด
นั้นเรามาดูในส่วนที่เหลือจากนี้
Three-- ว่าเป็นเรื่องเสียเวลา
โชคร้ายได้ แต่ผมก็ ยังคงถูกต้องในการทำเช่นนั้น
และอื่น ๆ ตอนนี้เขาสันนิษฐานว่า เลือกจำนวนที่เล็กที่สุด
และเพียงแค่ใส่มันที่จุดเริ่มต้น ของรายการที่ผมจะทำที่นี่
ตอนนี้สิ่งที่คุณต้องทำต่อไปแม้ว่า คุณไม่ได้คิดเกี่ยวกับมันเกือบ
เท่านี้หรือไม่?
ทำซ้ำขั้นตอนที่ ดังนั้นชนิดของห่วงบาง
มีความคิดที่เป็นที่คุ้นเคย
ดังนั้นนี่คือสี่
ที่กำลังมีขนาดเล็กที่สุด
นั่นคือผู้สมัคร
ไม่อีกแล้ว.
ตอนนี้ผมได้เห็นสอง
นั่นเป็นองค์ประกอบที่เล็กต่อไป
Three-- ที่ไม่ได้มีขนาดเล็กลงเพื่อให้ ตอนนี้เบนสามารถถอนออกมาทั้งสอง
>> และตอนนี้เราทำซ้ำขั้นตอนและ แน่นอนสามได้รับการดึงออกมาต่อไป
ทำซ้ำขั้นตอน
สี่ได้รับการดึงออกมา
และตอนนี้เรากำลังออกของตัวเลข ดังนั้นรายการจะต้องมีการจัดเรียง
>> และแน่นอนนี้เป็นขั้นตอนวิธีการอย่างเป็นทางการ
นักวิทยาศาสตร์คอมพิวเตอร์จะ เรียกสิ่งนี้ว่า "การจัดเรียงตัวเลือก"
คิดถูกจัดเรียง รายการ iteratively-- อีกครั้ง
และอีกครั้งและอีกครั้งเลือก จำนวนที่เล็กที่สุด
และสิ่งที่ดีเกี่ยวกับมัน มันเป็นเพียงเพื่อให้ใช้งานง่ายยี้
มันเป็นเรื่องง่ายมาก
และคุณสามารถทำซ้ำเดียวกัน การดำเนินการอีกครั้งและอีกครั้ง
มันง่าย
>> ในกรณีนี้มันเร็ว แต่ นานแค่ไหนที่ไม่เป็นจริงใช้เวลา?
ขอให้มันดูและ รู้สึกน่าเบื่อมาก
ดังนั้นหนึ่งสองสามสี่ห้าหก เจ็ดแปดเก้า, 10, 11, 12, 13, 14,
15 16-- จำนวนข้อ
ฉันแค่อยากมากขึ้นนี้ เวลามากกว่าเพียงแค่สี่
ดังนั้นถ้าฉันมีทั้ง พวงของตัวเลข now-- มัน
ไม่ได้เรื่อง สิ่งที่พวกเขา are-- ของให้
คิดเกี่ยวกับสิ่งนี้ อัลกอริทึมจริงๆเป็นเหมือน
>> สมมติว่ามีจำนวนที่มี
อีกครั้งไม่สำคัญว่า พวกเขาจะมี แต่พวกเขากำลังสุ่ม
ฉันกำลังใช้อัลกอริทึมของเบน
ฉันจำเป็นต้องเลือกหมายเลขที่เล็กที่สุด
ฉันจะทำอะไร?
และฉันจะทางร่างกาย ทำมันในครั้งนี้จะทำหน้าที่ออก
มองมอง, มองมองมอง
โดยเฉพาะเวลาที่ฉันได้รับการ ตอนท้ายของรายการสามารถ
ผมทราบดีว่ามีขนาดเล็กที่สุด จำนวนสองครั้งนี้
หนึ่งที่ไม่อยู่ในรายการ
ดังนั้นผมจึงใส่ลงไปอีกสอง
>> ฉันจะทำอะไรต่อไป
มองมองมองมอง
ตอนนี้ผมพบว่าหมายเลขเจ็ดเพราะ มีช่องว่างในเบอร์เหล่านี้
แต่เพียงโดยพลการ
ก็ดี
ดังนั้นตอนนี้ฉันสามารถใส่ลงเจ็ด
มองมองมอง
>> ตอนนี้ฉันสมมติของ แน่นอนว่าเบนไม่ได้
มี RAM เสริมพิเศษ หน่วยความจำเพราะของหลักสูตร
ฉันกำลังมองหาที่บ้านเลขที่เดียวกัน
แน่นอนฉันจะได้จำได้ ทั้งหมดของตัวเลขเหล่านั้น
และนั่นคือความจริงอย่างแน่นอน
แต่ถ้าเบนจำทั้งหมด ของตัวเลขที่เขาเห็น
เขาไม่ได้ทำจริงๆ ความคืบหน้าขั้นพื้นฐาน
เพราะเขามีอยู่แล้ว ความสามารถในการค้นหา
ผ่านตัวเลขบนกระดาน
ความทรงจำทั้งหมดของ ตัวเลขไม่ได้ช่วย
เพราะเขายังคงสามารถเป็นเครื่องคอมพิวเตอร์ เพียง แต่มองที่เราได้กล่าวว่าจำนวนหนึ่ง
ขณะนั้น.
ดังนั้นจึงมีการจัดเรียงของการโกงไม่มี มีที่คุณสามารถใช้ประโยชน์จาก
>> ดังนั้นในความเป็นจริงที่ผม ให้การค้นหารายการ
แท้จริงฉันมีเพียงแค่เก็บไป กลับมาผ่านมันถอนขนออก
จำนวนที่น้อยที่สุดต่อไป
และเป็นชนิดที่คุณสามารถอนุมาน จากการเคลื่อนไหวโง่ของฉัน
นี้เพิ่งได้รับมาก น่าเบื่อมากได้อย่างรวดเร็ว
และฉันดูเหมือนจะไปและกลับ มากลับมาไม่น้อย
ตอนนี้จะเป็นธรรมผมไม่ต้องไป ค่อนข้างเป็นที่ดีขอ see-- เป็นธรรม
ฉันไม่ต้องเดินค่อนข้าง ขั้นตอนต่อไปเป็นจำนวนมากในแต่ละครั้ง
เพราะของหลักสูตรที่ผม เลือกหมายเลขจากรายการ
รายการที่เหลือจะรับสั้น
>> และเพื่อให้คิดเกี่ยวกับ วิธีการหลายขั้นตอนฉันจริง
traipsing ผ่านในแต่ละครั้ง
ในสถานการณ์แรก เรามี 16 ตัวเลข
และเพื่อให้ maximally-- ให้เพียง ทำเช่นนี้สำหรับ discussion--
ผมมองผ่าน 16 ตัวเลขเพื่อหาสิ่งที่มีขนาดเล็กที่สุด
แต่เมื่อผมดึงออก จำนวนที่น้อยที่สุดวิธี
ยาวเป็นรายการที่เหลือแน่นอน?
เพียง 15
ดังนั้นวิธีการที่จำนวนตัวเลขได้เบนหรือฉันมี ที่จะมองผ่านครั้งที่สองในรอบ?
15 เพียงเพื่อไปหาที่เล็กที่สุด
แต่ตอนนี้แน่นอนรายการคือ เกินไปมีขนาดเล็กลงกว่า แต่ก่อน
ดังนั้นขั้นตอนวิธีการหลายไม่ฉัน ต้องใช้เวลาต่อไปหรือไม่
14 แล้ว 13 แล้ว 12 บวกจุด จุดจุดจนกว่าฉันซ้ายที่มีเพียงหนึ่ง
ดังนั้นตอนนี้นักวิทยาศาสตร์คอมพิวเตอร์จะ ขอให้ดีสิ่งที่ไม่ว่าทั้งหมดเท่ากัน?
มันจริงเท่ากับคอนกรีตบางส่วน ตัวเลขที่เราสามารถทำได้อย่างแน่นอน
ทำ arithmetically แต่เราต้องการที่จะพูดคุย เกี่ยวกับประสิทธิภาพของอัลกอริทึม
เล็ก ๆ น้อย ๆ 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
มันเป็นเพียงปัจจัยคงที่ นักวิทยาศาสตร์คอมพิวเตอร์จะบอกว่า
Let 's เพียง แต่มุ่งเน้น ตัวแปร really--
ตัวแปรที่ใหญ่ที่สุดในสมการ
>> ค้นหาเพื่อให้เส้นไม่ว่าจะทำอย่างใดอย่างหนึ่ง หน้าในเวลาหนึ่งหรือสองหน้าในเวลา
เป็นประเภทของพื้นฐานเดียวกัน
ก็ยังคงเกี่ยวกับคำสั่งของ n
แต่ผมอ้างว่ามีภาพของฉันก่อนหน้านี้ ว่าอัลกอริทึมที่สามไม่ได้
เชิงเส้น
มันไม่ได้เป็นเส้นตรง
มันเป็นเส้นโค้งและ สูตรพีชคณิตมีอะไร?
เข้าสู่ระบบของ n-- เพื่อเข้าสู่ระบบฐานสอง n
และเราไม่ต้องเข้าไปเกินไป รายละเอียดมากเกี่ยวกับลอการิทึมวันนี้
แต่ส่วนใหญ่นักวิทยาศาสตร์คอมพิวเตอร์จะไม่ แม้จะบอกคุณว่าฐานเป็น
เพราะมันเป็นเพียงแค่ ปัจจัยอย่างต่อเนื่องเพื่อที่จะพูด
ความแตกต่างที่เป็นตัวเลขเพียงเล็กน้อย
และอื่น ๆ นี้จะเป็นเรื่องธรรมดามาก วิธีการใช้คอมพิวเตอร์อย่างเป็นทางการโดยเฉพาะอย่างยิ่ง
นักวิทยาศาสตร์ที่คณะกรรมการหรือ โปรแกรมเมอร์ที่บอร์ดสีขาว
จริงเถียงซึ่ง ขั้นตอนวิธีการที่พวกเขาจะใช้
หรือสิ่งที่มีประสิทธิภาพ ขั้นตอนวิธีการของพวกเขาคือ
>> และนี่คือสิ่งที่ไม่จำเป็น คุณหารือในรายละเอียดที่ดีใด ๆ
แต่เป็นโปรแกรมเมอร์ที่ดีคือคนที่ ที่มีของแข็งพื้นหลังอย่างเป็นทางการ
เขาสามารถที่จะพูดคุยกับ คุณในชนิดของวิธีนี้
และจริงให้ ข้อโต้แย้งที่มีคุณภาพเป็น
ทำไมหนึ่งหรืออัลกอริทึม ชิ้นส่วนของซอฟต์แวร์
จะดีกว่าในบางวิธียังอีก
เพราะคุณสามารถทำได้อย่างแน่นอน เพียงแค่ใช้โปรแกรมของคนคนหนึ่ง
และนับจำนวนวินาที ก็จะใช้เวลาในการจัดเรียงตัวเลขบาง
และคุณสามารถเรียกใช้บางส่วน โปรแกรมบุคคลอื่น
และนับจำนวน วินาทีก็จะใช้เวลา
แต่นี้เป็นวิธีทั่วไปมากขึ้นว่า คุณสามารถใช้ในการวิเคราะห์ขั้นตอนวิธีการ
ถ้าคุณจะเพียงแค่ใน กระดาษหรือเพียงแค่วาจา
โดยไม่ได้ใช้มันโดยไม่ต้อง ได้พยายามปัจจัยการผลิตตัวอย่าง
คุณก็สามารถผ่านมันเหตุผล
และเพื่อให้มีการว่าจ้างนักพัฒนาหรือถ้า มีเขาหรือเธอเรียงลำดับของเถียงกับคุณ
ทำไมขั้นตอนวิธีการของพวกเขาลับของพวกเขา ซอสสำหรับการค้นหาพันล้าน
หน้าเว็บของคุณ บริษัท จะดีกว่านี้
เป็นชนิดของการขัดแย้งพวกเขา ควรจะต้องสามารถที่จะทำให้
หรืออย่างน้อยเหล่านี้เป็น ชนิดของสิ่งที่
ที่จะเกิดขึ้นในการอภิปรายที่ อย่างน้อยในการอภิปรายอย่างเป็นทางการมาก
ก็ดี
ดังนั้นเบนเสนอบางสิ่งบางอย่าง เรียงที่เรียกว่าเลือก
แต่ฉันจะเสนอว่ามี วิธีการอื่น ๆ ของการทำเช่นนี้มากเกินไป
สิ่งที่ฉันไม่ชอบ เกี่ยวกับอัลกอริทึมของเบน
คือว่าเขาเก็บไว้เดินหรือ มีผมเดินกลับมา
และกลับมาและกลับมา
เกิดอะไรขึ้นถ้าแทนฉันกำลังจะทำ บางสิ่งบางอย่างเช่นหมายเลขเหล่านี้ที่นี่
และฉันเป็นเพียงแค่จัดการกับแต่ละ จำนวนในการเปิดเป็นฉันได้รับมันได้หรือไม่
>> ในคำอื่น ๆ ที่นี่ รายการของตัวเลข
สี่หนึ่งสามสอง
และฉันจะทำต่อไปนี้
ฉันจะใส่ตัวเลข ที่พวกเขาอยู่ค่อนข้าง
กว่าการเลือกพวกเขาในช่วงเวลาหนึ่ง
ในคำอื่น ๆ ที่นี่เป็นจำนวนสี่
>> นี่คือรายการเดิมของฉัน
และฉันจะรักษา หลักรายการใหม่ที่นี่
ดังนั้นนี่คือรายการเก่า
นี่คือรายการใหม่
ผมเห็นจำนวนสี่คนแรก
รายการใหม่ของฉันคือครั้งแรกที่ว่างเปล่า ดังนั้นมันจึงเป็นนิด ๆ กรณี
ว่าสี่สารพันรายการในขณะนี้
ฉันเพียงแค่การจำนวนฉันได้รับ และฉันวางไว้ในรายการใหม่ของฉัน
>> เป็นรายการใหม่นี้เรียง?
ใช่.
มันโง่เพราะมีเพียงหนึ่ง องค์ประกอบ แต่มันเรียงอย่างแน่นอน
ไม่มีอะไรที่ออกจากสถานที่
มันน่าสนใจมากขึ้นขั้นตอนวิธีการนี​​้ เมื่อฉันย้ายไปยังขั้นตอนต่อไป
>> ตอนนี้ฉันมีหนึ่ง
ดังนั้นหนึ่งของหลักสูตรเป็นที่ จุดเริ่มต้นหรือจุดสิ้นสุดของรายการใหม่นี้หรือไม่?
การเริ่มต้น.
ดังนั้นผมจึงต้องทำงานบางอย่างในขณะนี้
ฉันได้รับการบางอย่าง เสรีภาพที่มีเครื่องหมายของฉัน
โดยเพียงแค่การวาดภาพสิ่งที่ ที่ฉันต้องการพวกเขา
แต่ที่ไม่ได้จริงๆ ถูกต้องในการใช้คอมพิวเตอร์
คอมพิวเตอร์ที่เรารู้ว่ามี RAM หรือ Random Access Memory,
และนั่นก็คือหนึ่งไบต์และ ไบต์อื่นและอีกไบต์
และถ้าคุณมีกิกะไบต์ของ RAM, คุณมีพันล้านไบต์
แต่พวกเขากำลังทางร่างกายในสถานที่หนึ่ง
คุณก็ไม่สามารถย้ายสิ่งรอบ ๆ โดยการวาดลงบนกระดาน
ที่ไหนก็ได้ที่คุณต้องการ.
ดังนั้นหากรายการใหม่ของฉันมี สี่สถานที่ในหน่วยความจำ
แต่น่าเสียดายที่สี่คือ อยู่ในสถานที่ที่ไม่ถูกต้อง
>> ดังนั้นเพื่อแทรกจำนวนหนึ่ง ฉันไม่สามารถเพียงแค่วาดได้ที่นี่
สถานที่ตั้งของหน่วยความจำนี้ไม่ได้อยู่
ที่จะโกงและฉันได้รับ โกง pictorially ไม่กี่นาที
ที่นี่
ดังนั้นจริงๆถ้าผมต้องการที่จะนำหนึ่งที่นี่ ฉันต้องคัดลอกสี่ชั่วคราว
แล้วใส่หนึ่งมี
>> ที่ดีที่ถูกต้อง ที่เป็นไปได้ในทางเทคนิค
แต่รู้ว่าเป็นงานพิเศษ
ผมไม่ได้เป็นเพียงแค่ใส่หมายเลขในสถานที่
ครั้งแรกที่ผมต้องย้าย จำนวนแล้ววางไว้ในสถานที่
ดังนั้นฉันชนิดของสองเท่าจำนวนเงินของการทำงานของฉัน
ดังนั้นให้ทราบว่า
>> แต่ฉันทำตอนนี้มีองค์ประกอบนี้
ตอนนี้ผมต้องการที่จะคว้าหมายเลขสาม
ที่แน่นอนไม่ได้เป็นสมาชิก?
ในระหว่าง.
ฉันไม่สามารถโกงอีกต่อไป และเพียงแค่ใส่มันมี
เพราะครั้งนี้หน่วยความจำ อยู่ในสถานที่ทางกายภาพ
ดังนั้นผมจึงมีการคัดลอกสี่ และใส่สามมากกว่าที่นี่
ไม่ใช่เรื่องใหญ่.
มันเป็นเพียงหนึ่งขั้นตอนพิเศษ again-- รู้สึกไม่แพงมาก
>> แต่ตอนนี้ผมย้ายไปสอง
ทั้งสองของหลักสูตรเป็นของที่นี่
ตอนนี้คุณเริ่มที่จะดูว่า การทำงานสามารถกองพะเนินเทินทึก
ตอนนี้สิ่งที่ฉันต้องทำอย่างไร
ใช่ฉันต้องย้ายทั้งสี่ จากนั้นผมก็ต้องคัดลอกสาม
และตอนนี้ฉันสามารถแทรกสอง
และจับกับเรื่องนี้ ขั้นตอนวิธีการที่น่าสนใจพอ
คือว่าสมมติว่าเรามีมากขึ้น กรณีที่มันเป็นสมมติว่าแปดเจ็ด
หกห้าสี่สามสองหนึ่ง
นี่คือในบริบทที่หลาย ๆ สถานการณ์กรณีที่เลวร้ายที่สุด
เพราะสิ่งยี้ เป็นอักษรข้างหลัง
>> มันไม่ได้จริงๆ ส่งผลกระทบต่อขั้นตอนวิธีการของเบน
เพราะในการเลือกของเบน การจัดเรียงเขาจะให้
จะกลับมาผ่านรายการ
และเพราะเขากำลังมองเสมอ ผ่านรายการที่เหลืออยู่ทั้งหมด
ชั่งหัวมัน ที่มีองค์ประกอบ
แต่ในกรณีนี้มีการแทรกของฉัน approach-- ลองนี้
>> ดังนั้นหนึ่งสองสามสี่ ห้าหกเจ็ดแปด
หนึ่งสองสามสี่, ห้าหกเจ็ดแปด
ฉันจะใช้เวลาแปด และฉันไม่ใส่มันอยู่ที่ไหน
ดีที่จุดเริ่มต้นของรายการของฉัน เพราะรายการใหม่นี้จะถูกจัดเรียง
และฉันข้ามมันออกมา
>> ฉันจะวางเจ็ดที่ไหน?
ยี้มัน
มันต้องไปที่นั่นเพื่อให้ ฉันต้องทำการคัดลอกบางส่วน
และตอนนี้เจ็ดที่นี่
ตอนนี้ผมย้ายไปหก
ตอนนี้ก็ทำงานมากยิ่งขึ้น
>> แปดได้ไปที่นี่
เซเว่นได้ไปที่นี่
ตอนนี้หกสามารถไปที่นี่
ตอนนี้ผมคว้าห้า
ตอนนี้แปดได้ไป นี่เจ็ดได้ไปที่นี่
หกได้ไปที่นี่และ ตอนนี้ห้าและทำซ้ำ
และผมสวยมาก ย้ายมันอย่างต่อเนื่อง
>> ดังนั้นในตอนท้าย algorithm-- นี้เราจะ เรียกว่าการแทรก sort-- จริง
มีการทำงานมากเกินไป
มันแตกต่างกันเพียง ชนิดของการทำงานกว่าเบน
การทำงานของเบนมีฉันไป ไปมาตลอดเวลา
เลือกต่อไปมีขนาดเล็กที่สุด องค์ประกอบอีกครั้งและอีกครั้ง
ดังนั้นมันจึงเป็นชนิดนี้มากภาพของการทำงาน
>> นี้ขั้นตอนวิธีการอื่น ๆ ซึ่งยังคงเป็น correct-- ก็จะได้งาน done--
เพียงแค่เปลี่ยนปริมาณของการทำงาน
ดูเหมือนว่าในตอนแรกคุณ ประหยัดเพราะคุณเพียงแค่
การจัดการกับแต่ละองค์ประกอบ ขึ้นด้านหน้าโดยไม่ต้องเดินทั้งหมด
ทางผ่านรายการเช่นเบนเป็น
แต่ที่เป็นปัญหาเหล​​่านี้โดยเฉพาะอย่างยิ่งใน กรณีบ้าที่มันทั้งหมดไปข้างหลัง
คุณเพียงแค่ชนิดของ เลื่อนการทำงานอย่างหนัก
จนกว่าคุณจะมีการแก้ไขข้อผิดพลาดของคุณ
>> และดังนั้นหากคุณสามารถคิดนี้ แปดเจ็ดหกห้า
และต่อมาสามสี่และสอง การเคลื่อนย้ายทางของพวกเขาผ่านรายการ
เราได้เปลี่ยนเพียง ประเภทของงานที่เรากำลังทำ
แทนการทำที่ จุดเริ่มต้นของการทำซ้ำของฉัน
ฉันแค่ทำมันที่ ท้ายของทุกซ้ำ
ดังนั้นจึงปรากฎว่าอัลกอริทึมนี้ เกินไปโดยทั่วไปเรียกว่าการแทรกเรียงลำดับ
ยังเป็นคำสั่งของ n ยืด
จริง ๆ แล้วมันไม่มีดีกว่า ไม่ดีที่ทั้งหมด
>> แต่มีวิธีการที่สาม ฉันจะให้กำลังใจเราที่จะต้องพิจารณา
ซึ่งเป็นแบบนี้
ดังนั้นคิดว่ารายการของฉันสำหรับความเรียบง่าย อีกครั้งเป็นสี่หนึ่งสาม
two-- เพียงตัวเลขสี่
เบนมีสัญชาตญาณที่ดี สัญชาตญาณของมนุษย์ที่ดี
ก่อนโดยที่เราคงที่ทั้งหมด รายการ eventually-- เรียงแทรก
ผมเกลี้ยกล่อมเราพร้อม
แต่ขอพิจารณา วิธีที่ง่ายที่สุดในการแก้ไขรายการนี​​้
>> รายการนี​​้ไม่ได้เรียง
ทำไม?
ในภาษาอังกฤษอธิบายว่าทำไม มันไม่ได้เรียงจริง
มันหมายความว่าอะไรที่จะไม่ถูกจัดเรียง?
>> นักศึกษา: มันไม่ได้เรียงตามลำดับ
>> DAVID ลัน: ไม่ได้เรียงตามลำดับ
ให้ฉันตัวอย่าง
>> นักศึกษา: ใส่ไว้ในการสั่งซื้อ
>> DAVID ลัน: OK
ให้ฉันเป็นตัวอย่างที่เฉพาะเจาะจงมากขึ้น
>> นักศึกษา: เรียงลำดับขึ้น
DAVID ลัน: เพื่อไม่น้อยไปหามาก
จะแม่นยำมากขึ้น
ผมไม่ทราบว่าสิ่งที่คุณหมายถึงโดยจากน้อยไปมาก
มีอะไรผิดหรือเปล่า?
>> นักศึกษา: ที่เล็กที่สุดของ ตัวเลขไม่ได้อยู่ในพื้นที่เป็นครั้งแรก
>> DAVID ลัน: จำนวนที่น้อยที่สุดของ ไม่ได้อยู่ในพื้นที่เป็นครั้งแรก
เฉพาะเจาะจงมากขึ้น.
ฉันเริ่มที่จะจับ
เรากำลังนับ แต่ สิ่งที่ออกคำสั่งที่นี่?
>> นักศึกษา: ลำดับตัวเลข
DAVID ลัน: ลำดับตัวเลข
ชนิดของการรักษาของทุกคน มัน here-- ระดับที่สูงมาก
เพียงแค่ตัวอักษรบอกฉันว่า ที่ไม่ถูกต้องเช่นอาจห้าปี
>> นักศึกษา: บวกหนึ่ง
>> DAVID ลัน: สิ่งที่?
>> นักศึกษา: บวกหนึ่ง
>> DAVID ลัน: สิ่งใดที่คุณหมายถึงหนึ่งบวก?
ให้ฉันที่แตกต่างกันห้าปี
มีอะไรผิดปกติแม่?
มีอะไรผิดปกติพ่อ?
คุณหมายถึงอะไรนี้ไม่ได้เรียง?
>> นักศึกษา: มันไม่ได้เป็นสถานที่ที่เหมาะสม
>> DAVID ลัน: มีอะไร ไม่ได้อยู่ในสถานที่ที่เหมาะสมหรือไม่
>> นักศึกษา: สี่
DAVID ลัน: ตกลงที่ดี
ดังนั้นสี่ไม่ได้ที่มันควรจะเป็น
โดยเฉพาะอย่างยิ่งเป็นสิทธินี้หรือไม่?
สี่และเป็นหนึ่งในครั้งแรก ตัวเลขสองผมเห็น
นี่คือใช่มั้ย?
ไม่มีพวกเขากำลังออกคำสั่งใช่มั้ย?
ในความเป็นจริงคิดว่าตอนนี้ เกี่ยวกับคอมพิวเตอร์ได้อีกด้วย
มันสามารถมองไปที่อาจจะเป็นหนึ่ง, บางทีสองสิ่งที่ once--
และที่จริงเพียงสิ่งเดียว ในเวลา แต่อย่างน้อยสามารถ
มองไปที่สิ่งหนึ่งแล้ว สิ่งต่อไปที่ขวาถัดไป
>> ดังนั้นเหล่านี้ในการสั่งซื้อ
ไม่แน่นอน
เพื่อให้คุณรู้อะไรไหม
ทำไมเราไม่ใช้ทารก ขั้นตอนการแก้ไขปัญหานี้
แทนการทำแฟนซีเหล่านี้ ขั้นตอนวิธีการเช่นเบนที่
เขาเรียงลำดับของการแก้ไขมันโดย วนลูปผ่านรายการ
แทนการทำสิ่งที่ฉันได้ที่ ฉันเพียงแค่ชนิดของมันคงที่ที่เราไป?
ขอเพียงอย่างแท้จริงทำลายลง ความคิดของลำดับตัวเลข order--,
เรียกมันว่าสิ่งที่คุณ want-- เข้าสู่การเปรียบเทียบจากจำนวนเหล่านี้
>> และเป็นหนึ่งในสี่
นี่คือคำสั่งที่ถูกต้องหรือไม่
ดังนั้นขอให้แก้ไขปัญหาที่
หนึ่งและสี่แล้ว เราก็จะคัดลอก
สิทธิทั้งหมดที่ดี
ฉันคงหนึ่งและสี่
สามสอง?
เลขที่
ให้ตรงกับคำพูดของฉันมือของฉัน
สี่และสาม?
>> มันไม่ได้ในการสั่งซื้อดังนั้นฉันจะ ที่จะทำอย่างใดอย่างหนึ่งสามสี่สอง
OK ดี.
ตอนนี้สี่สอง?
เราจำเป็นต้องแก้ไขปัญหานี้มากเกินไป
ดังนั้นหนึ่งในสามสองสี่
ดังนั้นมันจึงจะถูกจัดเรียง?
ไม่มี แต่มันเป็นสิ่งที่ใกล้ชิดกับการเรียง?
>> มันเป็นเพราะเราได้รับการแก้ไขนี้ ความผิดพลาดที่เราคงผิดพลาดนี้
และเราคงผิดพลาดนี้
ดังนั้นเราจึงคงสามข้อผิดพลาดเนื้อหา
ยังคงไม่ได้จริงๆมองเรียงลำดับ แต่ มันเป็นวัตถุที่ใกล้ชิดกับการเรียงลำดับ
เพราะเราได้รับการแก้ไขบางส่วนของความผิดพลาดเหล่านั้น
>> ตอนนี้สิ่งที่ฉันจะทำต่อไปหรือไม่
ชนิดของฉันมาถึงจุดสิ้นสุดของรายการ
ฉันดูเหมือนจะได้รับการแก้ไข ทุกความผิดพลาด แต่ไม่มี
เพราะในกรณีนี้ตัวเลขบาง อาจจะมีฟองขึ้นอย่างใกล้ชิด
ไปยังหมายเลขอื่น ๆ ที่ ยังคงมีการออกคำสั่ง
ดังนั้นขอทำมันอีกครั้งและผมจะ เพียงแค่ทำมันในสถานที่เวลานี้
หนึ่งและสาม?
ทุกอย่างปกติดี.
สามสอง?
ไม่มีแน่นอนจึงขอเปลี่ยนที่
ดังนั้นสองสาม
สามและสี่?
และตอนนี้ขอเพียงแค่เป็น อวดความรู้โดยเฉพาะอย่างยิ่งที่นี่
มันจะถูกจัดเรียง?
มนุษย์คุณรู้ว่ามันเรียง
>> ฉันควรจะลองอีกครั้ง
โอลิเวียดังนั้นจะเสนอผมลองอีกครั้ง
ทำไม?
เนื่องจากคอมพิวเตอร์ไม่ได้มี ความหรูหราของตามนุษย์ของเรา
เพียง glancing back-- ตกลงฉันทำ
วิธีการที่ไม่ตรวจสอบคอมพิวเตอร์ ว่ารายการจะถูกจัดเรียงในตอนนี้?
ในทางกลไก
>> ฉันควรจะไปผ่าน อีกครั้งและเพียงถ้าฉัน
ไม่ได้ทำ / พบข้อผิดพลาดใด ๆ ที่สามารถฉัน แล้วสรุปเป็นคอมพิวเตอร์ครับ
เราจะดีไป
ดังนั้นหนึ่งและสองสอง สามสามและสี่
ตอนนี้ผมสามารถพูดได้อย่างแน่นอนนี้คือ เรียงเพราะผมทำไม่มีการเปลี่ยนแปลง
ตอนนี้มันจะเป็นข้อผิดพลาดและเพียงแค่ โง่ถ้าฉัน, คอมพิวเตอร์
ถามคำถามเดียวกันนั้นอีกครั้ง คาดหวังว่าคำตอบที่แตกต่างกัน
ไม่ควรเกิดขึ้น
>> และดังนั้นตอนนี้รายการจะเรียง
แต่น่าเสียดายที่เวลาการทำงานของ ขั้นตอนวิธีนี้ยังเป็น n Squared
ทำไม?
เพราะคุณมีตัวเลข n และใน กรณีที่เลวร้ายคุณจะต้องย้ายหมายเลข n
n ครั้งเพราะคุณจะต้องเก็บไป กลับไปตรวจสอบและอาจแก้ไข
ตัวเลขเหล่านี้
และเราสามารถทำขึ้น การวิเคราะห์อย่างเป็นทางการเกินไป
>> ดังนั้นนี่คือสิ่งที่จะบอกว่าเราได้ดำเนินการ สามวิธีที่แตกต่างกันอย่างใดอย่างหนึ่ง
ของพวกเขาที่ใช้งานง่ายทันที ปิดค้างคาวจากเบน
เพื่อแทรกแนะนำของฉัน การจัดเรียงให้เป็นหนึ่งในนี้
ที่คุณชนิดของการสูญเสียสายตาของ ป่าสำหรับต้นไม้แรก
แต่แล้วถ้าคุณจะใช้ขั้นตอนกลับ voila เราได้รับการแก้ไขการเรียงลำดับความคิด
ดังนั้นนี่คือกล้าพูดว่า ระดับที่ต่ำกว่าบางที
กว่าบางส่วนของผู้อื่น อัลกอริทึม แต่ขอ
ดูว่าเราไม่สามารถมองเห็นภาพ เหล่านี้โดยวิธีการนี​​้
>> ดังนั้นนี่คือบางอย่างดี ซอฟแวร์ที่มีคน
เขียนโดยใช้บาร์ที่มีสีสันที่เป็น จะทำต่อไปนี้สำหรับเรา
แต่ละแถบเหล่านี้แสดงให้เห็นถึงตัวเลข
บาร์สูงที่ใหญ่กว่า จำนวนที่มีขนาดเล็กบาร์
ที่มีขนาดเล็กจำนวน
ดังนั้นความนึกคิดเราต้องการพีระมิดที่ดี ซึ่งจะเริ่มมีขนาดเล็กและได้รับใหญ่
และนั่นจะหมายถึงว่า แถบเหล่านี้จะถูกจัดเรียง
ดังนั้นฉันจะไปข้างหน้าและเลือก ตัวอย่างเช่นอัลกอริทึมของเบน
การจัดเรียงตัวเลือก first--
>> และสังเกตเห็นสิ่งที่มันทำ
วิธีที่พวกเขาได้รับเลือกให้เป็น เห็นภาพขั้นตอนวิธีนี้
คือว่าเหมือนที่ผมเป็น เดินผ่านรายการของฉัน
โปรแกรมนี้คือการเดิน ผ่านรายการของตัวเลข
ไฮไลท์ในสีชมพูแต่ละ ตัวเลขที่มันมองไปที่
และสิ่งที่กำลังจะเกิดขึ้นในตอนนี้?
>> จำนวนที่น้อยที่สุดที่ ฉันหรือเบนพบกึก
ได้รับการย้ายไปยังจุดเริ่มต้นของรายการ
และแจ้งให้ทราบว่าพวกเขาไม่ได้ขับไล่ หมายเลขที่อยู่ที่นั่น
และที่ดีอย่างสมบูรณ์
ฉันไม่ได้รับในระดับของรายละเอียดที่
แต่เราจำเป็นต้องใส่ ตัวเลขที่อยู่ที่ไหนสักแห่ง
ดังนั้นเราเพิ่งย้ายไปยัง เปิดจุดที่ถูกสร้างขึ้น
ดังนั้นฉันจะเพิ่มความเร็วในการนี​​้ ขึ้นเพราะมิฉะนั้นมัน
กลายเป็นที่น่าเบื่อมากได้อย่างรวดเร็ว
แอนิเมชั่ speed-- มีที่เราจะไป
ดังนั้นตอนนี้หลักการเดียวกัน ผมก็ใช้ แต่คุณ
สามารถเริ่มต้นที่จะรู้สึกอัลกอริทึมถ้าคุณ จะหรือเห็นมันเล็ก ๆ น้อย ๆ อย่างเห็นได้ชัด
และขั้นตอนวิธีนี้มีผลกระทบของ การเลือกองค์ประกอบที่เล็กถัดไป
เพื่อให้คุณกำลังจะเริ่ม เห็นมันทางลาดขึ้นทางด้านซ้าย
และในแต่ละซ้ำเป็นฉัน เสนอก็ไม่ได้ทำงานน้อยลงเพียงเล็กน้อย
มันไม่จำเป็นต้องไปตลอดทาง กลับไปทางซ้ายสุดของรายการ
เพราะมันอยู่แล้ว รู้เหล่านั้นจะถูกจัดเรียง
ดังนั้นชนิดของมันให้ความรู้สึกเหมือนมัน เร่งแม้ว่าแต่ละขั้นตอนคือ
การจำนวนเดียวกันของเวลา
มีเพียงขั้นตอนที่เหลือน้อยลง
และตอนนี้คุณสามารถชนิดของความรู้สึก ขั้นตอนวิธีการทำความสะอาดจุดสิ้นสุดของมัน
และแน่นอนตอนนี้ก็เรียง
>> ดังนั้นการจัดเรียงแทรกจะทำทั้งหมด
ฉันจำเป็นต้องสุ่มอาร์เรย์
และแจ้งให้ทราบที่ฉันสามารถทำได้เพียงแค่ ให้สุ่มมัน
และเราจะได้รับการประมาณการของ วิธีการเดียวกันเรียงแทรก
ผมขอชะลอตัวลงไปที่นี่
ขอเริ่มต้นที่มากกว่า
หยุด.
>> Let 's ข้ามสี่
เราจะไปที่นั่น.
สุ่มอาร์เรย์พวกเขา
และที่นี่เรา go-- เรียงแทรก
เล่น.
ขอให้สังเกตว่ามันจัดการกับแต่ละ องค์ประกอบพบทันที
แต่ถ้ามันอยู่ใน แจ้งให้ทราบสถานที่ที่ผิด
ทั้งหมดของการทำงานที่มีที่จะเกิดขึ้น
เราจะต้องเก็บขยับมากขึ้น และองค์ประกอบอื่น ๆ อีกมากมายที่จะทำให้ห้อง
เพื่อคนที่เราต้องการที่จะใส่ในสถานที่
>> ดังนั้นเราจึงมุ่งเน้นไปที่ ปลายด้านซ้ายของรายการเท่านั้น
แจ้งให้ทราบว่าเราไม่ได้มองแม้ at-- เรา ไม่ได้เน้นในสิ่งที่สีชมพู
ไปทางขวา.
เราเพียงแค่การจัดการกับ ปัญหาที่เกิดขึ้นในขณะที่เราไป
แต่เรากำลังสร้างจำนวนมาก ทำงานเพื่อตัวเราเองยังคง
ดังนั้นถ้าเราเพิ่มความเร็วในการนี​​้ขึ้น ตอนนี้จะไปเสร็จสิ้น
มันมีความรู้สึกที่แตกต่างกันไปแน่นอน
มันเป็นเพียงแค่มุ่งเน้นไปที่ปลายด้านซ้าย แต่ ทำทำงานมากขึ้นน้อยที่สุดเท่าที่ needed--
ชนิดของสิ่งที่ราบเรียบ มากกว่าการแก้ไขสิ่ง
แต่ในท้ายที่สุดการจัดการกับ แต่ละองค์ประกอบหนึ่งที่เวลา
จนกว่าเราจะได้รับไปยังผู้คนทั่วไปดีเรา ทุกคนรู้วิธีนี้จะจบ
ดังนั้นจึงเป็น underwhelming เล็ก ๆ น้อย ๆ อาจจะ
>> แต่รายการใน end-- ที่ spoiler-- เป็นไปได้เรียง
เพื่อให้ดูที่หนึ่งคนสุดท้าย
เราก็ไม่สามารถข้ามขั้นตอนนี้
เราเกือบจะมี
สองไปหนึ่งที่จะไป
และ voila
ยอดเยี่ยม
>> ดังนั้นตอนนี้ขอทำหนึ่งคนสุดท้าย อีกครั้งกับการจัดเรียงสุ่มฟอง
และแจ้งให้ทราบที่นี่โดยเฉพาะอย่างยิ่งถ้าฉันช้า ลงนี้ไม่ให้บินโฉบผ่าน
แต่สังเกตเห็นมันก็ทำให้คู่ การจัดเรียง comparisons-- ของการแก้ปัญหาในท้องถิ่น
แต่ทันทีที่เราได้รับ ตอนท้ายของรายการในสีชมพูที่
สิ่งที่จะต้องเกิดขึ้นอีกครั้งหรือไม่
ใช่มันจะต้อง เริ่มต้นเพราะเพียง
ความผิดพลาดจากจำนวนคงที่
และอาจจะมีการเปิดเผยยังคนอื่น ๆ
และดังนั้นหากคุณเพิ่มความเร็วในการนี​​้ขึ้นคุณจะ เห็นว่ามากที่สุดเท่าที่ชื่อมีความหมาย
ที่มีขนาดเล็ก elements-- หรือมากกว่า elements-- ขนาดใหญ่จะเริ่มต้น
ฟองขึ้นไปด้านบนถ้าคุณจะ
และองค์ประกอบที่มีขนาดเล็ก เริ่มต้นที่จะฟองลงไปทางซ้าย
และแน่นอนว่าเป็นชนิดของ ผลภาพได้เป็นอย่างดี
และอื่น ๆ นี้จะจบลงด้วยการตกแต่ง ในลักษณะที่คล้ายกันมากเกินไป
>> เราไม่ได้มีที่จะอาศัยอยู่ ในหนึ่งนี้โดยเฉพาะ
ผมขอเปิดตอนนี้มากเกินไป
มีเพียงไม่กี่ขั้นตอนวิธีการเรียงลำดับอื่น ๆ ในโลกที่ไม่กี่ที่
ถูกจับที่นี่
และโดยเฉพาะอย่างยิ่งสำหรับผู้เรียนที่ไม่ได้เป็น จำเป็นต้องภาพหรือคณิตศาสตร์
ในขณะที่เราทำมาก่อนที่เราสามารถทำได้ นอกจากนี้ยังทำเช่นนี้ audially
ถ้าเราเชื่อมโยงเสียงกับเรื่องนี้
และเพียงเพื่อความสนุกสนานที่นี่เป็น ขั้นตอนวิธีการที่แตกต่างกันไม่กี่
และหนึ่งในนั้นโดยเฉพาะอย่างยิ่งคุณ จะแจ้งให้ทราบเป็นที่เรียกว่า "merge sort."
>> มันเป็นจริงเป็นพื้นฐาน ขั้นตอนวิธีการที่ดีกว่า
เช่นที่ผสานการเรียงลำดับหนึ่ง คนที่คุณกำลังจะเห็น
ไม่ได้เป็นคำสั่งของ n Squared
มันอยู่ในคำสั่งของ n ครั้งเข้าสู่ระบบของ n ที่เป็นจริงและทำให้มีขนาดเล็กลง
ได้เร็วขึ้นกว่าที่อื่น ๆ อีกสาม
และมีคู่อื่น ๆ คนโง่ที่เราจะเห็น
>> ดังนั้นที่นี่เราไปกับเสียงบาง
นี่คือการจัดเรียงแทรกดังนั้นอีกครั้ง มันเป็นเพียงแค่การจัดการกับองค์ประกอบ
ที่พวกเขามา
นี้จะเรียงลำดับฟองดังนั้นจึงเป็นเรื่อง คิดของพวกเขาเป็นคู่ที่เวลา
และอีกครั้งในองค์ประกอบที่ใหญ่ที่สุด กำลังเดือดปุด ๆ ขึ้นไปด้านบน
>> ถัดไปขึ้นเรียงตัวเลือก
นี่คือขั้นตอนวิธีการของเบนที่ อีกครั้งที่เขาเลือกซ้ำ
องค์ประกอบที่เล็กต่อไป
และอีกครั้งตอนนี้คุณสามารถจริงๆได้ยินว่า ก็เร่งขึ้น แต่เฉพาะในเพื่อให้ห่างไกล
ในขณะที่มันทำน้อยลงและน้อย ทำงานในแต่ละซ้ำ
นี่คือการได้เร็วขึ้นหนึ่งผสานเรียงลำดับ ซึ่งเป็นกลุ่มเรียงลำดับของตัวเลข
ร่วมกันแล้วรวมพวกเขา
ดังนั้น look-- ซ้าย ครึ่งหนึ่งจะถูกจัดเรียงไว้แล้ว
>> ตอนนี้ก็เรียงลำดับครึ่งขวาและ ตอนนี้ก็จะรวมเป็นหนึ่ง
นี่คือสิ่งที่เรียกว่า "การจัดเรียง Gnome."
และชนิดที่คุณสามารถเห็นได้ว่า มันจะกลับมา
แก้ไขการทำงานนิด ๆ หน่อย ๆ ที่นี่ ก่อนที่มันจะมีวิธีการที่จะได้งานใหม่
และที่มัน
มีการจัดเรียงอื่นซึ่งเป็นเป็น จริงเพียงเพื่อวัตถุประสงค์ทางวิชาการ
ที่เรียกว่า "การจัดเรียงโง่" ซึ่งจะใช้เวลา ข้อมูลของคุณจะเรียงลำดับมันสุ่ม
และจากนั้นจะตรวจสอบหากมีการจัดเรียง
และถ้ามันไม่ได้ก็อีกครั้งมันแปลก ๆ สุ่มตรวจสอบหากมีการเรียงลำดับ
และถ้าไม่ซ้ำ
และในทางทฤษฎีความน่าจะเป็น นี้จะเสร็จสมบูรณ์
แต่หลังจากที่ค่อนข้างน้อยของเวลา
มันไม่ได้เป็นส่วนใหญ่ ที่มีประสิทธิภาพของอัลกอริทึม
ดังนั้นคำถามใด ๆ เกี่ยวกับผู้ที่ โดยเฉพาะอย่างยิ่งขั้นตอนวิธีการหรืออะไร
ที่เกี่ยวข้องมีมากเกินไป?
>> ดีตอนนี้ขอแซวนอกเหนือสิ่งที่ทุก เส้นเหล่านี้ที่ฉันได้รับการวาดภาพ
และสิ่งที่ฉันสมมติคอมพิวเตอร์ สามารถทำได้ภายใต้ฝากระโปรง
ฉันจะยืนยันว่าทั้งหมดของตัวเลขเหล่านี้ ฉันเก็บ drawing-- ที่พวกเขาต้องการที่จะได้รับ
เก็บไว้ที่อื่นในหน่วยความจำ
เราจะได้รับการกำจัดของผู้ชายคนนี้ตอนนี้มากเกินไป
>> ดังนั้นชิ้นส่วนของหน่วยความจำใน computer-- ดังนั้น RAM DIMM คือ
สิ่งที่เราค้นหาเมื่อวานนี้คู่ หน่วยความจำแบบอินไลน์ module-- ลักษณะเช่นนี้
และแต่ละชิปสีดำเล็ก ๆ น้อย ๆ เหล่านี้ เป็นจำนวนไบต์บางโดยทั่วไป
แล้วพินทองเช่น สายไฟที่เชื่อมต่อกับคอมพิวเตอร์
และคณะกรรมการซิลิกอนสีเขียวเป็นเพียง สิ่งที่ช่วยให้ทุกอย่างทั้งหมดเข้าด้วยกัน
ดังนั้นสิ่งนี้จริงๆหมายถึงอะไร
ถ้าผมชนิดของการวาดภาพเดียวกันนี้ สมมติสำหรับความเรียบง่าย
ที่ DIMM นี้คู่ โมดูลหน่วยความจำแบบอินไลน์
เป็นหนึ่งกิกะไบต์ของ RAM, หนึ่งกิกะไบต์ของ หน่วยความจำซึ่งเป็นวิธีการที่หลายไบต์รวม?
หนึ่งกิกะไบต์เป็นไบต์หลายวิธี?
ยิ่งไปกว่านั้น.
1,124 กิโลกรัมเป็น 1,000
เมกะล้าน
Giga เป็นพันล้าน
>> ฉันกำลังโกหก?
เราสามารถแม้แต่จะอ่านฉลาก?
นี้เป็นจริง 128 กิกะไบต์ดังนั้นมันมากขึ้น
แต่เราจะหลอกนี้ เป็นเพียงหนึ่งกิกะไบต์
เพื่อที่ว่าหมายความว่ามีเป็นพันล้าน ไบต์ของหน่วยความจำที่มีให้ฉัน
หรือ 8 พันล้านบิต แต่เรากำลังจะ ที่จะพูดคุยในแง่ของไบต์ในขณะนี้
ก้าวไปข้างหน้า
>> ดังนั้นสิ่งที่หมายถึงคือนี้อยู่ หนึ่งไบต์นี้เป็นไบต์อื่น
นี้เป็นไบต์อื่น และถ้าเราต้องการจริงๆ
จะเฉพาะเจาะจงเราจะต้อง วาดพันล้านสี่เหลี่ยมเล็ก ๆ
แต่สิ่งที่หมายความว่า?
ดีให้ฉันเพียงซูม ในภาพนี้
ถ้าฉันมีบางสิ่งบางอย่างที่มีลักษณะ เช่นนี้ตอนนี้ที่สี่ไบต์
>> และดังนั้นผมจึงสามารถใส่ตัวเลขสี่ตัวที่นี่
หนึ่งสองสามสี่.
หรือฉันสามารถใส่สี่ตัวอักษรหรือสัญลักษณ์
"เฮ้!" สามารถไปที่นั่น เพราะแต่ละตัวอักษร
เราพูดถึงก่อนหน้านี้ อาจจะแสดง
กับแปดบิตหรือ ASCII หรือไบต์
ดังนั้นในคำอื่น ๆ ที่คุณสามารถทำได้ ใส่ 8 พันล้านสิ่งที่อยู่ภายใน
นี้อย่างใดอย่างหนึ่งติดของหน่วยความจำ
ตอนนี้มันหมายความว่าอะไรที่จะนำสิ่งที่กลับมา เพื่อกลับไปกลับในหน่วยความจำเช่นนี้หรือไม่
นี่คือสิ่งที่เป็นโปรแกรมเมอร์ จะเรียกว่า "อาเรย์."
ในโปรแกรมคอมพิวเตอร์ที่คุณไม่คิดว่า เกี่ยวกับฮาร์ดแวร์พื้นฐานต่อ se
คุณเพียงแค่คิดว่าตัวเองมี การเข้าถึงทั้งหมดพันล้านไบต์
และคุณสามารถสิ่งที่คุณต้องการด้วย
แต่เพื่อความสะดวก มันมีประโยชน์โดยทั่วไป
เพื่อให้สิทธิความจำของคุณ ถัดจากแต่ละอื่น ๆ เช่นนี้
ดังนั้นถ้าฉันซูมใน this-- เพราะเราไม่ได้ไปแน่นอน
การวาดพันล้าน squares-- เล็ก ๆ น้อย ๆ สมมติว่าบอร์ดนี้แสดงให้เห็นถึง
ติดของหน่วยความจำที่ตอนนี้
และฉันก็จะวาดมากที่สุดเท่าที่ฉัน เครื่องหมายจบลงให้ผมมาที่นี่
ดังนั้นตอนนี้เรามีการติด ของหน่วยความจำบนกระดาน
ที่มีหนึ่งสองสามสี่ห้า หกหนึ่งสองสามสี่ห้าหก
ดังนั้น seven-- 42 ไบต์ หน่วยความจำบนหน้าจอทั้งหมด
ขอขอบคุณ.
ใช่ทำถูกเลขคณิตของฉัน
ดังนั้น 42 ไบต์ของหน่วยความจำที่นี่
ดังนั้นสิ่งนี้จริงหมายถึงอะไร
ดีโปรแกรมคอมพิวเตอร์ จริงจะโดยทั่วไป
คิดว่าหน่วยความจำนี้เป็นแอดเดรส
ในคำอื่น ๆ ทุกคนของเหล่านี้ สถานที่ในหน่วยความจำในฮาร์ดแวร์
มีที่อยู่ที่ไม่ซ้ำกัน
>> มันไม่ได้ซับซ้อนเท่าหนึ่งเสียงอึกทึก สแควร์, Cambridge, Mass. 02138
แต่มันเป็นเพียงตัวเลข
นี่คือจำนวนไบต์ศูนย์นี้เป็น หนึ่งในนี้เป็นสองนี้เป็นสาม
และนี่คือ 41
เดี๋ยวก่อน.
ฉันคิดว่าฉันกล่าวว่า 42 ช่วงเวลาที่ผ่านมา
ผมเริ่มนับที่ศูนย์ เพื่อให้เป็นจริงที่ถูกต้อง
ตอนนี้เราไม่ได้มีการวาดที่จริงมัน เป็นตารางและถ้าคุณวาดเป็นตาราง
ผมคิดว่าสิ่งที่จริง ได้รับบิตทำให้เข้าใจผิด
สิ่งที่จะเป็นโปรแกรมเมอร์, ในใจของเขาหรือเธอเอง
โดยทั่วไปคิดว่านี้ หน่วยความจำที่เป็นอยู่เช่นเดียวกับเทป
เช่นชิ้นส่วนของเทปกำบัง ที่เพิ่งไปบนและบนตลอดไป
หรือจนกว่าคุณจะวิ่งออกมาจากหน่วยความจำ
ดังนั้นวิธีที่ใช้กันมากขึ้นในการวาด และเพียงแค่คิดเกี่ยวกับหน่วยความจำ
จะว่านี่คือไบต์ศูนย์หนึ่ง สอง, สาม, และจากนั้นจุดจุดจุด
และคุณมี 42 ไบต์ดังกล่าวรวมแม้กระทั่ง แม้ว่าร่างกายมันอาจจริง
เป็นสิ่งที่มากขึ้นเช่นนี้
>> ดังนั้นถ้าตอนนี้คุณคิดว่าคุณ หน่วยความจำเช่นนี้เช่นเดียวกับเทป
นี้คือสิ่งที่เป็นโปรแกรมเมอร์อีกครั้ง จะเรียกอาร์เรย์ของหน่วยความจำ
และเมื่อคุณต้องการในการจัดเก็บจริง บางสิ่งบางอย่างในหน่วยความจำของคอมพิวเตอร์
คุณมักจะทำสิ่งที่ร้านค้า กลับไปกลับไปกลับไปกลับ
ดังนั้นเราจึงได้รับการพูดคุยเกี่ยวกับตัวเลข
และเมื่อฉันต้องการที่จะแก้ปัญหา เช่นสี่หนึ่งสามสอง
แม้ว่าฉันเป็นเพียงแค่การวาดภาพ เพียงตัวเลขสี่หนึ่งสาม
สองบนกระดานคอมพิวเตอร์จะ จริงๆมีการตั้งค่านี้ในหน่วยความจำ
>> และสิ่งที่จะติดกับ สองในหน่วยความจำของคอมพิวเตอร์?
ดีมีคำตอบว่าไม่มี
เราไม่ทราบจริงๆ
และตราบเท่าที่ คอมพิวเตอร์ไม่จำเป็นต้องใช้มัน
มันไม่ได้มีการดูแลสิ่งที่เป็นไป ไปยังหมายเลขที่มันไม่เกี่ยวกับการดูแล
และเมื่อฉันกล่าวว่าก่อนหน้านี้ว่าคอมพิวเตอร์ เท่านั้นที่สามารถดูที่อยู่ในช่วงเวลาหนึ่ง,
นี้เป็นชนิดที่ว่าทำไม
>> ไม่แตกต่างจากการบันทึก ผู้เล่นและหัวอ่าน
เพียง แต่ความสามารถในการมองไปที่บาง ร่องในบันทึกเก่าโรงเรียนทางกายภาพ
ในเวลาที่ใกล้เคียงกัน สามารถขอบคุณคอมพิวเตอร์
เพื่อ CPU และของมัน Intel ชุดคำสั่ง
ในหมู่ผู้ที่มีการเรียนการสอน ถูกอ่านจากหน่วยความจำ
หรือบันทึก memory-- คอมพิวเตอร์เท่านั้นสามารถดู
ที่สถานที่หนึ่งที่ time-- บางครั้งการรวมกันของพวกเขา
แต่จริงๆเพียงแค่สถานที่หนึ่งที่เวลา
ดังนั้นเมื่อเรากำลังทำ เหล่านี้ขั้นตอนวิธีการต่างๆ
ฉันไม่ได้เพียงแค่เขียนใน vacuum-- สี่หนึ่งสามสอง
ตัวเลขเหล่านี้เป็นของจริง ที่ไหนสักแห่งในหน่วยความจำทางกายภาพ
ดังนั้นจึงมีเล็ก ๆ น้อย ทรานซิสเตอร์หรือบางชนิด
ของอุปกรณ์อิเล็กทรอนิกส์ภายใต้ เครื่องดูดควันเก็บค่าเหล่านี้
>> และรวมบิตกี่ ที่เกี่ยวข้องกับการอยู่ในขณะนี้เพียงเพื่อจะชัดเจน?
ดังนั้นนี่คือสี่ไบต์หรือ ตอนนี้ก็ 32 บิตรวม
ดังนั้นมีจริง 32 ศูนย์และ คนเขียนสี่สิ่งเหล่านี้
มีมากยิ่งขึ้นกว่าที่นี่ แต่ อีกครั้งที่เราไม่สนใจเกี่ยวกับว่า
>> ดังนั้นตอนนี้ขอถามอีก คำถามโดยใช้หน่วยความจำ
เนื่องจากว่าในตอนท้าย ในวันนี้คือในความแปรปรวน
ไม่ว่าสิ่งที่เราอาจจะทำอย่างไรกับ คอมพิวเตอร์ในตอนท้ายของวัน
ฮาร์ดแวร์ยังคงเป็น เดียวกันภายใต้ฝากระโปรง
ฉันจะเก็บคำในที่นี่?
ดีคำในเครื่องคอมพิวเตอร์เช่น "เฮ้!" จะถูกเก็บไว้เพียงเช่นนี้
และถ้าคุณต้องการอีกต่อไป คำที่คุณสามารถเพียง
เขียนทับที่และพูดอะไรบางอย่าง เช่น "สวัสดี" และร้านค้าที่นี่
>> และเพื่อให้ที่นี่เกินไป contiguousness นี้ เป็นจริงได้เปรียบ
เพราะคอมพิวเตอร์สามารถเพียง อ่านจากขวาไปซ้าย
แต่นี่คือคำถาม
ในบริบทของคำนี้ H-E-L-L-o, เครื่องหมายอัศเจรีย์
วิธีการใช้คอมพิวเตอร์อาจจะทราบว่า คำที่เริ่มต้นและคำลงท้าย?
ในบริบทของตัวเลข วิธีการที่ไม่คอมพิวเตอร์
รู้นานลำดับของวิธีการ หมายเลขหรือที่มันเริ่มต้น?
ดีก็จะเปิด out-- และเราจะไม่ไปมากเกินไป
ลงไปในระดับของ detail-- นี้ คอมพิวเตอร์ย้ายสิ่งรอบ ๆ ในหน่วยความจำ
แท้จริงโดยวิธีการที่อยู่เหล่านี้
ดังนั้นในคอมพิวเตอร์ถ้าคุณ การเขียนโค้ดในการจัดเก็บสิ่งที่
เหมือนคำพูดสิ่งที่คุณกำลัง ทำจริงๆคือการพิมพ์
สำนวนที่ว่าจำที่อยู่ใน หน่วยความจำคอมพิวเตอร์ของคำเหล่านี้เป็น
เพื่อให้ฉันทำมาก ตัวอย่างง่ายๆ
>> ฉันจะไปข้างหน้าและ เปิดโปรแกรมข้อความที่เรียบง่าย
และฉันจะสร้าง ไฟล์ที่เรียกว่า hello.c
ข้อมูลส่วนใหญ่ที่เรา จะไม่ไปลงในรายละเอียดมาก
แต่ฉันจะเขียน โปรแกรมในภาษาเดียวกันนั้น
C. นี้อยู่ไกลข่มขู่มากขึ้น ฉันจะยืนยันกว่าเกา
แต่มันก็คล้ายกันมากในจิตวิญญาณ
ในความเป็นจริงเหล่านี้หยิก ชนิด braces-- คุณสามารถของ
คิดว่าสิ่งที่ผมก็ไม่ได้เช่นนี้
>> ลองทำเช่นนี้จริง
เมื่อธงสีเขียวคลิก ทำต่อไปนี้
ฉันต้องการที่จะพิมพ์ออกมา "สวัสดีครับ."
ดังนั้นนี่คือตอนนี้ pseudocode
ผมชนิดทำให้ฟางเส้น
ใน C, ภาษานี้ผมกำลังพูดถึง เกี่ยวกับการพิมพ์บรรทัดนี้สวัสดี
จริงกลายเป็น "printf" กับ วงเล็บและลำไส้ใหญ่กึ่ง
>> แต่มันเป็นความคิดเดียวกันแน่นอน
และนี้ใช้ง่ายมาก "เมื่อธงสีเขียวคลิก" กลายเป็น
มากความลับมากขึ้น "เป็นโมฆะหลัก Int."
และนี้จริงๆมีการทำแผนที่ไม่มี ดังนั้นฉันแค่ไปที่จะไม่สนใจว่า
แต่วงเล็บปีกกาเหมือน ชิ้นส่วนปริศนาโค้งเช่นนี้
>> เพื่อให้คุณสามารถชนิดของการคาดเดา
แม้ว่าคุณจะไม่เคยตั้งโปรแกรมก่อน สิ่งที่ไม่โปรแกรมนี้อาจจะทำอย่างไร
อาจจะพิมพ์สวัสดี ที่มีเครื่องหมายอัศเจรีย์
>> ดังนั้นลองว่า
ฉันจะเก็บมันไว้
และนี่คืออีกมาก สภาพแวดล้อมของโรงเรียนเก่า
ฉันไม่สามารถคลิกฉันไม่สามารถลาก
ฉันต้องพิมพ์คำสั่ง
ดังนั้นผมจึงต้องการที่จะเรียกใช้โปรแกรมของฉันดังนั้น ฉันอาจจะทำเช่นนี้เหมือน hello.c
นั่นเป็นไฟล์ฉันวิ่ง
แต่รอฉันหายไปขั้นตอน
สิ่งที่พวกเราพูดเป็นสิ่งที่จำเป็น ขั้นตอนในการใช้ภาษาเช่น C หรือไม่?
ผมเคยเขียนเพียงแหล่งที่มา รหัส แต่สิ่งที่ฉันต้อง?
ใช่ฉันต้องคอมไพเลอร์
ดังนั้นบน Mac ของฉันที่นี่ฉันมี โปรแกรมที่เรียกว่า GCC, GNU C คอมไพเลอร์
ซึ่งจะช่วยให้ฉันไปทำเปิด this-- รหัสที่มาของฉันเป็นเราจะเรียกมันว่า
รหัสเครื่อง
>> และฉันจะเห็นว่า อีกครั้งดังต่อไปนี้
เป็นศูนย์และคนฉันเพียงแค่ สร้างขึ้นจากรหัสที่มาของฉัน
ทั้งหมดของศูนย์และคน
และถ้าผมต้องการที่จะทำงาน ฉัน program-- มันเกิดขึ้น
จะเรียกว่า a.out สำหรับ reasons-- ประวัติศาสตร์ "สวัสดีครับ."
ฉันสามารถเรียกใช้อีกครั้ง
สวัสดีสวัสดีสวัสดี.
และมันดูเหมือนว่าจะทำงาน
>> แต่นั่นหมายความว่าในบางส่วนของฉัน หน่วยความจำของคอมพิวเตอร์เป็นคำ
H-E-L-L-o, เครื่องหมายอัศเจรีย์
และปรากฎเพียงเช่นกัน สิ่งที่คอมพิวเตอร์จะมักจะ
ทำเพื่อที่จะรู้ว่า สิ่งที่เริ่มต้นและ end-- มัน
จะใส่สัญลักษณ์พิเศษที่นี่
และการประชุมคือการวาง จำนวนศูนย์ในตอนท้ายของคำ
เพื่อให้คุณทราบว่ามัน จริงจบลงเพื่อให้คุณ
ไม่ให้พิมพ์ออกมากขึ้น ตัวละครมากกว่าที่คุณตั้งใจจริง
>> แต่ Takeaway ที่นี่แม้ แม้ว่าจะเป็นธรรมลับ
คือว่ามันในท้ายที่สุด ค่อนข้างง่าย
คุณจะได้รับการจัดเรียงของเทปเปล่า พื้นที่ที่คุณสามารถเขียนตัวอักษร
คุณก็ต้องมี สัญลักษณ์พิเศษเช่นพล
จำนวนศูนย์ที่จะใส่ในตอนท้ายของ คำพูดของคุณเพื่อให้คอมพิวเตอร์รู้
โอ้ฉันควรจะหยุดพิมพ์หลังจากที่ ฉันเห็นเครื่องหมายอัศเจรีย์
เพราะสิ่งต่อไปที่มี เป็นค่า ASCII ของศูนย์
หรืออักขระ null เป็น ใครบางคนจะเรียกมันว่า
แต่มีชนิดของปัญหา ที่นี่และขอให้กลับไป
ไปยังหมายเลขสักครู่
สมมติว่าผมทำในความเป็นจริง มีอาร์เรย์ของตัวเลขที่
และคิดว่า โปรแกรมที่ผมเขียนคือ
เหมือนหนังสือชั้นประถมศึกษาสำหรับครู และครูผู้สอนในชั้นเรียน
และโปรแกรมนี้จะช่วยให้เขาหรือเธอ พิมพ์ในคะแนนของนักเรียน
ในแบบทดสอบ
และสมมติว่านักเรียนที่ได้รับ 100 แบบทดสอบแรกของพวกเขาอาจจะ
เหมือน 80 บนหน้าหนึ่งแล้ว 75 แล้ว 90 ในการตอบคำถามที่สี่
>> เพื่อที่จุดนี้ในเรื่อง อาร์เรย์มีขนาดสี่
มีหน่วยความจำมากขึ้นอย่างที่อยู่ใน คอมพิวเตอร์ แต่อาร์เรย์เพื่อที่จะพูด
มีขนาดสี่
สมมติว่าขณะที่ครูต้องการ การกำหนดแบบทดสอบที่ห้าในชั้นเรียน
ดีหนึ่งในสิ่งที่เขา หรือเธอจะต้องทำ
ขณะนี้การจัดเก็บค่าเพิ่มเติมที่นี่
แต่ถ้าอาร์เรย์ครูมี สร้างขึ้นในโปรแกรมนี้เป็นโปรแกรมที่มีขนาดสำหรับ
หนึ่งในปัญหาที่เกิดขึ้นกับอาร์เรย์คือว่า คุณก็ไม่สามารถเก็บเพิ่มหน่วยความจำ
เพราะสิ่งที่ถ้าเป็นส่วนหนึ่งของอีก โปรแกรมมีคำว่า "เดี๋ยวก่อน" ที่นั่น?
>> ในคำอื่น ๆ หน่วยความจำของฉันสามารถ ใช้สำหรับสิ่งในโปรแกรม
และถ้าล่วงหน้าฉันพิมพ์ในเดี๋ยวก่อน ฉันต้องการที่จะป้อนข้อมูลสี่คะแนนแบบทดสอบ
พวกเขาอาจจะไปที่นี่และที่นี่
และถ้าคุณก็เปลี่ยนความคิดของคุณ ต่อมาและพูดว่าฉันต้องการตอบคำถามที่ห้า
คะแนนคุณไม่สามารถเพียงแค่ ใส่มันทุกที่ที่คุณต้องการ
เพราะสิ่งที่ว่านี้ หน่วยความจำจะถูกใช้
สำหรับสิ่งที่ else-- โปรแกรมอื่น ๆ หรือคุณสมบัติอื่น ๆ ของโปรแกรม
ว่าคุณกำลังทำงานอยู่หรือไม่
ดังนั้นคุณต้องคิดล่วงหน้า วิธีที่คุณต้องการในการจัดเก็บข้อมูลของคุณ
เพราะตอนนี้คุณได้ทาสี ตัวเองเป็นมุมดิจิตอล
>> ดังนั้นครูอาจแทน บอกว่าเมื่อเขียนโปรแกรม
ในการจัดเก็บของเขาหรือเธอ เกรดคุณรู้อะไรไหม
ฉันกำลังจะไปขอ เมื่อเขียนโปรแกรมของฉัน
ที่ฉันต้องการศูนย์หนึ่งสองสาม สี่ห้าหกแปดเกรดรวม
ดังนั้นหนึ่งสองสามสี่ ห้าหกเจ็ดแปด
ครูสามารถเพียงจัดสรร หน่วยความจำเมื่อเขียนโปรแกรมของเขาหรือเธอ
และบอกว่าคุณรู้อะไรไหม
ฉันไม่เคยจะกำหนดเพิ่มเติม กว่าแปดแบบทดสอบในภาคการศึกษา
ที่บ้าเพียง
ฉันไม่เคยจะจัดสรร
เพื่อให้วิธีนี้เขาหรือเธอมี ความยืดหยุ่นในการเก็บคะแนนของนักเรียน,
เช่น 75, 90, และอาจจะเป็นหนึ่งที่พิเศษ นักเรียนได้รับเครดิตพิเศษ 105
>> แต่ถ้าครูไม่เคย ใช้ทั้งสามช่องว่าง
มีการใช้งานง่าย Takeaway ที่นี่
เขาหรือเธอเป็นเพียงแค่การสูญเสียพื้นที่
ดังนั้นในคำอื่น ๆ ที่มีนี้ ถ่วงดุลอำนาจทั่วไปในการเขียนโปรแกรม
ที่คุณสามารถจัดสรร หน่วยความจำว่ามากที่สุดเท่าที่คุณต้องการ
คว่ำซึ่งก็คือค​​ุณสุด efficient-- คุณไม่ได้เป็นที่สิ้นเปลือง
ที่ all-- แต่ข้อเสียของการที่ เป็นสิ่งที่ถ้าคุณเปลี่ยนความคิดของคุณเมื่อ
การใช้โปรแกรมที่คุณต้องการในการจัดเก็บ ข้อมูลได้มากขึ้นกว่าที่คุณตั้งใจเดิม
>> ดังนั้นบางทีการแก้ปัญหาคือแล้ว เขียนโปรแกรมของคุณในลักษณะ
ที่พวกเขาใช้หน่วยความจำเพิ่มเติม กว่าที่พวกเขาต้องการจริง
วิธีนี้คุณจะไม่ การทำงานเป็นปัญหาว่า
แต่คุณกำลังถูกสิ้นเปลือง
และหน่วยความจำมากขึ้นโปรแกรมของคุณใช้ ในขณะที่เราพูดคุยกันเมื่อวานนี้ที่น้อยกว่า
หน่วยความจำที่มีอยู่ สำหรับโปรแกรมอื่น ๆ
ไม่ช้าก็เร็วคอมพิวเตอร์ของคุณอาจชะลอตัว ลงเนื่องจากหน่วยความจำเสมือน
ดังนั้นทางออกที่ดีอาจจะมีอะไร?
>> ภายใต้การจัดสรรดูเหมือนว่าไม่ดี
กว่าจัดสรรดูเหมือนว่าไม่ดี
ดังนั้นสิ่งที่อาจจะเป็นทางออกที่ดีกว่า?
จัดสรร
เป็นแบบไดนามิกมากขึ้น
อย่าบังคับตัวเองให้เลือก เบื้องต้นที่จุดเริ่มต้นสิ่งที่คุณต้องการ
และแน่นอนไม่เกินจัดสรร เกรงว่าท่านจะสิ้นเปลือง
>> และเพื่อให้บรรลุเป้าหมายที่เรา ต้องโยนโครงสร้างข้อมูลนี้
เพื่อที่จะพูดออกไป
และเพื่อให้สิ่งที่เป็นโปรแกรมเมอร์ โดยทั่วไปจะใช้
สิ่งที่เรียกว่าไม่ได้เป็น อาร์เรย์ แต่รายการที่เชื่อมโยง
ในคำอื่น ๆ เขาหรือเธอจะ เริ่มคิดของหน่วยความจำของพวกเขา
เป็นชนิดที่เป็นของรูปร่างที่พวกเขา สามารถวาดในลักษณะดังต่อไปนี้
ถ้าผมต้องการที่จะเก็บหมายเลขหนึ่งใน program-- จึงเป็นเดือนกันยายน
ฉันได้รับนักเรียนของฉันแบบทดสอบ; ฉันต้องการ ในการจัดเก็บแบบทดสอบครั้งแรกของนักเรียน
และพวกเขาได้ 100 ผม it-- กำลังจะถามคอมพิวเตอร์ของฉัน
โดยวิธีการของโปรแกรมที่ฉันได้ เขียนสำหรับหนึ่งก้อนของหน่วยความจำ
และฉันจะเก็บ จำนวน 100 ในนั้นและที่มัน
>> จากนั้นไม่กี่สัปดาห์ต่อมา เมื่อฉันได้รับการตอบคำถามที่สองของฉัน
และก็ถึงเวลาที่จะพิมพ์ ในการที่ 90% ผมจะ
จะถามคอมพิวเตอร์ Hey, คอมพิวเตอร์, ฉันจะมีหน่วยความจำอันอื่นได้หรือไม่
มันเป็นไปได้ที่จะให้ฉันนี้ อันว่างเปล่าของหน่วยความจำ
ฉันจะใส่หมายเลข 90 แต่ในโปรแกรมของฉันอย่างใดหรือ other--
และเราจะไม่ต้องกังวลเกี่ยวกับ ไวยากรณ์สำหรับ this-- ฉันต้องการ
อย่างใดโยงสิ่งเหล่านี้ร่วมกัน
และฉันจะโยงเข้าด้วยกันด้วย สิ่งที่ดูเหมือนว่าลูกศรที่นี่
>> แบบทดสอบที่สามที่เกิดขึ้น ฉันจะบอกว่าเดี๋ยวก่อนคอมพิวเตอร์
ให้ฉันหน่วยความจำอันอื่น
และฉันจะใส่ลง สิ่งที่มันเป็นเช่น 75,
และฉันต้องห่วงโซ่นี้ ร่วมกันอย่างใดในขณะนี้
แบบทดสอบที่สี่มาพร้อมและอาจ ที่ช่วงท้ายของภาคการศึกษา
และโดยจุดที่โปรแกรมของฉัน อาจจะมีการใช้หน่วยความจำ
ทั่วทุกสถานที่ทั่วร่างกาย
และอื่น ๆ เพียงเพื่อลูกผม จะวาดออกมานี้
quiz-- ฉันลืมว่ามันคืออะไร; ผม คิดว่าอาจจะ 80 หรือ something--
วิธีมากกว่าที่นี่
>> แต่นั่นก็ไม่เป็นไรเพราะ pictorially ฉันจะวาดเส้นนี้
ในคำอื่น ๆ ในความเป็นจริง ในฮาร์ดแวร์ของคอมพิวเตอร์ของคุณ
คะแนนครั้งแรกอาจจะ จบลงที่นี่เพราะมันเป็น
ที่เหมาะสมในการเริ่มต้นของภาคการศึกษา
หนึ่งต่อไปอาจจะจบลงที่นี่ เพราะบิตของเวลาได้ผ่านไป
และโปรแกรมที่ช่วยให้ทำงาน
คะแนนต่อไปซึ่งเป็น 75 อาจจะมากกว่าที่นี่
และคะแนนที่ผ่านมาอาจจะมี 80 ซึ่งเป็นมากกว่าที่นี่
>> ดังนั้นในความเป็นจริงทางร่างกายนี้อาจจะมี สิ่งที่หน่วยความจำของคอมพิวเตอร์ของคุณมีลักษณะเหมือน
แต่นี้ไม่ได้มีประโยชน์ทางจิต กระบวนทัศน์สำหรับโปรแกรมคอมพิวเตอร์
ทำไมคุณควรดูแลที่ ห่าข้อมูลของคุณกำลังจะสิ้นสุดลงได้หรือไม่
คุณต้องการเพียงแค่การจัดเก็บข้อมูล
>> นี้เป็นชนิดเช่นการสนทนาของเรา ก่อนหน้านี้ในการวาดภาพก้อน
ทำไมคุณดูแลสิ่งที่ มุมที่เป็นก้อน
และวิธีการที่คุณต้องเปิดการวาดมันได้หรือไม่
คุณต้องการเพียงแค่ก้อน
ในทำนองเดียวกันที่นี่คุณ เพียงแค่ต้องการหนั​​งสือชั้น
คุณเพียงต้องการที่จะคิดว่า นี้เป็นรายการของตัวเลข
ใครสนใจว่าเป็น ดำเนินการในฮาร์ดแวร์?
>> ดังนั้นสิ่งที่เป็นนามธรรมในขณะนี้ คือภาพที่นี่
นี่คือรายการที่เชื่อมโยงเป็น โปรแกรมเมอร์จะเรียกว่า
ตราบเท่าที่คุณมี รายการที่เห็นได้ชัดของตัวเลข
แต่มันเชื่อมโยง pictorially โดยวิธีการของลูกศรเหล่านี้
และลูกศรทั้งหมดเหล่านี้ are-- ใต้ เครื่องดูดควัน, ถ้าคุณอยากรู้อยากเห็น
จำได้ว่าฮาร์ดแวร์ทางกายภาพของเรามี ที่อยู่ศูนย์หนึ่งสองสามสี่
ลูกศรทั้งหมดเหล่านี้เป็นเหมือนแผนที่ หรือเส้นทางที่ 90 ถ้า is-- ในขณะนี้
ผมได้รับการนับ
>> ศูนย์หนึ่งสองสาม สี่ห้าหกเจ็ด
ดูเหมือนว่า 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--
ดังนั้นชื่อของเพียร์สัน, หมายเลขโทรศัพท์ หมายเลขประกันสังคมแพทย์
ประวัติศาสตร์
กล่องนี้อาจจะมีมาก ใหญ่มากซึ่งในกรณีนี้
ตัวชี้เล็ก ๆ ที่อยู่ของ ลิเมนต์ต่อไปก็ไม่ได้เป็นเรื่องใหญ่
มันเป็นเช่นขอบ ค่าใช้จ่ายก็ไม่เป็นไร
แต่ในกรณีนี้ใช่มันเป็นสองเท่า
คำถามที่ดี.
>> พูดคุยเกี่ยวกับเวลา เล็ก ๆ น้อย ๆ เป็นรูปธรรม
เป็นเวลาทำงานอะไร การค้นหารายการนี​​้?
สมมติว่าผมต้องการที่จะค้นหา ผ่านเกรดทั้งหมดของนักเรียน
และมีเกรด n ในโครงสร้างข้อมูลนี้
นี่เกินไปเราสามารถยืม คำศัพท์ก่อนหน้านี้
นี่คือโครงสร้างข้อมูลเชิงเส้น
>> O ใหญ่ของ n เป็นสิ่งที่จำเป็นที่จะได้รับ การสิ้นสุดของโครงสร้างข้อมูลนี้
whereas-- และเรายังไม่ได้เห็น นี้ before-- อาร์เรย์ที่จะช่วยให้คุณ
สิ่งที่เรียกว่าเวลาคงซึ่งหมายความว่า ขั้นตอนที่หนึ่งหรือสองขั้นตอนหรือ 10 steps--
ไม่สำคัญ
มันเป็นจำนวนคงที่
มันมีอะไรจะทำอย่างไรกับ ขนาดของอาร์เรย์
และเหตุผลในการนั้น อีกครั้งคือการเข้าถึงแบบสุ่ม
คอมพิวเตอร์สามารถเพียงทันที ข้ามไปยังสถานที่อื่น
เพราะพวกเขากำลังเหมือนกันทั้งหมด ระยะทางจากทุกสิ่งทุกอย่าง
มีความคิดที่ไม่เกี่ยวข้องคือ
ก็ดี
ดังนั้นถ้าฉันสามารถให้ฉันพยายามที่จะ วาดภาพสองภาพสุดท้าย
หนึ่งที่พบบ่อยมากที่รู้จักกันเป็นตารางแฮช
ดังนั้นเพื่อกระตุ้นการสนทนานี้ ให้ฉันคิดเกี่ยวกับวิธีการทำเช่นนี้
>> ดังนั้นวิธีการเกี่ยวกับเรื่องนี้?
สมมติว่าปัญหาที่เกิดขึ้น เราต้องการที่จะแก้ปัญหาในขณะนี้
คือการใช้ใน dictionary-- เพื่อให้ทั้งกลุ่มของคำในภาษาอังกฤษ
หรืออะไรก็ตาม
และมีเป้าหมายที่จะสามารถที่จะตอบ คำถามของรูปแบบนี้คือคำ?
ดังนั้นคุณจึงต้องการที่จะดำเนินการ ตรวจสอบการสะกดเพียง
เหมือนพจนานุกรมทางกายภาพ ที่คุณสามารถดูสิ่งขึ้นใน
สมมติว่าผมจะทำเช่นนี้กับอาร์เรย์
ฉันจะทำเช่นนี้
>> และคิดว่าคำพูดที่มีแอปเปิ้ล และกล้วยแคนตาลูป
และผมก็ไม่สามารถคิดของผลไม้ ที่เริ่มต้นด้วย D, ดังนั้นเราเพียง
จะมีสามผลไม้
ดังนั้นนี่คืออาร์เรย์และเรา การจัดเก็บทั้งหมดของคำเหล่านี้
ในพจนานุกรมนี้เป็นอาร์เรย์
คำถามก็คือวิธีการอื่น คุณสามารถเก็บข้อมูลนี้?
>> ดีฉันชนิดของการโกงที่นี่เพราะ แต่ละตัวอักษรเหล่านี้ในคำว่า
เป็นจริงไบต์ของแต่ละบุคคล
ดังนั้นถ้าผมอยากจะเป็น จู้จี้จุกจิกจู้จี้จุกจิกฉันควรจะจริงๆ
จะแบ่งนี้ขึ้นไปมาก ชิ้นเล็กของหน่วยความจำ
และเราสามารถทำตรงนั้น
แต่เรากำลังจะวิ่งเข้ามา ปัญหาที่เกิดขึ้นเช่นเดียวกับก่อน
เกิดอะไรขึ้นถ้าเป็นเมอร์เรียมเว็บสเตอร์หรือฟอร์ด ไม่ทุก year-- พวกเขาเพิ่มคำ
ไป dictionary-- เราทำไม่ได้ จำเป็นต้องการที่จะวาดภาพตัวเอง
ในมุมที่มีมากมายอยู่แล้ว?
>> ดังนั้นแทนที่จะอาจจะเป็นวิธีการที่ชาญฉลาด คือการใส่แอปเปิ้ลในโหนดของตัวเองหรือกล่อง
ในขณะที่เราจะพูดว่ากล้วยและ แล้วที่นี่เรามีแคนตาลูป
และสตริงเราสิ่งเหล่านี้ร่วมกัน
ดังนั้นนี่คืออาร์เรย์และ นี้เป็นรายการที่เชื่อมโยง
ถ้าคุณไม่สามารถค่อนข้างเห็นมันเป็นเพียงแค่ บอกว่า "อาเรย์" และกล่าวว่า "รายการ".
>> ดังนั้นเราจึงมีเดียวกัน ปัญหาที่แน่นอนเป็นมาก่อน
โดยขณะนี้เรามี แคล่วคล่องในรายการที่เชื่อมโยงของเรา
แต่เรามีพจนานุกรมค่อนข้างช้า
สมมติว่าผมต้องการที่จะมองขึ้นคำ
มันอาจจะพาฉัน O ใหญ่ของ n ขั้นตอนเพราะคำว่าอาจจะ
เป็นทุกทางในตอนท้ายของ รายการเช่นแคนตาลูป
และปรากฎว่า ในการเขียนโปรแกรม, การจัดเรียง
ของจอกศักดิ์สิทธิ์ของข้อมูล โครงสร้างเป็นสิ่งที่
ที่ช่วยให้คุณอย่างต่อเนื่อง เวลาเช่นอาร์เรย์
แต่ที่ยังคงช่วยให้คุณมีชีวิตชีวา
>> ดังนั้นเราจึงสามารถมีที่ดีที่สุดของโลกทั้งสอง?
และแน่นอนมีบางสิ่งบางอย่าง เรียกว่าตารางแฮช
ที่ช่วยให้คุณทำตรง ที่แม้จะประมาณ
ตารางแฮชเป็นนักเล่น โครงสร้างข้อมูลที่เรา
สามารถคิดเป็น รวมกันของ array--
และฉันจะวาดมัน เช่น this-- และรายการเชื่อมโยง
ว่าฉันจะวาดเช่นนี้มากกว่าที่นี่
>> และวิธีการสิ่งนี้ ผลงานจะเป็นดังนี้
หากนี่ now-- กัญชา table-- เป็นโครงสร้างข้อมูลที่สามของฉัน
และฉันต้องการที่จะเก็บ คำพูดในเรื่องนี้ฉันทำไม่ได้
ต้องการเพียงแค่การจัดเก็บทั้งหมดของ คำพูดกลับไปกลับไปกลับไปกลับ
ฉันต้องการที่จะใช้ประโยชน์จากบางส่วน ชิ้นส่วนของข้อมูล
เกี่ยวกับคำพูดที่จะช่วยให้ ฉันได้รับมันที่มันได้เร็วขึ้น
>> ให้ดังนั้นคำแอปเปิ้ล และกล้วยและแคนตาลูป
ผมจงใจเลือกคำพูดเหล่านั้น
ทำไม?
สิ่งที่จัดเรียงของพื้นฐาน ที่แตกต่างกันเกี่ยวกับสาม?
สิ่งที่เห็นได้ชัด?
พวกเขาเริ่มต้นด้วยตัวอักษรที่แตกต่างกัน
>> เพื่อให้คุณรู้อะไรไหม
แทนที่จะใส่ทุกคำของฉันใน ถังเดียวกันเพื่อที่จะพูด
เช่นเดียวกับในรายการใหญ่หนึ่งทำไมทำไม่ได้ อย่างน้อยผมลองเพิ่มประสิทธิภาพ
และทำให้รายการของฉัน 1/26 เป็นเวลานาน
เพิ่มประสิทธิภาพที่น่าสนใจ อาจจะมีเหตุผลที่ทำไม่ได้
I-- เมื่อใส่คำ ในโครงสร้างข้อมูลนี้
ในหน่วยความจำของคอมพิวเตอร์ทำไม ไม่ฉันใส่ทั้งหมด 'a' คำพูดที่นี่
ทั้งหมดที่ 'B' คำพูดที่นี่ และทั้งหมดที่ 'C' คำพูดที่นี่?
ดังนั้นนี้จบลงด้วยการวางแอปเปิ้ล ที่นี่ที่นี่กล้วยแคนตาลูปที่นี่
เป็นต้น
>> และถ้าผมมีเพิ่มเติม คำ like-- สิ่งที่อื่นได้หรือไม่
แอปเปิ้ล, กล้วย, ลูกแพร์
ทุกคนคิดว่าผลไม้ ที่เริ่มต้นด้วย A, B, C หรือ?
ที่สมบูรณ์แบบ Blueberry--
ที่กำลังจะจบลงที่นี่
และเพื่อให้เราดูเหมือนจะมี เล็กน้อยวิธีการแก้ปัญหาที่ดีกว่า
เพราะตอนนี้ถ้าผมต้องการ เพื่อค้นหาแอปเปิ้ลผม
first-- ฉันทำไม่ได้เป็นเพียงการดำน้ำ ในโครงสร้างข้อมูลของฉัน
ฉันไม่ได้ดำน้ำในหน่วยความจำของคอมพิวเตอร์ของฉัน
ครั้งแรกที่ฉันมองไปที่ตัวอักษรตัวแรก
>> และนี่คือสิ่งคอมพิวเตอร์ นักวิทยาศาสตร์จะบอกว่า
คุณกัญชาในโครงสร้างข้อมูลของคุณ
คุณจะใช้การป้อนข้อมูลของคุณซึ่งใน กรณีนี้เป็นคำเช่นแอปเปิ้ล
คุณวิเคราะห์มันมองไปที่ ตัวอักษรตัวแรกในกรณีนี้
จึง hashing มัน
Hashing เป็นเหตุคำทั่วไป คุณนำสิ่งที่เป็น input
และคุณผลิตออกบางส่วน
และการส่งออกในการที่ กรณีที่เป็นที่ตั้ง
คุณต้องการค้นหาเป็นครั้งแรก ที่ตั้งสถานที่สองสาม
ดังนั้นใส่เป็นแอปเปิ้ล ส่งออกเป็นครั้งแรก
การป้อนข้อมูลที่เป็นกล้วยที่ การส่งออกควรจะเป็นครั้งที่สอง
การป้อนข้อมูลที่เป็นแคนตาลูป การส่งออกที่ควรจะเป็นที่สาม
การป้อนข้อมูลที่เป็นบลูเบอร์รี่ที่ การส่งออกอีกครั้งควรจะเป็นครั้งที่สอง
และนั่นคือสิ่งที่จะช่วยให้คุณใช้เวลา ทางลัดผ่านหน่วยความจำของคุณ
เพื่อให้ได้คำ หรือข้อมูลมีประสิทธิภาพมากขึ้น
>> ตอนนี้ลดลงเวลาของเราที่อาจเกิดขึ้น โดยเท่าหนึ่งออกจาก 26
เพราะถ้าคุณคิดว่าคุณ มีเป็นจำนวนมาก "A" คำว่า "Z"
คำว่า "Q" คำพูดที่ ไม่ได้จริงๆ realistic--
คุณกำลังจะมีเอียงข้าม ตัวอักษรบาง alphabet--
แต่นี้จะเป็นที่เพิ่มขึ้น วิธีการที่จะช่วยให้
คุณจะได้รับในคำพูดมากขึ้นอย่างรวดเร็ว
และในความเป็นจริงที่มีความซับซ้อน โปรแกรมที่ Googles ของโลก
Facebooks ของ world-- พวกเขาจะใช้ตารางแฮช
สำหรับจำนวนมากของวัตถุประสงค์ที่แตกต่างกัน
แต่พวกเขาจะไม่เป็นเช่นนั้นไร้เดียงสาเป็น เพียงแค่มองไปที่ตัวอักษรตัวแรก
ในแอปเปิ้ลหรือกล้วยหรือ ลูกแพร์หรือแคนตาลูป
เพราะในขณะที่คุณสามารถเห็นเหล่านี้ รายชื่ออาจจะยังคงได้รับความยาว
>> และดังนั้นนี้ยังอาจจะมีการจัดเรียง ของ linear-- เพื่อให้การจัดเรียงของช้า
เช่นเดียวกับโอใหญ่ของ n ที่เรากล่าวก่อนหน้านี้
ดังนั้นสิ่งที่ตารางแฮชดีจริงจะ do-- มันจะมีอาร์เรย์ขนาดใหญ่มาก
และมันจะใช้มากขึ้น ฟังก์ชั่นแปลงแป้นพิมพ์ที่มีความซับซ้อน
เพื่อที่จะไม่เพียง แต่มองไปที่ "A".
บางทีมันอาจจะดูที่ระดับ "A-P-P-L-E" และ อย่างใดแปลงที่ห้าตัวอักษร
ในสถานที่ที่ แอปเปิ้ลควรจะเก็บไว้
เราเพียงแค่ไร้เดียงสาโดยใช้ตัวอักษร 'a' เพียงอย่างเดียวเพราะมันเป็นเรื่องที่ดีและง่าย
>> แต่ตารางแฮชใน ท้ายที่สุดที่คุณสามารถคิด
ของการรวมกันของ อาร์เรย์แต่ละที่
มีรายการที่เชื่อมโยงที่นึกคิด ควรจะเป็นสั้นที่สุด
และนี่คือไม่ได้เป็นทางออกที่ชัดเจน
ในความเป็นจริงมากของการปรับแต่ง ที่เกิดขึ้นภายใต้ประทุนเมื่อ
การดำเนินการเหล่านี้ชนิดของ โครงสร้างข้อมูลที่มีความซับซ้อน
คือสิ่งที่เป็นที่เหมาะสม ความยาวของอาร์เรย์?
ฟังก์ชั่นแฮชที่เหมาะสมคืออะไร?
คุณจะทำอย่างไรในการจัดเก็บสิ่งที่อยู่ในหน่วยความจำ?
>> แต่ตระหนักถึงวิธีการได้อย่างรวดเร็ว การเรียงลำดับของการสนทนานี้
เพิ่มขึ้นอย่างใดอย่างหนึ่งเพื่อให้ห่างไกลว่ามันเป็นชนิด ของเหนือหัวของคนที่จุดนี้ซึ่ง
เป็นเรื่องปกติ
แต่เราเริ่มต้นการเรียกคืนด้วยอย่างแท้จริง บางสิ่งบางอย่างในระดับต่ำและอิเล็กทรอนิกส์
และอื่น ๆ นี้อีกครั้งเป็นแบบนี้ รูปแบบของนามธรรม
ที่เมื่อคุณเริ่มต้นที่จะใช้สำหรับ รับตกลงฉันมี it-- มี
หน่วยความจำกายภาพตกลงได้มันทุก ตำแหน่งทางกายภาพมีอยู่
ตกลงผมได้รับมันฉันสามารถเป็นตัวแทนของ ที่อยู่เหล่านั้นเป็น arrows--
คุณได้อย่างรวดเร็วสามารถเริ่มต้นที่จะมี การสนทนาที่มีความซับซ้อนมากขึ้นว่า
ในที่สุดดูเหมือนจะช่วยให้เรา ในการแก้ปัญหาเช่นการค้นหา
และการเรียงลำดับได้อย่างมีประสิทธิภาพมากขึ้น
และส่วนที่เหลือมั่นใจ too-- เพราะผมคิดว่านี้
เป็นที่ลึกที่สุดของเราได้ไปเป็นบางส่วน เหล่านี้หัวข้อ CS proper-- เราได้
ทำในวันและครึ่งหนึ่งของที่นี้ ชี้สิ่งที่คุณมักจะอาจจะทำมากกว่า
หลักสูตรของแปดสัปดาห์ในภาคการศึกษาที่
>> คำถามใด ๆ เกี่ยวกับเหล่านี้หรือไม่
ไม่ได้หรือไม่
ก็ดี
ดีทำไมเราไม่หยุดที่นั่น เริ่มต้นกลางวันไม่กี่นาทีในช่วงต้น
กลับมาในเวลาเพียงประมาณหนึ่งชั่วโมง?
และฉันจะอู้ bit กับคำถาม
แล้วฉันจะต้องไป ใช้สายคู่ถ้าที่ตกลง
ฉันจะเปิดเพลงบางอย่างในขณะเดียวกัน แต่กลางวันควรจะรอบมุม