DAVID Malan: Tất cả các quyền. Chúng tôi đã trở lại. Vì vậy, trong phân khúc này trên chương trình gì Tôi nghĩ rằng chúng tôi muốn làm là một kết hợp của sự vật. Một, làm một chút của một cái gì đó tay-on, mặc dù sử dụng một vui tươi hơn environment-- lập trình một trong đó là minh chứng của chính xác các loại ý tưởng chúng tôi đã được nói đến, nhưng một ít chính thức hơn. Hai, xem xét một số những cách kỹ thuật hơn mà một lập trình sẽ thực sự giải quyết vấn đề như vấn đề tìm kiếm mà chúng ta nhìn trước và cũng là một cách cơ bản hơn vấn đề thú vị của phân loại. 

Chúng tôi chỉ là giả định từ nhận đi rằng cuốn sách điện thoại đã được sắp xếp, nhưng mà mình thực sự là loại một vấn đề khó khăn với nhiều cách khác nhau để giải quyết nó. Vì vậy, chúng tôi sẽ sử dụng như là một lớp học của các vấn đề đại diện của những điều mà có thể được giải quyết nói chung. Và sau đó chúng tôi sẽ nói chuyện về một số chi tiết những gì được gọi là dữ liệu structures-- cách fancier như danh sách liên kết và bảng băm và cây một lập trình viên sẽ thực sự sử dụng và thường sử dụng trên một tấm bảng vẽ một bức tranh về những gì anh ta hoặc cô hình dung thực hiện một số phần của phần mềm. 

Vì vậy, chúng ta hãy làm những thực hành phần đầu tiên. Vì vậy, chỉ có được bàn tay của bạn bẩn với một môi trường được gọi scratch.mit.edu. Đây là một công cụ mà chúng tôi sử dụng trong lớp học của chúng tôi. Mặc dù nó được thiết kế cho lứa tuổi từ 12 trở lên, chúng tôi sử dụng nó cho lên phần của điều đó khá một chút vì nó là một tốt đẹp, vui vẻ cách đồ họa của việc học một chút gì đó về lập trình. Vì vậy, đi tới URL đó, nơi bạn sẽ thấy một trang khá như thế này, và đi trước và bấm Tham gia Scratch ở góc trên bên phải và chọn một tên người dùng và một Mật khẩu và cuối cùng là có được cho mình một scratch.mit.edu account--. Tôi nghĩ rằng tôi muốn sử dụng như là một cơ hội đầu tiên để hiển thị này. Một câu hỏi nảy ra trong giờ nghỉ về những gì đang thực sự trông như thế nào. Và chúng tôi đã nói chuyện trong giờ nghỉ về C, trong particular-- đặc biệt là một mức thấp hơn trong một ngôn ngữ trở lên. Và tôi chỉ cần làm một cách nhanh chóng Google tìm kiếm để tìm mã C cho tìm kiếm nhị phân, các thuật toán mà chúng tôi sử dụng để tìm kiếm cuốn sách điện thoại trước đó. Điều này ví dụ cụ thể, tất nhiên, không tìm kiếm một cuốn sách điện thoại. Nó chỉ là tìm kiếm một bó toàn bộ số trong bộ nhớ của máy tính. Nhưng nếu bạn muốn chỉ có được một hình ảnh ý nghĩa của những gì một chương trình thực tế ngôn ngữ có vẻ như, có vẻ một chút gì đó như thế này. Vì vậy, nó là khoảng 20-cộng, Khoảng 30 dòng mã, nhưng cuộc trò chuyện chúng tôi đã có trên nghỉ khoảng cách này thực sự bị biến thành số không và những người thân và nếu bạn không thể chỉ trở lại mà xử lý và đi từ số không và những người thân sao để mã. 

Thật không may, quá trình là để biến đổi rằng đó là dễ dàng hơn nhiều hơn làm. Tôi đã đi trước và thực sự bật rằng chương trình, tìm kiếm nhị phân, thành số không và những người thân bằng cách của một chương trình được gọi là trình biên dịch mà tôi xảy ra để có ở đây ngay trên máy Mac của tôi. Và nếu bạn nhìn vào màn hình ở đây, đặc biệt tập trung trên sáu cột giữa chỉ, bạn sẽ thấy chỉ số không và những người thân. Và đó là những số không và những người soạn một cách chính xác rằng chương trình tìm kiếm. 

Và vì vậy mỗi đoạn năm bit, mỗi byte của số không và những người ở đây, đại diện một số chỉ dẫn thường bên trong của một máy tính. Và trên thực tế, nếu bạn đã nghe marketing khẩu hiệu "Intel bên trong" - đó là, Tất nhiên, chỉ có nghĩa là bạn có một Intel CPU hoặc bộ não bên trong máy tính. Và điều đó có nghĩa là một CPU rằng bạn có một tập lệnh, vậy để nói chuyện. 

Mỗi CPU trên thế giới, nhiều người trong chúng được thực hiện bởi Intel những ngày này, hiểu một hữu hạn số lượng hướng dẫn. Và những người hướng dẫn là mức quá thấp như thêm hai con số này với nhau, nhân hai số này với nhau, di chuyển này mảnh dữ liệu từ đây đến đây trong bộ nhớ, lưu này thông tin từ đây đến đây trong bộ nhớ, và vì vậy forth-- rất, rất Ở mức độ thấp, chi tiết gần như điện tử. Nhưng với những toán học hoạt động cùng với những gì chúng ta đã thảo luận trước đó, các đại diện của dữ liệu là số không và những người thân, có thể bạn xây dựng tất cả mọi thứ mà máy tính có thể làm ngày hôm nay, cho dù đó là văn bản, đồ họa, âm nhạc, hay nói cách khác. 

Vì vậy, điều này rất dễ dàng để có được bị mất trong cỏ dại một cách nhanh chóng. Và có rất nhiều thách thức cú pháp theo đó nếu bạn thực hiện đơn giản, ngu ngốc nhất của lỗi chính tả không ai trong số các chương trình sẽ làm việc gì. Và do đó, thay vì sử dụng một ngôn ngữ như C sáng nay, Tôi nghĩ rằng nó sẽ được vui hơn để thực sự làm một cái gì đó trực quan hơn, mà trong khi thiết kế cho trẻ em thực sự là một biểu hiện hoàn hảo của một chương trình thực tế language-- chỉ xảy ra sử dụng hình ảnh thay vì văn bản để đại diện cho những ý tưởng. 

Vì vậy, một khi bạn thực sự có một tài khoản trên scratch.mit.edu, nhấp vào nút Create ở phía trên bên trái của trang web. Và bạn sẽ thấy một môi trường như một trong những Tôi về để nhìn thấy trên màn hình của tôi đây. Và chúng tôi sẽ dành một chút chút thời gian chơi ở đây. Hãy xem, nếu chúng ta không thể giải quyết một số bài vấn đề với nhau trong các cách sau đây. 

Vì vậy, những gì bạn sẽ thấy bên trong này environment-- và thực sự chỉ cho tôi tạm dừng. Có ai không đây? Không phải ở đây? ĐƯỢC. Vì vậy, hãy để tôi chỉ ra một vài đặc điểm của môi trường này. 

Vì vậy, ở phía trên bên trái của màn hình, chúng tôi có giai đoạn Scratch, vì vậy để nói chuyện. Scratch không chỉ là tên của ngôn ngữ lập trình này; nó cũng là tên của con mèo bạn nhìn thấy bằng cách mặc định có màu cam. Ông là trên sân khấu, vì vậy giống như tôi đã mô tả rùa đầu xuất hiện trong một hình chữ nhật môi trường bảng trắng. thế giới của con mèo này chỉ hạn chế hoàn toàn cho rằng hình chữ nhật lên trên đó. 

Trong khi đó, ở bên phải Mặt bên đây, đó là chỉ là một khu vực kịch bản, một slate trống nếu bạn sẽ. Đây là nơi mà chúng ta sẽ viết chương trình của chúng tôi chỉ trong một khoảnh khắc. Và các khối xây dựng mà chúng tôi có trách nhiệm sử dụng để viết này program-- câu đố miếng, nếu bạn là will-- những người ở đây ở giữa, và họ đang được phân loại bởi chức năng. Vì vậy, ví dụ, tôi sẽ đi trước và chứng minh ít nhất một trong số này. Tôi sẽ đi trước và bấm các loại điều khiển lên hàng đầu. 

Vì vậy, đây là những loại lên hàng đầu. Tôi sẽ nhấp vào mục Control. Thay vào đó, tôi sẽ nhấp vào Sự kiện thể loại, một trong những động đầu tiên hàng đầu. Và nếu bạn muốn theo cùng thậm chí khi chúng ta làm điều này, bạn hoàn toàn hoan nghênh. Tôi sẽ để click và kéo này Người đầu tiên ", khi lá cờ màu xanh lá cây nhấp vào." Và sau đó tôi sẽ thả nó chỉ khoảng ở phía trên cùng của bảng đá phiến trống của tôi. 

Và những gì tốt đẹp về Scratch là điều này mảnh ghép, khi khóa liên động với câu đố khác miếng, sẽ làm đúng nghĩa đen những gì những mảnh ghép nói để làm. Vì vậy, ví dụ, Scratch là đúng tại ở giữa thế giới của mình. Tôi sẽ đi trước và chọn bây giờ, chúng ta hãy nói, các loại chuyển động, nếu bạn muốn làm việc same-- loại Motion. Và bây giờ nhận thấy tôi có một toàn bộ bó của mảnh ghép ở đây rằng, một lần nữa, loại làm những gì họ nói. Và tôi sẽ đi trước và kéo và thả các khối di chuyển ngay trên đây. 

Và nhận thấy rằng ngay sau khi bạn nhận được gần dưới cùng của "lá cờ màu xanh lá cây nhấp nút ", thông báo làm thế nào một dòng trắng xuất hiện, như thể đó là gần như từ tính, nó muốn đi đến đó. Chỉ cần cho đi, và nó sẽ chụp với nhau và hình dạng sẽ phù hợp. có lẽ Và bây giờ bạn có thể hầu như đoán nơi chúng tôi đang đi với điều này. 

Nếu bạn nhìn vào các giai đoạn Scratch trên đây và nhìn vào phần đầu của nó, bạn sẽ thấy một ánh sáng màu đỏ, một dừng ký và một lá cờ màu xanh lá cây. Và tôi sẽ đi trước và xem màn hình-- của tôi chỉ trong một khoảnh khắc, nếu bạn có thể. Tôi sẽ nhấp vào màu xanh lá cây cờ ngay bây giờ, và ông chuyển những gì dường như là 10 bước hoặc 10 pixel, 10 chấm, trên màn hình. 

Và như vậy không phải là thú vị, nhưng hãy để tôi đề xuất mà không hề dạy này, chỉ cần bằng cách sử dụng riêng let intuition-- của riêng bạn tôi đề nghị bạn tìm hiểu làm thế nào để làm Scratch đi bộ phải ra khỏi sân khấu. ông đã thực hiện theo cách cho phía bên phải của màn hình, tất cả các con đường bên phải. Hãy để tôi cung cấp cho bạn một thời điểm hoặc để vật lộn với điều đó. Bạn có thể muốn có một cái nhìn ở các thể loại khác của các khối. Tất cả các quyền. Như vậy chỉ cần tóm tắt lại, khi chúng ta có lá cờ màu xanh lá cây nhấp vào đây và di chuyển 10 bước là chỉ dẫn, mỗi lần tôi nhấp vào lá cờ màu xanh lá cây, những gì đang xảy ra? Vâng, đó là chạy chương trình của tôi. Vì vậy, tôi có thể làm điều này có lẽ 10 lần bằng tay, nhưng điều này cảm thấy một chút chút hackish, có thể nói, nhờ đó mà tôi không thực sự giải quyết vấn đề. Tôi chỉ cố gắng một lần nữa và Một lần nữa và một lần nữa cho đến khi tôi sắp xếp của vô tình đạt được các chỉ thị mà tôi đặt ra để đạt được trước đó. 

Nhưng chúng ta biết từ chúng tôi giả trước đó rằng có khái niệm này trong lập trình của vòng lặp, làm một cái gì đó một lần nữa và một lần nữa. Và vì vậy tôi thấy rằng một bó của bạn đạt cho mảnh gì đố? Lặp lại cho đến khi. Vì vậy, chúng ta có thể làm điều gì đó như lặp lại cho đến khi. Và những gì đã làm bạn lặp lại cho đến khi chính xác? 

ĐƯỢC. Và hãy để tôi đi với một trong đó là hơi đơn giản chỉ là một khoảnh khắc. Hãy để tôi đi trước và làm điều này. Chú ý rằng, như bạn có thể phát hiện dưới kiểm soát, có khối lặp lại này, mà không giống như nó là lớn. Không có nhiều phòng giữa hai vạch vàng. Nhưng như một số bạn có thể có nhận thấy, nếu bạn kéo và thả, thấy thế nào nó phát triển để điền vào hình dạng. 

Và thậm chí bạn có thể nhồi nhét hơn. Nó sẽ chỉ tiếp tục phát triển nếu bạn kéo và di chuột qua nó. Và tôi không biết điều gì tốt nhất ở đây, vì vậy hãy để tôi ít nhất lặp lại năm lần, Chẳng hạn, và sau đó quay trở lại sân khấu và nhấp vào lá cờ màu xanh lá cây. Và bây giờ nhận thấy nó không hoàn toàn ở đó. 

Bây giờ một số bạn đề xuất, như Victoria chỉ cần không, lặp lại 10 lần. Và điều đó thường làm có được anh ta tất cả các cách, nhưng sẽ không có được một mạnh mẽ hơn cách tùy tiện hơn để tìm ra bao nhiêu di chuyển để thực hiện? Điều gì có thể tốt hơn một khối hơn lặp lại 10 lần được? 

Yeah, vậy tại sao không làm một cái gì đó mãi mãi? Và bây giờ hãy để tôi di chuyển mảnh ghép này bên đó và thoát khỏi một này. Bây giờ thấy không có vấn đề nơi Scratch bắt đầu, ông đi đến cạnh. Và may mắn MIT, ai làm cho cào, chỉ làm cho chắc chắn rằng ông không bao giờ biến mất hoàn toàn. Bạn luôn có thể lấy cái đuôi của mình. 

Và chỉ bằng trực giác, tại sao lại tiếp tục di chuyển? Chuyện gì đang xảy ra ở đây? Ông dường như đã dừng lại, nhưng sau đó nếu tôi chọn lên và kéo ông tiếp tục muốn đi qua đó. Tại sao vậy? Quả thật, một máy tính là nghĩa đen sẽ làm những gì bạn nói với nó để làm. Vì vậy, nếu bạn nói với nó trước đó làm sau điều mãi mãi, di chuyển 10 bước, nó sẽ tiếp tục đi và đi cho đến khi tôi nhấn dấu hiệu dừng lại màu đỏ và ngăn chặn các chương trình hoàn toàn. 

