>> DAVID MALAN: Pekala.
Biz geri döndü.
programlama bu segmentte ne yani Ben şeylerin bir karışımıdır yapmak düşündüm.
Bir, biraz yapmak bir şey eller-on,
Bir daha oynak kullanarak da olsa programlama environment--
gösterebileceği bir fikirlerin tam çeşitleri
Biz bahsediyoruz oldum ama biraz daha resmen.
İki, bazı bakmak Daha fazla teknik yolları
Bir programcı aslında çözecek arama sorunu gibi sorunlar
Daha önce de baktı ki ve Ayrıca daha temelden
sıralama ilginç bir problem.
>> Biz sadece olsun gitmek farz Bu telefon rehberi sıralama olduğunu,
ama tek başına aslında bir tür bir çok farklı şekillerde sert bir sorun
bunu çözmek için.
Bu yüzden biz bu kullanacağız sorunların bir sınıfı
şeylerin temsilcisi olduğunu Genel olarak çözülebilir.
Ve sonra biz konuşacağız bazı ayrıntılı olarak ne hakkında
veri denir structures-- bağlantılı listeler gibi meraklısı yolları
ve hash tabloları ve ağaçlar o Bir programcı aslında olur
kullanımı, genellikle, kullanımı ve Bir beyaz tahta üzerinde boyamak için
bir resmi şeyin o uygulanması için öngörülüyor
bazı yazılım parçası.
>> Yani ilk bölümü eller yapalım.
Yani sadece kirli ellerini almak çevre denir scratch.mit.edu.
Bu kullandığımız bir araçtır Bizim lisans sınıfta.
o tasarlanmıştır olsa 12 yaş ve üstü için,
biz bunu kullanmak Bu yeraldığını parçası
o güzel, eğlenceli beri öğrenme grafik yolu
programlama hakkında küçük bir şey.
Peki nerede o URL'ye baş Oldukça böyle bir sayfa göreceksiniz,
ve devam edin ve tıklayın Sağ üst taraftaki Scratch katılın
ve bir kullanıcı adı ve a seçin Parola ve sonuçta kendinizi olsun
Bir account-- scratch.mit.edu.
Ben bir olarak kullanabilirsiniz düşündüm fırsat öncelikle bu göstermek için.
Bir soru molası sırasında gündeme geldi Ne hakkında kodu aslında benziyor.
Ve biz konuşuyorduk C hakkında mola sırasında,
bölgesindeki particular-- özellikle Eski bir dilde alt düzey.
Ve ben sadece hızlı yaptım Google C kodu bulmak için arama
ikili arama, algoritması için biz Daha önce bu telefon rehberini aramak için kullanılır.
Bu özel örnek, tabii ki, Bir telefon rehberi aramaz.
Bu sadece bir sürü arar bilgisayarın belleğindeki sayılar.
Ama sadece bir görsel olsun istiyorsanız Ne gerçek bir programlama duygusu
Bu gibi görünüyor dil görünüyor Böyle küçük bir şey.
Yani, yaklaşık 20 artı kod 30 kadar hatları,
ama konuşma biz molası yapıyorduk
nasıl bu aslında hakkında oldu birler ve sıfırlar dönüştü alır
ve sadece o dönemezsiniz eğer işlemek ve birler ve sıfırlar gitmek
koduna geri.
>> Ne yazık ki, proses yani dönüştürücü olduğunu
çok daha kolay olduğunu yapmaktan daha söyledi.
Devam ettim ve aslında döndü Bu program İkili Arama,
Bir yoluyla sıfır ve olanları içine Program Derleyici denilen Ben
benim Mac burada sahip olur.
Ve ekranda bakarsanız Burada, özellikle odaklama
bu orta altı sütun üzerine sadece, Yalnızca sıfırları ve olanları görürsünüz.
Ve bu sıfırlar ve hangilerinin olduğunu tam olarak bu arama programı oluşturmak.
>> Ve böylece beş bitlik her yığın, Burada sıfırlar ve olanları her bayt,
Bazı öğretim temsil tipik olarak bir bilgisayar içinde.
Ve aslında, duydum eğer Pazarlama sloganı "Intel Inside" - yani,
Tabii, sadece bir var demektir bilgisayarın içindeki Intel CPU veya beyin.
Ve bu bir CPU olmanın ne demek Bir komut seti var,
sözde.
>> Birçok dünyadaki her işlemci, Onları bu gün Intel tarafından yapılan,
sonlu anlar Talimatlar sayısı.
Ve bu talimatlar çok düşük seviyededir olarak, bu iki sayı eklemek
Birlikte bu iki sayıyı çarpmak, Buradan elde edilen verilerin bu parça taşımak
Burada bellekte için, bu tasarruf Buradan elde edilen bilgiler, bellekte buralara
ve böylece forth-- çok, çok düşük seviyeli, neredeyse elektronik ayrıntılar.
Ama bu matematiksel ile operasyonlar birleştiğinde
daha önce tartıştığımız ne, veri temsili
can birler ve sıfırlar gibi Her şeyi kurmak
Bir bilgisayar olup olmadığını, bugün yapabileceği o, metinsel, grafik, müzik var
ya da.
>> Yani bu almak çok kolay hızlı bir şekilde otların kaybetti.
Ve bir sürü var sözdizimsel zorluklar
bu sayede en basit yaparsanız, Programın yazım hataları hiçbiri aptalca
olursa olsun çalışacaktır.
Ve böylece yerine kullanarak C gibi dil Bu sabah,
Ben bunun olacağını düşündüm daha eğlenceli aslında yapmak
daha fazla görsel bir şey, hangi Çocuklar için tasarlanmış ise
Mükemmel bir tezahürü aslında gerçek bir programlama
dil alanındaki lazım olur metin yerine resim kullanmak
bu fikirleri temsil etmek.
>> Eğer gerçekten bir var bir kere Yani scratch.mit.edu hesap,
Oluştur düğmesini tıklayın üstündeki sitenin bıraktı.
Ve böyle bir ortam görmelisiniz Ben ekranda gördüğünüz üzereyim biri
İşte.
Ve biz biraz harcayacağınız Zaman biraz burada oynuyor.
Hepimizin bazı çözemez Bakalım şu şekilde sorunlar birlikte.
>> Peki bu içinde göreceksiniz environment-- ve aslında sadece izin
Beni duraklatmak.
Herkes Buraya değil mi?
Burada değil?
TAMAM.
Bu yüzden bana bir kaç işaret izin Bu ortamın özellikleri.
>> Ekranın sol üst kısmında Yani, biz Çizik sahne var, tabiri caizse.
Çizilmeye sadece adı Bu programlama dilinin;
o da kedinin adı olduğunu Eğer turuncu orada varsayılan görüyoruz.
O, bir sahnede yani çok ben tarif gibi
Bir varlık olarak daha önce kaplumbağa dikdörtgen beyaz tahta ortamı.
Bu kedinin dünya tamamen sınırlıdır Oradaki dikdörtgen yukarı üstüne.
>> Bu arada, sağ tarafta Burada tarafta, öyle
Sadece bir komut dosyaları alanı, boş barut eğer olacak.
Bu ne yazmak için gidiyoruz nerede sadece bir an bizim programlar.
Ve yapı taşları, biz eder Bu bulmacayı program-- yazmak için kullanın
Parçalar, bir will-- ise ortasında burada olanlar,
ve kategorize konum işlevselliği ile.
Yani, örneğin, ben önde gidiyorum ve bunlardan en az bir göstermektedir.
Devam edin ve tıklayın gidiyorum kontör Kontrol kategorisi.
>> Peki bu kontör kategoriler vardır.
Ben Denetim kategorisini tıklatın gidiyorum.
Aksine, ben olayları tıklayın gidiyorum kategorisinde, çok ilki kontör.
Ve hatta birlikte takip etmek istiyorsanız Biz bunu, sen oldukça buyrun.
Ben tıklayın ve bu sürüklemek için gidiyorum İlki, "yeşil bayrak tıklandığında."
Ve sonra ben sadece damla gidiyorum kabaca benim boş levhaların üst kısmında.
>> Ve Scratch hakkında güzel ne bu puzzle parçası, o zaman
Diğer bulmaca ile iç içe parçalar, kelimenin tam anlamıyla yapacak
Bu puzzle parçaları yapmak ne demek.
Yani, örneğin, Scratch doğru şimdi onun dünyanın ortasında.
Devam edin ve seçmek için gidiyorum Şimdi, diyelim ki, Hareket kategorisi,
Eğer yapmak istiyorum eğer Hareket kategorisini same--.
Ve şimdi bir bütün var fark Burada puzzle parçaları demet
Yine, tür yapmak, öyle diyorlar.
Ve ben devam edin ve sürükle ve gidiyorum Burada üzerinde hareket bloğu bırakın.
>> Ve bu kısa sürede size olsun fark "Yeşil bayrak dibine yakın
tıklandığında "butonuna haber nasıl bir beyaz çizgi görünür,
neredeyse var sanki Manyetik, oraya gitmek istiyor.
Sadece gidelim, ve yapışır Birlikte ve şekiller maç olacak.
Ve şimdi yapabilirsiniz belki de neredeyse biz bu nereye gidiyoruz sanırım.
>> Eğer Scratch aşamada bakacak olursak Burada ve üzerinde bunun üstüne bakmak,
Eğer kırmızı ışık görürsünüz, bir işareti ve bir yeşil bayrak durdurun.
Ve ben önde gidiyorum ve benim screen-- izlemek
Sadece bir an için, eğer sen-ebil.
Ben tıklayın gidiyorum Şu anda bayrağı yeşil,
ve o 10 adım gibi görünen taşındı ya da ekranda 10 piksel, 10 nokta.
>> Ve böylece heyecan verici değil, ama bana teklif izin
Hatta bu öğretim olmadan sadece Kendi intuition-- let kendi kullandığı
Beni nasıl anlamaya öneriyoruz Sağ sahneden Scratch yürüyüş yapmak.
Onu sağ tarafı için yol yapmak var ekran, sağa tüm yol.
Sana bir an vereyim ya da böylece güreşmek.
Sen bir göz atmak isteyebilirsiniz Blokların diğer kategoriler de.
Pekala.
Yani sadece biz varken, tekrarlamak için yeşil bayrak burada tıklanan
ve 10 adım olduğunu taşımak Sadece talimat, her zaman
yeşil bayrak tıklayın neler oluyor?
Eh, o benim program çalışıyor.
Yani bu yapabileceğini belki elle 10 kez,
ama bu biraz hissediyor Biraz hackish, tabiri caizse,
bu sayede gerçekten değilim problem çözme.
Ben sadece tekrar çalışıyorum ve tekrar ve tekrar
kadar çeşit kazara direktifi ulaşmak
ben daha önce ulaşmak için yola çıktı.
>> Ama biz biliyoruz bizim pseudocode önce var olduğunu
döngü programlanmasında bu kavram, Tekrar ve tekrar bir şey yapıyor.
Ve böylece gördüm ki sana bir demet Ne bulmaca parçası uzandı?
kadar tekrarlayın.
Bu yüzden bir şey yapabileceğini gibi kadar tekrarlayın.
Ve tam kadar ne tekrar mı?
>> TAMAM.
Ve benim biriyle gidelim Sadece bir an için biraz daha basit.
Beni devam edip bu yapalım.
sahip olabilir, dikkat edin Kontrol altında keşfedilen
Bu tekrar blok var olduğu öyle görünmüyor büyük.
değil çok oda var Bu iki sarı çizgiler arasında.
Ama bazılarınız olabilir Eğer sürükle ve bırak eğer, fark,
o şekli doldurmak için nasıl büyür dikkat edin.
>> Ve hatta daha tıkmak olabilir.
Sadece eğer büyümeye devam edeceğiz sürükle ve bunun üzerinde gezdirin.
Ve ben ne olduğunu bilmiyorum Burada en iyi, bu yüzden izin
En azından için, beş kez tekrarlayın örneği ve ardından sahneye geri dönmek
ve yeşil bayrak tıklayın.
Ve şimdi oldukça orada değil dikkat edin.
>> Şimdi bazılarınız olarak, önerilen Victoria sadece 10 kez tekrarlayın etmedi.
Ve bu genellikle yapar tüm yol onu,
ama orada olur bir daha sağlam keyfi bulmaktan daha yolu
kaç hamle yapmak için?
Ne daha iyi bir blok olabilir tekrar 10 kat daha olabilir mi?
>> Evet, neden sonsuza kadar bir şey yapamaz?
Ve şimdi bu puzzle parçası dönelim içeride ve bu bir kurtulun.
Şimdi nerede Scratch olursa olsun fark başlar, o kenarına gider.
Ve minnetle MİT, kim sadece Scratch yapar
emin ki o asla yapar tamamen kaybolur.
Her zaman kuyruğunu yakalayabilir.
>> Ve sadece sezgisel, Neden hareketli tutmak mı?
Burada neler oluyor?
O, durmuş gibi görünüyor ama Ben ve sürükle pick up sonra eğer
o oraya gitmek isteyen tutar.
Neden?
Gerçekten, bir bilgisayar tam anlamıyla yapmanız bunu söylemek ne olacak.
Eğer söyleseydim Yani daha önce yapmak sonsuza kadar bir şey takiben 10 adım hareket,
gidiyor ve devam edecek Ben kırmızı dur işareti vurmak kadar
ve tamamen programı durdurmak.
>> değil mi bu yüzden bile Bunu nasıl yapabilirdim
Daha hızlı Scratch hamle yapmak ekran boyunca?
Daha adımlar, doğru mu?
Bunun yerine 10 yapıyor Bir seferde, neden biz değiliz
go ahead ve aşağıdaki amaçlara yönelik değiştirmek 50 Ne propose-- ki?
Yani şimdi ben yeşil tıklayın gidiyorum bayrak ve aslında, o gerçekten çok hızlı gidiyor.
>> Ve bu, tabii ki, sadece bir animasyon bir tezahürüdür.
Animasyon nedir?
Sadece size insan a gösteriyor Gerçekten hareketsiz görüntülerin sürü,
Gerçekten, gerçekten hızlı.
Ve eğer öyleyse biz sadece söylüyorsun onu daha adımları hareket etmek,
Biz sadece etkisi için olmak yaşıyorsanız o ekranda değişiklik
her zaman, daha hızlı bir şekilde her birimi.
>> Ben önerdi Şimdi yeni bir meydan okuma Onu kenarından sıçrama sahip oldu.
Peki bulmaca bilmeden ince çünkü parçalar exist--
Eğer alamadım eğer challenge-- evresi nedir
sezgisel yapmak istiyorsun?
Onu nasıl geri sıçrama olurdu ve ileri, sol ve sağ arasında?
>> Evet.
Bu yüzden çeşit gerekir durumun, ve
bu yüzden, çıkarabilseniz var gibi görünüyor Kontrol kategorisi altında, konuşuyoruz.
Bu blokların hangisi biz muhtemelen istiyorsun?
Evet, belki ", sonra."
Yani sarı bloklar arasında fark biz bu "eğer" var, burada var
ya da bu "eğer başka" blok bu olacak Bize bunu yapmak için bir karar vermek için izin
ya bunu yapmak için.
Ve sen bile yuva onları Birden fazla şeyler yapmak.
Ya da henüz burada gitmiş değil verdiyseniz, Algılama kategorisine devam
ve-- o burada bakalım.
>> Peki blok burada yardımcı olabilir O sahneden eğer algılamak için?
Evet, bu blokların bazı fark parametrize edilebilir tabiri caizse.
Bunlar bir çeşit değil, özelleştirilebilir HTML aksine dün nitelikleriyle,
nerede bu nitelikler tür Bir etiketin davranışını özelleştirmek.
Benzer şekilde burada, ben bu dokunma yakala Blok ve değişim ve soru sormak,
Fareyi dokunuyorsun imleç gibi işaretçi
ya da kenar dokunuyorsun?
>> Bu yüzden bana gitmek ve bu yapalım.
Ben bir an için uzaklaşmak için gidiyorum.
Beni bu puzzle parçası alalım Burada, bu puzzle parçası bu,
ve ben karışmak gidiyorum Sadece bir an için onları yukarı.
Ben, bu hareket için gidiyorum dokunmadan kenarına değiştirebilirsiniz,
Bunu yapmak ve ben harekete gidiyorum.
Yani burada bazı maddeler vardır.
Ben istediğim her şeyi buldum.
>> Birisi nasıl önermek istiyorum ben Bu belki yukarıdan aşağıya bağlayabilirsiniz
problemini çözmek amacıyla Çizilmeye hareket için sağa sola doğru
Her sağdan sola soldan Zaman sadece duvara sıçrayan?
Ne yapmak istiyorsun?
Hangi blok Ben bağlamak gerekir "Yeşil bayrak ilk tıklanan"?
>> Tamam, o yüzden başlayalım "sonsuza kadar."
Bundan sonra içeride gidiyor?
Başkası.
Tamam, adımları taşıyın.
Pekala.
Sonra ne?
O zaman eğer.
Ve görünüyor olsa da, fark birbirine sıkıca sandviç,
Sadece dolduracak şekilde büyüyecektir.
Sadece bunu istiyorum nerede atlayacaktır.
>> Ve ben aranızda ne koymak ve eğer o zaman?
Muhtemelen "eğer kenar dokunmadan."
Ve ihbar, yine, bu çok büyük Bunun için, ancak dolduracak şekilde büyüyecektir.
Ve sonra 15 derece dönüş?
Kaç derece?
Evet, 180 dönecektir etrafında beni tüm yol.
Yani bu hakkı var eğer görelim.
Beni uzaklaştırmak edelim.
>> Bana Scratch yukarı sürükleyin edelim.
Bu yüzden bozuk biraz var Şimdi, ama bu sorun değil.
Nasıl kolayca onu sıfırlayabilirsiniz?
Ben biraz hile gidiyorum.
Yani başka ekliyorum blok, sadece temiz olması için.
Onu 90 derece işaret etmek istiyorum Varsayılan olarak sağa,
bu yüzden sadece ona gidiyorum programlı yapmak.
Ve işte başlıyoruz.
Biz bunu yapmış gibi görünüyor.
Çünkü, biraz garip O baş aşağı yürüyor.
en bir hata olduğunu diyelim.
Bu bir hata.
Bir hata, bir program, a bir hatadır Ben, insan, yapılan mantık hatası.
Neden baş aşağı gidiyor?
MİT berbat yoksa ben mi?
>> Evet, yani, o MİT en değil hata. Onlar bana bir puzzle parçası verdi
Bu derece bir dizi çevirmek diyor.
Ve Victoria'nın önerisiyle, Ben 180 derece dönüyorum,
hangi doğru sezgi.
Ama tam anlamıyla 180 derece çevirerek 180 derece döndükten araçları,
ve bu gerçekten değil Ne istediğimi, görünüşe göre.
en azından o öyle, çünkü Bu iki boyutlu dünya
böylece dönüm gerçekten gidiyor onu baş aşağı çevirmek için.
>> Muhtemelen Ne bloğu kullanmak istiyorum Burada ne olduğunu görmek yerine, esaslı?
Bunu nasıl düzeltebilirim olabilir?
Evet, bu yüzden noktası olabilir ters yönde.
Ve aslında bu bile var yeterli olacak değil,
Biz sadece sert kod can çünkü sağa veya sola işaret etmek.
>> Sence neler yapabileceğini biliyor musunuz?
Biz var gibi görünüyor Burada kolaylık bloğu.
Ben yakınlaştırmak için, bkz bir şey burada ister misiniz?
MİT bir var gibi Yani görünüyor soyutlama burada inşa etti.
Bu blok eş olduğu görülmektedir Diğer bloklar, çoğul hangi?
>> Bu bir blok eşdeğer görünmektedir blokların bütün bu üçlü için
biz burada var.
çıkıyor Yani kolaylaştırabilirsiniz benim Bütün bunlar kurtularak programı
ve sadece burada bu koymak.
Ve şimdi o hala biraz var arabası ve şimdi için iyidir.
Biz olmak bırakacağım.
Ama program bile olduğunu basit ve bu da,
temsilci olurdu programming-- bir gol
ideal olarak kodunuzu yapmaktır Basit, mümkün olduğunca kompakt,
yine de olurken mümkün olduğunca okunabilir.
Sen o kadar özlü yapmak istemiyorum çok zor olduğunu anlamak için.
>> Ama yerini ettik fark bir ile üç blok,
ve bu muhtemelen iyi bir şey.
Ben kavramı abstracted ettik ve sen olmadığını kontrol
Sadece bir blok ile kenarında.
Şimdi aslında bu eğlenceli olabilir.
Bu çok katmıyor entelektüel değer ama oynak değer.
Ben devam edeceğim ve burada bu ses kapmak.
Bu yüzden bana devam edelim, ve bana izin Bir an için programı durdurmak.
Ben aşağıdakileri kaydetmemiz gidiyorum, Benim mikrofona erişim sağlayan.
>> İşte başlıyoruz.
Ah.
Tekrar deneyelim.
İşte başlıyoruz.
Tamam, ben yanlış bir şey kaydedildi.
İşte başlıyoruz.
Ah.
Pekala.
Şimdi bu kurtulmak gerekir.
Pekala.
>> Yani şimdi ben bir Sadece kayıt "ouch."
Şimdi bu yüzden gidiyorum önde ve bu "ah" diyorlar.
Geri dönmek için gidiyorum Benim komut dosyaları için, ve şimdi
ihbar denir bu blok var ses "miyav" çalmak veya ses çalma "ah."
Ben bu sürüklemek için gidiyor ve burada yaşıyorum Ben komik etkisi bu koymalıyız?
Evet, şimdi bu tür var buggy, çünkü artık bu block--
fark bu nasıl "kenarında ise, sıçrama "kendine yeten türüdür.
Yani bu düzeltmek gerekir.
Beni devam edip bu yapalım.
Beni bu kurtulmak edelim ve geri dönmek Bizim orijinal, daha bilinçli
işlevselliği.
"Kenar dokunmadan, daha sonra" Ben istiyorum Victoria önerdiği gibi, çevirmek,
180 derece.
Ve ben oynamak istiyorum yapmak Orada "ah" sesi?
>> Evet, dışarıda olduğunu fark O sarı blok.
Bu yüzden de, olurdu hata, ama ben fark ettik.
Yani burada o kadar sürüklemek için gidiyorum, ve ihbar şimdi içeride "eğer."
"Eğer" Yani bu tür gibi kol gibi lekenin
sadece gidiyor bunun içinde ne yapmak.
Yani şimdi ben uzaklaştırmak eğer annoying-- riski
>> BİLGİSAYAR: Ah, ah, ah.
>> DAVID MALAN: Ve sadece sonsuza kadar devam edecektir.
Şimdi sadece şeyler hızlandırmak için Burada, beni devam edin ve yukarı açalım,
en bana biraz gidelim açarsanız let sınıftan Kendi şeyler.
Ve en, bu diyelim, beni açmak izin biri bizim öğretim arkadaşlarının biri tarafından yapılan
birkaç yıl önce.
Yani biraz sizin hatırlamak olabilir yesteryear bu oyun,
ve aslında dikkat çekici.
Yaptığımız olsa Şu anda programları basit,
en bu ne düşünelim Aslında benziyor.
Bana oyun hit olsun.
>> Yani bu oyunda, bir var kurbağa ve oku kullanarak keys--
o ben Hatırlayamıyorum-- daha büyük adımlar atar Bu kurbağa üzerinde kontrole sahip.
Ve gol meşgul karşısında elde etmektir araçların içine çalıştırmadan yol.
Ve, ben burada gidersem en see-- izin ben bir günlük kaydırma için beklemek zorunda.
Bu bir hata gibi hissediyor.
Bu bir hata türüdür.
Pekala.
Ben burada bu çıkıyorum Orada, ve sonra tutmak
Tüm elde edene kadar gidiyor zambak yastıkları kurbağalar.
Şimdi bu görünebilir daha karmaşık
ama en kırmaya çalışalım Bu aşağı zihinsel
ve sözlü bileşen bloklar halinde.
Yani muhtemelen bir bulmaca var biz henüz görmedik parça
ancak bu tuş yanıt'S, şeyler klavyeden çarptı.
>> Yani muhtemelen bir tür var tuşuna yukarı eşitse, diyor blok,
Daha sonra Scratch-- ile bir şeyler yapmak belki o 10 adım bu şekilde hareket ettirin.
Aşağı tuşuna basılırsa, 10 adım taşımak Bu şekilde, ya da sol tuş, 10 adım hareket
Bu şekilde, 10 adımlar vardır.
Ben açıkça bir kurbağa haline kedi çevirdin.
Yani bu sadece nerede Kazı aramaları biz dökersin-- kostüm olarak
sadece kurbağa resmini ithal.
>> Ama oluyor başka ne?
Ne kod diğer hatları, başka hangi puzzle parçaları
Blake yaptığı, bizim eğitim dost, Görünüşe göre, bu programda kullanmak?
Ne her şeyi yapıyor move-- Ne programlama inşa?
>> Hareket, yani sure-- emin, blok taşıyın.
Ve bu hareket bloğu ne Büyük olasılıkla iç?
Evet, döngü çeşit, belki sonsuza kadar belki tekrar bloke block--
blok kadar tekrarlayın.
Ve bu ne günlükleri yapıyor ve zambak yastıkları ve her şey hareket
geri ve ileri.
Sadece sonsuz oluyor.
>> Neden arabalar bazı diğerlerinden daha hızlı hareket?
Bu programlar hakkında farklı nedir?
Evet, muhtemelen bazıları alıyor aynı anda daha fazla adım ve bazıları
Aynı anda daha az adımlar.
Ve görsel efekt Yavaş karşı hızlı.
>> ne olduğunu düşünüyorsun?
Benim kurbağa var tüm yol cadde ve nehir
zambak ped, bir şey üzerine kayda değer oldu.
Ne kadar kısa sürede bunu yaptığı gibi oldu?
Durdu.
Bu kurbağa durdu ve İkinci kurbağa var.
Peki yapı olmalı orada kullanılan ne özelliği?
>> Evet, bu yüzden bir çeşit var de orada kondisyon "eğer".
Biz bunu tartismadik-- görmedik out-- ve döner ama oradaki diğer bloklar var
Eğer dokunmadan ise, söyleyebiliriz Ekranda başka bir şey,
Eğer "o zaman." zambak pedi, dokunmadan eğer
Ve o zaman biz var İkinci kurbağa görünmesi.
Yani bu oyun kesinlikle olsa bile çok bile ilk bakışta rağmen tarihli
orada çok Explorer gibi ve Blake gidiyor İki dakika içinde bu kadar kırbaç değil,
muhtemelen onu birkaç aldı saat bu oyunu oluşturmak için
Onun bellek veya videolara dayanarak Bunun yesteryear sürümünün.
Fakat bu küçük şeylerin hepsini izolasyon ekranda oluyor
Bu çok basit aşağı kaynatın constructs-- hareketler veya ifadeler
Konuştuğumuz gibi, döngüler ve koşulları ve bu konuda.
birkaç diğer meraklısı özellik var.
Bazıları sadece destek estetik veya akustik,
sesler gibi ben sadece oynadım.
Ama çoğunlukla, sen Bu dil, Scratch var,
temel tüm yapı taşları sen misin
C, Java, JavaScript var, PHP, Ruby, Python,
ve diğer dillerin herhangi bir sayı.
Scratch hakkında herhangi bir sorunuz var mı?
Pekala.
Bu yüzden Scratch için daha derin dalış olmaz, Bu hafta sonu buyrun rağmen,
Eğer özellikle çocuklar varsa veya yeğenlerinin ve,
Scratch onları tanıtmak için.
Aslında bir harika oynak var çevre ile kendi yazarları dediği gibi,
çok yüksek tavanlı.
biz başladık olsa çok düşük seviyeli ayrıntıları,
Eğer gerçekten biraz yapabilirsiniz onunla ve bu belki de
tam olarak bu bir gösteri.
>> Ama şimdi biraz daha geçiş izin Sofistike sorunlar, eğer sen,
"Arama" olarak bilinen ve daha genel ", sıralama".
Biz bu telefon rehberi earlier-- burada vardı sadece discussion-- başka bir
Biz aramak başardık daha verimli bir şekilde nedeniyle
önemli bir varsayımın.
Ve sadece açık olmak ne varsayım ben yapım oldu
Bu telefon defterinde arama yaparken?
Mike Smith olduğunu telefon rehberi, I rağmen
ele almak mümkün olacaktır Onsuz senaryo
Ben sadece erken orada durdu.
Kitap alfabetik olduğunu.
Ve bu çok cömert varsayım, çünkü
Ben tür kulüpler someone-- anlamına gelir bir köşe kesici,
gibi birisi, çünkü hızlı değilim Başka benim için zor bir sürü iş yaptım.
>> Ama ne olursa telefon kitap sıralanmamış edildi?
Belki Verizon tembel var, sadece attı Herkesin adları ve numaraları orada
belki sırayla hangi onlar telefon hizmeti için kaydoldum.
Ve ne kadar zaman bu beni sürer Mike Smith gibi birini bulmak için?
1000 sayfa telefonu kaç book-- sayfalar Ben bakmak gerekiyor?
>> Hepsi.
Sen şans çeşit konum.
Kelimenin tam anlamıyla her bakmak zorunda sayfa telefon rehberi sadece eğer
rasgele sıralı.
Şanslı olsun ve Mike bulabilirsiniz ilk sayfada, çünkü o
ilk müşterisi oldu telefon hizmeti sipariş etmek.
Ama o da, son olabilirdi.
>> Yani rastgele düzen iyi değil.
Bu yüzden sıralamak olduğunu varsayalım telefon rehberi ya da genel sıralama verilerde
biz verildi.
bunu nasıl yapabilirim?
>> Peki, beni sadece deneyeyim Burada basit bir örnek.
Beni devam edin ve bir yazı tura atalım gemide kaç sayılar.
Vardır Elimizdeki rakamları varsayalım en, dört, iki, bir ve üç diyelim.
Ve Ben, bizim için bu numaraları sıralamak.
>> Tamam iyi.
Bunu nasıl yaptın?
Pekala.
Yani en küçük ile başlar değer ve yüksek,
ve bu gerçekten iyi bir sezgi var.
Ve o biz fark insanlar aslında oldukça vardır
sorunları çözme iyi Bu gibi en azından
veri nispeten küçük olduğunda.
En kısa sürede yüzlerce başladığınızda sayılar, sayılar binlerce,
sayıların milyonlarca Ben muhtemelen Oldukça o kadar hızlı could not do it,
olduğunu varsayarak sayılar boşluklar.
Bir milyon saymak oldukça kolay Aksi takdirde, sadece zaman alıcı.
>> Yani algoritma geliyor Ben şimdi sadece eskisi gibi
En küçük sayı için arama oldu.
Yani biz insanlar alabilir olsa bile görsel bilgi bir çok,
Bir bilgisayar aslında Biraz daha sınırlı.
bilgisayar olabilir sadece Bir seferde bir bayt bakmak
Bir olan Zamanın ya da belki dört bayt Bir olan Zamanın bugünlerde belki 8 bayt
ancak çok az sayıda belirli bir anda bayt.
>> Yani biz gerçekten var olduğu göz önüne alındığında dört ayrı değerler burada--
ve sahip olarak Ben düşünebilirsiniz O bir bilgisayar gibi olsaydı üzerinde blinders
O başka bir şey göremiyorum Bir olan Zamanın az bir sayıdan
bu yüzden genellikle olduğu gibi, üstlenecek İngilizce, biz sağdan sola doğru okumak gerekir.
Yani ilk sayı Ben muhtemelen baktım çok hızlı bir şekilde daha sonra dört ve
bu oldukça büyük fark number-- bana bakmaya devam edelim.
>> İki var.
Bir dakika bekle.
İki dört daha küçüktür.
Hatırlıyorum gidiyorum.
İki şimdi küçüğüdür.
Şimdi Şehre bile iyi.
Bu bile küçük.
Ben yaklaşık iki unutmak için gidiyorum ve şimdi bir tane hatırlıyorum.
>> Ve o bakıyor durdurabilir?
Eh, o dayalı olabilir Bu bilgiler ışığında,
ama o daha iyi arama ediyorum Listenin geri kalanı.
listede ne sıfır olursa Çünkü?
Ne bir negatif listede olsaydı?
O sadece onun cevabını biliyor O ayrıntısına eğer doğru
tüm liste kontrol etti.
Bu yüzden bu geri kalanı bakmak.
Bu üç-- zaman kaybı oldu.
şanssız var, ama ben Bunu yapmak için doğru yine.
Ve böylece şimdi o muhtemelen En küçük sayı seçilmiş
ve sadece başında koymak Listenin, ben burada yapacağım olarak.
Şimdi bile, sonra ne yaptın neredeyse bu konuda düşünmüyordu
Bu ölçüde?
işlemi tekrarlayın, döngünün böylece bir çeşit.
tanıdık bir fikri var.
Yani burada dörttür.
Şu anda en küçük var.
Bu bir aday.
Artık değil.
Şimdi iki gördüm.
Bu küçük bir sonraki eleman var.
Böylece, daha küçük değil üç- Şimdi Ben ikisini koparmak.
>> Ve şimdi işlemi yineleyin ve Tabii üç sonraki çıkardı alır.
işlemi tekrarlayın.
Dört çıkardı alır.
Ve şimdi sayılar bitti, böylece liste sıralanması gerekir.
>> Ve gerçekten de, bu resmi bir algoritma.
Bir bilgisayar bilimcisi olur "Seçim tür" diyoruz
Fikir tür bir varlık Yine iteratively-- listesi
ve tekrar seçilmesi küçük sayı.
o hakkında ve güzel ne sadece bu yüzden lanetlemek sezgisel.
Çok basit.
Ve aynı tekrarlayabilirsiniz operasyon tekrar tekrar.
Basit.
>> Bu durumda, hızlı, ancak aslında ne kadar sürer?
en görünüyor yapalım ve Biraz daha sıkıcı hissediyorum.
Bu yüzden, bir, iki, üç, dört, beş, altı, yedi, sekiz, dokuz, 10, 11, 12, 13, 14,
15, 16-- rasgele sayı.
Ben sadece daha bu istedim Sadece dört kereden.
Yani bir bütün var eğer sayıların demet bunu şimdi--
Hatta önemli değil Onlar izin 's mudur nedir
bu ne düşünmek algoritma gerçekten gibidir.
>> Orada sayılar vardır varsayalım.
Yine, önemli değil neyi Onlar, ancak rastgele konum.
Ben Ben'in algoritması uyguluyorum.
Ben küçük numarayı seçmeniz gerekir.
Ben ne yaparım?
Ve ben fiziksel olarak gidiyorum onu dışarı hareket bu sefer yapmak.
Looking görünümlü, seyir, seyir, seyir.
Sadece ben almak zaman Listenin sonuna can
Ben küçük fark iki numaralı bu kez oldu.
Bir listede değil.
Yani iki indirdi.
>> Bundan sonra ne yapacağım?
seyir, seyir, seyir, seyir.
Şimdi, çünkü numara yedi bulundu Bu Numaraları boşluklar var
ama sadece keyfi.
Pekala.
Yani şimdi ben yedi aşağı koyabilirsiniz.
Looking bakarak bakarak.
>> Şimdi, varsayarak yaşıyorum Tabii ki, Ben böyle şeyler yapmaz
Ekstra RAM, ekstra belleği için, tabii ki,
Ben aynı sayıda bakıyorum.
Elbette hatırladım olabilir Bu sayıların hepsi
ve kesinlikle doğrudur.
Ama Ben bütün hatırlar eğer sayıların o gördü,
o gerçekten vermiş değil temel ilerleme
o zaten, çünkü arama yeteneği
gemide numaralar arasında.
her anımsama sayılar, yardımcı olmuyor
o bir bilgisayar olarak yine de, çünkü Sadece, biz söyledim, bir numara bakmak
zamanında.
Yani hile yok çeşit var Orada kaldıraç olabilir.
>> gerçekte, böylece ben Listeyi aramaya devam,
Gerçekten sadece devam etmek zorunda , Ileri ve geri içinden dışarı koparma
Bir sonraki en küçük sayı.
Ve ne tür çıkarabiliriz benim aptal hareketleri,
Bu sadece çok olur çok hızlı bir şekilde can sıkıcı,
ve ben geri gidiyor gibi görünüyor ve ileri, geri ve ileri biraz.
Şimdi dürüst olmak gerekirse, ben gitmek zorunda değilsiniz oldukça iyi, en adil olmak see-- izin
Oldukça yürümek zorunda değilsiniz gibi birçok adımlar her zaman.
Çünkü tabii ki, ben de listeden numara seçin
Kalan liste daha kısa oluyor.
>> Ve bu yüzden hakkında düşünelim kaç adım aslında değilim
Her bir zaman içinde Traipsing.
İlk durumda Biz 16 numara vardı
ve böylece şimdi sadece maximally-- Bir discussion-- için bunu
Ben 16'ya kadar bakmak zorunda kaldı sayılar küçük bulmak için.
Ama bir kez dışarı koparıp küçük sayı, nasıl
Uzun tabii kalan listesini oldu?
Sadece 15.
Peki kaç sayı Ben ya da ben var mı etrafında ikinci kez bakmak için?
15, sadece gidip küçük bulmak için.
Ama şimdi, tabii, liste, bir çok daha önce olduğundan daha küçüktür.
Peki kaç adım yaptım ben dahaki sefere almak zorunda?
14 ve daha sonra 13 ve sonra 12 artı nokta, Ben sadece biriyle kaldım kadar nokta, nokta.
Yani şimdi bir bilgisayar bilimcisi olur herkesin eşit olduğunu ne, iyi, sorabilir miyim?
Aslında bazı somut eşittir numara biz kesinlikle olabilir
aritmetik, ama biz konuşmak istiyoruz algoritmaların verimliliği hakkında
daha formulaically biraz liste ne kadar uzun bağımsızdır.
>> Ve böylece biliyor musun?
Bu 16 gibi, ama daha önce söylediğim, Sadece sorunun boyutunu diyelim
n Bazı sayı n.
Belki öyle, belki değil, 16 yaşında Üç, belki de bir milyon dolar.
Bilmiyorum.
Umurumda değil.
Ne istiyorum gerçekten bir Bir formül I can
Bu algoritma karşılaştırmak için kullanın diğer algoritmalar karşı
Birisi iddia olabilir iyi ya da kötü.
>> Bu yüzden çıkıyor ve sadece ben İlkokuldan bu biliyorum,
Bu aslında aynı dışarı çalışır n üzerinde n olarak bir şey artı iki yere.
Ve bu, bir eşit olur Tabii ki, artı n üzerinde iki kare n.
Yani ben bir formül istedi kaç adımlar için
tüm bakarak dahil edildi Tekrar ve tekrar bu numaraları
ve tekrar ve tekrar, ben söyleyebilirim o n-plus n üzerinde iki kare var.
Ama ne biliyor musunuz?
Bu sadece pis görünüyor.
Ben sadece gerçekten istemek şeylerin genel anlamda.
Ve sizden çağırmak olabilir lise orada
En yüksek mertebeden dönem kavramıdır.
Bu terimlerin hangisi n , N, ya da yarısını kare,
Zamanla çoğu etkisi var?
Daha büyük n, aldığı En bu konularda?
>> Diğer bir deyişle, ben takarsanız milyonda n kare
büyük olasılıkla olacak hakim faktörü,
Çünkü bir milyon kez kendisi çok daha büyük
daha artı bir milyon ilave.
Yani biliyor musun?
Bu tür bir yama büyük numara bir numara kare ise.
Bu gerçekten önemli değil.
Biz sadece haç gidiyoruz dışarı ve unutun.
Ve böylece bir bilgisayar bilimcisi söyleyebilirim bu algoritma verimliliği
n mertebesindedir squared-- Gerçekten bir yaklaşım anlamına gelir.
Bu tür kabaca n kare.
Zaman içinde, daha büyük bir ve daha büyük n bu, alır
ne için iyi bir tahmin olduğunu verim ve verimlilik eksikliği
Bu algoritma aslında.
Ve ben türetmek, elbette, Aslında matematik yapmaktan.
Ama şimdi ben sadece sallayarak ediyorum ellerim, çünkü ben sadece
Bu algoritmanın genel anlamda istiyorum.
>> Dolayısıyla aynı mantığı kullanarak, bu arada, Başka bir algoritma düşünelim
biz zaten at-- doğrusal arama baktı.
Ne zaman arıyordum Telefon book-- için
arama, onu sıralama değil Telefon book-- yoluyla
biz olduğunu söylüyordu 1.000 adım, ya da 500 adım.
Ama bu genelleme edelim.
n sayfalar varsa telefon rehberi, ne
çalışma süresi veya Doğrusal arama verimliliği?
Bu sırasına var kaç adım bulmak için
Mike Smith, doğrusal arama kullanarak İlk algoritma, hatta ikinci?
>> En kötü durumda, Mike Kitabın sonunda.
Telefon rehberi 1000 sayfa vardır Yani eğer, Biz en kötü durumda, son kez dedi
kabaca nasıl alabilir birçok sayfa Mike bulmak için?
1000 gibi.
Bu bir üst sınır var.
Bu olabilecek en kötü durum.
Fakat yine de, biz uzakta hareket ediyoruz Şimdi 1.000 gibi numaralardan.
Sadece n var.
>> Yani mantıklı sonucu nedir?
bir telefonda Mike bulma n sayfası vardır kitap
çok kötü durumda, sürebilir, kaç n emriyle adımlar?
Gerçekten de, bir bilgisayar bilim adamı söyleyebilirim
çalışma süresi, ya da performans veya verimlilik
bir algoritma benzeri veya verimsizlik, doğrusal bir arama n emriyle üzerindedir.
Ve biz aynı uygulayabilirsiniz birşeyler kapısı mantığı
Ben sadece ikinci olduğu gibi Algoritma biz telefon rehberi vardı
nerede bir defada iki sayfa gitti.
>> Yani 1000 sayfa telefon rehberi olabilir 500 sayfa dönüşler bizi, artı bir
biz biraz geri çift eğer.
Yani bir telefon rehberi n sayfalar varsa, ancak Biz bir defada iki sayfa yapıyoruz
Bu kabaca ne var?
üzerinde iki N, böylece ikisi üzerinde n gibi.
Ama iddia a yapılan iki-- üzerinde an önce o n
bu sadece n aynı tür.
Bu, sadece bir sabit faktör var bilgisayar mühendisleri söyleyebilirim.
tek odaklanmak izin değişkenler, gerçekten--
denklemde büyük değişkenler.
>> birini yapılan Böylece ister doğrusal arama, Bir seferde bir sayfa veya bir defada iki sayfa,
tür temelde aynıdır.
Bu n sırasına hala.
Ama önce benim resim ile iddia Üçüncü algoritma olmadığını
doğrusal.
Bu düz bir çizgi değildi.
O eğri çizgi vardı ve cebirsel formülü ne vardı?
n- Log yani n tabanını iki oturum açın.
Ve biz de gitmek zorunda değilsiniz logaritma çok detay bugün
ama çoğu bilgisayar bilimciler olmaz Hatta baz ne olduğunu söyleyeyim.
o Çünkü hepsi sadece sürekli faktörler, tabiri caizse,
Sadece hafif sayısal farklılıklar.
Ve böylece bu çok yaygın olurdu özellikle resmi bilgisayar için yolu
bir tahta bilim adamları ya da bir beyaz tahta at programcılar
Aslında savunarak hangi onlar kullanmak istiyorsunuz algoritması
ya da ne verimlilik kendi algoritmasıdır.
>> Ve bu mutlaka bir şey değildir Eğer, herhangi bir ayrıntılı olarak ele
ama iyi bir programcı birisi kim sağlam, resmi bir geçmişe sahiptir.
O konuşmak mümkün değil Bu arada bu tür size
ve aslında yapmak nitel argümanlar
için neden bir algoritma veya Yazılımın tek parça
başka bir şekilde daha üstündür.
kesinlikle olabilir çünkü Sadece bir kişinin programı çalıştırmak
ve saniye sayısını bazı numaraları sıralamak alır
ve bazı çalıştırabilirsiniz Diğer kişinin programı
ve sayısını saniye onu alır.
Ancak bu daha genel bir yol olduğunu Eğer algoritmaları analiz etmek için kullanabileceğiniz,
Sadece üzerinde, eğer sen Kağıt ya da sadece sözlü.
Olmadan bile olmadan çalışan Hatta, örnek girişleri çalışıyor
Sadece bu kadar ikna edebilirim.
Ve böylece bir geliştirici veya eğer işe ile ona sahip ya da onu tür size iddia
neden kendi algoritması, onların gizli milyarlarca arama için sos
için web sayfalarının senin Şirket, bu, daha iyidir
argümanların türlü onlar ideal yapmak gerekir.
Ya da en azından bunlar şeyler çeşitleri
Şuna, tartışma geleceğini Bir çok resmi tartışma en azından.
Pekala.
Yani ben bir şey önerdi Seçim sıralama denir.
Ama orada olduğunu önermek için gidiyorum de bunu yapmanın başka yolları.
Gerçekten ne gibi değildi Ben'in algoritması hakkında
O yürümeye devam etti, ya da olduğunu beni ileri geri yürümek zorunda
ve ileri geri ve ileri geri.
yerine ben yapmak nelerdi Burada bu sayılar gibi bir şey
ve ben sadece her başa vardı numara da onu verilen kulüpler gibi?
>> Diğer bir deyişle, burada numaraların listemi.
Dört, bir, üç, iki.
Ve ben aşağıdakileri yapmak için gidiyorum.
Rakamları eklemek için gidiyorum onlar yerine nereye ait
Bir teker teker seçerek daha.
Diğer bir deyişle, burada dördüncü var.
>> İşte benim asıl liste.
Ve ben korumak için gidiyorum Burada esasen yeni bir liste.
Yani bu eski listesidir.
Bu yeni listesidir.
Ben dört numara ilk bkz.
Benim yeni liste, başlangıçta boştur bu nedenle trivially olduğu
Bu dört şimdi liste tasnif edilebilir.
Ben sadece, bana verilen numarayı alıyorum ve benim yeni listede koyuyorum.
>> Bu yeni liste sıralanır?
Evet.
Sadece bir tane var çünkü aptal eleman, ama kesinlikle olarak sıralanmış.
yersiz bir şey yok.
Daha ilginç, bu algoritma, Bir sonraki adıma geçmek zaman.
>> Şimdi bir tane var.
Bu yüzden, bir, tabii ki, önceki ait başlayan veya bu yeni listenin sonu?
Başlangıç.
Bu yüzden şimdi bazı işler yapmak zorunda.
Bazı alarak oldum Benim işaretleyici ile özgürlükler
sadece şeyler çizerek Onları istediğiniz yere,
ama bu gerçekten değil Bir bilgisayardaki doğru.
Bildiğimiz gibi bir bilgisayar, sahip RAM veya Random Access Memory,
ve bu bir bayt olduğunu ve Başka bir bit ve bir bayt.
Ve bir gigabayt varsa RAM, bir milyar bayta var,
ama bir yerde fiziksel konum.
Sadece etrafında şeyler hareket edemez gemide çizerek
nereye istersen.
Yeni liste varsa Yani bellekte dört konum,
Ne yazık ki dörttür Zaten yanlış yerde.
>> Yani numara eklemek için bir Ben sadece burada çekemez.
Bu bellek konumu yok.
Bu hile olur, ve ben olmuştur bir kaç dakika için resimsel hile
İşte.
Yani gerçekten, ben burada bir tane koymak istiyorsanız, Ben geçici olarak dört kopyalamak zorunda
ve daha sonra oraya bir tane koyun.
>> Yani, bu doğru, gayet Bu, teknik olarak mümkün değil
ama bu ekstra bir iş gerçekleştirmek.
Ben sadece bir yerde numarayı koymadı.
Önce bir hareket vardı sayı, sonra bir yere koyun
bu yüzden tür iş benim miktarını iki katına çıktı.
Yani akılda tutmak.
>> Ama şimdi bu eleman ile işim bitti.
Şimdi üç numarayı kapmak istiyorum.
Nerede, tabii ki aittir?
Arasında.
Artık hile olamaz ve sadece orada koymak
Yine, bu belleğin çünkü fiziksel konumlarda olduğunu.
Yani dört kopyalamak zorunda ve buraya üç koyun.
Önemli bir şey değil.
Sadece bir ilave adım vasıtasıyla yine çok ucuz hisseder.
>> Ama şimdi iki hareket.
İki, tabii ki, buraya ait.
Şimdi nasıl görmeye başlarsınız iş birikmesine neden olabilirler.
Şimdi ne yapmam gerekiyor?
Evet, dört taşımak zorunda, Sonra, üç kopyalamak zorunda
ve şimdi iki ekleyebilirsiniz.
Ve bu ile yakalamak algoritması, ilginç bir şekilde,
biz bir daha aşırı var varsayalım s sekiz, yedi diyelim var durum,
altı, beş, dört, üç, iki, bir.
Bu, birçok bağlamda, bir, En kötü durum senaryosu,
lanetlemek şey çünkü kelimenin tam anlamıyla geriye olduğunu.
>> Gerçekten değil Ben'in algoritması etkiler
Çünkü Ben'in seçiminde sıralama o tutacak
ileri ve geri listede geçiyor.
Ve hep arıyordum çünkü Bütün kalan Listede,
önemli değil elemanları burada.
Ama yerleştirilmesi, bu durumda approach-- şunu deneyelim.
>> Bu yüzden, bir, iki, üç, dört, beş, altı, yedi, sekiz.
Bir iki üç dört, beş, altı, yedi, sekiz.
Ben, sekiz almaya gidiyorum ve nerede koymak mı?
Eh, benim listesinin başında, Bu yeni liste sıralanır çünkü.
Ve ben bunu çapraz.
>> Nerede yedi koyuyorsun?
Kahretsin.
Bu, oraya gitmek gerekiyor bu yüzden Bazı kopyalama yapmak zorunda.
Ve şimdi yedi buraya.
Şimdi altı geçmek.
Şimdi bile daha fazla iş var.
>> Sekiz buraya gitmek zorunda.
Yedi buraya gitmek zorunda.
Şimdi altı buradan gidebilirsiniz.
Şimdi beş yakala.
Şimdi sekiz gitmek zorunda Burada, yedi buraya gitmek zorunda,
Altı buraya gitmek zorunda, ve şimdi beş ve tekrarlayın.
Ve hemen hemen değilim Sürekli taşımak.
>> Yani sonunda, bu algorithm-- yaparız Ekleme aslında sort-- diyoruz
çok bir sürü iş vardır.
Sadece farklı Ben'in daha işin çeşit.
Ben'in işi bana gidiş vardı ileri geri her zaman,
En küçük bir sonraki seçme eleman tekrar tekrar.
Bu yüzden işin bu çok görsel nazikti.
>> hala Bu, diğer algoritma correct-- bu işi alacak done--
sadece iş miktarını değiştirir.
Başlangıçta sen gibi görünüyor Sadece çünkü, tasarruf
her elemanın ile ilgili ön tüm yürüme olmadan
Ben gibi Listede yoluydu.
Ama sorun, özellikle bu içinde olduğu hepsi geriye bu deli durumlarda,
Eğer tür sadece konum zor iş ertelenmesi
Eğer hataları düzeltmek zorunda kadar.
>> Ve bu yüzden eğer bu hayal edebiliyorum sekiz ve yedi ve altı ve beş
ve daha sonra dört, üç, iki Listede kendi yolunu hareketli,
biz sadece değiştirdik işin türü biz yapıyoruz.
Yerine de bunu yapmanın Benim yinelemenin başlayan
Ben sadece bunu yapıyorum her yineleme sonu.
Bu yüzden, bu algoritma çıkıyor Çok genel olarak adlandırılan ekleme sıralama,
kare n sırasına da.
Bu, daha iyi aslında daha iyi vasıl tüm.
>> Ancak, üçüncü bir yaklaşım var Ben, düşünmeye bizi teşvik edecek
hangi budur.
Yani basitlik için, listemi varsayalım Yine, dört, bir, üç,
sadece dört sayı iki--.
Ben, iyi bir sezgi vardı iyi insan sezgi
önce, hangi biz bütün sabit eventually-- ekleme sıralama listesi.
Bizi birlikte sürülmesi.
Ama düşünelim Bu listeyi düzeltmek için basit yolu.
>> Bu liste sıralanır.
Niye ya?
İngilizce, niçin aslında sıralanmış değil.
sıralanmasını değil ne anlama geliyor?
>> ÖĞRENCİ: Bu sıralı değil.
>> DAVID MALAN: sıralı değil.
Bana bir örnek ver.
>> ÖĞRENCİ: sırayla koyun.
>> DAVID MALAN: Tamam.
Bana bir daha spesifik bir örnek verin.
>> ÖĞRENCİ: sipariş Artan.
DAVID MALAN: küçükten büyüğe değil.
daha hassas olması.
Ne yükselerek ne demek bilmiyorum.
Sorun nedir?
>> ÖĞRENCİ: küçük numaraları birinci boşluk değildir.
>> DAVID MALAN: Küçük sayı en ilk değil uzayda.
Daha spesifik ol.
Ben yakalamak için başlıyorum.
Biz sayma, ama konum Burada sıra dışı ne var?
>> ÖĞRENCİ: Sayısal dizisi.
DAVID MALAN: Sayısal dizisi.
tutma Herkesin tür Çok yüksek düzeyde Doğuların.
Sadece tam anlamıyla ne olduğunu söyle beş yaşındaki kudretinin gibi yanlış.
>> ÖĞRENCİ: Artı bir.
>> DAVID MALAN: Bu nedir?
>> ÖĞRENCİ: Artı bir.
>> DAVID MALAN: Ne artı bir demek istiyorsun?
bana farklı bir beş yaşındaki verin.
Yanlış, anne nedir?
Yanlış, baba nedir?
Eğer bu sıralama değil de ne demek?
>> ÖĞRENCİ: Doğru yer değil.
>> DAVID MALAN: neler var değil doğru yerde?
>> ÖĞRENCİ: Dört.
DAVID MALAN: Tamam, güzel.
olması gereken yerde Yani dört değil.
Özellikle, bu doğru mu?
Dört ve bir birinci Gördüğüm iki sayı.
Bu doğru mu?
Hayır, onlar sıra dışı, değil mi?
Aslında, şimdi düşünüyorum de bir bilgisayar hakkında.
Sadece, belki biri bakabilirsiniz once-- belki iki şey
ve aslında tek bir şey Bir seferde, ama can en azından
bir şeye daha sonra bakmak hemen yanındaki sonraki şey.
>> Peki bu sırayla mı?
Tabii ki değil.
Yani biliyor musun?
Neden bebeği yapmayız Bu sorunu giderme adımları
Bunun yerine, bu fantezi yapıyor Ben gibi algoritmalar
O tür bunu tamir ediyor Listede döngü
Bunun yerine, nerede ne yaptığını yapıyor Biz gitmek gibi sadece tür sabit?
Sadece tam anlamıyla yıkmak edelim order-- numara sırasına kavramı,
Eğer zaman-- ne diyoruz Bu ikili karşılaştırmalar içine.
>> Dört ve bir.
Bu doğru sıralama var mı?
Yani bunu düzeltmek edelim.
Bir ile dört, ve daha sonra biz sadece kopya edeceğiz.
Pekala, iyi.
Bir ve dört sabit.
Üç ve iki?
Yok hayır.
benim sözlerim benim parmak maç olsun.
Dört ve üç?
>> Bu sırayla değil, bu yüzden ben gidiyorum birini üç, dört, iki yapmak.
Tamam iyi.
Şimdi dört ve iki?
Biz de bunu düzeltmek gerekir.
Yani bir, üç, iki, dört.
Yani sıralanır?
Hayır, ama bu sıralama daha yakın?
>> Bu sabit, çünkü bir hata, biz, bu hatayı sabit
ve biz bu hatayı düzelttim.
Bu yüzden belki üç hata düzeltildi.
Hala gerçekten sıralı bakmak değil, o sıralı nesnel yakın
Biz bu hataları bazı sabit çünkü.
>> Şimdi ne yapacağım?
Ben tür listesinin sonuna ulaştı.
Ben sabit gibiydi Tüm hatalar, ama hayır.
Bu durumda, bazı numaralar için yakın yukarı kabarmış olabilir
diğer numaralara bozuk hala.
O yüzden tekrar yapalım ve ben olacak sadece bir yerde bu sefer bunu.
Bir ve üç?
Bu iyi.
Üç ve iki?
Tabii ki hayır, o yüzden bunu değiştirmek edelim.
Yani iki, üç.
Üç ve dört?
Ve şimdi sadece olalım Burada özellikle bilgiçlik.
o sıralanır?
Siz insanlar bunun sıralanmış biliyorum.
>> Tekrar denemek gerekir.
Yani Olivia tekrar deneyin öneriyor.
Niye ya?
Bir bilgisayar olmadığından insan gözlerinin lüks
sadece back-- Tamam bakarak, ben bittim.
Nasıl bilgisayar belirliyor Listede sıralanır?
Mekanik.
>> Ben geçmesi gerekir Bir kez daha, sadece eğer
Ben herhangi bir hata bulmak / olabilir yapmayın Daha sonra yep, bilgisayar gibi sonuçlandırmak,
biz gitmek için iyi bir konum.
Yani bir ve iki, iki ve üç, üç ve dört.
Şimdi kesinlikle bu olduğunu söyleyebiliriz Ben hiçbir değişiklik yaptı, çünkü sıralanır.
Şimdi bir hata olması ve sadece olurdu aptalca eğer ben, bilgisayar,
Yine bu aynı sorular farklı cevaplar bekliyor.
olmamalı.
>> Ve şimdi liste sıralanır.
Ne yazık ki, çalışma süresi Bu algoritma da kare: n.
Niye ya?
Eğer n numaraları ve var çünkü En kötü durumda size n numaralarını taşımak zorunda
n kere gidiyorsun tutmak zorunda çünkü tekrar kontrol etmek ve potansiyel düzeltmek
Bu rakamlar.
Ve biz daha fazlasını yapabiliriz Çok resmi analiz.
>> Yani bu attık demek hepsi bu Üç farklı uygulamalar, tek
Bunlardan hemen kolay Ben gelen yarasa kapalı
Benim önerilen yerleştirilmeden Bu bir tür
ne tür gözden kaybetmek nerede Başlangıçta ağaçlar için orman.
Ama sonra, bir adım geri almak durumunda işte, biz sıralama kavramı çözdüm.
Yani bu, söylemek cesaret olduğunu daha düşük bir seviyede belki
Bu diğer bazıları daha algoritmalar, ama hadi
Biz görselleştirmek olamaz görmek Bu arada, bu.
>> Yani bu biraz güzel Yazılım birisi
bu renkli çubuklar kullanarak yazdı Bizim için aşağıdakileri yapacak.
Bu çubukların her biri bir sayısını gösterir.
Daha büyük, bar uzun boylu sayı, küçük bar,
sayı daha küçük.
Yani ideal güzel bir piramit istiyorum küçük başlar ve büyük alır nerede,
ve bu anlamına gelecektir Bu çubuklar sıralanır.
Bu yüzden, go ahead ve seçmek için gidiyorum Örneğin, Ben algoritması
birinci-- seçim sıralama.
>> Ve ne yaptığını fark.
onlar seçtiniz yolu Bu algoritma görselleştirmek
Benim gibi, yani listemde yürürken,
bu program yürüyor numaraları listesine sayesinde,
pembe her vurgulayarak o bakıyor numara.
Ve hemen gerçekleşmesi gereken ne hakkında?
>> küçük sayı o Ben ya da ben aniden bulundu
Listenin başında taşındı alır.
Ve onlar tahliye yaptılar Bildirimi orada numarası
ve o mükemmel para cezası.
Ben ayrıntı bu düzeyde alamadım.
Ama biz koymak gerekir bir yerde bu sayı,
böylece biz sadece onu taşındı oluşturulan açık nokta.
Yani bu hızlandırmak için gidiyorum yukarı, aksi takdirde bunun nedeni
kısa sürede çok sıkıcı olur.
Animasyon oraya hız-- gidiyoruz.
Şimdi aynı prensip Ben uygulayarak, ama sen
eğer, algoritma hissetmeye başlayabilirsiniz olacak, ya da biraz daha net görüyorum.
Bu algoritma etkisine sahiptir Bir sonraki en küçük elemanı seçerek,
böylece başlamak için gidiyoruz soldaki yukarı rampa bkz.
Ve her tekrarında, ben Önerilen, biraz daha az iş yapar.
Bu tüm yol gitmek zorunda değildir geri listenin sol ucuna,
zaten çünkü sıralanır olanlar bilir.
öyle gibi Dolayısıyla bu tür hissediyor Her bir adım olmasına rağmen, hızlandırıcı
zaman aynı miktarda alarak.
Geri kalan sadece az adımlar var.
Ve şimdi biraz hissedebilirsiniz algoritması, bunun sonu temizlik
ve gerçekten de şimdi sıralanmış oluyor.
>> Yani ekleme sıralama tüm yapılır.
Ben dizi yeniden randomize gerekir.
Ve fark ben sadece can Bunu rastgele tutmak,
ve biz bir yaklaşım alırsınız Aynı yaklaşım, ekleme sıralama.
Beni burada onu yavaşlatmak edelim.
en bu baştan başlayalım.
Dur.
>> en dört geçelim.
Oraya gidiyoruz.
Münafık dizi Rastgele.
Ve burada ekleme tür go--.
Oyun.
her ile uğraşan var dikkat edin o hemen karşılaştığında eleman,
ama içinde aitse yanlış yer bildirimi
ne var işin tüm.
Biz daha değişen tutmak zorunda ve daha fazla öğe yer açmak için
biri için biz yerine koymak istiyorum.
>> Bu yüzden odaklanıyoruz listenin sadece sol ucunu.
biz bile biz at-- bakmadım Fark Pembe bir şey vurgulanan değil
sağa.
Biz sadece ile uğraşıyoruz sorunları biz, gitmek gibi
ama biz bir sürü oluştururken hala kendimiz için çalışmak.
Ve biz bu hızlandırmak eğer öyleyse Şimdi tamamlanması gitmek için,
gerçekten buna farklı bir havası vardır.
Sadece sol ucunda odaklanarak var ama needed-- olarak biraz daha iş yapıyor
yumuşatma şeyler tür üzerinde, şeyleri tamir,
fakat sonuçta uğraşan Bir anda her eleman bir
biz de Şeyin için elde edene kadar, biz Bütün bu sona erecek biliyorum,
yüzden biraz underwhelming belki var.
>> Ama end-- liste spoiler-- sıralanabilir gidiyor.
Yani bir sonuncusu bakalım.
Biz sadece şimdi atlamayı olamaz.
Neredeyse geldik.
İki kimse gitmek, gitmek için.
Ve işte.
Mükemmel.
>> Yani şimdi en son birini yapalım, yeniden randomizing kabarcık sıralama ile.
Ve bunu yavaş, özellikle burada fark aşağı, bu sayede swooping devam etmez.
Ama sadece pairwise yapar fark yerel çözümler comparisons-- tür.
Ama en kısa sürede biz olsun Pembe listenin sonuna,
Ne tekrar yaşanmaması zorunda olacak?
Evet, öyle olmak zorunda olacak , Baştan başlamak çünkü o sadece
sabit ikili hatalar.
Ve bu henüz diğerleri tarafından ortaya çıkarılmış olabilir.
Bu hızlandırmak Ve eğer öyleyse, sen olacak , Adından da anlaşılacağı kadar, görüyoruz
, Öğelerin-- küçük ya da daha doğrusu Büyük öğelerin-- başlıyor
kabarcık tepesine kadar, eğer sen.
Ve küçük elemanları aşağı sola kabarcık başlıyor.
Ve gerçekten de, bu tür var yanı sıra görsel efekt.
Ve böylece bu terbiye sona erecek çok çok benzer bir şekilde, içinde.
>> Biz yaşamak zorunda değilsiniz Bu özel biri.
ben de, şimdi bu açalım.
birkaç diğer sıralama algoritmaları var Dünyada birkaç olan
Burada yakalanır.
Ve özellikle öğrenciler için kim değil mutlaka görsel veya matematiksel,
Daha önce yaptığımız gibi, biz Ayrıca İşitme bunu
Bu bir ses ilişkilendirmek ise.
Ve sadece eğlence için, burada bir Birkaç farklı algoritmalar,
sen Özellikle bunlardan biri ve denir fark edecek "birleştirme sıralama."
>> Aslında bir temelde Daha iyi algoritma,
Bir çeşit birleştirme böyle görmek üzereyiz olanlar,
kare n sırası değil.
Bu n kere giriş sırasına var aslında daha küçük ve bu nedenle N,
bu diğer üçü daha hızlı.
Ve diğer bir çift var göreceğiz aptal olanlar.
>> Yani burada bazı ses ile gitmek.
Bu yüzden tekrar ekleme tür Sadece elemanları ile uğraşıyor
Geldikleri gibi.
Bu kabarcık sıralama, bu yüzden var Onlara bir seferde çiftleri dikkate.
Ve yine, büyük elemanlar tepesine kadar köpüren olan.
>> yukarı sonraki seçim sıralama.
Bu Ben'in algoritmasıdır yine o yinelemeli seçerek ediyor
Bir sonraki en küçük öğesi.
Ve yine, şimdi gerçekten duyabiliyorum o ancak şimdiye kadar hızlandırmak oluyor
daha az ve daha az yapıyor olarak her tekrarında çalışır.
Bu daha hızlı biridir, birleştirmeli sıralama, sayı kümeleri sıralama olduğu
Birlikte ve sonra bunları birleştirerek.
Yani sol Bak-- Yarım zaten sıralanır.
>> Şimdi sağ yarısını sıralama ve var şimdi onları birleştiren tek gidiyor.
Bu denilen şey "Gnome sort."
Ve ne tür olduğunu görebilirsiniz o, ileri ve geri gidiyor
biraz burada işi sabitleme ve yeni iş orada devam önce.
Ve bu kadar.
başka bir tür var, gerçekten sadece akademik amaçlı,
alır "aptal sıralama," denir veri, rastgele sıralar
o sıralanır ve eğer sonra denetler.
eğer değilse ve bu yeniden sıralar onu o sıralanmış eğer rastgele denetler,
ve tekrar değilse.
Ve teorik olarak, olasılıksal Bu, tamamlayacak
ancak zaman biraz sonra.
Çoğu değil algoritmaların etkili.
olanlara Böylece herhangi bir soru Belirli algoritmalar ya da bir şey
de orada ilgili?
>> Peki, şimdi ne dışında tüm kızdırmak izin Bu satırlar Ben çizim oldum vardır
ve ne bilgisayar varsayarak yaşıyorum başlık altında yapabilirsiniz.
Ben bu sayıların hepsi iddia ediyorum Ben onlar almak gerekiyor drawing-- tutmak
belleğinde bir yerde saklanır.
Biz de şimdi bu adam kurtulmak gerekir.
>> Bir bellek Yani bir parça RAM kadar DIMM computer--
Dün, çift aradıklarınızı Bu gibi görünüyor module-- sıralı bellek.
Ve bu küçük siyah cips her Tipik haliyle, bayt bir sayıdır.
Ve sonra altın iğneler gibi bilgisayara bağlayın teller,
ve yeşil silisyum kurulu sadece bir tüm ne her şeyi birlikte tutar.
Peki bu gerçekten ne anlama geliyor?
Ben biraz bu aynı resim çizmek için, en basitlik için varsayalım
Bu DIMM, çift olduğunu sıralı bellek modülü,
RAM bir gigabayt, bir gigabayt kaç bayt toplam hafıza,?
Bir gigabayt kaç bayt?
Daha Fazlası.
1124, kilo 1.000 olduğunu.
Mega milyon.
Giga bir milyar dolar.
>> Yalan muyum?
biz bile etiket okuyabilir miyim?
Bu aslında 128 gigabayt, yani daha var.
Ama biz bu taklit edeceğiz Sadece bir gigabayt olduğunu.
anlamına Yani bir milyar var Bana kullanılabilir bellek bayt
ya da 8 milyar bit, ama biz gidiyoruz Şimdi bayt açısından konuşmak,
ileriye doğru hareket.
>> Peki anlamına gelir bu olduğunu bir byte, bu başka bir bayt,
bu başka bir bayt, ve biz gerçekten isteseydi
biz olurdu belirli olması Bir milyar küçük kareler çizin.
Ama bu ne anlama geliyor?
Peki, beni sadece Büyütmek izin Bu resimde de.
Ben bir şey var ise o görünüyor Bu şimdi olduğu gibi, o dört bayt var.
>> Ve bu yüzden burada dört numara koymak olabilir.
Bir iki üç dört.
Ya da ben dört harf veya sembolleri koymak olabilir.
"Hey!" Orada gidebiliriz, harflerin her biri için,
Biz, daha önce tartışılan temsil edilebilir
Sekiz bit ya da ASCII veya bir byte ile.
Yani diğer bir deyişle, yapabilirsiniz içeride 8 milyar şeyler koymak
bellek bu bir sopa.
Şimdi geri şeyler koymak için ne anlama geliyor Böyle bellekte geri geri?
Bu ne bir programcı Bir "dizi." çağırır
Bir bilgisayar programında, sanmıyorum altta yatan donanım hakkında, haddi zatında.
sahip olarak sadece kendiniz düşünmek Bir milyar bayt toplam erişim,
ve hiçbir şey onunla istediğiniz olabilir.
Ama kolaylık sağlamak için genellikle kullanışlı
Bellek saklı tutar için Böyle yanyana.
Yani bu-- yakınlaştırmak ise biz kesinlikle gitmiyoruz çünkü
Bir milyar küçük squares-- çizmek için Şimdi bu kurul temsil varsayalım
Şimdi bellek sopa.
Ve ben gibi birçok şekilde çekersiniz benim işaretleyici beni buraya vererek biter.
Yani şimdi bir sopa var gemide bellek
Bu var bir, iki, üç, dört, beş, altı, bir, iki, üç, dört, beş, altı,
bu yüzden 42 bayt yedi-- Ekran toplam bellek.
Teşekkür ederim.
Evet, benim aritmetik doğru yaptım.
Burada bellek Yani 42 bayt.
Yani bu aslında ne anlama geliyor?
Eh, bir bilgisayar programcısı olur aslında genel olarak
adreslenebilir olarak bu bellek düşünüyorum.
Diğer bir deyişle, bu, her bir bellekteki yerleri, donanım,
benzersiz bir adresi vardır.
>> Bu Bir Brattle kadar karmaşık değil Kare, Cambridge, Mass., 02138.
Bunun yerine, o sadece bir sayı var.
Bu bayt sayısı sıfır, bu ise Bir, İki ve bu da üçtür
ve 41 olduğu.
Bir dakika bekle.
Ben bir an önce 42 söylemiştin.
Ben, sıfırdan saymaya başladı böylece aslında doğru.
Şimdi biz aslında çizmek gerek yok bir ızgara olarak ve bir ızgara olarak çizerseniz
Ben şeyler aslında düşünüyorum biraz yanıltıcı olsun.
Ne bir programcı olur, kendi zihninde,
genellikle bu düşünüyorum Bellek sadece bir kaset gibi olduğu,
maskeleme bandı bir parçası gibi sadece ve üzerinde sonsuza kadar gider
ya da bellek bitene kadar.
Yani bir daha yaygın yolu çizmek için ve sadece bellekte düşünmek
Bu bayt sıfır, biri olacağını, iki, üç ve daha sonra, nokta nokta nokta.
Ve hatta, 42 tür bayt toplam sahip fiziksel aslında ama belki
Bunun gibi daha bir şey.
>> Şimdi düşünüyorum Yani senin hafıza Bu gibi sadece bir kaset gibi,
Bu ne bir programcı yine belleğin bir dizi çağırır.
Ve aslında saklamak istediğinizde Bir bilgisayarın belleğinde bir şey,
genellikle mağaza şeyler back-to-back back-to-back.
Bu yüzden numaraları hakkında konuşuyorduk.
Ve ben istediğim zaman sorunları çözmek için gibi dört, bir, üç, iki,
Hatta sadece çizim olsa Sadece sayılar dört, bir, üç,
Gemide iki bilgisayar olur Gerçekten bellekte bu kurulum var.
>> Ve yanında ne olurdu bilgisayarın belleğinde iki?
Eh, buna cevap yok.
Biz gerçekten bilmiyoruz.
Ve sürece bilgisayar ihtiyacı yok,
Bir sonraki ne o umurumda zorunda değildir sayılara bu bakım ile ilgili yok.
Ve ben daha önce bir bilgisayarda olduğunu söyledi bir seferde sadece tek bir adrese bakabilirsiniz,
Bu yüzden türüdür.
>> Değil bir kayda aksine çalar ve bir okuma kafası
sadece belirli bir bakmak edememek fiziksel eski okul kayıtlarında oluk
Aynı anda, benzer şekilde Bir bilgisayar sayesinde can
onun CPU ve onun için Intel komut seti,
kimin talimat arasında bellekten okunur
veya bir memory-- kaydetmek Bilgisayar yalnızca bakabilirsiniz
Bir olan Zamanın az bir yerde Bazen bunların bir kombinasyonu,
ancak bir seferde gerçekten sadece bir konum.
Ne zaman yaptıklarını Bu çeşitli algoritmalar,
Ben sadece bir yazma değilim vacuum-- dört, bir, üç, iki.
Bu numaraları aslında aittir bellek fiziksel yerde.
Yani küçücük vardır transistörler veya bir çeşit
altında elektronik davlumbaz, bu değerleri saklamak.
>> Ve toplamda kaç bit Şu anda dahil, sadece temiz olması için?
Yani bu dört bayt veya şimdi 32 bit toplam bulunuyor.
Yani aslında 32 sıfır vardır ve Bu dört şeyi oluşturan olanlar.
Buraya daha var, ama Yine biz bu umurumda değil.
>> Yani şimdi Başka bir soralım bellek kullanarak soru,
sonunda çünkü Günün Varyans yer almaktadır.
Ne olursa olsun biz yapmak ne olabilir Günün sonunda bilgisayar
donanım hala başlık altında aynı.
Buradan nasıl bir kelime saklamak ki?
Eh, bir bilgisayarda bir kelime gibi "Hey!" sadece bu gibi saklanır.
Ve daha uzun isteseydi kelime, sadece can
Bu üzerine ve bir şeyler söylemek Burada "Merhaba" ve mağaza gibi.
>> Ve böylece burada da, bu contiguousness bir avantaj, aslında
Bir bilgisayar sadece can çünkü sağdan sola doğru okunan.
Ama burada bir soru.
bu kelime bağlamında, h-e-l-l-o, ünlem,
bilgisayar nerede nasıl kelime başlar ve kelime nerede biter?
numaraları bağlamında, nasıl bilgisayar yapar
know how dizisi uzun sayılar ya nerede başlar?
Eh, out-- döner ve biz çok fazla gitmeyecek
detail-- bu seviyeye bilgisayarların hafızasında etrafında malzeme taşımak
kelimenin tam anlamıyla bu adreslerin yoluyla.
sen eğer bir bilgisayarda Yani kod yazma şeyleri saklamak için
kelimeler gibi, ne olduğunu Gerçekten yazmaya yapıyor
hatırlar ifadeler Bilgisayarın hafızası bu kelimelerdir.
Bu yüzden bana çok bir yapayım, çok basit bir örnek.
>> Ben devam edeceğim ve basit bir metin programı açmak,
ve ben yaratmak için gidiyorum Bir dosya merhaba.c denir.
Bu bilgilerin çoğu biz çok detaylı girmeyeceğim,
ama yazmak için gidiyorum Aynı dilde program
C. Bu, çok daha korkutucu Ben, Scratch daha iddia ediyorum
ama ruhu içinde çok benzer.
Aslında, bu küme braces-- yapabilirsiniz tür
Ben sadece bu kadar ne yaptığını düşünüyorum.
>> en doğrusu, bu yapalım.
Yeşil bayrak tıklandığında, aşağıdakileri yapın.
Ben yazdırmak istiyorum "merhaba."
Yani bu şimdi pseudocode olduğunu.
Ben tür hatları bulanıklık var.
C, bu dil konuşuyorum yaklaşık bu hat baskı merhaba
aslında "printf" ile olur Bazı parantezler ve yarı-kolon.
>> Ama aynı fikir.
Ve bu derece kullanıcı dostu "Yeşil bayrak tıklandığında" olur
çok daha gizemli "int main boşluk."
Ve bu gerçekten hiç eşlemesi, bu yüzden sadece bu görmezden gidiyorum.
Ama kaşlı gibidir Böyle kavisli puzzle parçaları.
>> Yani yapabilirsiniz tür sanırım.
Hatta, daha önce programlanmış hiç eğer Bu program muhtemelen ne yapıyor?
Muhtemelen merhaba yazdırır bir ünlem işareti ile.
>> Yani o deneyelim.
Ben onu kurtarmak için gidiyorum.
Ve bu yine çok olduğunu eski okul ortamı.
Ben sürüklemek değil, tıklayın olamaz.
Ben komutları yazmanız gerekir.
Bu yüzden, bu yüzden benim programı çalıştırmak istiyorum Ben hello.c gibi, bunu yapmak olabilir.
Ben koştum dosya.
Ama bir adım eksik, bekleyin.
Ne yaptık ki bir gerekli C gibi bir dil için adım?
Ben sadece kaynak yazdım Kod, ama ne ihtiyacım var?
Evet, ben bir derleyici gerekir.
Burada benim Mac Yani, ben bir GCC çağrılan program, GNU C derleyicisi,
hangi bana paha dönüş yapmanızı sağlar Benim kaynak kodu içine, biz onu arayacağım,
Makine kodu.
>> Ve bunu görebiliyorum, Yine, aşağıdaki şekilde, bu
sıfırlar ve olanları ben sadece benim kaynak kodundan oluşturulan
sıfırlar ve olanları bütün.
Ve ben çalıştırmak istiyorsanız benim program-- o olur
için a.out çağrılacak Tarihsel reasons-- "Merhaba."
Tekrar çalıştırabilirsiniz.
Merhaba Merhaba Merhaba.
Ve çalışıyor gibi görünüyor.
>> Ama bu bir yere gelir benim Bilgisayarın hafızası kelimeler
h-e-l-l-o, ünlem.
Ve bu, bir kenara, sadece bir olarak, çıkıyor ne bir bilgisayar zamanki
bu yüzden bilir nerede bunu şeyler başlatmak ve bu kadar end--
Burada özel bir sembol koymak için gidiyor.
Ve kongre koymaktır Bir kelimenin sonundaki sayısı sıfırdır
Bunu nereden biliyorsun ki Aslında, biter, böylece
Daha fazla ve daha fazla baskı tutmayın senden karakterler aslında niyetinde.
>> Ama burada paket, hatta Bu oldukça gizemli olsa,
sonuçta olmasıdır nispeten basit.
Sen, bir boş bir kaset tür verildi Harfleri yazabilir hangi alanı.
Sadece bir olması keyfi gibi özel sembol,
sayısı sıfır, sonunda koymak sözlerin bilgisayar bilmesi,
oh, sonra yazdırmayı durdurmak gerekir Ben ünlem bakın.
Orada sonraki şey, çünkü sıfır ASCII değeridir
veya null karakter olarak Birisi çağırır.
Ama bir problem tür var Burada, ve geri dönmek edelim
Bir an için numaraları.
Yapmam varsayalım, aslında, , Sayılar bir dizi var
ve varsayalım Ben yazıyorum programı
Bir öğretmen için bir not defteri gibi ve öğretmenler sınıf.
Ve bu program ona izin verir öğrencilerinin puanlarını yazmak için
testleriyle ilgili.
Ve öğrenci aldığını varsayalım ilk sınavda 100, belki
Daha sonra bir sonraki birinde bir 80 gibi 75, daha sonra dördüncü sınavda 90.
>> Hikayenin bu noktasında Yani, Dizi boyutu dört taşımaktadır.
kesinlikle daha fazla bellek içinde var Bilgisayar, fakat dizi, tabiri caizse,
büyüklüğü dört taşımaktadır.
Öğretmen istediği şimdi varsayalım sınıfa beşinci sınav atamak.
Eh, şeylerden biri o ya da o yapmak zorunda olacak
şimdi burada bir ek değer saklamak olduğunu.
Ama dizinin eğer öğretmen vardır Bu programda oluşturulan, için boyut taşımaktadır
bir dizi ile sorunlardan biri olduğunu Sadece belleğe eklemeye devam edemez.
Çünkü ne olur başka bir parçası Program orada "hey" kelimesini vardır?
>> Diğer bir deyişle, zaman bellek olabilir Bir programda herhangi bir şey için kullanılır.
Ve önceden ben, hey, yazdığınız takdirde Ben girdi, dört sınav puanları istiyorum,
Burada ve burada gidebilir.
Ve aniden fikrinizi değiştirirseniz Daha sonra ben beşinci sınav istediğini söylüyorsun
Skor, yapamazsın sadece istediğiniz yere koyun,
Çünkü bu ne varsa Bellek kullanılıyor
bir şey için başka bir program else-- ya da programın başka bir özelliği,
çalıştırıyorsanız bu mu?
Yani önceden düşünmek zorunda Eğer veri depolamak istiyorum nasıl,
Şimdi boyalı çünkü Kendinizi bir dijital köşeye.
>> Yani bir öğretmen yerine olabilir Bir program yazarken demek
saklamak için onun sınıflarda, biliyor musun?
Ben, istemek için gidiyorum benim program yazarken,
Ben istiyorum sıfır, bir, iki, üç, dört, beş, altı, sekiz notları toplam.
Bu yüzden, bir, iki, üç, dört, beş, altı, yedi, sekiz.
Öğretmen sadece aşırı ayırabilirsiniz Bellek kendi programını yazarken
ve ne biliyorsun, demek?
Ben asla daha atamak için gidiyorum Bir dönem sekiz sınavlar daha.
Bu sadece deli.
Bunu ayırmak asla.
bu şekilde o sahip olacak şekilde mağaza öğrenci puanları esneklik,
75, 90, ve belki biri ekstra gibi Öğrenci, 105 ekstra kredi var.
>> Ama eğer öğretmen asla Bu üç boşluk kullanır,
Burada sezgisel bir paket var.
O ya da o sadece alanı israf edilmektedir.
Bu yüzden, diğer bir deyişle, orada programlama ortak takas
ya tahsis nerede tam olarak çok bellek istediğiniz gibi,
başaşağı süper olman efficient-- sen savurgan değilsin
at Bay Kane ama olumsuz ne fikrini ne zaman değiştirirseniz
Saklamak istediğiniz programı kullanarak Senden daha fazla veri başlangıçta amaçlanan.
>> Yani belki çözüm daha sonra ise Böyle bir şekilde programlar yazmak
Onlar daha fazla bellek kullandığını aslında ihtiyacınız olandan.
Eğer gitmiyorsun Bu şekilde Bu sorun haline çalıştırmak için,
ama savurgan davranıyorsun.
Ve programın kullandığı daha fazla bellek, Dün konuştuğumuz gibi, daha az
kullanılabilir bellek Diğer programlar için,
er bilgisayar yavaşlatabilir aşağı nedeniyle sanal bellek.
Ve böylece ideal bir çözüm olabilir ne?
>> Altı tahsisi kötü görünüyor.
Aşırı tahsis kötü görünüyor.
Peki daha iyi bir çözüm olabilir?
Yeniden tahsis.
Daha dinamik olun.
Bir seçim kendinizi zorlamayın priori, başında ne istiyorsun.
Ve elbette, aşırı tahsis yok Size diye savurgan olmak.
>> Ve böylece bu hedefe ulaşmak için, biz Bu veri yapısı atmak gerekir,
öylesine uzakta, konuşmak için.
Ve böylece ne bir programcı tipik kullanacak
değil bir şekilde adlandırılır Dizi ama bir bağlantılı liste.
Başka bir deyişle, o olacak kendi hafıza düşünmeye başlar
Bir şeklin olmak tür olarak onlar şu şekilde çizebilirsiniz.
Ben bir numara saklamak isterseniz o Eylül yüzden bir program--,
Ben öğrencilere bir sınav verdik; istiyorum Öğrencilerin ilk sınav saklamak için,
ve onlar dökersin-- I bir 100 var benim bilgisayar soracağım,
Birkaç gün önce programın yoluyla belleğin bir parça için, yazılı.
Ve ben saklamak için gidiyorum İçinde sayı 100, ve o kadar.
>> Sonra birkaç hafta sonra Benim ikinci sınav olsun,
ve tip zamanı Bu% 90, ben gidiyorum
Bilgisayarı sormak, hey, bilgisayar, Ben bellek başka öbek olabilir?
Bana bunu vermek için gidiyor bellek boş yığın.
Ben, sayı 90 koymak için gidiyorum ama benim programda bir şekilde ya da other--
ve biz endişelenecek olmayacak İhtiyacım bu-- sözdizimi
her nasılsa birlikte bunları zincir.
Ve ben birlikte onları zincir olacak burada ne bir ok gibi görünüyor.
>> çıkageldi üçüncü yarışması, Ben diyeceğim, hey, bilgisayar,
Bana bellek başka yığın verir.
Ve ben aşağı koymak için gidiyorum ne olursa olsun, 75 gibiydi
ve ben zinciri bu var Birlikte şimdi nasılsa.
Dördüncü yarışması birlikte geliyor ve belki Bu dönem sonuna doğru bu.
Ve bu noktada benim program tarafından bellek kullanıyor olabilir
biryere, her fiziksel bitti.
Ve bu yüzden sadece tekmeler, ben Bu ileri çekmek için gidiyor
quiz-- Ne olduğunu unutmak; ben belki düşünmek 80 veya şey--
yolu buraya.
>> Ama bu, çünkü resimsel, gayet iyi Bu çizgi çizmek için gidiyorum.
Diğer bir deyişle, gerçekte, bilgisayarınızın donanım,
İlk puan olabilir öyle çünkü burada sona
Sağ dönem başında.
Bir sonraki burada sonunda olabilir zaman biraz geçti çünkü
ve program çalışırken tutar.
Ertesi skor, 75, buraya olabilir.
Ve son puan olabilir Buraya bir 80.
>> Yani gerçekte, fiziksel olarak, bu olabilir ne bilgisayarınızın bellek gibi görünüyor.
Ama bu kullanışlı zihinsel değil Bir bilgisayar programcısı için paradigma.
Neden nerede önemsemeliyiz halt veri biten nedir?
Sadece veri depolamak istiyor.
>> Bu bizim tartışma gibi tür olduğunu küp çizim önceki.
Neden umurunda ne açı küp olduğunu
ve bunu nasıl çizmek çevirmek zorunda?
Sadece bir küp istiyorum.
Benzer şekilde burada, seni Sadece sınıf defterine istiyorum.
Sadece düşünmek istiyorum numaralarının listesi olarak bu.
öyle nasıl kimin umurunda donanımda uygulanan?
>> Şimdi soyutlama Yani Burada bu resim.
Bu şekilde, liste bağlı bir edildi Bir programcı çağırır,
Eğer bir var sürece Liste, belli ki sayılar.
Ama resimsel bağlı olan Bu okların yoluyla,
ve tüm bu oklar altında mudur Kaput, meraklı iseniz,
fiziksel donanım sahip olduğunu hatırlamak adresleri, bir, iki, üç, dört sıfır.
Tüm bu oklar bir harita gibidir veya yön, eğer 90 o-- şimdi
Ben saymak lazım.
>> Sıfır, bir, iki, üç, dört, beş, altı, yedi.
90 gibi görünüyor bellek adres numarası yedi.
Tüm bu oklar are kağıt biraz hurda gibi
Buna yön veriyor Bu haritayı takip diyor programı
Konuma yedi almak için.
Ve orada bulacaksınız Öğrencinin ikinci sınav puanı.
Bu arada, 75-- ben bu devam ederse, Bu yedi, sekiz, dokuz, 10, 11, 12,
13, 14, 15.
>> Bu, diğer ok sadece temsil hafıza konumuna 15 bir harita.
Fakat yine de, programcı genellikle yapar detay bu düzeyde umurumda değil.
Ve en her programlama dil, bugün, programcı
hatta nerede bellekte bilemezsiniz Bu rakamlar aslında.
o sahip tüm hakkında bakım Onlar bir şekilde birbirine bağlantılı olduğunu
Böyle bir veri yapısı.
>> Ama öyle değil çıkıyor çok teknik olsun.
Ama sırf belki can Burada bu tartışma var göze,
Biz tekrar varsayalım Burada bir dizi bu sorunu.
biz burada olacak pişman olmadığını görelim.
Bu, 100, 90, 75 ve 80'dir.
>> Bana kısaca bu iddiayı yapalım.
Bu bir dizidir, ve yine, Bir dizinin göze çarpan özelliği
tüm verileri geri olmasıdır geri anlamıyla memory-- içinde geri
bir byte ya da belki dört bayt, uzak bayt bazı sabit sayısı.
Bağlantılı bir listede, biz çizmek olabilir Bu gibi başlık altında kim
O şeyler bilir nerede?
Hatta böyle bir akış gerek yoktur.
bazı verilerin olabilir Orada yukarı sola.
Sen bile bilmiyorsun.
>> Ve böylece bir dizi, bir var rasgele erişim olarak bilinen özellik.
Ve rasgele erişim aracıdır bilgisayar anında atlayabilir
Bir dizideki herhangi bir yere.
Niye ya?
bilgisayar biliyor çünkü İlk konum olduğunu
sıfır, bir, iki, üç.
>> Ve böylece gitmek istiyorum sonraki elemana bu element,
kelimenin tam anlamıyla, içinde Bilgisayarın aklı, sadece bir tane ekleyin.
Üçüncü öğeye gitmek istiyorsanız, Sadece, sadece, bir sonraki elemanın Şehre eklemek
bir tane ekle.
Ancak, bu sürümde Hikayenin, varsayalım
Bilgisayar şu anda arıyor ya da numara 100 ile ilgili.
Nasıl bir sonraki alabilirim sınıf kitabında notu?
>> Sen yedi almak zorunda keyfi adımlar.
bir sonrakine almak için gereken 15 almak için başka sekiz adımları atın.
Diğer bir deyişle, bir değil, sayılar arasındaki sürekli boşluk,
ve bu yüzden sadece sürer Bilgisayar daha fazla zaman noktasıdır.
bilgisayar aramak zorunda sırayla bellek üzerinden
Eğer aradığınızı bulmak için.
>> bir dizi bir olma eğilimindedir, oysa bu yüzden hızlı veri structure-- çünkü sen
gerçekten sadece basit aritmetik yapabilirsiniz ve bir ekleyerek istediğiniz yere almak,
bağlantılı liste instance-- için, Eğer bu özelliği feda.
Sadece birinci gidemez İkinci üçüncü dördüncü için.
Haritayı takip etmek zorunda.
Daha fazla adımlar atmak zorunda bu değerler, almak için hangi
bir maliyet ekleyerek gözükmektedir.
Bu yüzden bir fiyat ödeyerek, ama ne oldu konum Dan burada arayışında olduğunu özelliği?
Ne bağlantılı liste yapar görünüşe yapmamızı sağlayacak,
menşe oldu Bu özel bir hikaye?
>> Kesinlikle.
buna dinamik boyutu.
Biz bu listeye ekleyebilirsiniz.
Hatta bu yüzden, listeyi daraltmak için Biz sadece kadar bellek kullandığınızı
biz aslında istediğimiz gibi ve bu yüzden Biz aşırı tahsisi asla değilsin.
>> Şimdi sadece, gerçekten sirke-seçici olmak gizli bir maliyet var.
Yani sadece bana ikna izin vermemeliyiz Bu zorlayıcı bir takas olduğunu.
Burada başka bir gizli maliyet var.
yarar, açık olmak Biz dinamizm elde ediyoruz.
Başka bir eleman istiyorsanız, ben sadece can çizin ve orada bir numara koymak.
Ve sonra onu bağlayabilirsiniz Burada bir resim ile,
Buraya ise, yine, ben yasiyorsaniz Bir köşeye kendimi boyalı
başka bir şey zaten kullanıyorsa Burada bellek, ben şans bitti.
Ben köşeye kendimi boyadım.
>> Ama gizli ne Bu resimde maliyeti?
Sadece miktar değil Bu gereken zaman
Buradan buraya gitmek, bu daha sonra, yedi adım
Birden fazla sekiz adım.
Başka bir gizli maliyet nedir?
Sadece zaman.
Ek bilgi Gerektiğinde bu resmi elde etmek.
>> Evet, o harita, o küçük artıkları Kağıt, ben onları açıklayan tutmak gibi.
Bu arrows-- Bunlar serbest değildir.
Bildiğiniz bir computer-- Bir bilgisayar neler.
Bu sıfırları ve olanları vardır.
Eğer bir ok ya da temsil etmek isterseniz harita veya bir sayı, bazı bellek gerekir.
Diğer fiyata Yani Bağlantılı bir liste için ödeme,
ortak bir bilgisayar bilimi Kaynak, aynı zamanda alandır.
>> Nitekim bu yüzden, bu yüzden genel olarak, ödünleşmeler arasında
Yazılım mühendisliği tasarımı sistem zaman ve space-- olduğu
senin maddeler iki, iki En pahalı maddeler.
Bu bana daha fazla zaman mal oluyor Ben bu haritayı takip etmek zorunda, çünkü
ama aynı zamanda beni daha fazla alan mal oluyor Ben haritayı tutmak zorunda çünkü.
Yani umut olarak biz tür ettik dün ve bugün üzerinde tartışılan,
yararları olduğu maliyeti ağır olacak.
>> Ama burada hiçbir belirgin bir çözüm var.
Belki de better-- olduğunu a la hızlı ve kirli,
Kareem earlier-- önerildiği gibi Soruna bellek atmak.
Sadece daha fazla bellek satın daha az düşünüyorum problem çözme konusunda sert,
ve daha kolay bir şekilde bunu çözmek.
Ve gerçekten daha önce, ne zaman Biz ödünleşmeler hakkında konuştuk,
o boşluk değildi Bilgisayar ve zaman.
Bu geliştirici zaman, hangi başka kaynaktır.
>> Yani yine, bu denge var karar vermeye çalışırken şeylerden hangi
Eğer harcamaya istekli?
en ucuz hangisi?
Hangisi daha iyi sonuçlar verir?
Evet?
>> Aslında.
Bu durumda, eğer maps-- sayıları temsil
Bu, birçok dilde denir "Işaretçileri" veya "adresleri" -
o çift boşluk var.
Eğer çift olarak kötü olması gerekmez Şu anda biz sadece sayıları depolamak ediyoruz.
biz saklamak olduğunu varsayalım Bir hastanededaha hasta kayıtları
Pierson isimleri, telefon numaraları, böylece sosyal güvenlik numaraları, doktor
tarih.
Bu kutu, fazla olabilir , Çok daha büyük bir durumda
minik bir işaretçi, adresi Bir sonraki büyük bir anlaşma değil element--.
Böyle bir saçak var farketmez maliyet.
Ancak bu durumda, evet, bir iki katına var.
İyi soru.
>> saat a bahsedelim daha somut olarak küçük.
çalışma süresi nedir Bu listeyi aranırken?
Ben aramak istedim varsayalım Tüm öğrencilerin sınıflara geçtikçe,
n notları var Bu veri yapısı içinde.
Burada da, biz ödünç alabilir daha önceki kelime.
Bu doğrusal bir veri yapısıdır.
>> n Büyük O almak için gerekli ne olduğunu Bu veri yapısının sonuna kadar,
whereas-- ve biz görmedik Bu bir dizi size verir before--
Ne yani, sabit zaman denir bir adım ya da iki adım veya 10 steps--
önemli değil.
Bu sabit bir sayıdır.
Bu ile ilgisi yoktur Dizinin boyutu.
Ve Bunun nedeni, Yine, rasgele erişim olduğunu.
Bilgisayar can sadece hemen başka bir yere atlamak,
hepsi aynı çünkü her şey mesafe.
dahil hiçbir düşünce yoktur.
Pekala.
I can Yani, bana deneyelim son iki resim boya.
karma tablo olarak bilinen çok yaygın bir.
Yani bu tartışma motive etmek, Bana bunu nasıl düşüneyim.
>> Peki buna ne dersin?
Sorun Varsayalım ki Şimdi çözmek istiyoruz
Bir dictionary-- içinde uyguluyor İngilizce kelimeleri yani bir sürü
ya da her neyse.
Ve gol cevap verebilmek için Formun soruları bu bir kelimedir?
Yani uygulamak istediğiniz Bir yazım denetleyicisi, sadece
fiziksel bir sözlük gibi Eğer bir şeyler aramak olabilir.
Ben bir dizi ile bunu vardı varsayalım.
Ben bu yapabilirdi.
>> Ve kelimeler elma varsayalım ve muz ve kavun.
Ve ben meyve düşünemiyorum O d ile başlar, bu yüzden biz sadece konum
Üç meyve olacak.
Yani bu bir dizidir ve biz konum Bu kelimelerin hepsi depolama
bir dizi olarak, bu sözlükte.
Soru, başka nasıl olduğunu Bu bilgiyi saklamak olabilir?
>> Eh, biraz, çünkü burada hile ediyorum kelime bu harflerin her biri
Gerçekten tek bir bayt olduğunu.
Bu yüzden gerçekten olmak istedim sirke seçici, ben gerçekten gerekir
çok içine bu kadar bölünebilen olması belleğin küçük parçalar,
ve biz tam olarak bunu yapabiliriz.
Ama biz çalıştırmak için gidiyoruz eskisi gibi sorun.
Ne, eğer Merriam Webster veya Oxford olarak Her onlar kelimeler eklemek year-- yapar
dictionary-- biz yok mutlaka kendimizi boyamak istiyorum
bir dizi ile bir köşeye?
>> Bunun yerine, belki daha akıllı bir yaklaşım Kendi düğüm ya da kutuya elma koymak için,
dediğimiz gibi, muz, ve Daha sonra burada kavun var.
bunlar birbirine ve biz dize.
Yani bu dizidir ve Bu bağlantılı listesidir.
oldukça göremiyorsanız, sadece diyor "dizi" ve bu "diyor liste."
>> Bu yüzden aynı olması önce tam olarak konular,
bu sayede şu anda sahip Bizim bağlantılı liste dinamizm.
Ama biz oldukça yavaş bir sözlük var.
Ben bir kelime aramak istediğinizi varsayalım.
Bana n büyük O sürebilir adımlar, kelime olabilir çünkü
sonunda tüm yol olacak kavun gibi liste.
Ve o çıkıyor programlama, sıralama
Verilerin Holy Grail yapıları, bir şey
Bu sizin sabit verir bir dizi gibi zaman
ama bu yine de dinamizmi verir.
>> Bu yüzden her iki dünyanın en iyi olabilir?
Ve gerçekten, bir şey var hash tablosu olarak adlandırılan
Bu tam olarak yapmanızı sağlar olsa yaklaşık o.
Bir karma tablo meraklısı olduğunu Veri yapısı biz
olarak düşünebiliriz Bir array-- kombinasyonu
ve ben çizmek gidiyorum bu-- ve bağlantılı listeler gibi
Buraya böyle çizmek edeceğiz.
>> Bu şey ve yolu aşağıdaki gibi çalışır.
Bu table-- hash şimdi-- eğer benim üçüncü veri yapısı,
ve ben saklamak istiyorum Bu kelimeler, I do not
Sadece tüm saklamak istediğiniz kelimeler arka arkaya arkaya arkaya.
Biraz yararlanmak isteyen bilgi parçası
sağlayacak kelimeleri Daha hızlı nerede benim olsun.
>> Yani kelimeler elma vermiş ve muz ve kavun,
Ben kasten bu kelimeleri seçtik.
Niye ya?
Ne temelde çeşit Üç farkı nedir?
açık nedir?
Farklı harflerle başlar.
>> Yani biliyor musun?
tüm sözlerimi koymak yerine Aynı kova, tabiri caizse,
gibi büyük bir listede, neden yok Ben en azından bir optimizasyon deneyin
ve benim listeleri 1/26 sürece olun.
Bir zorlayıcı optimizasyon yok neden olabilir
Ben- sözcük ekleme Bu veri yapısı içinde,
bilgisayarın belleğinden, neden içine Ben burada tüm 'bir' sözlerini koymayın
hepsi burada 'b' sözleri, ve burada tüm 'c' sözleri?
Yani bu bir elma koyarak biter Burada, burada ve burada muz, kavun,
ve benzeri.
>> Ve ben bir ek varsa kelime başka ne da--?
Elma, muz, armut.
Herkes meyve düşünmek a, b ya da c ile başlar?
Blueberry-- mükemmel.
Burada sonuna kadar gidiyor.
Ve bu yüzden bir var gibi marjinal iyi çözüm,
Şimdi isterseniz, çünkü elma aramak için, ben
birinci-- Ben sadece dalış yok benim veri yapısı içine.
Ben bilgisayarın hafızasına dalmayın.
Ben ilk ilk harfi bakmak.
>> Ve bu ne bir bilgisayar bilim adamı söyleyebilirim.
Sen veri yapısı içine hash.
Sen girişi almak Bu durumda elma gibi bir kelimedir.
Sen bakarak, analiz Bu durumda ilk harfi,
böylece bu karma.
Hashing genel bir terim mademki olduğunu Eğer girdi olarak bir şey almak
ve bazı çıktı üretmek.
Ve bu çıkış durum konumu
Eğer, birinci aramak istediğiniz Konumu, ikinci konumu, üçüncü.
Yani giriş elma, çıkış ilk.
Giriş muz, olduğu Çıkışın, ikinci olmalıdır.
giriş, kavun olduğunu çıkış, üçüncü olmalıdır.
giriş, yaban mersini olduğunu çıkış tekrar ikinci olmalıdır.
Ve bu almaya yardımcı olur ne hafızanıza aracılığıyla kısayolları
kelimeleri almak için veya veri daha etkili.
>> Şimdi bu potansiyel bizim zaman keser kadar 26 kişiden biri olarak tarafından,
Eğer farz çünkü eğer sen misin "Z" gibi birçok "bir" kelime var
"Q" kelimeleri gibi kelimeler hangi Gerçekten realistic-- değildir
Eğer genelinde çarpık zorunda gidiyoruz alphabet-- belirli harfleri
ama bu bir artımlı olurdu izin vermez yaklaşım
Eğer çok daha hızlı kelime almak için.
Ve gerçekte, sofistike Program, dünyanın Google'ın,
--daha dünya Facebooks onlar bir karma tablo kullanmak
farklı amaçlar bir sürü.
Ama kadar saf olmaz Sadece ilk harfi bakmak
elma ya da muz veya armut veya kavun,
Bu gördüğünüz gibi çünkü listeleri hala uzun alabilir.
>> Ve böylece bu hala tür olabilir bir linear-- böylece tür yavaş,
n büyük O olduğu gibi biz daha önce tartıştık.
Peki gerçekten iyi bir karma tablo olacak çok daha büyük bir dizi olacak sanıyor-.
Ve çok daha kullanacak sofistike karma işlevi,
böylece sadece bakmak değil "a."
Belki de bakar "a-p-p-L-e" ve her nasılsa bu beş harf dönüştürür
nerede konuma Elma saklanmalıdır.
Biz sadece safça harfi 'a' kullanıyorsanız yalnız, güzel ve basit çünkü.
>> Ama karma tablo içinde sonunda, aklınıza gelebilecek
yer alan bir kombinasyonu olarak Bir dizi, her biri
Bu ideal bir bağlantılı liste var mümkün olduğu kadar kısa olması gerekir.
Ve bu bariz bir çözüm değildir.
ince ayar aslında, çok Bu başlık ne zaman altında devam ediyor
bu tür uygulama sofistike veri yapıları
Doğru budur Dizinin uzunluğu?
Sağ hash fonksiyonu nedir?
Nasıl bellekte şeyleri saklamak mı?
>> Ama nasıl hızlı bir şekilde gerçekleştirmek tartışma bu tür
bu tür olduğunu, ya şimdiye kadar tırmandı Bu noktada kişinin başının üzerinde hangi
iyi.
Ama biz gerçekten birlikte, hatırlama başladı bir şey düşük seviyeli ve elektronik.
Ve böylece bu yine bu soyutlama tema,
nereye için almaya başlar kez verilen, tamam, ben orada dökersin-- var
fiziksel bellek, tamam, her, got it fiziksel konumu, bir adresi vardır
Tamam, anladım ben temsil edebilir arrows-- sıra bu adresler
Eğer çok hızlı olması başlayabilirsiniz Daha sofistike konuşmalar olduğunu
Sonunda bize izin gibi görünüyor arama gibi sorunları çözmek için
ve daha etkin sıralama.
Ve, too-- emin Ben bu düşünüyorum çünkü
bazı içine gittin en derin biz ettik proper-- bu CS konuların
Bu bir gün bir buçuk yapılır genellikle üzerinde ne yapacağını işaret
Bir dönem sekiz hafta elbette.
>> Bu herhangi bir sorunuz var mı?
Yok hayır?
Pekala.
Peki, neden orada duraklama yok Bir kaç dakika erken öğle başlatmak,
sadece yaklaşık bir saat devam?
Ve ben oyalanmak edeceğiz sorularla biraz.
Sonra gitmek zorunda gidiyorum Sorun olmazsa bir kaç aramaları almak.
Ben, bu arada bazı müzik açmak gerekir ama öğle köşeyi olmalıdır.