Vì vậy, ngay cả khi bạn không làm điều này, làm thế nào có thể tôi làm Scratch di chuyển nhanh hơn trên màn hình? Bước khác nữa, phải không? Vì vậy, thay vì làm 10 tại một thời điểm, tại sao chúng ta không đi trước và thay đổi nó đối với: những gì bạn sẽ propose-- 50? Vì vậy, bây giờ tôi sẽ nhấp vào màu xanh lá cây cờ, và quả thực, ông đi rất nhanh. 

Và điều này, tất nhiên, chỉ là một biểu hiện của hình ảnh động. hình ảnh động là gì? Nó chỉ cho bạn thấy một con người bó toàn bộ các hình ảnh vẫn thực sự, thực sự, thực sự nhanh chóng. Và như vậy, nếu chúng ta chỉ cho anh di chuyển nhiều bước, chúng tôi chỉ có tác dụng được với thay đổi nơi ông là trên màn hình tất cả các nhanh hơn trên một đơn vị thời gian. 

Bây giờ thử thách tiếp theo mà tôi đề xuất là để có anh bật ra khỏi mép. Và không biết những gì đố mảnh exist-- vì nó tốt nếu bạn không nhận được để giai đoạn của challenge-- gì Bạn muốn làm bằng trực giác? Làm thế nào chúng ta sẽ có anh ta nhảy qua nhảy lại ra, giữa bên trái và phải không? 

Yeah. Vì vậy, chúng tôi cần một số loại các điều kiện, và chúng tôi dường như có điều kiện, do đó, để nói chuyện, thuộc thể loại điều khiển. Mà trong các khối Chúng ta có thể muốn? Vâng, có thể "nếu, sau đó." Vì vậy, nhận thấy rằng trong số các khối màu vàng chúng tôi có ở đây, có này "nếu" hay đây "nếu, khác" khối đó sẽ cho phép chúng tôi đưa ra quyết định để làm điều này hoặc để làm điều đó. và thậm chí bạn có thể làm tổ chúng để làm nhiều điều. Hoặc nếu bạn đã không đi đến chưa, đi trước để loại Sensing và- hãy xem nếu nó ở đây. 

Vì vậy, những gì khối có thể là hữu ích ở đây để phát hiện nếu anh ta ra khỏi sân khấu? Yeah, nhận thấy rằng một số các khối có thể được parametrized, vậy để nói chuyện. Chúng có thể được sắp xếp tùy chỉnh, không không giống như HTML hôm qua với các thuộc tính, nơi những thuộc tính loại tùy chỉnh hành vi của một thẻ. Tương tự như vậy ở đây, tôi có thể lấy cảm động này khối và thay đổi và đặt câu hỏi, bạn đang chạm vào chuột con trỏ như con trỏ hoặc là bạn chạm vào các cạnh? 

Vì vậy, hãy để tôi đi vào và làm điều này. Tôi sẽ thu nhỏ cho một thời điểm. Hãy để tôi lấy mảnh ghép này ở đây, câu đố này tác phẩm này, và tôi sẽ lẫn lộn chúng chỉ trong một khoảnh khắc. Tôi sẽ di chuyển này, thay đổi này để cạnh cảm động, và tôi sẽ chuyển động làm điều này. Vì vậy, đây là một số thành phần. Tôi nghĩ rằng tôi đã có tất cả mọi thứ tôi muốn. 

một người nào đó muốn đề nghị làm thế nào tôi có thể kết nối những lẽ đầu xuống dưới để giải quyết các vấn đề của việc có Scratch di chuyển phải sang trái sang phải để trái sang phải sang trái, mỗi Hiện chỉ đập vào tường? Tôi muốn làm gì? Những khối tôi nên kết nối đến "Cờ khi màu xanh lá cây nhấp đầu tiên"? 

OK, vì vậy chúng ta hãy bắt đầu với "mãi mãi." Những gì diễn ra bên trong tiếp theo? Một người nào khác. OK, di chuyển bước. Tất cả các quyền. Rồi sao? Vì vậy, sau đó nếu. Và nhận thấy, mặc dù có vẻ kẹp chặt chẽ với nhau, nó sẽ chỉ phát triển để điền vào. Nó sẽ chỉ nhảy ở nơi tôi muốn nó. 

Và để tôi đặt những gì giữa nếu và sau đó? Có lẽ "nếu chạm vào cạnh." Và thông báo, một lần nữa, nó quá lớn cho nó, nhưng nó sẽ phát triển để điền vào. Và sau đó lần lượt 15 độ? Bao nhiêu độ? Yeah, vì vậy 180 sẽ quay tôi tất cả các con đường xung quanh. Vì vậy, chúng ta hãy xem nếu tôi có quyền này. Hãy để tôi thu nhỏ. 

Hãy để tôi kéo cào lên. Vì vậy, ông là một chút méo bây giờ, nhưng đó là tốt. Làm thế nào tôi có thể thiết lập lại anh ấy dễ dàng? Tôi sẽ ăn gian một chút. Vì vậy, tôi thêm một khối, chỉ để được rõ ràng. Tôi muốn anh ấy chỉ 90 độ bên phải theo mặc định, vì vậy tôi chỉ cần đi để nói cho anh ta để làm điều đó theo chương trình. Và ở đây chúng tôi đi. Chúng ta dường như đã thực hiện nó. Đó là một chút kỳ lạ, bởi vì ông đang đi lộn ngược. Hãy gọi đó là một lỗi. Đó là một sai lầm. Một lỗi là một sai lầm trong một chương trình, một lỗi logic mà tôi, những con người, thực hiện. Tại sao ông đi lộn ngược? Đã MIT vít lên hoặc đã làm tôi? 

Vâng, tôi có nghĩa là, nó không phải của MIT lỗi. Họ đã cho tôi một mảnh ghép nói rằng một số biến số của độ. Và theo gợi ý của Victoria, Tôi quay 180 độ, đó là trực giác đúng. Nhưng quay 180 độ theo nghĩa đen có nghĩa là quay 180 độ, và đó không phải thực sự những gì tôi muốn, rõ ràng. Bởi vì ít nhất anh ta ở thế giới hai chiều này, nên bước ngoặt thực sự đi để lật ngược cậu lên. 

Tôi có thể muốn sử dụng những gì khối thay vào đó, dựa trên những gì bạn nhìn thấy ở đây? Làm thế nào chúng ta có thể khắc phục điều này? Yeah, vì vậy chúng tôi có thể chỉ theo hướng ngược lại. Và trên thực tế, ngay cả đó là sẽ không đủ, bởi vì chúng ta chỉ có thể cứng mã để chỉ trái hoặc phải. 

Bạn biết những gì chúng ta có thể làm gì? Có vẻ như chúng ta có một khối thuận tiện ở đây. Nếu tôi phóng to, xem một cái gì đó chúng tôi muốn ở đây? Vì vậy, nó trông giống như MIT có một trừu tượng được xây dựng tại đây. Khối này có vẻ là tương đương mà các khối khác, số nhiều? 

một khối này có vẻ là tương đương để toàn bộ ba này của khối mà chúng ta có ở đây. Vì vậy, nó quay ra tôi có thể đơn giản hóa của tôi chương trình bằng cách loại bỏ tất cả mà và chỉ cần đặt này tại đây. Và bây giờ anh vẫn còn một chút lỗi, và đó là tốt cho bây giờ. Chúng tôi sẽ để lại được. Nhưng chương trình của tôi thậm chí còn đơn giản hơn, và điều này, quá, sẽ là đại diện của một mục tiêu trong programming-- là lý tưởng làm cho mã của bạn như đơn giản, nhỏ gọn càng tốt, trong khi vẫn đang là đọc càng tốt. Bạn không muốn làm cho nó rất gọn gàng rằng đó là khó hiểu. 

Nhưng nhận thấy tôi đã thay thế ba khối với một, và đó là cho là một điều tốt. Tôi đã tóm tắt đi những khái niệm kiểm tra xem bạn đang trên các cạnh chỉ với một khối. Bây giờ chúng ta có thể vui vẻ với điều này, trên thực tế. Điều này không có thêm rất nhiều giá trị trí tuệ nhưng giá trị vui tươi. Tôi sẽ đi trước và lấy âm thanh này ở đây. Vì vậy, hãy để tôi đi trước, và cho tôi ngăn chặn các chương trình cho một thời điểm. Tôi sẽ ghi lại như sau, cho phép truy cập vào micro của tôi. 

Ở đây chúng tôi đi. Ouch. Hãy thử điều này một lần nữa. Ở đây chúng tôi đi. OK, tôi ghi lại những điều sai trái. Ở đây chúng tôi đi. Ouch. Ouch. Tất cả các quyền. Bây giờ tôi cần phải thoát khỏi điều đó. Tất cả các quyền. 

Vì vậy, bây giờ tôi có một ghi chỉ "ouch". Vì vậy, bây giờ tôi sẽ đi trước và gọi đây là "ouch". Tôi sẽ quay trở lại để kịch bản của tôi, và bây giờ thông báo có khối này được gọi là chơi âm thanh "meo meo" hoặc chơi âm thanh "ouch". Tôi sẽ kéo này, và ở đâu Tôi nên đặt này cho hiệu ứng hài hước? Yeah, vì vậy bây giờ nó là loại lỗi, bởi vì bây giờ này block-- nhận thấy cách này "nếu trên bờ, thư bị trả lại "là loại khép kín. Vì vậy, tôi cần phải sửa lỗi này. Hãy để tôi đi trước và làm điều này. Hãy để tôi nhận được thoát khỏi điều này và quay trở lại để gốc của chúng tôi, thận trọng hơn chức năng. Vì vậy, "nếu chạm vào cạnh, sau đó" Tôi muốn biến, như Victoria đề xuất, 180 độ. Và tôi muốn chơi âm thanh "ouch" đó? 

Yeah, nhận thấy nó ở bên ngoài rằng khối màu vàng. Vì vậy, đây cũng sẽ là một lỗi, nhưng tôi đã nhận thấy nó. Vì vậy, tôi sẽ kéo nó lên đây, và thông báo bây giờ là bên trong "nếu". Vì vậy, "nếu" là loại này giống như blot cánh tay giống như mà chỉ sẽ làm những gì bên trong của nó. Vì vậy, bây giờ nếu tôi thu nhỏ tại nguy cơ annoying-- 

MÁY TÍNH: Ouch, ouch, ouch. 

DAVID Malan: Và nó sẽ chỉ đi mãi mãi. Bây giờ chỉ cần đẩy nhanh việc ở đây, hãy để tôi đi trước và mở ra, hãy say-- cho tôi đi đến một số các công cụ của riêng tôi từ lớp. Và hãy để tôi mở ra, hãy nói, này một được làm theo một nghiên cứu sinh giảng dạy của chúng tôi một vài năm trước đây. Vì vậy, một số bạn có thể gọi lại game này từ năm qua, và nó thực sự đáng chú ý. Mặc dù chúng tôi đã thực hiện các đơn giản nhất của chương trình ngay bây giờ, chúng ta hãy xem xét điều này thực sự trông như thế nào. Hãy để tôi nhấn play. 

Vì vậy, trong trò chơi này, chúng ta có một ếch, và sử dụng các mũi tên keys-- anh sẽ bước lớn hơn tôi remember-- Tôi có thể kiểm soát ếch này. Và mục tiêu là để có được trên bận rộn đường mà không cần chạy vào xe ô tô. Và chúng ta hãy see-- nếu tôi lên đây, tôi phải chờ đợi cho một đăng nhập để di chuyển bằng. Điều này cảm thấy giống như một lỗi. Đây là loại lỗi. Tất cả các quyền. Tôi đang trên này ở đây, ở đó, và sau đó bạn giữ đi cho đến khi bạn nhận được tất cả các con ếch, các miếng lily. Bây giờ điều này có thể trông tất cả các phức tạp hơn, nhưng chúng ta hãy cố gắng để phá vỡ này xuống tinh thần và bằng lời nói thành các khối thành phần của nó. Vì vậy, có lẽ là một câu đố mảnh mà chúng tôi đã không nhìn thấy được nêu nhưng đó là phản ứng với tổ hợp phím, đến những điều tôi nhấn trên bàn phím. 

Vì vậy, có lẽ một số loại khối mà nói, nếu khóa bằng lên, sau đó làm điều gì đó với Scratch-- có thể di chuyển nó 10 bước theo cách này. Nếu phím xuống được nhấn, di chuyển 10 bước Bằng cách này, hoặc phím trái, di chuyển 10 bước Bằng cách này, 10 bước mà. Tôi đã bật rõ con mèo vào một con ếch. Vì vậy, đó chỉ là nơi trang phục, như các cuộc gọi Scratch it-- chúng tôi chỉ cần nhập khẩu một hình ảnh của con ếch. 

Nhưng những gì khác đang xảy ra? Những dòng mã khác những mảnh ghép khác đã Blake, giáo viên của chúng tôi, sử dụng trong chương trình này, rõ ràng? Có gì làm cho mọi thứ move-- những gì chương trình xây dựng? 

Motion, sure-- nên di chuyển khối, chắc chắn. Và đó khối di chuyển là những gì bên trong, nhiều khả năng? Vâng, một số loại vòng lặp, có thể một mãi mãi chặn, có thể lặp lại block-- lặp lại cho đến khi khối. Và đó là những gì làm cho các bản ghi và các miếng lily và mọi thứ khác di chuyển quay đi quay lại. Nó chỉ xảy ra không ngừng. 

Tại sao một số xe ô tô di chuyển nhanh hơn so với những người khác? khác nhau về những chương trình này là gì? Vâng, có thể là một số trong số họ đang dùng nhiều bước cùng một lúc và một số trong số họ ít bước cùng một lúc. Và các hiệu ứng hình ảnh là nhanh so với chậm. 

bạn nghĩ chuyện gì đã xảy ra? Khi tôi nhận ếch của tôi tất cả các cách trên đường phố và dòng sông lên lily pad, một cái gì đó đáng chú ý xảy ra. Những gì đã xảy ra ngay sau khi tôi đã làm điều đó? Nó đã dừng lại. ếch mà dừng lại, và Tôi có một con ếch thứ hai. Vì vậy, những gì xây dựng phải sử dụng ở đó, tính năng gì? 

Yeah, do đó, có một số loại "Nếu" điều kiện trên đó, quá. Và nó quay out-- chúng tôi không thấy này-- nhưng có các khối khác trong đó mà có thể nói, nếu bạn đang cảm động một điều khác trên màn hình, nếu bạn đang chạm vào pad lily, "sau đó." Và sau đó đó là khi chúng ta làm cho con ếch thứ hai xuất hiện. Vì vậy, mặc dù trò chơi này chắc chắn là rất ngày, mặc dù ở cái nhìn đầu tiên có rất nhiều đang xảy on-- và Blake không whip này lên trong hai phút, nó có lẽ ông đã mất vài giờ để tạo ra trò chơi này dựa trên bộ nhớ hoặc video của mình của phiên bản năm qua của nó. Nhưng tất cả những điều nhỏ nhặt đi trên màn hình trong sự cô lập đun sôi xuống những rất đơn giản phong trào constructs-- hoặc báo cáo như chúng ta đã thảo luận, các vòng lặp và điều kiện, và đó là về nó. Có một vài tính năng khác fancier. Một số trong số đó là hoàn toàn thẩm mỹ, âm thanh, như những âm thanh tôi chỉ chơi với. Nhưng đối với hầu hết các phần, bạn có trong ngôn ngữ này, Scratch, tất cả các nền tảng xây dựng khối mà bạn có trong C, Java, JavaScript, PHP, Ruby, Python, và nhiều ngôn ngữ khác. Mọi thắc mắc về Scratch? Tất cả các quyền. Vì vậy, chúng tôi sẽ không đi sâu vào sâu hơn để cào, mặc dù bạn đang chào đón cuối tuần này, đặc biệt là nếu bạn có con hay cháu gái và cháu trai và như vậy, để giới thiệu họ đến Scratch. Nó thực sự là một tuyệt vời vui tươi môi trường với, như tác giả của nó nói, trần nhà rất cao. Mặc dù chúng ta bắt đầu với rất thấp cấp thông tin chi tiết, bạn thực sự có thể làm khá một chút với nó, và điều này có lẽ là một cuộc biểu tình chính xác điều đó. 

Nhưng bây giờ chúng ta chuyển sang một số chi tiết vấn đề phức tạp, nếu bạn muốn, được gọi là "tìm kiếm" và "Phân loại", thông thường hơn. Chúng tôi đã có danh bạ điện thoại này earlier-- đây khác chỉ cho discussion-- rằng chúng ta đã có thể tìm kiếm hiệu quả hơn vì của một giả định quan trọng. Và chỉ để được rõ ràng, những gì giả định là tôi làm khi tìm kiếm thông qua các cuốn sách điện thoại này? Đó Mike Smith là trong danh bạ điện thoại, mặc dù tôi sẽ có thể xử lý kịch bản mà không có anh đó nếu tôi chỉ dừng lại sớm. Cuốn sách là chữ cái. Và đó là một rất hào phóng giả định, bởi vì đó nghĩa someone-- tôi là loại cắt một góc, như tôi nhanh hơn bởi vì một người nào đó khác đã làm rất nhiều công việc khó khăn đối với tôi. 

Nhưng những gì nếu điện thoại Cuốn sách đã được phân? Có lẽ Verizon đã lười biếng, chỉ ném tên và số của tất cả mọi người ở đó có thể trong thứ tự mà họ đăng ký dịch vụ điện thoại. Và bao nhiêu thời gian nó đưa tôi để tìm một người như Mike Smith? 1.000 điện thoại trang book-- bao nhiêu trang nào để xem xét thông qua? 

Tất cả bọn họ. Bạn đang loại ra khỏi may mắn. Bạn có nghĩa là phải nhìn vào mỗi trang nếu các cuốn sách điện thoại chỉ là được sắp xếp ngẫu nhiên. Bạn có thể nhận được may mắn và tìm Mike trên trang đầu tiên, bởi vì ông là khách hàng đầu tiên để đặt hàng dịch vụ điện thoại. Nhưng ông có thể đã được người cuối cùng, quá. 

Vì vậy, thứ tự ngẫu nhiên là không tốt. Vì vậy, giả sử chúng ta phải sắp xếp danh bạ điện thoại hoặc dữ liệu phân loại chung mà chúng ta đã được ban cho. Làm thế nào chúng ta có thể làm điều đó? 

Vâng, hãy để tôi chỉ cần cố gắng một ví dụ đơn giản ở đây. Hãy để tôi đi trước và quăng một vài con số trên bảng. Giả sử những con số chúng tôi có được, hãy nói, bốn, hai, một, và ba. Và, Ben, sắp xếp những con số này cho chúng tôi. 

Được rồi, tốt lắm. Cậu đã làm thế nào vậy? Tất cả các quyền. Vì vậy, bắt đầu với nhỏ nhất giá trị và cao nhất, và đó thực sự trực giác tốt. Và nhận ra chúng tôi rằng con người là thực sự khá giỏi giải quyết vấn đề như thế này, ít nhất là khi dữ liệu là tương đối nhỏ. Ngay sau khi bạn bắt đầu có hàng trăm số, hàng ngàn số, hàng triệu con số, Ben lẽ không thể làm điều đó khá là nhanh, giả sử rằng có những khoảng trống trong các con số. Khá dễ dàng để truy cập đến một triệu cách khác, tiêu thụ chỉ là thời gian. 

Vì vậy, các thuật toán nó âm thanh như Ben sử dụng chỉ cần bây giờ là tìm kiếm cho số nhỏ nhất. Vì vậy, mặc dù con người chúng ta có thể mất trong rất nhiều thông tin trực quan, một máy tính thực sự là hạn chế hơn một chút. Các máy tính có thể chỉ nhìn vào một byte tại một thời điểm hoặc có thể bốn byte tại một time-- những ngày này có lẽ 8 byte tại một time-- nhưng một số lượng rất nhỏ các byte tại một thời điểm nhất định. 

Vì vậy, cho rằng chúng ta thực sự có bốn giá trị riêng biệt đây-- và bạn có thể nghĩ về Ben là có bị mù mắt nếu ông là một máy tính như vậy rằng ông không thể nhìn thấy bất cứ điều gì khác hơn một số tại một time-- vì vậy chúng tôi sẽ thường giả định, như trong Tiếng Anh, chúng ta sẽ đọc từ phải sang trái. Vì vậy, số đầu tiên Bến lẽ trông tại bốn và sau đó rất nhanh chóng nhận ra đó là một khá lớn number-- cho tôi tiếp tục tìm. 

Có hai. Chờ một chút. Hai là nhỏ hơn so với bốn. Tôi sẽ nhớ. Hai bây giờ là nhỏ nhất. Bây giờ cùng-- mà thậm chí còn tốt hơn. Điều đó thậm chí nhỏ hơn. Tôi sẽ quên đi hai và chỉ cần nhớ một cái bây giờ. 

Và anh có thể ngừng tìm kiếm? Vâng, anh ấy có thể dựa trên thông tin này, nhưng ông muốn tìm kiếm tốt hơn phần còn lại của danh sách. Bởi vì những gì nếu không có trong danh sách? Điều gì nếu tiêu cực một là trong danh sách? Ông chỉ biết rằng câu trả lời của mình là đúng nếu anh ta triệt đã kiểm tra toàn bộ danh sách. Vì vậy, chúng ta nhìn vào những việc còn lại. Three-- đó là một sự lãng phí thời gian. Got không may mắn, nhưng tôi đã vẫn chính xác để làm như vậy. Và vì vậy bây giờ anh có lẽ chọn số nhỏ nhất và chỉ cần đặt nó ở đầu của danh sách, như tôi sẽ làm ở đây. Bây giờ bạn đã làm gì tiếp theo, mặc dù bạn không nghĩ về nó gần đến mức độ này? Lặp lại quá trình này, vì vậy một số loại vòng lặp. Có một ý tưởng quen thuộc. Vì vậy, đây là bốn. Đó là hiện nhỏ nhất. Đó là một ứng cử viên. Không còn nữa. Bây giờ tôi đã nhìn thấy hai. Đó là phần tử nhỏ nhất tiếp theo. Three-- đó không phải là nhỏ, vì vậy tại Bến có thể nhổ ra hai. 

Và bây giờ chúng ta lặp lại quá trình này, và tất nhiên ba bị kéo ra sau. Lặp lại quá trình này. Bốn bị kéo ra. Và bây giờ chúng ta đang trên con số, vì vậy danh sách phải được sắp xếp. 

Và quả thực, đây là một thuật toán chính thức. Một nhà khoa học máy tính sẽ gọi đây là "sắp xếp chọn" ý tưởng là loại một liệt kê iteratively-- lại và một lần nữa và một lần nữa lựa chọn số nhỏ nhất. Và những gì tốt đẹp về nó là nó chỉ là như vậy darn trực quan. Đó là đơn giản như vậy. Và bạn có thể lặp lại cùng một hoạt động một lần nữa và một lần nữa. Nó đơn giản. 

Trong trường hợp này nó đã được nhanh chóng, nhưng bao lâu nó thực sự mất? Hãy làm cho nó có vẻ và cảm thấy tẻ nhạt hơn một chút. Vì vậy, một, hai, ba, bốn, năm sáu, bảy, tám, chín, 10, 11, 12, 13, 14, 15, 16-- số tùy ý. Tôi chỉ muốn có thêm này thời gian hơn so với chỉ bốn. Vì vậy, nếu tôi đã có một toàn bộ loạt các con số now-- nó thậm chí không quan trọng những gì họ are-- của chúng suy nghĩ về điều này thuật toán thực sự là như thế. 

Giả sử có số đó. Một lần nữa, không có vấn đề gì họ, nhưng họ là ngẫu nhiên. Tôi đang áp dụng thuật toán của Ben. Tôi cần phải chọn số nhỏ nhất. Tôi làm gì? Và tôi sẽ phải thể chất làm điều đó thời gian này để hành động nó ra. Nhìn, nhìn, tìm kiếm, tìm kiếm, tìm kiếm. Chỉ bằng thời gian tôi nhận được để cuối của danh sách có thể Tôi nhận ra nhỏ nhất Số là hai thời gian này. Một không có trong danh sách. Vì vậy, tôi đặt xuống hai. 

Tôi làm gì tiếp theo? Nhìn, nhìn, nhìn, nhìn. Bây giờ tôi thấy số bảy, vì có những khoảng trống trong những numbers-- nhưng chỉ tùy ý. Tất cả các quyền. Vì vậy, bây giờ tôi có thể đặt xuống bảy. Nhìn tìm kiếm, tìm kiếm. 

Bây giờ tôi giả định, các Tất nhiên, đó Ben không có thêm RAM, thêm bộ nhớ, bởi vì, tất nhiên, Tôi đang nhìn vào cùng một số. Chắc chắn tôi có thể nhớ tất cả những con số, và điều đó hoàn toàn đúng. Nhưng nếu Ben nhớ lại tất cả của các con số ông nhìn thấy, ông đã không thực sự làm tiến bộ cơ bản bởi vì anh ta đã có khả năng tìm kiếm thông qua các số trên bảng. Nhớ tất cả các số không giúp đỡ, bởi vì anh ta vẫn có thể là một máy tính chỉ nhìn vào, chúng tôi đã nói, một số tại một thời điểm. Vì vậy, không loại cheat có mà bạn có thể tận dụng. 

Vì vậy, trong thực tế, như tôi tiếp tục tìm kiếm danh sách, Tôi nghĩa là có phải chỉ cần tiếp tục đi qua lại thông qua nó, tuốt ra số nhỏ nhất tiếp theo. Và như bạn có thể loại suy luận từ phong trào ngớ ngẩn của tôi, này chỉ được rất tẻ nhạt rất nhanh chóng, và tôi dường như được đi lại và ra, qua lại khá một chút. Bây giờ để cho công bằng, tôi không phải đi khá, tốt, chúng ta hãy see-- để được công bằng, Tôi không phải đi bộ khá nhiều bước mỗi lần. Bởi vì, tất nhiên, như tôi chọn số điện thoại từ danh sách, danh sách còn lại là nhận được ngắn hơn. 

Và như vậy chúng ta hãy suy nghĩ về bao nhiêu bước Tôi thực sự traipsing qua từng thời gian. Trong tình huống đầu tiên chúng tôi đã có 16 con số, và vì vậy chúng ta hãy chỉ maximally-- làm điều này cho một discussion-- Tôi đã xem xét thông qua 16 số để tìm nhỏ nhất. Nhưng một khi tôi móc con số nhỏ nhất, làm thế nào dài là danh sách còn lại, tất nhiên? Chỉ cần 15. Vì vậy, có bao nhiêu số đã Ben hoặc tôi có để xem xét thông qua lần thứ hai xung quanh? 15, chỉ để đi tìm nhỏ nhất. Nhưng bây giờ, tất nhiên, danh sách này là, quá, nhỏ hơn so với trước đây. Vì vậy, có bao nhiêu bước đã làm tôi phải dành thời gian tiếp theo? 14 và sau đó 13 và sau đó 12, cộng với dấu chấm, dấu chấm, dấu chấm, cho đến khi tôi là trái với chỉ một. Vì vậy, bây giờ là một nhà khoa học máy tính sẽ yêu cầu, cũng, những gì mà tất cả bằng nhau? Nó thực sự tương đương với một số bê tông số mà chúng ta có thể chắc chắn làm số học, nhưng chúng tôi muốn nói về hiệu quả của thuật toán một chút formulaically hơn, độc lập bao lâu trong danh sách là. 

Và như vậy bạn biết những gì? Đây là 16, nhưng như tôi đã nói trước đây, chúng ta chỉ cần gọi cho kích thước của vấn đề n, trong đó n là một số số. Có thể đó là 16, có lẽ nó ba, có lẽ đó là một triệu. Tôi không biết. Tôi không quan tâm. Những gì tôi thực sự muốn là một công thức mà tôi có thể sử dụng để so sánh các thuật toán này chống lại các thuật toán khác rằng ai đó có thể yêu cầu bồi thường tốt hơn hoặc tồi tệ hơn. 

Vì vậy, nó quay ra, và chỉ có tôi biết điều này từ hồi phổ thông, rằng điều này thực sự hoạt động ra để cùng điều khi n trên n cộng với một trong hai. Và điều này xảy ra để bằng, của Tất nhiên, n bình phương cộng với n qua hai. Vì vậy, nếu tôi muốn có một công thức cho bao nhiêu bước đã tham gia tìm kiếm ở tất cả của những con số một lần nữa và một lần nữa và một lần nữa và một lần nữa, tôi sẽ nói nó n bình phương cộng với n qua hai. Nhưng bạn biết những gì? Điều này chỉ có vẻ lộn xộn. Tôi chỉ thực sự muốn có một cảm giác chung của sự vật. Và bạn có thể nhớ lại từ trường trung học mà có là khái niệm hạn cao nhất. Mà những điều khoản này, các n bình phương, n, hoặc một nửa, có tác động nhất theo thời gian? Các n lớn hơn được, mà những vấn đề này nhiều nhất? 

Nói cách khác, nếu tôi cắm trong một triệu, n bình phương sẽ có nhiều khả năng nhất các yếu tố chi phối, vì một triệu lần chính nó là lớn hơn rất nhiều hơn cộng thêm một thêm triệu. Vì vậy, bạn biết những gì? Đây là một darn như lớn số nếu bạn vuông một số. Điều này không thực sự quan trọng. Chúng tôi chỉ đi ngang đó ra và quên nó đi. Và do đó, một nhà khoa học máy tính sẽ nói rằng hiệu quả của thuật toán này là vào thứ tự của n squared-- Tôi có nghĩa là thực sự là một xấp xỉ. Nó là loại khoảng n bình phương. Qua thời gian, lớn hơn và lớn hơn n được, điều này là một ước lượng tốt cho những gì hiệu quả hoặc thiếu hiệu quả của thuật toán này là thực sự. Và tôi lấy được rằng, tất nhiên, từ thực sự làm toán. Nhưng bây giờ tôi chỉ vẫy bàn tay của tôi, bởi vì tôi chỉ muốn có một cảm giác chung của thuật toán này. 

Vì vậy, bằng cách sử dụng cùng một logic, trong khi đó, chúng ta hãy xem xét thuật toán khác chúng tôi đã nhìn at-- tìm kiếm tuyến tính. Khi tôi đã được tìm kiếm cho book-- điện thoại không phân loại nó, tìm kiếm qua book-- điện thoại chúng tôi luôn nói rằng đó là 1000 bước, hoặc 500 bước. Nhưng chúng ta hãy khái quát đó. Nếu có n trang trong danh bạ điện thoại, có chuyện gì thời gian chạy hoặc hiệu quả của tìm kiếm tuyến tính? Đó là vào thứ tự của bao nhiêu bước để tìm Mike Smith sử dụng tìm kiếm tuyến tính, Thuật toán đầu tiên, hoặc thậm chí thứ hai? 

Trong trường hợp xấu nhất, Mike là ở phần cuối của cuốn sách. Vì vậy, nếu các cuốn sách điện thoại có 1.000 trang, chúng ta nói thời gian qua, trong trường hợp xấu nhất, nó có thể mất khoảng bao nhiều trang để tìm Mike? Giống như 1000. Đây là một ràng buộc trên. Đó là một tình huống tồi tệ nhất có thể. Nhưng một lần nữa, chúng ta đang di chuyển ra từ con số như 1000 bây giờ. Nó chỉ là n. 

Vì vậy, kết luận hợp lý là những gì? Tìm Mike trong điện thoại cuốn sách đó có các trang n có thể mất, trong trường hợp tồi tệ nhất, bao nhiêu bước vào thứ tự của n? Và thực sự là một máy tính nhà khoa học sẽ nói rằng thời gian chạy, hoặc hiệu suất hoặc hiệu quả hoặc không hiệu quả, của một thuật toán như một tìm kiếm tuyến tính là vào thứ tự của n. Và chúng ta có thể áp dụng cùng một logic của một cái gì đó vượt ra ngoài như tôi chỉ cần làm vào thứ hai thuật toán chúng ta đã có với các cuốn sách điện thoại, nơi mà chúng tôi đã đi hai trang tại một thời điểm. 

Vì vậy, 1.000 trang điện thoại cuốn sách có thể đưa chúng tôi 500 lượt trang, cộng với một nếu chúng ta tăng gấp đôi trở lại một chút. Vì vậy, nếu một cuốn sách điện thoại có các trang n, nhưng chúng tôi đang làm hai trang tại một thời điểm, đó là khoảng những gì? N qua hai, vì vậy đó là giống như n qua hai. Nhưng tôi đã yêu một thời điểm trước đó n qua two-- đó là loại giống như chỉ n. Nó chỉ là một yếu tố không đổi, các nhà khoa học máy tính sẽ nói. Hãy chỉ tập trung vào các biến, really-- các biến lớn nhất trong phương trình. 

Vì vậy, tìm kiếm tuyến tính, cho dù thực hiện một trang tại một thời điểm hoặc hai trang tại một thời điểm, là loại cơ bản giống nhau. Nó vẫn là vào thứ tự của n. Nhưng tôi khẳng định với hình ảnh của tôi trước đó rằng các thuật toán thứ ba là không tuyến tính. Đó không phải là một đường thẳng. Nó là đường cong, và các đại số công thức có là gì? Log của n-- để đăng nhập cơ sở hai của n. Và chúng tôi không phải đi vào quá chi tiết hơn về logarit ngày hôm nay, nhưng hầu hết các nhà khoa học máy tính sẽ không thậm chí nói với bạn những gì cơ bản là. Bởi vì nó là tất cả chỉ yếu tố liên tục, có thể nói, chỉ khác nhau số nhẹ. Và vì vậy đây sẽ là một rất phổ biến cách cho máy tính đặc biệt chính thức các nhà khoa học tại một hội đồng quản trị hoặc lập trình viên tại một bảng trắng thực sự tranh cãi đó thuật toán họ sẽ sử dụng hoặc những gì hiệu quả các thuật toán của họ. 

Và đây không phải là điều gì cần thiết bạn thảo luận tại bất kỳ chi tiết, nhưng một lập trình tốt là một người nào đó người có một, nền chính thức vững chắc. Anh ấy có thể nói chuyện với bạn trong các loại hình cách và thực sự làm lập luận định tính như tại sao một thuật toán hoặc một phần của phần mềm là cấp trên trong một số cách khác. Bởi vì bạn có thể chắc chắn chỉ cần chạy chương trình của một người và đếm số giây nó cần để sắp xếp một số con số, và bạn có thể chạy một số chương trình của người khác và đếm số giây nó mất. Nhưng đây là một cách tổng quát hơn, bạn có thể sử dụng để phân tích các thuật toán, nếu bạn muốn, chỉ cần trên giấy hay chỉ bằng lời nói. Thậm chí không cần chạy nó, mà không thậm chí cố gắng đầu vào mẫu, bạn chỉ có thể lý do thông qua nó. Và do đó, với việc thuê một nhà phát triển hoặc nếu có anh ta hoặc cô loại tranh luận với bạn tại sao thuật toán của họ, bí mật của họ nước sốt để tìm kiếm tỷ các trang web cho bạn công ty là tốt hơn, những là các loại của các đối số họ lý tưởng nên có thể thực hiện. Hoặc ít nhất đó là những các loại vật rằng sẽ đưa ra trong cuộc thảo luận, tại ít nhất là trong một cuộc thảo luận rất chính thức. Tất cả các quyền. Vì vậy, Ben đề nghị một cái gì đó gọi là chọn loại. Nhưng tôi sẽ đề xuất rằng có cách khác để làm điều này, quá. Những gì tôi đã không thực sự thích về thuật toán của Ben là ông tiếp tục đi, hoặc khi tôi đi bộ qua lại và qua lại và lui. Điều gì nếu thay vào đó tôi được làm một cái gì đó giống như những con số ở đây và tôi được chỉ đối phó với mỗi số lần lượt như tôi cho nó? 

Nói cách khác, đây là danh sách các số điện thoại. Bốn là, một, ba, hai. Và tôi sẽ làm như sau. Tôi sẽ chèn số nơi mà họ thuộc khá hơn chọn chúng cùng một thời gian. Nói cách khác, đây là con số bốn. 

Dưới đây là danh sách ban đầu của tôi. Và tôi sẽ duy trì cơ bản là một danh sách mới đây. Vì vậy, đây là danh sách cũ. Đây là danh sách mới. Tôi thấy số bốn đầu tiên. danh sách mới của tôi là bước đầu trống rỗng, do đó, nó là trivially trường hợp bốn mà bây giờ cả mọi loại danh sách. Tôi chỉ lấy số tôi đưa ra, và tôi đặt nó trong danh sách mới của tôi. 

Là danh sách mới này được sắp xếp? Yeah. Đó là ngu ngốc vì chỉ có một yếu tố, nhưng nó hoàn toàn được sắp xếp. Không có gì ra khỏi vị trí là. Thật thú vị hơn, thuật toán này, khi tôi chuyển sang bước tiếp theo. 

Bây giờ tôi có một. Vì vậy, một, tất nhiên, thuộc về tại bắt đầu hoặc kết thúc của danh sách mới này? Sự bắt đầu. Vì vậy, tôi phải làm một số công việc bây giờ. Tôi đã tham gia một số quyền tự do với điểm đánh dấu của tôi bằng cách chỉ vẽ mọi thứ nơi tôi muốn họ, nhưng đó không thực sự chính xác trong một máy tính. Một máy tính, như chúng ta biết, có RAM, hay Random Access Memory, và đó là một byte và một byte và byte khác. Và nếu bạn có một gigabyte của RAM, bạn có một tỷ byte, nhưng chúng thể chất ở một địa điểm. Bạn không thể chỉ di chuyển những thứ xung quanh bằng cách vẽ lên bảng bất cứ nơi nào bạn muốn. Vì vậy, nếu danh sách mới của tôi có bốn địa điểm trong bộ nhớ, tiếc là bốn là đã ở vị trí sai. 

Vì vậy, để chèn số một Tôi không thể chỉ vẽ nó ở đây. bộ nhớ vị trí này không tồn tại. Đó sẽ là lừa dối, và tôi đã gian lận trong những bức tranh cho một vài phút đây. Vì vậy, thực sự, nếu tôi muốn đặt một ở đây, Tôi phải tạm thời sao chép bốn và sau đó đặt một ở đó. 

Đó là tốt, đó là đúng, đó là kỹ thuật có thể, nhưng nhận ra đó là việc làm thêm. Tôi không chỉ đưa số tại chỗ. đầu tiên tôi đã phải di chuyển một số lượng, sau đó đặt nó tại chỗ, vì vậy tôi loại tăng gấp đôi số lượng làm việc của mình. Vì vậy, giữ cho rằng trong tâm trí. 

Nhưng bây giờ tôi đang thực hiện với yếu tố này. Bây giờ tôi muốn lấy số ba. Ở đâu, tất nhiên, nó thuộc về ai? Ở giữa. Tôi không thể ăn gian nữa và chỉ cần đặt nó ở đó, bởi vì, một lần nữa, bộ nhớ này là ở vị trí vật lý. Vì vậy, tôi phải sao chép bốn và đặt ba trên đây. Không phải là một thỏa thuận lớn. Nó chỉ là một bước thêm again-- cảm thấy rất rẻ tiền. 

Nhưng bây giờ tôi chuyển sang hai. Hai, tất nhiên, thuộc về đây. Bây giờ bạn bắt đầu để xem như thế nào công việc có thể chồng chất lên. Bây giờ những gì tôi phải làm gì? Vâng, tôi phải di chuyển bốn, sau đó tôi phải sao chép ba, và bây giờ tôi có thể chèn hai. Và bắt với điều này thuật toán, thú vị đủ, được rằng giả sử chúng ta có một chi tiết cực đoan Trường hợp đó là hãy nói tám, bảy, sáu, năm, bốn, ba, hai, một. Đây là, trong nhiều trường hợp, trường hợp xấu nhất, vì điều darn là nghĩa đen về phía sau. 

Nó không thực sự ảnh hưởng đến thuật toán của Ben, bởi vì trong lựa chọn của Ben loại anh ta sẽ giữ đi lui trong danh sách. Và bởi vì ông luôn tìm kiếm thông qua danh sách còn lại toàn bộ, nó không quan trọng nơi mà các yếu tố này. Nhưng trong trường hợp này với chèn của tôi approach-- hãy thử này. 

Vì vậy, một, hai, ba, bốn, năm, sáu, bảy, tám. Một hai ba bốn, năm, sáu, bảy, tám. Tôi sẽ lấy tám, và nơi nào tôi đặt nó? Vâng, vào đầu danh sách của tôi, bởi vì danh sách mới này được sắp xếp. Và tôi vượt qua nó ra. 

Tôi đặt bảy ở đâu? Khỉ thật. Nó cần phải đi đến đó, vì vậy Tôi phải làm một số sao chép. Và bây giờ bảy tại đây. Bây giờ tôi chuyển sang sáu. Bây giờ nó làm việc nhiều hơn. 

Tám phải đi đây. Bảy phải đi đây. Bây giờ sáu có thể đi đây. Bây giờ tôi lấy năm. Bây giờ tám phải đi ở đây, bảy phải đi đây, Sáu phải đi đây, và tại ngũ và lặp lại. Và tôi là khá nhiều di chuyển nó liên tục. 

Vì vậy, ở cuối, algorithm-- này chúng ta sẽ gọi nó chèn sort-- thực có rất nhiều công việc, quá. Nó chỉ khác nhau loại công việc hơn so với Ben. công việc của Ben đã cho tôi đi qua lại tất cả các thời gian, chọn tiếp theo nhỏ nhất yếu tố một lần nữa và một lần nữa. Vì vậy, nó là loại này rất trực quan của công việc. 

thuật toán khác này, đó vẫn là correct-- nó sẽ có được công việc done-- chỉ thay đổi số lượng công việc. Nó trông giống như ban đầu bạn tiết kiệm, bởi vì bạn chỉ đối phó với mỗi phần tử lên phía trước mà không đi tất cả các cách thức thông qua danh sách như Ben đã. Nhưng vấn đề là, đặc biệt là trong những trường hợp điên nơi mà nó là tất cả về phía sau, bạn chỉ cần loại trì hoãn công việc khó khăn cho đến khi bạn có để sửa chữa sai lầm của bạn. 

Và vì vậy nếu bạn có thể tưởng tượng này tám và bảy và sáu và năm và sau bốn ba và hai di chuyển theo cách của họ thông qua danh sách, chúng tôi đã chỉ cần thay đổi loại công việc chúng tôi đang làm. Thay vì làm việc đó tại bắt đầu lặp đi lặp lại của tôi, Tôi chỉ làm nó ở Cuối mỗi lần lặp. Vì vậy, nó chỉ ra rằng thuật toán này, quá, thường được gọi là sắp xếp chèn, cũng là thứ tự của n bình phương. Nó thực sự không tốt, không tốt ở tất cả. 

Tuy nhiên, có một cách tiếp cận thứ ba Tôi sẽ khuyến khích chúng ta phải xem xét, đó là điều này. Vì vậy, giả danh sách của tôi, vì đơn giản một lần nữa, là bốn, một, ba, two-- chỉ bốn số. Ben có trực giác tốt, trực giác tốt của con người trước đây, mà chúng tôi cố định toàn bộ liệt kê eventually-- loại chèn. Tôi dỗ dành chúng tôi cùng. Nhưng chúng ta hãy xem xét các Cách đơn giản để sửa danh sách này. 

Danh sách này không được sắp xếp. Tại sao? Trong tiếng Anh, giải thích lý do tại sao nó không thực sự được sắp xếp. có nghĩa là gì không để được sắp xếp? 

HỌC SINH: Nó không phải tuần tự. 

DAVID Malan: Không tuần tự. Hãy cho tôi một ví dụ. 

HỌC SINH: Đặt chúng theo thứ tự. 

DAVID Malan: OK. Hãy cho tôi một ví dụ cụ thể hơn. 

HỌC SINH: Sắp xếp tăng dần. DAVID Malan: Không thứ tự tăng dần. Được chính xác hơn. Tôi không biết những gì bạn có nghĩa là tăng dần. Chuyện gì vậy? 

HỌC SINH: Nhỏ nhất trong số số không có trong không gian đầu tiên. 

DAVID Malan: số nhỏ nhất của không phải trong không gian đầu tiên. Hãy cụ thể hơn. Tôi bắt đầu để đón về. Chúng tôi sẽ tính được, nhưng những gì ra khỏi trật tự ở đây? 

HỌC SINH: dãy số học. DAVID Malan: dãy số học. loại tất cả mọi người của công tác kế nó đây-- mức rất cao. Chỉ cần theo nghĩa đen cho tôi biết những gì sai lầm như một sức lăm tuổi. 

HỌC SINH: Thêm một. 

DAVID Malan: Đó là gì? 

HỌC SINH: Thêm một. 

DAVID Malan: Bạn có nghĩa là một cộng gì? Hãy cho tôi một khác nhau lăm tuổi. sai, mẹ là gì? sai, cha là gì? bạn có ý nghĩa gì này không được sắp xếp? 

HỌC SINH: Đây không phải là nơi thích hợp. 

DAVID Malan: có gì không đúng chỗ? 

HỌC SINH: Bốn. DAVID Malan: OK, tốt. Vì vậy, bốn không phải là nơi mà nó nên được. Đặc biệt, là quyền này? Bốn và một, đầu tiên hai số tôi nhìn thấy. Thê nay đung không? Không, chúng ra lệnh, phải không? Trong thực tế, cho rằng bây giờ về một máy tính, quá. Nó chỉ có thể nhìn vào có thể một, có lẽ hai việc cùng once-- và thực sự chỉ có một điều tại một thời điểm, nhưng nó có thể ít nhất nhìn vào một điều thì Điều tiếp theo ngay bên cạnh nó. 

Vì vậy, có những theo thứ tự? Tất nhiên là không. Vì vậy, bạn biết những gì? Tại sao chúng ta không đem em bé bước sửa chữa vấn đề này thay vì làm những ưa thích các thuật toán như Ben, nơi ông loại sửa chữa nó bằng cách Looping qua danh sách thay vì làm những gì tôi đã làm, nơi Tôi chỉ là loại cố định nó như chúng ta đi đâu? Hãy chỉ theo nghĩa đen phá vỡ khái niệm về số thứ tự order--, gọi nó là bất cứ điều gì bạn want-- vào những so sánh theo cặp. 

Bốn và một. Đây có phải là thứ tự đúng? Vì vậy, hãy khắc phục điều đó. Một và bốn, và sau đó chúng tôi sẽ chỉ sao chép đó. Được rồi, tốt. Tôi cố định một trong bốn người. Ba và hai? Không. Hãy để những lời của tôi phù hợp với ngón tay của tôi. Bốn và ba? 

Nó không phải theo thứ tự, vì vậy tôi sẽ để làm một, ba, bốn, hai. Được rồi, tốt lắm. Bây giờ bốn và hai? Chúng tôi cần phải sửa lỗi này, quá. Vì vậy, một, ba, hai, bốn người. Vì vậy, nó được sắp xếp? Không, nhưng nó gần gũi hơn với sắp xếp? 

Đó là, bởi vì chúng tôi cố định này sai lầm, chúng tôi cố định sai lầm này, và chúng tôi cố định sai lầm này. Vì vậy, chúng tôi cố định ba sai lầm cho là. Tuy không thực sự tìm được sắp xếp, nhưng nó là quan gần gũi hơn với sắp xếp bởi vì chúng ta cố định một số những sai lầm. 

Bây giờ tôi phải làm gì tiếp theo? Tôi loại đạt đến cuối danh sách. Tôi dường như đã cố định tất cả những sai lầm, nhưng không có. Bởi vì trong trường hợp này, một số con số có thể có bọt lên gần gũi hơn với các số khác mà vẫn đang trong trật tự. Vì vậy, hãy làm điều đó một lần nữa, và tôi sẽ chỉ làm điều đó ở nơi thời gian này. Một và ba? Tốt rồi. Ba và hai? Tất nhiên không có, vì vậy chúng ta hãy thay đổi điều đó. Vì vậy, hai, ba. Ba và bốn? Và bây giờ chúng ta chỉ cần có đặc biệt là mô phạm ở đây. Có phải sắp xếp? Bạn con người biết nó được sắp xếp. 

Tôi phải cố gắng một lần nữa. Vì vậy, Olivia đang đề nghị tôi thử lại. Tại sao? Bởi vì một máy tính không có sự sang trọng của đôi mắt con người của chúng tôi chỉ liếc back-- OK, tôi đang thực hiện. Làm thế nào để các máy tính xác định rằng danh sách này hiện đang được sắp xếp? Cơ học. 

Tôi nên đi qua một lần nữa, và chỉ khi tôi không thực hiện / tìm thấy bất kỳ sai lầm có thể tôi sau đó kết luận như máy tính, vâng, chúng tôi đang tốt để đi. Vì vậy, một và hai, hai và ba, ba và bốn. Bây giờ tôi không nói rằng đây là sắp xếp, bởi vì tôi đã không có thay đổi. Bây giờ nó sẽ là một lỗi và chỉ Thật ngớ ngẩn nếu tôi, máy tính, hỏi những câu hỏi tương tự một lần nữa mong câu trả lời khác nhau. không nên xảy ra. 

Và vì vậy bây giờ danh sách được sắp xếp. Thật không may, thời gian chạy của Thuật toán này cũng là n bình phương. Tại sao? Bởi vì bạn có n số, và trong trường hợp xấu nhất bạn phải di chuyển số n n lần vì bạn phải tiếp tục đi lại để kiểm tra và có thể khắc phục những con số này. Và chúng ta có thể làm một nhiều hơn phân tích chính thức, quá. 

Vì vậy, đây là tất cả để nói rằng chúng tôi đã thực hiện ba cách tiếp cận khác nhau, một của chúng trực quan ngay lập tức off the bat từ Ben để chèn đề nghị của tôi loại với trang này nơi bạn loại đánh mất rừng cho cây ban đầu. Nhưng sau đó nếu bạn lùi lại một bước, thì đấy, chúng tôi đã cố định các khái niệm phân loại. Vì vậy, đây là, dám nói, một mức độ thấp hơn có lẽ hơn một số người khác thuật toán, nhưng chúng ta hãy xem nếu chúng ta không thể hình dung những bằng cách này. 

Vì vậy, đây là một số đẹp phần mềm mà một người nào đó viết sử dụng các thanh đầy màu sắc đó là sẽ làm những điều sau đây cho chúng ta. Mỗi một thanh đại diện cho một số. Taller thanh, lớn hơn số lượng, thanh nhỏ hơn, nhỏ hơn số lượng. Vì vậy, lý tưởng chúng ta muốn có một kim tự tháp đẹp nơi nó bắt đầu nhỏ và trở nên trầm trọng, và điều đó có nghĩa rằng các thanh này đều được sắp xếp. Vì vậy, tôi sẽ đi trước và chọn, Ví dụ, thuật toán của Ben first-- sắp xếp chọn. 

Và nhận thấy những gì nó làm. Cách họ đã chọn hình dung thuật toán này là, giống như tôi là đi bộ qua danh sách của tôi, Chương trình này là đi bộ thông qua danh sách các số, nổi bật trong mỗi màu hồng số mà nó đang tìm kiếm tại. Và những gì sắp xảy ra ngay bây giờ? 

Số lượng nhỏ nhất Tôi hay Ben tìm thấy bất ngờ được chuyển lên đầu danh sách. Và việc thông báo họ đã đuổi số đó là có, và đó là hoàn toàn tốt đẹp. Tôi đã không nhận ra rằng mức độ chi tiết. Nhưng chúng ta cần phải đặt rằng số nơi nào đó, vì vậy chúng tôi chỉ cần di chuyển nó vào chỗ mở đã được tạo ra. Vì vậy, tôi sẽ tăng tốc độ này lên, bởi vì nếu không nó trở nên rất tẻ nhạt một cách nhanh chóng. Animation speed-- có chúng tôi đi. Vì vậy, tại cùng một nguyên tắc Tôi đã được áp dụng, nhưng bạn có thể bắt đầu cảm thấy các thuật toán, nếu bạn sẽ, hoặc nhìn thấy nó rõ ràng hơn một chút. Và thuật toán này có tác dụng lựa chọn các phần tử nhỏ nhất tiếp theo, do đó, bạn đang đi để bắt đầu nhìn thấy nó lên đoạn đường nối bên trái. Và trên mỗi lần lặp, như tôi đề xuất, nó làm một chút công việc ít hơn. Nó không phải đi tất cả các cách trở về đầu bên trái của danh sách, vì nó đã biết những đều được sắp xếp. Vì vậy, nó loại cảm thấy như nó tăng tốc, mặc dù mỗi bước là uống cùng một lượng thời gian. Chỉ là có ít hơn các bước còn lại. Và bây giờ bạn có thể loại cảm nhận thuật toán làm sạch kết thúc của nó, và thực hiện nó được sắp xếp. 

Vì vậy, sắp xếp chèn là hoàn tất. Tôi cần phải ngẫu nhiên mảng. Và nhận thấy tôi có thể chỉ giữ ngẫu nhiên đó, và chúng ta sẽ có được một xấp xỉ của các phương pháp tương tự, sắp xếp chèn. Hãy để tôi làm chậm nó xuống đây. Hãy bắt đầu rằng hơn. Dừng lại. 

Hãy bỏ qua bốn. Hiện chúng tôi đi. Chọn ngẫu nhiên mảng họ. Và ở đây chúng tôi go-- sắp xếp chèn. Chơi. Chú ý rằng nó đối phó với mỗi yếu tố nó gặp ngay lập tức, nhưng nếu nó thuộc về thông báo sai chỗ tất cả các công việc đó đã xảy ra. Chúng tôi phải tiếp tục chuyển hơn và nhiều yếu tố để làm cho căn phòng cho một trong chúng tôi muốn đưa ra. 

Vì vậy, chúng tôi đang tập trung vào các đầu bên trái của chỉ danh sách. Thông báo của chúng tôi thậm chí còn không nhìn at-- chúng tôi đã không được nhấn mạnh trong bất cứ điều gì màu hồng rẽ phải. Chúng tôi chỉ đối phó với những vấn đề như chúng tôi đi, nhưng chúng tôi đang tạo ra rất nhiều làm việc cho chính mình vẫn còn. Và như vậy, nếu chúng ta tăng tốc độ này lên bây giờ để đi đến hoàn thành, nó có một cảm giác khác nhau để nó thực sự. Nó chỉ tập trung vào cuối bên trái nhưng làm một công việc ít hơn như needed-- loại thứ mịn trên, sửa chữa những điều, nhưng giao dịch cuối cùng với mỗi phần tử cùng một lúc cho đến khi chúng tôi nhận được là-- tốt, chúng tôi tất cả biết cách này sẽ kết thúc, vì vậy nó là một underwhelming chút có lẽ. 

Nhưng danh sách trong end-- spoiler-- sẽ được sắp xếp. Vì vậy, chúng ta hãy nhìn vào một người cuối cùng. Chúng ta không thể bỏ qua bây giờ. Chúng ta gần đến rồi. Hai để đi, một đi. Và thì đấy. Xuất sắc. 

Vì vậy bây giờ chúng ta hãy làm một cái cuối cùng, lại ngẫu nhiên với bong bóng sắp xếp. Và hãy chú ý ở đây, đặc biệt là nếu tôi làm chậm nó xuống, điều này không giữ sà qua. Nhưng nhận thấy nó chỉ làm cho cặp loại comparisons-- các giải pháp địa phương. Nhưng ngay khi chúng tôi nhận được cuối của danh sách trong màu hồng, những gì sẽ phải xảy ra một lần nữa? Yeah, nó sẽ phải bắt đầu lại, bởi vì nó chỉ sai lầm cố định theo cặp. Và đó có thể đã tiết lộ nhưng những người khác. Và vì vậy nếu bạn tăng tốc độ này lên, bạn sẽ thấy rằng, giống như tên của nó, nhỏ hơn elements-- hay đúng hơn, các elements-- lớn đang bắt đầu bong bóng lên đến đỉnh, nếu bạn muốn. Và các yếu tố nhỏ hơn bắt đầu bong bóng xuống bên trái. Và quả thực, đó là loại các hiệu ứng hình ảnh là tốt. Và điều này sẽ kết thúc kết thúc theo một cách rất giống nhau, quá. 

Chúng tôi không có để ở trên một đặc biệt này. Hãy để tôi mở này ngay bây giờ, quá. Có một vài thuật toán sắp xếp khác trên thế giới, một vài trong số đó bị bắt ở đây. Và đặc biệt là cho người học không phải là người nhất thiết phải hình ảnh hay toán học, như chúng ta đã làm trước đây, chúng ta có thể cũng làm điều này audially nếu chúng ta kết hợp một âm thanh với điều này. Và chỉ để cho vui, đây là một vài thuật toán khác nhau, và một trong số họ nói riêng bạn sẽ nhận thấy được gọi là "sắp xếp hợp nhất." 

Nó thực sự là một cơ bản thuật toán tốt hơn, mà hợp nhất phân loại, một trong những những người bạn đang về để xem, không phải là thứ tự của n bình phương. Đó là vào thứ tự của n lần đăng nhập của n, mà thực sự là nhỏ hơn và do đó nhanh hơn so với những người ba khác. Và có một vài khác những người ngớ ngẩn mà chúng ta sẽ thấy. 

Vì vậy, ở đây chúng tôi đi với một số âm thanh. Đây là sắp xếp chèn, vì vậy một lần nữa nó chỉ là đối phó với các yếu tố khi họ đến. Đây là bong bóng sắp xếp, vì vậy nó coi đó là những cặp cùng một lúc. Và một lần nữa, các yếu tố lớn nhất đang sủi bọt lên đầu trang. 

Tiếp theo sắp xếp chọn. Đây là thuật toán của Ben, nơi một lần nữa anh ấy chọn lặp đi lặp lại phần tử nhỏ nhất tiếp theo. Và một lần nữa, bây giờ bạn có thể thực sự nghe nó tăng tốc nhưng chỉ trong chừng mực như nó đang làm ít hơn và ít hơn làm việc trên mỗi lần lặp. Đây là một nhanh hơn, hợp nhất phân loại, đó là phân loại các cụm số với nhau và sau đó kết hợp chúng. Vì vậy look-- trái một nửa đã được sắp xếp. 

Bây giờ nó sắp xếp nửa bên phải, và bây giờ nó sẽ kết hợp chúng thành một. Đây là một cái gì đó gọi là "Gnome loại." Và bạn có thể phần nào thấy rằng nó sẽ trở lại và ra, sửa chữa làm việc một chút ở đây và đó trước khi nó tiến hành công việc mới. Và đó là nó. Có một loại, đó là thực sự chỉ cho mục đích học tập, gọi là "ngu ngốc loại", trong đó có dữ liệu của bạn, sắp xếp nó một cách ngẫu nhiên, và sau đó kiểm tra nếu nó được sắp xếp. Và nếu nó không phải là, nó lại loại nó ngẫu nhiên, kiểm tra nếu nó được sắp xếp, và nếu không lặp đi lặp lại. Và trên lý thuyết, xác suất này sẽ hoàn thành, nhưng sau khi khá một chút thời gian. Đây không phải là nhất hiệu quả của thuật toán. Vì vậy, bất kỳ câu hỏi về những các thuật toán cụ thể hoặc bất cứ điều gì liên quan ở đó, quá? 

Vâng, bây giờ chúng ta trêu chọc nhau những gì tất cả những dòng này mà tôi đã vẽ và những gì tôi giả sử máy tính có thể làm bên dưới mui xe. Tôi cho rằng tất cả những con số Tôi giữ drawing-- họ cần phải nhận được được lưu trữ ở đâu đó trong bộ nhớ. Chúng tôi sẽ thoát khỏi anh chàng này ngay bây giờ, quá. 

Vì vậy, một phần của bộ nhớ trong computer-- nên RAM DIMM là những gì chúng tôi đã tìm kiếm cho ngày hôm qua, kép bộ nhớ nội tuyến module-- trông như thế này. Và mỗi người trong các con chip nhỏ màu đen là một số byte, thông thường. Và sau đó các chân vàng là như dây kết nối nó với máy tính, và bảng silicon màu xanh lá cây chỉ là những gì giữ tất cả mọi thứ lại với nhau. Vì vậy, điều này thực sự nghĩa là gì? Nếu tôi loại vẽ bức tranh này giống nhau, giả sử vì đơn giản mà DIMM này, kép mô-đun bộ nhớ nội tuyến, là một gigabyte bộ nhớ RAM, một gigabyte bộ nhớ, mà là bao nhiêu tổng số byte? Một gigabyte là bao nhiêu byte? Nhiều hơn thế. 1.124 là kg, 1000. Mega là triệu. Giga là một tỷ đồng. 

Tôi nói dối? chúng tôi thậm chí có thể đọc các nhãn? Điều này thực sự là 128 gigabyte, do đó, nó nhiều hơn. Nhưng chúng tôi sẽ giả vờ này chỉ là một gigabyte. Vì vậy, đó có nghĩa là có một tỷ byte của bộ nhớ có sẵn cho tôi hoặc 8 tỷ bit, nhưng chúng ta sẽ để nói chuyện về các byte bây giờ, tiến về phía trước. 

Vì vậy, điều đó có nghĩa là đây là một byte, đây là một byte, đây là một byte, và nếu chúng ta thực sự muốn được cụ thể chúng ta sẽ phải vẽ một tỷ hình vuông nhỏ. Nhưng điều đó có nghĩa gì? Vâng, hãy để tôi chỉ phóng to ở trên hình ảnh này. Nếu tôi đã có cái gì đó trông như bây giờ điều này, đó là bốn byte. 

Và vì vậy tôi có thể đặt bốn số ở đây. Một hai ba bốn. Hoặc tôi có thể đặt bốn chữ hoặc biểu tượng. "Chào!" có thể đi ngay, bởi vì mỗi chữ cái, chúng ta đã thảo luận trước đó, có thể được biểu với tám bit hoặc ASCII hoặc một byte. Vì vậy, nói cách khác, bạn có thể đặt 8 tỉ những thứ bên trong điều này một thanh bộ nhớ. Bây giờ những gì nó có nghĩa là để đưa mọi thứ trở lại sao để sao lưu trong bộ nhớ như thế này? Đây là những gì một lập trình viên sẽ gọi một "mảng". Trong một chương trình máy tính, bạn không nghĩ rằng về phần cứng cơ bản, mỗi se. Bạn chỉ nghĩ về mình là có truy cập vào một tổng tỷ byte, và bạn có thể bất cứ điều gì bạn muốn với nó. Nhưng để thuận tiện nó thường hữu ích để giữ đúng bộ nhớ của bạn bên cạnh nhau như thế này. Vì vậy, nếu tôi phóng to trên này-- bởi vì chúng ta chắc chắn sẽ không để vẽ một tỷ squares-- chút chúng ta hãy giả sử rằng ban này đại diện rằng thanh bộ nhớ bây giờ. Và tôi sẽ chỉ thu hút nhiều người như tôi đánh dấu kết thúc cho tôi ở đây. Vì vậy, bây giờ chúng tôi có một cây gậy bộ nhớ trên bảng đó là có một, hai, ba, bốn, năm, sáu, một, hai, ba, bốn, năm, sáu, seven-- quá 42 byte bộ nhớ trên tổng số màn hình. Cho tôi biết. Vâng, đã làm số học của tôi ngay. Vì vậy, 42 byte của bộ nhớ ở đây. Vì vậy, điều này thực sự nghĩa là gì? Vâng, một lập trình viên máy tính sẽ thực sự nói chung nghĩ về bộ nhớ này là địa chỉ. Nói cách khác, mỗi một trong những địa điểm trong bộ nhớ, trong phần cứng, có một địa chỉ duy nhất. 

Nó không phải là phức tạp như Một Brattle Square, Cambridge, Mass., 02138. Thay vào đó, nó chỉ là một con số. Đây là byte số không, điều này là một, đây là hai, đây là ba, và điều này là 41. Chờ một chút. Tôi nghĩ tôi đã nói 42 là thời điểm trước đây. Tôi bắt đầu đếm từ số không, vì vậy đó là thực sự chính xác. Bây giờ chúng ta không phải thực sự rút ra nó như một mạng lưới, và nếu bạn vẽ nó như một mạng lưới Tôi nghĩ rằng điều này thực sự có được một chút sai lầm. Thật là một lập trình viên sẽ, trong tâm trí riêng của mình, thường nghĩ về điều này bộ nhớ như là giống như một băng, giống như một miếng băng che mà chỉ cần đi và mãi mãi hoặc cho đến khi bạn chạy ra khỏi bộ nhớ. Vì vậy, một cách phổ biến hơn để vẽ và chỉ nghĩ về bộ nhớ sẽ được rằng đây là byte số không, một, hai, ba, và sau đó dấu chấm, dấu chấm, dấu chấm. Và bạn có tổng số 42 byte như vậy, thậm chí mặc dù thể chất nó có thể thực sự có một cái gì đó như thế này. 

Vì vậy, nếu bây giờ bạn nghĩ về bạn bộ nhớ như thế này, giống như một băng, đây là những gì một lập trình một lần nữa sẽ gọi một mảng của bộ nhớ. Và khi bạn muốn thực sự lưu trữ một cái gì đó trong bộ nhớ của máy tính, bạn thường làm cửa hàng thứ back-to-back to back-to-back. Vì vậy, chúng tôi đã nói chuyện về những con số. Và khi tôi muốn giải quyết vấn đề như bốn, một, ba, hai, mặc dù tôi đã chỉ vẽ chỉ số có bốn người, một, ba, hai trên bảng, máy tính sẽ thực sự đã thiết lập này trong bộ nhớ. 

Và những gì sẽ là bên cạnh hai trong bộ nhớ của máy tính? Vâng, không có câu trả lời cho điều đó. Chúng tôi thực sự không biết. Và do đó, miễn là máy tính không cần nó, nó không phải chăm sóc những gì tiếp theo với những con số đó không chăm sóc về. Và khi tôi nói trước đó rằng một máy tính chỉ có thể nhìn vào một địa chỉ ở một thời gian, đây là loại lý do tại sao. 

Không giống như một kỷ lục máy nghe nhạc và một đầu đọc chỉ có thể nhìn một lúc nào đó rãnh trong một bản ghi cũ-học vật lý tại một thời điểm, tương tự có thể một máy tính nhờ CPU của nó và của nó tập lệnh Intel, trong có hướng dẫn được đọc từ bộ nhớ hoặc lưu vào một memory-- máy tính chỉ có thể nhìn tại một địa điểm ở một time-- đôi khi một sự kết hợp của họ, nhưng thực sự chỉ là một địa điểm tại một thời điểm. Vì vậy, khi chúng tôi đã làm các thuật toán khác nhau, Tôi không chỉ viết trong một vacuum-- bốn, một, ba, hai. Những con số này thực sự thuộc về ở đâu đó vật lý trong bộ nhớ. Vì vậy, có chút nhỏ transistor hoặc một số loại thiết bị điện tử bên dưới mui xe lưu trữ các giá trị. 

Và trong tổng số, bao nhiêu bit là tham gia ngay bây giờ, chỉ để được rõ ràng? Vì vậy, đây là bốn byte, hoặc bây giờ nó là tổng số 32 bit. Vì vậy, thực sự có 32 số và những sáng tác bốn điều. Thậm chí còn nhiều hơn ở đây, nhưng một lần nữa chúng tôi không quan tâm về điều đó. 

Vì vậy, bây giờ hãy hỏi khác câu hỏi sử dụng bộ nhớ, bởi vì đó là lúc kết thúc trong ngày là ở phương sai. Không có vấn đề gì, chúng tôi có thể làm gì với máy tính, vào cuối ngày phần cứng vẫn là cùng bên dưới mui xe. Làm thế nào tôi có thể lưu trữ một từ trong đây? Vâng, một từ trong một máy tính như "Chào!" sẽ được lưu trữ như thế này. Và nếu bạn muốn có một còn từ, bạn có thể chỉ đơn giản ghi đè lên đó và nói điều gì đó như "hello" và cửa hàng đó ở đây. 

Và như vậy ở đây, quá, contiguousness này thực sự là một lợi thế, vì một máy tính có thể chỉ đọc từ phải sang trái. Nhưng đây là một câu hỏi. Trong bối cảnh của từ này, h-e-l-l-o, dấu chấm than, như thế nào có thể máy tính biết nơi từ bắt đầu và nơi từ kết thúc? Trong bối cảnh các số, làm thế nào các máy tính biết bao lâu chuỗi các số là hoặc nơi nó bắt đầu? Vâng, nó quay out-- và chúng ta sẽ không đi quá nhiều vào mức độ detail-- máy tính di chuyển những thứ xung quanh trong bộ nhớ nghĩa đen bằng cách các địa chỉ này. Vì vậy, trong một máy tính, nếu bạn viết code để lưu trữ những thứ như lời nói, những gì bạn đang thực sự làm là đánh máy biểu thức có nhớ nơi ở bộ nhớ của máy tính những lời này. Vì vậy, hãy để tôi làm một rất, ví dụ rất đơn giản. 

Tôi sẽ đi trước và mở ra một chương trình văn bản đơn giản, và tôi sẽ tạo ra một tập tin gọi là hello.c. Hầu hết các thông tin này, chúng tôi sẽ không đi vào chi tiết, nhưng tôi sẽ viết thư chương trình có cùng ngôn ngữ, C. Đây là mức đáng sợ hơn, Tôi cho rằng, so với Scratch, nhưng nó rất giống nhau trong tinh thần. Trong thực tế, những xoăn loại braces-- bạn có thể của nghĩ về những gì tôi chỉ cần làm như thế này. 

Hãy làm điều này, thực sự. Khi lá cờ màu xanh lá cây nhấp, làm như sau. Tôi muốn in ra "hello". Vì vậy, đây là bây giờ giả. Tôi là loại làm mờ các dòng. Trong C, ngôn ngữ này tôi đang nói về, in dòng này hello thực sự trở thành "printf" với một số dấu ngoặc đơn và dấu chấm phẩy. 

Nhưng đó là ý tưởng chính xác. Và điều này rất dễ sử dụng "Khi lá cờ màu xanh lá cây nhấp" trở thành các nhiều phức tạp hơn "int void main." Và điều này thực sự không có bản đồ, vì vậy tôi chỉ cần đi để bỏ qua điều đó. Nhưng các dấu ngoặc nhọn giống như các mảnh ghép cong như thế này. 

Vì vậy, bạn có thể loại của đoán. Thậm chí nếu bạn đã không bao giờ được lập trình trước, những gì chương trình này có thể làm gì? Có lẽ in chào với một dấu chấm than. 

Vì vậy, hãy cố gắng đó. Tôi sẽ lưu nó. Và điều này là, một lần nữa, rất môi trường học cũ. Tôi có thể không kích, tôi không thể kéo. Tôi phải gõ lệnh. Vì vậy, tôi muốn chạy chương trình của tôi, vì vậy Tôi có thể làm được điều này, như hello.c. Đó là các tập tin tôi chạy. Nhưng chờ đợi, tôi đang thiếu một bước. Điều gì đã làm chúng ta nói là một cần thiết bước cho một ngôn ngữ như C? Tôi đã chỉ viết mã nguồn mã, nhưng những gì tôi cần? Vâng, tôi cần một trình biên dịch. Vì vậy, trên máy Mac của tôi ở đây, tôi có một chương trình gọi là GCC, GNU C compiler, cho phép tôi làm điều này-- lượt mã nguồn của tôi vào, chúng tôi sẽ gọi nó, mã máy. 

Và tôi có thể thấy rằng, một lần nữa, như sau, những là số không và cái tôi chỉ tạo ra từ mã nguồn của tôi, tất cả các số không và những người thân. Và nếu tôi muốn chạy tôi program-- nó xảy ra để được gọi là a.out cho reasons-- lịch sử "hello". Tôi có thể chạy nó một lần nữa. Xin chào xin chào xin chào. Và có vẻ như được làm việc. 

Nhưng điều đó có nghĩa là ở đâu đó trong tôi bộ nhớ của máy tính là những lời h-e-l-l-o, dấu chấm than. Và hóa ra, chỉ là một sang một bên, những gì một máy tính sẽ thường làm sao cho nó biết nơi mọi thứ bắt đầu và end-- nó sẽ đặt một biểu tượng đặc biệt ở đây. Và ước là đặt số không ở cuối của một từ để bạn biết nó ở đâu thực sự kết thúc, vì vậy mà bạn không giữ in ra nhiều hơn và nhiều hơn nữa nhân vật hơn bạn thực sự có ý định. 

Nhưng takeaway ở đây, thậm chí mặc dù điều này là khá phức tạp, là nó cuối cùng tương đối đơn giản. Bạn đã được đưa ra sắp xếp của một băng, một trống không gian mà bạn có thể viết thư. Bạn chỉ cần phải có một biểu tượng đặc biệt, giống như tùy tiện số không, để đặt ở cuối lời nói của bạn để máy tính biết được, oh, tôi nên dừng lại sau khi in ấn Tôi thấy các dấu chấm than. Bởi vì điều tiếp theo có là một giá trị ASCII của số không, hoặc các ký tự null như ai đó sẽ gọi nó. Nhưng có loại của một vấn đề ở đây, và chúng ta hãy quay trở lại đến các số trong một khoảnh khắc. Giả sử rằng tôi làm, trên thực tế, có một dãy số, và giả sử rằng chương trình tôi đang viết là giống như một cuốn sách cấp cho giáo viên và một giáo viên lớp học. Và chương trình này cho phép anh ta hoặc cô gõ vào điểm số của học sinh về câu đố. Và giả sử rằng các học sinh bị rơi 100 trên bài kiểm tra đầu tiên của họ, có thể như một 80 người tiếp theo, sau đó một 75, sau đó 90 trên bài kiểm tra thứ tư. 

Vì vậy, tại thời điểm này trong những câu chuyện, mảng có kích thước bốn. Có bộ nhớ hoàn toàn ở những máy tính, nhưng các mảng, có thể nói, có kích thước bốn. Giả sử bây giờ mà giáo viên muốn để gán một bài kiểm tra thứ năm đến lớp. Vâng, một trong những điều ông hoặc cô ấy sẽ phải làm bây giờ là lưu trữ một giá trị khác ở đây. Nhưng nếu mảng giáo viên có tạo trong chương trình này là các kích thước cho, một trong những vấn đề với một mảng là bạn không thể chỉ giữ thêm vào bộ nhớ. Bởi vì những gì nếu một phần khác của chương trình có chữ "hey" đúng không? 

Nói cách khác, bộ nhớ của tôi có thể sử dụng cho bất cứ điều gì trong một chương trình. Và nếu trước tôi gõ, hey, Tôi muốn nhập vào bốn điểm bài kiểm tra, họ có thể đi ở đây và ở đây. Và nếu bạn đột nhiên thay đổi tâm trí của bạn sau đó và nói rằng tôi muốn có một bài kiểm tra thứ năm điểm số, bạn không thể chỉ đặt nó bất cứ nơi nào bạn muốn, bởi vì những gì nếu điều này bộ nhớ đang được sử dụng cho một cái gì đó else-- một số chương trình khác hoặc một số tính năng khác của chương trình rằng bạn đang chạy? Vì vậy, bạn phải suy nghĩ trước làm thế nào bạn muốn để lưu trữ dữ liệu của bạn, bởi vì bây giờ bạn đã vẽ mình vào một góc kỹ thuật số. 

Vì vậy, một giáo viên might thay vì nói khi viết một chương trình để lưu trữ của mình lớp, bạn biết những gì? Tôi sẽ yêu cầu, khi viết chương trình của tôi, mà tôi muốn không, một, hai, ba, bốn, năm, sáu, tám lớp tổng số. Vì vậy, một, hai, ba, bốn, năm, sáu, bảy, tám. Giáo viên có thể chỉ hơn phân bổ bộ nhớ khi viết chương trình của mình và nói, bạn biết những gì? Tôi sẽ không bao giờ phải chỉ định nhiều hơn tám câu đố trong một học kỳ. Đó chỉ là điên. Tôi sẽ không bao giờ phân bổ đó. Vì vậy, mà cách này người đó có linh hoạt để điểm số cửa hàng sinh viên, như 75, 90, và có thể một phụ nơi học sinh có thêm tín dụng, 105. 

Nhưng nếu giáo viên không bao giờ sử dụng ba không gian, có một takeaway trực quan ở đây. Anh ta hoặc cô ấy chỉ là lãng phí thời gian. Vì vậy, nói cách khác, có này sự cân bằng chung trong lập trình nơi bạn có thể phân bổ chính xác như bộ nhớ nhiều như bạn muốn, lộn ngược trong số đó là bạn siêu efficient-- bạn không bị lãng phí tại all-- nhưng nhược điểm trong đó là gì nếu bạn thay đổi tâm trí của bạn khi sử dụng các chương trình mà bạn muốn lưu trữ nhiều dữ liệu hơn bạn dự định ban đầu. 

Vì vậy, có lẽ giải pháp là, sau đó, viết chương trình của bạn trong một cách như vậy mà họ sử dụng nhiều bộ nhớ hơn hơn là họ thực sự cần. Bằng cách này bạn sẽ không chạy vào vấn đề đó, nhưng bạn đang bị lãng phí. Và các bộ nhớ chương trình của bạn sử dụng, như chúng ta đã thảo luận ngày hôm qua, ít bộ nhớ có sẵn cho các chương trình khác, sớm hơn máy tính của bạn có thể làm chậm xuống vì bộ nhớ ảo. Và vì vậy giải pháp lý tưởng có thể là những gì? 

Theo phân giao có vẻ xấu. Qua phân giao có vẻ xấu. Vì vậy, những gì có thể là một giải pháp tốt hơn? Việc phân bổ lại. Hãy năng động hơn. Đừng ép buộc mình phải chọn một tiên, ngay từ đầu, những gì bạn muốn. Và chắc chắn không quá phân bổ, vì sợ rằng bạn là lãng phí. 

Và do đó, để đạt được mục tiêu đó, chúng tôi cần phải ném cấu trúc dữ liệu này, vậy để nói chuyện, đi. Và vì vậy những gì là một lập trình thường sẽ sử dụng được cái gì gọi là không phải là một mảng nhưng một danh sách liên kết. Nói cách khác, anh ta hoặc cô ấy sẽ bắt đầu suy nghĩ về bộ nhớ của họ như là loại hình dạng của họ có thể rút ra theo cách sau. Nếu tôi muốn để lưu trữ một số trong một program-- vì vậy nó là tháng chín, Tôi đã trao cho sinh viên của tôi một bài kiểm tra; tôi muốn để lưu trữ bài kiểm tra đầu tiên của học sinh, và họ đã nhận 100 trên it-- tôi sẽ hỏi máy tính của tôi, bằng cách của chương trình tôi đã bằng văn bản, trong một đoạn bộ nhớ. Và tôi sẽ lưu trữ số 100 trong nó, và đó là nó. 

Sau đó, một vài tuần sau đó khi tôi nhận được bài kiểm tra thứ hai của tôi, và đó là thời gian để gõ trong đó 90%, tôi sẽ để yêu cầu máy tính, hey, máy tính, Tôi có thể có một đoạn bộ nhớ? Nó sẽ cung cấp cho tôi điều này đoạn trống của bộ nhớ. Tôi sẽ đưa vào các số 90, nhưng trong chương trình của tôi bằng cách nào đó hoặc other-- và chúng ta sẽ không phải lo lắng về cú pháp cho này-- tôi cần bằng cách nào đó chuỗi những thứ cùng nhau. Và tôi sẽ chuỗi chúng lại với nhau với những gì trông giống như một mũi tên ở đây. 

Các bài kiểm tra thứ ba mà đi lên, Tôi sẽ nói, hey, máy tính, cho tôi một đoạn bộ nhớ. Và tôi sẽ đặt xuống bất cứ điều gì nó được, như 75, và tôi phải chuỗi này nhau ngay bây giờ bằng cách nào đó. đố thứ tư đến cùng, và có lẽ đó là vào cuối học kỳ. Và bởi thời điểm đó chương trình của tôi có thể sử dụng bộ nhớ khắp nơi, trên khắp cơ thể. Và vì vậy chỉ cần cho đá, tôi sẽ vẽ này ra quiz-- tôi quên những gì nó là; tôi nghĩ có lẽ 80 hoặc một cái gì đó-- cách trên đây. 

Nhưng đó là tốt, bởi vì những bức tranh Tôi sẽ vẽ đường này. Nói cách khác, trong thực tế, trong phần cứng của máy tính, số điểm đầu tiên có thể kết thúc ở đây vì nó là đúng vào lúc bắt đầu của học kỳ. Người tiếp theo có thể kết thúc ở đây bởi vì một chút thời gian đã trôi qua và chương trình tiếp tục chạy. Điểm số tiếp theo, đó là 75, có thể là ở đây. Và điểm cuối cùng có thể là 80, đó là ở đây. 

Vì vậy, trong thực tế, thể chất, điều này có thể là những gì bộ nhớ của máy tính của bạn trông như thế nào. Nhưng điều này không phải là một tinh thần hữu ích mô hình cho một lập trình viên máy tính. Tại sao bạn nên chăm sóc nơi quái dữ liệu của bạn là kết thúc? Bạn chỉ muốn để lưu trữ dữ liệu. 

Đây là loại giống như cuộc thảo luận của chúng tôi trước đó của bản vẽ các khối lập phương. Tại sao bạn quan tâm là góc của khối lập phương và làm thế nào bạn có để biến để rút ra nó? Bạn chỉ muốn một khối lập phương. Tương tự như vậy ở đây, bạn chỉ muốn cuốn sách lớp. Bạn chỉ muốn nghĩ về này như là một danh sách các số. Ai quan tâm làm thế nào nó thực hiện trong phần cứng? 

Vì vậy, sự trừu tượng hiện nay là hình ảnh ở đây. Đây là một danh sách liên kết, như một lập trình viên sẽ gọi nó, chừng nào bạn có một danh sách, rõ ràng là các con số. Nhưng nó được liên kết trong những bức tranh bằng cách của những mũi tên, và tất cả những mũi tên bên dưới are-- mui xe, nếu bạn tò mò, nhớ lại rằng phần cứng vật lý của chúng tôi có địa chỉ số không, một, hai, ba, bốn. Tất cả các mũi tên này là giống như một bản đồ hoặc hướng dẫn, nơi mà nếu 90 hợp-- nay Tôi đã để đếm. 

Zero, một, hai, ba, bốn, năm, sáu, bảy. Dường như 90 là địa chỉ bộ nhớ số bảy. Tất cả những mũi tên rất là giống như một mẩu giấy nhỏ đó là đem lại hướng đến chương trình nói rằng theo bản đồ này để có được vị trí bảy. Và ở đó bạn sẽ tìm thấy số điểm bài kiểm tra thứ hai của học sinh. Trong khi đó, 75-- nếu tôi tiếp tục này, đây là bảy, tám, chín, 10, 11, 12, 13, 14, 15. 

mũi tên khác này chỉ đại diện cho một bản đồ bộ nhớ vị trí 15. Nhưng một lần nữa, các lập trình viên thường làm không quan tâm về mức độ chi tiết này. Và trong hầu hết tất cả các lập trình ngôn ngữ ngày nay, các lập trình viên thậm chí sẽ không biết đâu trong bộ nhớ những con số thực tế. Tất cả các anh hay cô ấy phải quan tâm là rằng họ bằng cách nào đó liên kết với nhau trong một cấu trúc dữ liệu như thế này. 

Nhưng hóa ra không để có được quá kỹ thuật. Nhưng chỉ vì chúng ta có thể có lẽ đủ khả năng để có cuộc thảo luận này ở đây, giả sử rằng chúng ta lại vấn đề này ở đây của một mảng. Chúng ta hãy xem nếu chúng ta hối tiếc sẽ ở đây. Đây là 100, 90, 75, và 80. 

Hãy cho tôi một thời gian ngắn làm cho tuyên bố này. Đây là một mảng, và một lần nữa, Nét đặc trưng của một mảng là tất cả các dữ liệu của bạn trở lại trở lại trở lại trong memory-- nghĩa đen một byte hoặc có thể bốn byte, một số số cố định của byte đi. Trong một danh sách liên kết, mà chúng ta có thể rút ra như thế này, bên dưới mui xe người biết đâu những thứ đó là gì? Nó thậm chí không cần phải chảy như thế này. Một số dữ liệu có thể là trở lại trái lên ở đó. Bạn thậm chí không biết. 

Và như vậy với một mảng, bạn có một tính năng được gọi là truy cập ngẫu nhiên. Và những gì các phương tiện truy cập ngẫu nhiên là mà máy tính có thể nhảy ngay lập tức đến vị trí bất kỳ trong một mảng. Tại sao? Bởi vì máy tính biết rằng vị trí đầu tiên là bằng không, một, hai và ba. 

Và vì vậy nếu bạn muốn đi từ yếu tố này để các phần tử tiếp theo, bạn có nghĩa là, trong tâm trí của máy tính, chỉ cần thêm một. Nếu bạn muốn đi đến yếu tố thứ ba, chỉ cần thêm cùng-- phần tử tiếp theo, chỉ cần thêm một. Tuy nhiên, trong phiên bản này của câu chuyện, giả sử máy tính hiện đang tìm kiếm tại hoặc đối phó với số lượng 100. Làm thế nào để bạn có thể tiếp theo lớp trong sổ điểm? 

Bạn phải mất bảy bước, mà là tùy ý. Để có được một kế tiếp, bạn phải mất thêm tám bước để có được 15. Nói cách khác, nó không phải là một khoảng cách liên tục giữa các con số, và do đó, nó chỉ mất máy tính nhiều hơn thời gian là điểm. Các máy tính có để tìm kiếm thông qua bộ nhớ trong trật tự để tìm thấy những gì bạn đang tìm kiếm. 

Vì vậy, trong khi một mảng có xu hướng được một dữ liệu nhanh structure-- vì bạn có nghĩa là chỉ làm phép tính đơn giản và có được nơi bạn muốn bằng cách thêm một, cho instance-- một danh sách liên kết, bạn hy sinh tính năng đó. Bạn có thể không chỉ đi từ đầu tiên thứ hai đến thứ ba thứ tư. Bạn phải làm theo bản đồ. Bạn phải mất nhiều bước để có được những giá trị, có vẻ như là thêm một chi phí. Vì vậy, chúng tôi đang phải trả giá, nhưng những gì là các tính năng mà Dan đã tìm kiếm ở đây? Những gì hiện một danh sách liên kết rõ ràng cho phép chúng ta làm, đó là nguồn gốc của Câu chuyện đặc biệt này? 

Chính xác. Một kích thước động đến nó. Chúng tôi có thể thêm vào danh sách này. Chúng tôi thậm chí có thể thu nhỏ danh sách, vì rằng chúng ta chỉ sử dụng như là bộ nhớ như chúng ta thực sự muốn và vì vậy chúng tôi không bao giờ qua phân giao. 

Bây giờ chỉ cần để được thực sự Nít-cầu kỳ, có một chi phí ẩn. Vì vậy, bạn không nên chỉ cho tôi thuyết phục bạn biết rằng đây là một sự cân bằng hấp dẫn. Có một chi phí ẩn ở đây. Lợi ích, để được rõ ràng, là chúng ta có được tính năng động. Nếu tôi muốn một yếu tố khác, tôi có thể chỉ rút ra nó và đặt một số trong đó. Và sau đó tôi có thể liên kết nó với một hình ảnh ở đây, trong khi ở đây, một lần nữa, nếu tôi đã vẽ bản thân mình vào một góc, nếu cái gì khác đã được sử dụng bộ nhớ ở đây, tôi gặp may. Tôi đã vẽ bản thân mình vào một góc. 

Nhưng những gì là ẩn chi phí trong bức tranh này? Nó không phải chỉ là số tiền thời gian mà nó cần để đi từ đây đến đây, đó là bảy bước, sau đó tám bước, mà là nhiều hơn một. một chi phí ẩn là gì? Không chỉ là thời gian. Thông tin bổ sung cần thiết để đạt được hình ảnh này. 

Vâng, đó là bản đồ, những mẩu nhỏ của giấy, như tôi tiếp tục miêu tả họ như. Những arrows-- những không được tự do. Một computer-- bạn biết những gì một máy tính có. Nó có số không và những người thân. Nếu bạn muốn đại diện cho một mũi tên hay một bản đồ hoặc một số, bạn cần một số bộ nhớ. Vì vậy, các giá khác bạn trả cho một danh sách liên kết, một khoa học máy tính thông thường tài nguyên, cũng là không gian. 

Và quả thực như vậy, do đó thường, trong cân bằng trong việc thiết kế kỹ thuật phần mềm hệ thống là thời gian và space-- là hai trong số các thành phần của bạn, hai của các thành phần đắt nhất của bạn. Đây là chi phí cho tôi thêm thời gian bởi vì tôi phải làm theo bản đồ này, nhưng nó cũng được chi phí cho tôi nhiều không gian hơn bởi vì tôi phải giữ bản đồ này xung quanh. Vì vậy, hy vọng, như chúng ta đã loại thảo luận ngày hôm qua và ngày hôm nay, là những lợi ích sẽ lớn hơn chi phí. 

Nhưng không có giải pháp rõ ràng ở đây. Có lẽ nó là better-- một cách nhanh chóng la và dơ bẩn, như Kareem đề xuất earlier-- để ném bộ nhớ vào vấn đề. Chỉ cần mua thêm bộ nhớ, suy nghĩ ít hơn khó khăn về việc giải quyết vấn đề, và giải quyết nó một cách dễ dàng hơn. Và quả thực trước đó, khi chúng tôi nói chuyện về sự cân bằng, nó không phải là không gian trong máy tính và thời gian. Đó là thời gian phát triển, trong đó lại là một nguồn tài nguyên. 

Vì vậy, một lần nữa, đó là hành động cân bằng này cố gắng để quyết định những điều bạn có sẵn sàng để chi tiêu? Đó là ít tốn kém nhất? Trong đó sản lượng các kết quả tốt hơn? Yeah? 

Thật. Trong trường hợp này, nếu bạn đại diện cho các số trong maps-- chúng được gọi bằng nhiều thứ tiếng "Con trỏ" hoặc "Địa chỉ" - đó là gấp đôi không gian. Đó không nhất thiết phải là xấu như tăng gấp đôi nếu ngay bây giờ chúng tôi chỉ lưu trữ số. Giả sử chúng ta được lưu trữ hồ sơ bệnh nhân trong một hospital-- nên tên Pierson của, số điện thoại, số an sinh xã hội, bác sĩ lịch sử. Hộp này có thể là nhiều, lớn hơn nhiều, trong trường hợp này một con trỏ nhỏ bé, địa chỉ của tiếp theo element-- nó không phải là một vấn đề lớn. Đó là một rìa như vậy giá nó không quan trọng. Nhưng trong trường hợp này, yeah, nó tăng lên gấp đôi. Câu hỏi hay. 

Hãy nói về thời gian một ít cụ thể hơn. thời gian chạy là gì tìm kiếm danh sách này? Giả sử tôi muốn tìm kiếm thông qua tất cả các lớp của học sinh, và có n lớp trong cấu trúc dữ liệu này. Ở đây, chúng ta có thể mượn từ vựng của trước đó. Đây là một cấu trúc dữ liệu tuyến tính. 

Big O của n là những gì cần thiết để có được đến cuối của cấu trúc dữ liệu này, whereas-- và chúng tôi đã không nhìn thấy này before-- một mảng mang lại cho bạn những gì được gọi là hằng số thời gian, có nghĩa là một bước hoặc hai bước hoặc 10 steps-- không quan trọng. Đó là một số cố định. Nó không có gì để làm với kích thước của mảng. Và lý do đó, một lần nữa, là truy cập ngẫu nhiên. Các máy tính có thể chỉ ngay lập tức nhảy đến một vị trí khác, bởi vì chúng ta đều như nhau khoảng cách từ tất cả mọi thứ khác. Không có nghĩ như thế. Tất cả các quyền. Vì vậy, nếu tôi có thể, hãy để tôi cố gắng vẽ hai hình ảnh chính thức. Một trong rất phổ biến được biết đến như một bảng băm. Vì vậy, để thúc đẩy cuộc thảo luận này, để em suy nghĩ làm thế nào để làm điều này. 

Vậy làm thế nào về điều này? Giả sử rằng các vấn đề chúng ta muốn giải quyết hiện nay được thực hiện trong một dictionary-- do đó, một bó toàn bộ các từ tiếng Anh hay bất cứ cái gì. Và mục tiêu là để có thể trả lời câu hỏi của form là này một từ? Vì vậy, bạn muốn thực hiện kiểm tra chính tả, chỉ như một từ điển vật lý mà bạn có thể tìm những thứ lên trong. Giả sử tôi đã làm điều này với một mảng. Tôi có thể làm điều này. 

Và giả sử các từ này là táo và chuối và dưa đỏ. Và tôi không thể nghĩ rằng các loại trái cây bắt đầu bằng d, vì vậy chúng tôi chỉ sẽ có ba quả. Vì vậy, đây là một mảng, và chúng tôi lưu trữ tất cả những từ này trong từ điển này là một mảng. Câu hỏi đặt ra, sau đó, là làm thế nào khác bạn có thể lưu trữ thông tin này? 

Vâng, tôi là loại gian lận ở đây, bởi vì mỗi một trong các chữ cái trong từ thực sự là một byte cá nhân. Vì vậy, nếu tôi thực sự muốn trở thành nit-kén chọn, tôi thực sự cần được chia nhỏ ra thành nhiều những phần nhỏ hơn của bộ nhớ, và chúng tôi có thể làm chính xác điều đó. Nhưng chúng ta sẽ chạy vào các vấn đề tương tự như trước. Nếu như, như Merriam Webster hoặc Oxford làm mỗi year-- họ thêm từ đến dictionary-- chúng tôi không nhất thiết muốn vẽ chính mình vào một góc với một mảng? 

Vì vậy, thay vào đó, có thể là một cách tiếp cận thông minh hơn là đặt quả táo vào nút hoặc hộp riêng của mình, như chúng ta sẽ nói, chuối, và sau đó ở đây chúng tôi có dưa đỏ. Và chúng tôi chuỗi những thứ cùng nhau. Vì vậy, đây là mảng, và đây là danh sách liên kết. Nếu bạn có thể không hoàn toàn nhìn thấy, nó chỉ nói "mảng", và điều này cho biết "danh sách." 

Vì vậy, chúng tôi có cùng một các vấn đề chính xác như trước, nhờ đó mà chúng ta có năng động trong danh sách liên kết của chúng tôi. Nhưng chúng tôi có một từ điển khá chậm. Giả sử tôi muốn tìm kiếm một từ. Nó có thể đưa tôi O lớn của n bước, bởi vì Từ này có thể được tất cả các con đường ở cuối danh sách, như dưa đỏ. Và nó chỉ ra rằng trong lập trình, sắp xếp của Chén thánh của dữ liệu cấu trúc, là một cái gì đó cung cấp cho bạn liên tục thời gian giống như một mảng nhưng mà vẫn mang lại cho bạn sự năng động. 

Vì vậy, chúng ta có thể có tốt nhất của cả hai thế giới? Và quả thực, có cái gì đó gọi là bảng băm cho phép bạn thực hiện chính xác rằng, mặc dù khoảng. Một bảng băm là một fancier cấu trúc dữ liệu mà chúng ta có thể nghĩ đến như là sự kết hợp của một array-- và tôi sẽ rút ra nó như này-- và danh sách liên kết rằng tôi sẽ vẽ như thế này ở đây. 

Và cách điều này công trình như sau. Nếu đây now-- băm table-- là cấu trúc dữ liệu thứ ba của tôi, và tôi muốn lưu trữ từ này, tôi không muốn chỉ cần lưu trữ tất cả các Nói cách trở lại trở lại để trở lại để trở lại. Tôi muốn tận dụng một số mẩu thông tin về các từ đó sẽ cho phép tôi có được nó mà nó nhanh hơn. 

Vì vậy, cho những lời táo và chuối và dưa đỏ, Tôi cố tình chọn những từ đó. Tại sao? Có gì loại cơ bản khác nhau về ba? Có gì rõ ràng? Họ bắt đầu bằng chữ cái khác nhau. 

Vì vậy, bạn biết những gì? Thay vì đặt tất cả những lời ta trong xô cùng, có thể nói, giống như trong một danh sách lớn, tại sao không Tôi ít nhất là cố gắng tối ưu và làm cho danh sách của tôi 1/26 như lâu dài. Một tối ưu hóa hấp dẫn có thể là lý do tại sao không I-- khi chèn một từ vào cấu trúc dữ liệu này, vào bộ nhớ của máy tính, tại sao tôi không đặt tất cả các 'a' từ đây, tất cả các 'b' từ đây, và tất cả các 'c' từ đây? Vì vậy, điều này kết thúc lên đặt một quả táo ở đây, chuối ở đây, dưa đỏ ở đây, và kể từ đó trở đi. 

Và nếu tôi có thêm từ like-- gì khác? Táo, chuối, lê. Bất cứ ai cũng nghĩ đến một loại trái cây bắt đầu với a, b, c? hoàn hảo Blueberry--. Có nghĩa là sẽ kết thúc ở đây. Và vì vậy chúng tôi dường như có một nhẹ giải pháp tốt hơn, bởi vì bây giờ nếu tôi muốn để tìm kiếm cho táo, tôi first-- tôi không chỉ lặn vào cấu trúc dữ liệu của tôi. Tôi không đi sâu vào bộ nhớ máy tính của tôi. lần đầu tiên tôi nhìn vào các chữ cái đầu tiên. 

Và đây là những gì một máy tính nhà khoa học nói. Bạn băm vào cấu trúc dữ liệu của bạn. Bạn lấy đầu vào của bạn, mà trong trường hợp này là một từ như táo. Bạn phân tích nó, nhìn vào chữ cái đầu tiên trong trường hợp này, do đó băm nó. Băm là một trong đó thuật ngữ chung bạn có một cái gì đó như là đầu vào và bạn sản xuất một số sản lượng. Và đầu ra trong đó trường hợp là vị trí bạn muốn tìm kiếm, người đầu tiên địa điểm, vị trí thứ hai, thứ ba. Vì vậy, đầu vào là táo, đầu ra là đầu tiên. Đầu vào là chuối, các đầu ra nên được thứ hai. Đầu vào là dưa đỏ, sản lượng nên được ba. Đầu vào là quả việt quất, các đầu ra nên lại lần hai. Và đó là những gì giúp bạn lấy các phím tắt thông qua bộ nhớ của bạn để có được những lời hoặc dữ liệu hiệu quả hơn. 

Bây giờ này cắt giảm thời gian của chúng tôi có khả năng bởi nhiều như một trong số 26, bởi vì nếu bạn cho rằng bạn có nhiều "một" lời nói như "z" từ như chữ "q", mà là không thực sự realistic-- bạn sẽ phải nghiêng qua thư nhất định của alphabet-- nhưng điều này sẽ là một gia tăng cách tiếp cận mà không cho phép bạn để có được những lời nhanh hơn nhiều. Và trong thực tế, một tinh vi chương trình, Googles của thế giới, các Facebooks của world-- họ sẽ sử dụng một bảng băm cho rất nhiều mục đích khác nhau. Nhưng họ sẽ không ngây thơ chỉ cần nhìn vào các chữ cái đầu tiên trong táo hoặc chuối hoặc lê hay dưa đỏ, bởi vì khi bạn có thể thấy những danh sách vẫn có thể có được lâu dài. 

Và do đó, đây vẫn có thể là loại của linear-- để loại chậm, như với O lớn của n mà chúng ta đã thảo luận trước đó. Vì vậy, những gì một thực tế bảng băm tốt sẽ do-- nó sẽ có một mảng lớn hơn nhiều. Và nó sẽ sử dụng một nhiều hơn hàm băm phức tạp, do đó nó không chỉ cần nhìn vào "một." Có lẽ nó nhìn vào "a-p-p-l-e" và bằng cách nào đó chuyển đổi những năm chữ cái vào vị trí nơi táo nên được lưu trữ. Chúng tôi chỉ đơn thuần sử dụng chữ 'a' một mình, bởi vì nó đẹp và đơn giản. 

Nhưng một bảng băm, trong Cuối cùng, bạn có thể nghĩ như là một sự kết hợp của một mảng, mỗi trong số đó có một danh sách liên kết mà lý tưởng nên càng ngắn càng tốt. Và đây không phải là một giải pháp rõ ràng. Trong thực tế, phần lớn việc điều chỉnh mà đi vào bên dưới mui xe khi thực hiện các loại cấu trúc dữ liệu phức tạp là bên phải là những gì chiều dài của mảng? hàm băm phải là gì? Làm thế nào để bạn lưu trữ những thứ trong bộ nhớ? 

Nhưng nhận ra như thế nào một cách nhanh chóng loại này thảo luận leo thang, hoặc là cho đến nay mà nó là loại trên đầu của một người tại thời điểm này, mà Ổn. Nhưng chúng tôi bắt đầu, thu hồi, với sự một cái gì đó ở mức độ thấp và điện tử. Và do đó, đây lại là thế này chủ đề trừu tượng, mà một khi bạn bắt đầu để đưa cho cấp, OK, tôi đã có it-- có bộ nhớ vật lý, OK, đã nhận nó, mỗi vị trí địa lý có địa chỉ, OK, tôi đã nhận nó, tôi có thể đại diện những địa chỉ như arrows-- bạn có thể nhanh chóng bắt đầu có cuộc hội thoại phức tạp hơn cuối cùng dường như được cho phép chúng tôi để giải quyết vấn đề như tìm kiếm và phân loại hiệu quả hơn. Và yên tâm, too-- bởi vì tôi nghĩ rằng đây là sâu nhất, chúng tôi đã đi vào một số các chủ đề CS proper-- chúng tôi đã thực hiện trong một ngày và một nửa ở đây chỉ những gì bạn thường có thể làm hơn quá trình tám tuần trong một học kỳ. 

Mọi thắc mắc về những? Không? Tất cả các quyền. Vâng, tại sao chúng ta không dừng lại ở đó, bắt đầu ăn trưa sớm vài phút, tiếp tục chỉ trong khoảng một giờ? Và tôi sẽ nán lại cho một chút với câu hỏi. Sau đó, tôi sẽ phải đi mất một vài cuộc gọi nếu đó là OK. Tôi sẽ bật nhạc trong khi chờ đợi, nhưng trưa nên quanh góc.