>> [REPRODUCCIÓ DE MÚSICA]
>> ANDI Peng: Benvinguts a la setmana 3 de la secció.
Gràcies, nois, per a tots ve a aquesta hora d'inici el dia d'avui.
Tenim un bonic i petit grup íntim avui.
Així que espero que arribarem a acabat, potser, d'hora,
una mica d'hora avui.
Així que ràpidament, només algunes anuncis per a l'ordre del dia d'avui.
Abans de començar, estem va anar sobre
alguns problemes logístics breus, pset preguntes, interrogar, coses així.
I després anem a bussejar en dret.
Utilitzarem un depurador GDB de trucada començar desacreditant el nostre codi, que David
explicar en conferència l'altre dia.
Anem a repassar els quatre tipus de classes.
Anirem sobre ells amb força rapidesa ja que són molt intensius.
Però saber que totes les diapositives i codi font són sempre en línia.
Així que no dubti, en la seva lectura, a tornar enrere i fer una ullada a això.
>> Anirem a través notació asimptòtica, que
és només una forma elegant de dir "els temps d'execució"
on tenim la gran O, el que David va explicar en conferència.
I també hem Omega, que és el temps d'execució de límit inferior.
I parlarem una mica més en profunditat pel que fa a com els treballs.
I finalment, anem a repassar recerca binària, perquè molts de vostès que ja tenen
va mirar als seus conjunts de processadors probablement saber que aquesta és una pregunta que està en el seu conjunt de processadors.
Així que tots estarem feliços que cobrim això avui.
>> I finalment, per la seva secció de comentaris, en realitat
l'esquerra a uns 15 minuts a Al final només repassar
logística de pset3, qualsevol pregunta, potser una mica d'orientació, si es vol,
abans de començar la programació.
Així que anem a tractar d'aconseguir a través de el material amb força rapidesa.
I després podem passar algun temps tenint més preguntes per al conjunt de processadors.
D'ACORD.
>> Ràpidament, de manera que només uns pocs anuncis abans de començar avui.
En primer lloc, recepció per fer a través de dos dels seus conjunts de processadors.
Vaig consultar a tu-- Sí, anem a aconseguir un aplaudiment per a aquest.
En realitat, jo estava molt, realment impressionats.
Jo vaig qualificar el primer conjunt de processadors per a vostès setmana i últims nois van fer increïble.
>> Estil estava en punt a més d'alguns comentaris.
Assegureu-vos que està sempre comentant el seu codi.
Però els seus conjunts de processadors estaven a punt.
I segueix així.
I és bo per al grau de veig que vostès estan posant
en tant esforç en el seu estil i el seu disseny en el seu codi
que ens agradaria perquè vostè vegi.
Així que estic passant per la meva gratitud per a la resta de les AATT.
>> No obstant això, hi ha una algunes preguntes debrief
Només vull anar més que faria que tant la meva vida
i un munt de l'altra TA 'viu una mica més fàcil.
En primer lloc, m'he adonat d'això passat week-- quants de vostès
han estat funcionant en check50 el seu codi abans d'enviar?
D'ACORD.
Així que tothom hauria d'estar fent check50, porque-- 1 secret-- realitat
executar check50 com a part de la nostra correcció guions per provar el codi.
Així que si el seu codi està fallant check50, amb tota probabilitat,
que probablement va a fracassar el procés de registre també.
De vegades els nois tenir les respostes correctes.
Igual que, en cobdiciosos, alguns vostè té els números correctes,
que acaba d'imprimir algunes coses extra.
I aquest material extra en realitat no passa la verificació,
perquè l'equip no realment sap el que està buscant.
I així s'acaba d'executar a través de, veure que la seva sortida no
igualarem el que esperem la resposta ser, i marcar que és un error.
>> I sé que va succeir en alguns dels seus casos d'aquesta setmana.
Així que vaig tornar i manual classificat de nou codi de tots.
En el futur, però, per favor, per favor, asseguri
que s'està executant comprovar 50 en el teu codi.
A causa que és una mena de dolor per a la TA a haver de tornar enrere i manualment reclassificar
cada conjunt de processadors única per a cada únic, exemple mica perdut.
Així que no em trec cap punt.
Crec que em vaig treure potser un o dos per al disseny.
En el futur, tot i que, si vostè està fallant check50,
es prendran punts apagat per a la correcció.
>> A més, són conjunts de processadors a causa divendres al migdia.
Crec que hi ha un nen de set minuts període de gràcia finals que li donem.
Per temps de Harvard, que els permeti set minuts tard a tot.
Així que aquí a Yale, anem a adherir-se a això també.
Però més o menys, a les 00:07, si el seu conjunt de processadors no es troba en,
que serà marcat com a tard.
I així, mentre es marca el més tard, el TA-- estic
encara serà la classificació dels seus conjunts de processadors.
Així que vostè encara veu aparèixer un grau.
No obstant això, saber que en Al final del semestre,
tots els conjunts de processadors finals seran només posat a zero automàticament per l'ordinador.
>> Fem això per dues raons.
Un, de vegades obtenim excusat, com a excuses de Dean,
més endavant que jo no sé res encara.
Així que ens agrada assegurar-nos que estem classificació tot per si de cas, com, estic
falta l'excusa d'un degà.
I en segon lloc, tenir en ment, vostè pot encara
excloure un conjunt de processadors que té punts d'abast complet.
I així ens agrada grau tots els conjunts de processadors només
per assegurar-se que el seu àmbit d'aplicació allà i vostè els està tractant.
Així que fins i tot si és tard, se li segueix obtenir crèdit per als punts d'abast, crec.
>> Així moralitat de la història és, fer Assegureu-vos que els seus conjunts de processadors estan en el temps.
I si no estan en el temps, Sap que no és gran.
Sí, abans de passar, algú té qualsevol pregunta respecte retroalimentació pset?
Sí.
>> AUDIÈNCIA: Has dit que pot caure un dels conjunts de processadors?
>> ANDI Peng: Sí.
Així que hi ha nou conjunts de processadors general en el transcurs del semestre.
I si vostè té abast points-- el abast és just,
més o menys, se li intenta la problema, estàs posant en el temps,
se li mostra que vostè té demostrat que hagis llegit l'especificació.
Això és més o menys abast.
I si vostè està complint punts d'abast, que
pot caure més baix un fos d'abast complet.
Així que això és en el seu avantatge per completar i provar cada conjunt de processadors.
>> Fins i tot upload-- si cap de ells treballen, pujar-los tots.
I després anem a tant de bo siguem capaços de li donarà alguns d'aquests punts enrere.
Fresc.
Alguna altra pregunta?
Gran.
>> En segon lloc, l'oficina hores-- uns pocs notes ràpides sobre les hores d'oficina.
Així que primer, arribar d'hora a la setmana.
Ningú està mai en horari d'oficina els dilluns.
Christabel va venir a les hores d'oficina de la nit anterior.
Sí, Christabel.
I què ens tenim a l'oficina hores d'anit, Christabel?
>> AUDIÈNCIA: Teníem gelat.
>> ANDI Peng: Així que està bé, vam tenir gelat en horari d'oficina ahir a la nit.
Encara que no puc prometre que tindrem gelat en horari d'oficina
cada setmana, el que puc prometre és que hi haurà una significativament
millor proporció d'estudiants per TA.
Igual que fiar, és com tres a un.
Atès que, contrastar això amb Dijous, tens al voltant de 150
molt estressada nens i no gelat.
I no és només productiva per a qualsevol persona.
Així moralitat de la història és, arribar d'hora a les hores d'oficina i les coses bones
passarà.
>> També, vingui preparat per fer preguntes.
Saps?
Independentment del que els TA, em pensar, he estat dient,
hem estat rebent un parell d'estudiants que vénen en dijous a, com, 10:50
no haver llegit l'especificació sent així que m'ajudi, que m'ajudi.
Desafortunadament en aquest punt, no hi ha no hi ha molt que puguem fer per ajudar-lo.
Així que si us plau vingui a principis de la setmana.
Vingui d'hora per les hores d'oficina.
Vingui preparat per fer preguntes.
Assegureu-vos que vostè, com a un estudiant, són on
ha de ser perquè el TA pot guiar-lo al llarg,
que és el que les hores d'oficina ha de ser assignat per.
>> En segon lloc, pel que sé professors agradaria sorprendre'ns amb proves.
Vaig tenir un professor dels com, jo, per cert,
recordar que de meitat de període vostè té dilluns que ve.
Sí, jo no sé res d'això de meitat de període.
Així que seré que TA que recorda tot el que prova
0-- perquè, ja saps, estem CS.
Ara que hem matrius done, s'obté per què és prova 0, no interrogar 1, eh?
D'ACORD.
Oh, tinc algunes rialles en aquesta.
D'ACORD.
>> Així concurs 0 serà el 14 d'octubre, si vostè està en la secció de dilluns a dimecres
i 15 d'octubre, si vostè està en la secció de dimarts a dijous.
Això no s'aplica per als aquells de vostès a Harvard
que-- Crec que tots podràs prendre els seus exàmens en la 14a.
>> Així que sí, la setmana que ve, si David, a la conferència, es va,
si, així que en això prova la setmana que ve, a tots
no serà sorprès perquè vostè va venir a la secció
i vostè sap que el seu concurs 0 és en dues setmanes.
I tindrem opinió sessions i tot.
Així que no et preocupis per tenir por per això.
Qualsevol pregunta abans-- alguna pregunta en totes les qüestions logístiques relatives,
classificació, les hores d'oficina, seccions?
Sí.
>> AUDIÈNCIA: Així que la prova és serà durant la conferència?
>> ANDI Peng: Sí.
Així que la prova, crec, és 60 minuts assignats en aquest interval de temps
que vostè acaba de prendre a la sala de conferències.
Així que vostè no ha de venir a en, com, un atzar 19:00.
Està tot bé.
Sí.
Fresc.
>> Tot bé.
Així que anem a introduir un concepte per a vostè
aquesta setmana que David ja té classe del tocat en la conferència de la setmana passada.
Es diu GDB.
I quants de vostès, mentre que en el curs de l'escriptura dels seus conjunts de processadors,
han notat un gran botó que diu "Depuració" a la part superior del seu IDE?
D'ACORD.
Així que ara anem a realment arribem a descobrir el misteri del que en realitat botó
ho fa.
I et garanteixo que, es tracta d'un , Bella que té mèrit.
>> Així que, fins ara, crec que ha hagut dues coses
els estudiants han estat mai fent en depurar conjunts de processadors.
Un d'ells, o bé afegir a printf () - pel que cada poques línies,
s'agreguen en un printf () - oh, què és aquesta variable?
Oh, què és aquesta variable ara-- i quin tipus de veure la progressió
del seu codi ja que s'executa.
O el segon mètode que fan els nens és que acaba d'escriure tot l'assumpte
i després anar així al final.
Esperem que funciona.
Et garanteixo que, GDB és millor que tots dos d'aquests mètodes.
Sí.
Així que aquest serà el seu nou millor amic.
Perquè és una cosa bella visualment que mostra tant
el que el seu codi està fent en un punt específic
així com el que la totalitat del seu variables que estan portant,
com quins són els seus valors, en aquest punt específic.
I d'aquesta manera, vostè pot realment establir punts d'interrupció en el codi.
Vostè pot executar a través de línia per línia.
I BGF només tindrà per vostè, mostren perquè vostè,
el que totes les seves variables són, què estan fent,
el que està passant en el codi.
I de tal manera, que és molt més fàcil de veure
el que està succeint en lloc de-ció printf o escriure les seves declaracions.
>> Així que farem un exemple d'això més endavant.
Així que això sembla una mica abstracte.
No es preocupi, nosaltres farem exemples.
I així, en essència, els tres més grans, funcions més utilitzades que necessitarà en el BGF
són la continuació, passar per sobre, i Pas a botons.
Vaig a dirigir- hi ha, en realitat, en aquest moment.
>> Així es pot veure que tots els nois o hauria d'apropar una mica?
A la part posterior, es pot veure això?
He de fer un zoom?
Només una mica?
D'acord, guai.
Som-hi.
D'ACORD.
>> Així que tinc, aquí, el meu aplicació de cobdiciosos.
I mentre molts de vostès va escriure cobdiciosos en bucle while form-- que
és una manera perfectament acceptable fer it-- una altra manera de fer-ho és simplement
dividir en el mòdul.
Perquè llavors vostè pot tenir el seu valor i després tenen la resta.
I llavors vostè pot simplement afegir tot junt.
La lògica del que estic fent aquí té sentit per a tothom,
abans de començar?
Tipus de?
Fresc.
Gran.
És una peça molt sexy del codi, diria jo.
Com he dit, David, en donar una conferència, després d'un temps,
tots vostès començarà a veure codi com una cosa que és bonic.
I a vegades, quan veus bonica codi, és una sensació meravellosa.
>> Així que no obstant això, mentre que aquest codi és molt bonic, que no funciona correctament.
Així que anem a córrer check50 en això.
Comprovi 50 20-- oop.
2?
És que PSet2?
Sí.
Oh, pset1.
D'ACORD.
Així correm check50.
>> I com vostès poden veure aquí, està fallant un parell de casos.
I per a alguns de vostès, al curs de fer els seus butlletins de problemes,
vostè és com, ah, ¿per què no està funcionant.
Per què és treballant des de fa valors, però no per a altres?
Bé, GDB es va a ajudar a la figura per què aquestes entrades no estaven funcionant.
>> D'ACORD.
Així que anem a veure, un dels xecs que estava fallant en check50
era el valor d'entrada de 0,41.
Així que la resposta correcta que que hauria d'estar rebent és un 4.
Però en lloc del que estic imprimint és el 3-n, que és incorrecte.
Així que anem a executar això manualment, simplement assegurar-se que check50 està treballant.
Fem ./greedy.
Vaja, he de fer cobdiciós.
Som-hi.
Ara ./greedy.
>> Quant se li deu?
Fem 0.41.
I sí, ens veiem aquí que està la sortida 3
quan la resposta correcta, De fet, hauria de ser abril.
Així que anem a entrar al BGF i ​​vegem com ens pot anar sobre la fixació d'aquest problema.
>> Així que el primer pas en Sempre depurar el seu codi
és establir un punt d'interrupció, o d'un punt en el qual
desitja que l'ordinador o la depurador per iniciar mirant.
Així que si vostè realment no sé quin és el teu problema,
en general, el típic volem fer és configurar el nostre punt d'interrupció en el principal.
Així que si vostès poden veure això botó vermell allà,
sí, aquest era jo l'establiment d'un punt de ruptura per a la funció principal.
Faig clic en això.
>> I llavors em puc anar al meu botó de depuració.
Vaig colpejar aquest botó.
Permetin-me amplia la imatge si puc.
Som-hi.
Així que tenim, aquí, un panell de la dreta.
Ho sento, nois a la part posterior, que en realitat no pot veure molt bé.
Però, en essència, tot aquest panell de la dreta està fent
és no perdre de vista tant del lloc de relleu línia, que és la línia de codi
que l'equip està executant actualment, així com totes les seves variables
aquí baix.
>> Així que tens centaus, monedes, n, totes declarat a coses diferents
en aquest punt.
No es preocupi, perquè en realitat no tenen ells inicialitzat a qualsevol variable encara.
Així que a l'ordinador, la seva equip acaba de veure,
oh, 32767 va ser l'última funció utilitzada d'aquest espai de memòria en el meu equip.
Així que aquí és on actualment centaus és.
Però ningú que una vegada que s'executa el codi, hauria de convertir inicialitzat.
>> Així que anem a anar a través, línia per line, el que està passant aquí.
D'ACORD.
Així que aquí estan els tres botons que acabo d'explicar.
Vostè té el joc, o la funció Executar, botó, vostè té el pas sobre el botó,
i també té el Pas a botó.
I, essencialment, els tres ells només van a través del seu codi
i fer coses diferents.
>> Així que en general, quan vostè està de depuració, nosaltres no volem només cal prémer Play,
perquè Play n'hi ha prou amb executar el seu codi al final de la mateixa.
I llavors no ho farà realitat saber quin és el seu problema
és menys que estableixi múltiples punts d'interrupció.
Si estableix diversos punts d'interrupció, s'acaba de forma automàtica
córrer d'un punt de ruptura, a la següent, a la següent.
Però en aquest cas que hem només que un, perquè
volen treballar nostre camí de dalt a baix a baix.
Així que anem a ignorar aquest botó en aquest moment per als propòsits d'aquest programa.
>> Així que el pas sobre la funció només passos sobre cada línia
i et diu el que l'equip està fent.
El Pas en funció va en la funció real
això és en la seva línia de codi.
Així, per exemple, com printf (), que és una funció, no?
Si volgués pas físicament en la funció printf (),
Jo realment entrar en el tros de codi on printf () va ser escrit i veure
el que està passant allà.
>> Però en general, se suposa que el codi que et donem funciona.
Assumim el printf () està treballant.
Suposem que getInt () està treballant.
Així que no hi ha necessitat de entrar en aquestes funcions.
Però si hi ha funcions que escrigui vostè mateix
que desitja comprovar el que està passant,
vostè vol fer un pas en aquesta funció.
>> Així que ara només anem al passar per sobre d'aquest tros de codi.
Així que anem a veure.
Oh, imprimir, "Oh hai, com es va deure en gran canvi? "
No ens importa.
Sabem que està funcionant, així que passar per sobre d'ella.
>> Així que n, que és la nostra carrossa que que hem initialized-- o declared--
a la part superior, ara estem igualant que a GetFloat ().
Així que anem a passar per sobre d'això.
I veiem en la fons aquí, el programa
m'està incitant a l'entrada d'un valor.
Així d'entrada de deixar que el valor que volem per provar aquí, que és 0,41.
Gran.
>> Així que ara N-- Vostès Veure aquí, al bottom-- és
stored-- perquè no han arrodonit però, és
emmagatzemada en aquest gegant com flotant que és 0,4099999996,
que és prou a prop del nostre propòsits, ara mateix, a 0,41.
I després ja veurem més endavant, a mesura que continuar passant per sobre del programa,
després aquí, n s'ha convertit en arrodonida i centaus s'ha convertit en 41.
Gran.
Així que sabem que el treball de la nostra arrodoniment.
Sabem que tenim la nombre correcte de centaus,
així que sabem que això és no és realment el problema.
>> Així que seguim pas a pas en aquest programa.
Anem aquí.
I així, després d'aquesta línia de codi, ha de saber quants quarts que tenim.
Fem un pas més.
I vostè veure el que fem, de fet, tenim un sol trimestre perquè hem restem 25
del nostre valor inicial de 41.
I tenim 16 esquerra per als nostres centaus.
>> Tothom entén com el programa està intensificant a través
i per què centaus ara s'ha convertit en 16 i per què, ara, les monedes s'ha convertit en 1?
Està tot el món seguint aquesta lògica?
Fresc.
Així que a partir d'aquest punt, el de treball del programa, no?
Sabem que està fent exactament el que volem que ho faci.
I no ho vam fer realitat han d'imprimir, oh, què
és cèntims en aquest punt, el que és les monedes en aquest punt.
>> Seguim passant pel programa.
Pas acabat.
Fresc.
Repassem monedes de deu centaus.
Gran.
Veiem que es pren de $ 0.10 per a un cèntim.
I ara tenim dues monedes.
Això és correcte.
>> Repassem penics i veiem que que ens queda més centaus.
Hmm, això és estrany.
Fins aquí, al programa, que se suposava haver restat meus penics.
Potser jo no estava fent que la línia dreta.
I per desgràcia, es pot veure aquí, perquè sabem
que estem trepitjant a través de línies 32 i 33,
aquí és on el nostre programa inadequadament van tenir les variables corren.
Així que podem mirar i veure, oh, Estic restant centaus aquí,
però no estic realment afegir a la meva valor de la moneda.
Estic afegint a centaus.
I jo no vull afegir a centaus, vull afegir a monedes.
Així que si canviem això a monedes, tenim un programa de treball.
Puc córrer check50.
Vostè només pot sortir del BGF dret aquí i després executar check50 nou.
Jo només podia fer això.
He de fer cobdiciós.
0.41.
I aquí, és la impressió la resposta correcta.
>> Així com vostès poden veure, el BGF és una eina molt potent
per quan tenim tant codi passant i tantes variables
que és difícil per a nosaltres, com un ésser humà, no perdre de vista.
L'equip, en el BGF depurador, té la capacitat
fer un seguiment de tot.
Ja ho sé, en Visionaire, vostès probablement podria haver afectat alguns errors de segmentació
a causa que s'estava executant fora dels límits de la matriu.
En l'exemple de César, això és exactament el que he implementat aquí.
>> Així que em vaig oblidar de comprovar ¿Què passaria si jo
no tenir dos arguments de la línia d'ordres.
Simplement no em poso en el registre d'entrada.
I així, si em quedo Debug-- configurar meu punt de ruptura a la dreta allà.
Corro de depuració.
>> D'ACORD.
Sí.
Així que en realitat, el BGF se suposava m'han dit que hi ha
Va ser un error de segmentació allà.
No sé el que estava passant allà mateix, però quan em vaig trobar amb ell,
que estava treballant.
Quan s'executa a través de línies de codi i BGF podria deixar de cop i volta sobre tu,
puja i mira el que és l'error vermell.
L'hi diré, bé, tingut un error de segmentació,
el que significa que va intentar accedir espai en una matriu que no existia.
Sí.
>> Així que en el següent problema estableixi aquesta setmana, nois
probablement tindrà una gran quantitat de Variables surant al voltant.
No va a estar segur del que tots ells signifiquen en un moment determinat.
Així GDB realment l'ajudarà a esbrinar el que tots ells estan igualant
i ser capaç de veure que visualment.
Hi ha algú confós sobre com res d'això estava treballant?
Fresc.
Tot bé.
Així que després d'això, estem anar a bussejar en dret
en són quatre diferents tipus de classes per a aquesta setmana.
Quants de vostès, primer sobretot, abans de començar,
han llegit tota l'especificació per pset3?
D'ACORD.
Estic orgullós de vosaltres.
Això és com la meitat de la classe, que és significativament més que l'última vegada.
>> Així que això és genial, perquè quan parlem sobre el contingut
en lecture-- o ho sento, en secció- m'agrada
relacionar molt d'això de nou al que el conjunt de processadors és
i com voleu implementar això en el seu conjunt de processadors.
Així que si vostè ve tenint llegir l'especificació, que va
ser molt més fàcil perquè vostè entengui el que estic parlant quan dic,
oh bo, això podria ser una realitat bon lloc per posar en pràctica aquest tipus.
Així que aquells de vostès que han llegit el spec saber que, com a part del seu conjunt de processadors,
vostè va a haver de escriure un tipus d'espècie.
Així que això pot ser molt útil per a molts de vostès avui.
>> Així que anem a començar amb, en essència, el tipus més senzill
de gènere, l'ordenació per selecció.
L'algorisme típic per com ens agradaria anar sobre això
és-- David va passar per aquests tots en conferència, així que passaré ràpidament al llarg
aquí-- és essencialment, que tenir una matriu de valors.
I després trobar el menor valor sense classificar
i canvies aquest valor amb el primer valor sense classificar.
I després et quedes amb la repetició amb la resta de la seva llista.
>> I aquí hi ha una explicació visual de la manera com havia de funcionar.
Així, per exemple, si haguéssim de començar amb una sèrie de cinc elements, l'índex
0 a 4, amb 3, 5, 2, 6, i 4 valors col·locat en el array-- així que ara,
només assumirem que tots estan sense classificar
perquè no hem provat el contrari.
>> Llavors, com una tria tipus faria la feina és que ho faria primer
executar a través de la totalitat de la matriu sense classificar.
Seria seleccionar el valor més petit.
En aquest cas, 3, a la dreta Ara, és el més petit.
Es posa a 5.
No, 5 no és gran no sigui: o ho sento, no és inferior a: 3.
Per tant el valor mínim és encara 3.
I llavors s'arriba a 2.
L'equip considera que, oh, 2 és inferior a 3.
2 ha d'ésser ara el valor mínim.
I així febrer swaps amb aquest primer valor.
>> Així que després d'una passada, nosaltres de fet veiem que el 2 i el 3 s'intercanvien.
I només continuarem fent això de nou amb la resta de la matriu.
Així que anem a simplement executar a través de els últims quatre índexs de la matriu.
Veurem que 3 és el següent valor mínim.
Així que anem a canviar això amb 4.
I llavors només anem a mantenir que travessa fins que, finalment, es
arribar a un arranjament ordenat en el qual 2, 3, 4, 5, i 6 es tot Tipus.
Tots entenen la lògica de com funciona una selecció espècie?
>> Només tens algun tipus d'un valor mínim.
Ets fer el seguiment del que és.
I cada vegada que el trobes, canvies el amb el primer valor al array--
o bé, no és la primera value-- el següent valor en la matriu.
Fresc.
>> Així com vostès classe de va veure des d'un breu cop d'ull,
anem a Pseudocodi això.
Així que si vostès a la part posterior voleu formar un grup, tothom en una taula
poden formar un petit company, vaig per donar-li tipus com tres minuts
simplement parlar a través de la lògica, en anglès,
de com podríem ser capaços d'implementar pseudocodi per escriure una ordenació per selecció.
I hi ha dolços.
Si us plau vingui i aconseguir caramels.
Si estàs a la part de darrere i desitja dolços, puc tirar caramels a vostè.
En realitat, fer fresc usted--.
Oh, ho sento.
D'ACORD.
>> Així que si ens agradaria, ja que una classe, escriure pseudocodi
per com es podria acostar- aquest problema, tot just sent lliure.
Aniré al seu voltant i, per tal, demani grups
per a la següent línia de el que hauríem d'estar fent.
Així que si vostès volen començar fora, ¿què és el primer
Què fer quan vostè està tractant de posar en pràctica una forma de resoldre aquest programa
per ordenar selectivament una llista?
Anem a suposar que tenir una matriu, ¿d'acord?
>> AUDIÈNCIA: Vols crear alguns espècie de [inaudible] que ets
corrent a través de tota la seva gamma.
>> ANDI Peng: Correcte.
Així que vas a voler repetir a través de cada espai, no?
Tan gran.
Si vostès volen que em donés el juntament line-- sí, a la part posterior.
>> AUDIÈNCIA: Fes- sobretot per als més petits.
>> ANDI Peng: No.
Així que volem anar a través i verifiqui veure el que el valor mínim és, oi?
Vaig a abreujar que a "min".
Què és el que vostès volen fer després has trobat el valor mínim?
>> AUDIÈNCIA: [inaudible]
ANDI Peng: ¿Així que vas a voler canviar amb el primer d'aquesta sèrie,
Oi?
Aquest és el principi, que vaig a dir.
Tot bé.
Així que ara que ha canviat el primer un, ¿què és el que vols fer després d'això?
Així que ara sabem que aquest d'aquí ha de ser el valor més petit, no?
Llavors vostè té un descans addicional de la matriu que està sense classificar.
Així que el que vull fer aquí, si nois volen donar-me la següent línia?
AUDIÈNCIA: Llavors vol iterar a través de la resta de la matriu.
ANDI Peng: Sí.
I així ho fa a través de la iteració tipus de implicar que probablement necessitarem?
Quin tipus de--
>> AUDIÈNCIA: Oh, una variable addicional?
ANDI Peng: Probablement una altra per al bucle, oi?
Així que probablement voldrem iterar through-- gran.
I després vas a tornar i Probablement comprovar el mínim de nou,
Oi?
I vostè va a seguir repetint això, perquè els bucles només va
per seguir funcionant, no?
>> Així com vostès poden veure, només tenen un pseudocodi en general
de com volem que aquest programa es vegi.
Aquest reiterar aquí, què fem normalment necessitarà escriure en el nostre codi
si volem recórrer un matriu, quin tipus d'estructura?
Crec que Christabel ja s'ha dit abans.
>> AUDIÈNCIA: Un bucle for.
>> ANDI Peng: Un bucle for?
Exactament.
Així que aquest és probablement Serà un bucle for.
Què és un xec aquí va a entendre?
Normalment, si desitja comprovar si alguna cosa és alguna cosa else--
>> AUDIÈNCIA: Si.
>> ANDI Peng: Un cas, ¿no?
I llavors el bescanvi Aquí, anem a anar més tard, perquè David
passar per que en la conferència també.
I llavors la segona iteració implies--
>> AUDIÈNCIA: Una altra de bucle.
>> ANDI Peng: --another bucle for, exactament.
Així que si estem buscant en aquest correctament,
pot veure que estem probablement va a necessitar un niat bucle for
amb una sentència condicional allà i després una veritable peça de codi que és
canviarà els valors.
Així que en general, que he escrit un codi de pseudocodi aquí.
I llavors estem realment va físicament, com una classe,
tractar d'aplicar això avui.
Tornem a aquest IDE.
>> UH oh.
Per què és que no-- aquí està.
D'ACORD.
Ho sentim, però vaig a tractar d'apropar una mica més.
Som-hi.
Tot el que estic fent aquí és que he creat un programa anomenat "selecció / sort.c."
He creat una sèrie de nou anys valors, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Actualment, com pugui veure, són desordenats.
n serà el nombre que li diu la quantitat de valors
que té en el seu arsenal.
En aquest cas, tenim nou valors.
I només tinc un bucle for aquí que imprimeix la matriu sense classificar.
>> I al final, jo també tinc una per bucle que només imprimeix cap a fora una altra vegada.
Així que en teoria, si aquest programa funciona correctament, al final,
ha de mostrar un imprimeixen bucle for en el qual 1, 2, 3, 4, 5, 6, 7, 8,
9 són tot correctament en ordre.
>> Així que tenim el nostre pseudocodi aquí.
Algú vol A-- Només sóc va a anar demanar volunteers--
digues-me exactament què escriure si volem, en primer lloc, simplement iterar
a través del principi d'aquesta matriu?
Quina és la línia de codi que sóc Probablement necessitarà aquí?
>> AUDIÈNCIA: [inaudible]
>> ANDI Peng: Sí, se sent A-- sento lliure, vostè
no han de suportar up-- sensació llibertat per aixecar la veu una mica.
>> AUDIÈNCIA: Per int i és igual 0--
>> ANDI Peng: Sí, bé.
>> AUDIÈNCIA: i és menor que la longitud de la matriu.
>> ANDI Peng: Així que tingui en la ment aquí, perquè nosaltres
no tenen una funció que ens diu la longitud d'una matriu,
ja tenim una valor que emmagatzema això.
Oi?
Una altra cosa a tenir en mente-- en una matriu
de nou valors, quins són els índexs?
Diguem que aquesta matriu va ser 0-3.
Vostè veu que l'últim índex és en realitat març.
No és 4, tot i que hi ha quatre valors en la matriu.
>> Així que aquí, hem de tenir molta cura del que la nostra condició per a la longitud
va ser.
>> AUDIÈNCIA: ¿No seria n almenys 1?
ANDI Peng: Va n menys 1, exactament.
Té sentit, per què és n menys 1, tothom?
És perquè les matrius són indexats de zero.
Comencen a 0 i s'executen fins an almenys 1.
Sí, és una mica complicat.
D'ACORD.
I llavors--
AUDIÈNCIA: Isnt'1 que ja atesos, però,
per no dir "inferior o igual a "i dir" menys? "
>> ANDI Peng: Aquesta és una molt bona pregunta.
Així que, sí.
Però també, la forma en què estem fer efectiu el dret de comprovar,
cal comparar dos valors.
Així que vostè realment vol sortir de la "a" buit.
Perquè si es compara aquest, no vas
tenir res després comparar, no?
Sí.
Així que i ++.
Anem a afegir els nostres suports a.
Vaja.
Gran.
Així que tenim el començament del nostre bucle exterior.
Així que ara que probablement volem crear una variable per mantenir
pista del valor més petit, no?
Algú vol donar-me la línia de codi que faria això?
Què necessitem si anem voler emmagatzemar alguna cosa?
>> Dreta.
Potser un millor nom perquè seria ser-- "temp" totalment works--
potser una més ben anomenat seria, si volem que el value-- més petit
>> AUDIÈNCIA: Min.
ANDI Peng: min, aquí anem.
min seria bo.
I aquí, què fem que inicialitzar a?
Això és una mica complicat.
A causa que en aquest moment en el a partir d'aquesta matriu,
vostè no ha mirat res, oi?
Llavors, què, de forma automàtica, si estem només en i és igual a 0,
¿Què volem per inicialitzar el nostre primer valor mínim de?
AUDIÈNCIA: i.
ANDI Peng: i, exactament.
Christabel, per què volem per inicialitzar a i?
>> AUDIÈNCIA: Perquè, bé, estem començant amb 0.
Així que perquè no tenim res per comparar a, el mínim va a acabar sent 0.
>> ANDI Peng: Exactament.
Així que ella és exactament correcte.
Com que tenim en realitat no mirat res encara,
no sabem quin és el nostre valor mínim és.
Volem simplement inicialitzar a I, que, actualment, és aquí.
I a mesura que continuem baixar aquesta matriu,
veurem que, amb cada passi addicional, i increments.
I així, en aquest punt, i probablement va
a voler ser el mínim, perquè va a ser el que sigui
és el principi de la matriu sense classificar.
Fresc.
>> Així que ara volem afegir un bucle for aquí això és
va recórrer el sense classificar, o la resta d'aquesta sèrie.
Algú vol donar-me un línia de codi que faria això?
Hint-- Què necessitem ací baix?
¿Què passarà en aquest bucle for?
Sí.
AUDIÈNCIA: Així que ens agradaria tenir un nombre enter diferent,
perquè ens estem quedant per la resta de la matriu en lloc de la i, així que potser
j.
>> ANDI Peng: Sí, j sona bé per a mi.
És igual?
>> AUDIÈNCIA: Llavors seria i + 1, perquè estàs començant en el següent valor.
I després a la end-- així que de nou, j és menys de n menys 1, i després j ++.
ANDI Peng: Gran.
>> I després aquí, anem a voler per comprovar si es compleix la nostra condició,
Oi?
Perquè vols canviar el valor mínim
si en realitat és més petit que el que vostè està comparant a, oi?
Llavors, què anem a voler en aquesta llista?
Comproveu.
Quin tipus de declaració estem probablement anem
tu voleu utilitzar si que vulgueu comprovar alguna cosa?
>> AUDIÈNCIA: Una sentència if.
>> ANDI Peng: Una sentència if.
Així que si: i el que serà la condició que volem a l'interior
de la nostra sentència if?
>> AUDIÈNCIA: Si el valor de j és menor que el valor de I--
>> ANDI Peng: Exactament.
Així que si: pel que aquesta sèrie es diu "matriu".
Gran.
Així que si array-- què va ser això?
Digues-ho de nou.
>> AUDIÈNCIA: Si array-j és menor que matriu-i, llavors canviaria el min.
Així que el mínim seria j.
>> ANDI Peng: Té sentit?
D'ACORD.
I ara aquí, en realitat desitgi implementar el canvi, oi?
Així que recorda, en la conferència, que David, quan ell estava tractant de canviar ell-- del que era
suc de taronja it-- i milk--
>> AUDIÈNCIA: Això era fastigós.
>> ANDI Peng: Sí, això era una mica brut.
Però va ser una bona bonica concepte de temps demostrant.
Així que pensa en els seus valors aquí.
Tens una matriu de minuts, una gran varietat de i,
o el que estàvem tractant de canviar aquí.
I és probable que no es pot abocar en entre si, al mateix temps, oi?
Així que, què anem a haver de crear aquí
per tal d'intercanviar correctament els valors?
>> AUDIÈNCIA: Una variable temporal.
>> ANDI Peng: Una variable temporal.
Així que farem int temp.
Mira, això seria una millor temps A-- Whoa, què va ser això?
D'ACORD.
Així que això hauria estat una millor temps per nomenar el "temp." variables
Així que farem int temp.
Què farem setembre temp igual a aquí?
AUDIÈNCIA: Min?
ANDI Peng: És una mica complicat.
En realitat, no importa al final.
No importa el que per a que triï de canviar de
sempre que vostè està fent segur que ets fer el seguiment del que estàs intercanviant.
>> AUDIÈNCIA: Podria ser array-i.
>> ANDI Peng: Sí, farem array-i.
I llavors quin és la següent línia de codi que volem tenir aquí?
AUDIÈNCIA: array-i és igual array-j.
ANDI Peng: I finalment?
AUDIÈNCIA: array-j és igual array-i.
AUDIÈNCIA: O array-j iguals -array temp-- o, temp.
>> ANDI Peng: OK.
Així que anem a executar això i veure si es va a treballar.
On està això passi?
Oh, això és un problema.
Mira, en la línia 40, que estem tractant d'usar matriu de j?
Però, d'on j només existeixen en?
>> AUDIÈNCIA: En el bucle for.
ANDI Peng: Correcte.
Llavors, què haurem de fer?
>> AUDIÈNCIA: Definir fora ell--
AUDIÈNCIA: Sí, suposo que tens utilitzar una altra sentència if, oi?
Així com, si el minimum-- bé, deixa pensar.
>> ANDI Peng: Nois, tractar per fer una ullada de Let
veiem, el que és una cosa que podem fer aquí?
>> AUDIÈNCIA: OK.
Així que si el mínim no és igual a j-- pel que si el mínim és encara jo--
llavors no hauríem de canviar.
>> ANDI Peng: ¿Això potser i?
Què vol dir aquí?
>> AUDIÈNCIA: O sí, si el mínim no és igual a I, si.
ANDI Peng: OK.
Bé, això resol, una cosa així, els nostres problemes.
Però això encara no resol el problema del que passa si j-- des j
no existeix fora d'ella, el que Com se'ns vol fer amb ell?
Declarar fora?
Anem a tractar d'executar aquest.
UH oh.
La nostra espècie no està funcionant.
>> Com es pot veure, la nostra inicial matriu tenia aquests valors.
I després que hauria de tenir estat en 1, 2, 3, 4, 5, 6, 7, 8, 9.
No està funcionant.
Ahh.
Què fem?
AUDIÈNCIA: Depuració.
ANDI Peng: Molt bé, podem provar això.
Podem depurar.
Reduir una mica.
Anem a posar el nostre punt d'interrupció.
Anem com-- acord.
>> Així doncs ja sabem que aquestes línies, 15 a 22,
es working-- perquè tot el que estic fent és simplement iterar a través i printing--
Puc seguir endavant i saltar això.
Anem a començar en la línia 25.
Oop, deixa desfer-me d'això.
>> AUDIÈNCIA: Llavors el punt d'interrupció on comença la depuració?
ANDI Peng: O parades.
AUDIÈNCIA: O parades.
ANDI Peng: Sí.
Podeu configurar diversos punts d'interrupció i només pot saltar d'una a una altra.
Però en aquest cas no sabem on l'error està succeint.
Així que només volem començar de dalt a baix.
Sí.
D'ACORD.
>> Així que aquesta línia d'aquí, podem intervenir.
Es pot veure aquí baix, tenim una matriu.
Aquests són els valors que es troben a la matriu.
Veus això, com l'índex 0, es correspon a la value-- oh,
Vaig a tractar de fer un zoom.
Malauradament, és molt difícil a veure- a l'índex de matriu 0,
tenim un valor de 4 i a continuació, així successivament i així successivament.
Tenim les nostres variables locals.
Ara mateix i és igual a 0, el que volem que sigui.
>> I així seguirem pas a pas a través.
La nostra mínim és igual a 0, que també volem que sigui.
I llavors entrem en el nostre segon per llaç, si array-j és menor de gamma-i,
que no ho era.
Així que vas veure com que ometen sobre això?
>> AUDIÈNCIA: Llavors, si el cas mínim, tot això-- no hauria que
estar dins de la primera bucle for?
ANDI Peng: No, perquè vostè encara vol provar.
Vols fer una comparació cada temps, fins i tot després d'executar a través d'ell.
No només vol fer-ho en el primer pas.
Vols fer-ho amb cada passada addicional de nou.
¿Així que vols comprovar seva condició interior.
Així que només anem a seguir corrent per aquí.
Et vaig a donar una pista nois.
Té a veure amb el fet que quan vostè està comprovant la seva condicional,
vostè no està comprovant per a l'índex correcte.
Així que ara vostè està comprovant índex de matriu de j és menys de matriu
Índex de i.
Però, què estàs fent cap amunt en el principi del bucle for?
No estàs configurant j igual a i?
>> Sí, pel que pot en realitat sortir del depurador aquí.
Així que donem una ullada a la nostra pseudocodi.
Para-- anem a començarà a les i és igual a 0.
Anirem fins an almenys 1.
Anem a veure, què tenim aquest dret?
Sí, això era correcte.
>> Així que aquí dins, estem crearà un valor mínim
i establir que igual a i.
¿Vam fer això?
Sí, ho va fer.
Ara en el nostre interior per bucle, estem farà j és igual a i n almenys 1.
¿Vam fer això?
De fet, ho vam fer.
>> Així que, però, què estem comparant aquí?
>> AUDIÈNCIA: j més 1.
ANDI Peng: Exactament.
I llavors vostè va a voler establir seva mínima igual a j plus 1 també.
Així que em vaig anar a través d'aquesta realitat ràpidament.
Entenen vostès per què és j més 1?
D'ACORD.
>> Així que en el seu conjunt, en el primer pas a través,
el bucle for, per int i és igual a 0, anem a
assumeix això no s'ha canviat encara.
Tenim una gran varietat de, per complet, només quatre elements no ordenats, oi?
Així que volem inicialitzar i igual a 0.
I em va acaba executar aquest bucle.
I així, en la primera passada, anem per inicialitzar una variable anomenada "min"
que també és igual a I, perquè no tenim un valor mínim.
Així que aquesta és actualment igual a 0 també.
I després anem a passar.
I volem repetir.
Ara que hem trobat el que el nostre mínima És a dir, volem recórrer
de nou per veure si es tracta de comparar, oi?
Així j, aquí, es va a la igualtat d'i, que és 0.
I després, si arsenal j més i, que és el que està al costat una altra vegada, com menys
del que el seu mínim actual valor és, que desitja intercanviar.
>> Així que anem a dir que hem té, com, 2, 5, 1, 8.
En aquest moment, i és igual a 0 i j és igual a 0.
I aquest és el nostre valor mínim.
Si varietat j-plus jo-- pel que si el això és després de la qual estem veient
és més gran que l'anterior, que es convertirà en el mínim.
>> Així que aquí veiem que 5 no és menys que això.
Així que va a estar 5.
Veiem que 1 és menor que 2, oi?
Així que ara que sabem que el nostre mínim és serà el valor de l'índex en 0, 1, 2.
Sí?
I després quan arribes aquí, vostè pot canviar els valors correctes.
>> Així que quan vostès simplement van tenir la j abans, no estaven buscant en el
després d'ella.
Estaves mirant el mateix valor, el qual
és per això que no estava fent res.
¿Això té sentit per a tothom, per això necessitem que mai 1 allà?
D'ACORD.
Ara anem a executar a través d'ell per fer Assegureu-vos que la resta del codi és correcte.
Per què és que això passi?
Ah, és el mínim aquí.
Estàvem comparant el valor incorrecte.
Oh no.
>> Ah, sí, aquí estàvem el bescanvi dels valors erronis també.
A causa de que estàvem buscant en i i j.
Aquests són els que marxàvem.
En realitat, volem canviar la mínim, el mínim actual,
amb el que l'exterior és.
I com vostès poden veure a baix aquí, tenim un arranjament ordenat.
Simplement tenia a veure amb el fet que quan
ens anàvem el valors que estàvem comparant,
que no estàvem buscant en els valors correctes.
Estàvem buscant en el mateix aquí, en realitat no és el canvi.
Vostè ha de mirar l'un al costat a ell i després es pot canviar.
Així que això és el que era una mena de molestant el nostre codi abans.
I el que vaig fer aquí ho és tot el depurador podria haver fet per a tu
Jo només ho va fer al tauler, perquè és més fàcil
per veure en lloc de tractar per apropar el depurador.
¿Això té sentit per a tothom?
Fresc.
>> Tot bé.
Podem passar a parlar de notació asimptòtica, que
és només una forma elegant de dir la temps d'execució de tots aquests tipus.
Així que sé David, a la conferència, referit als temps d'execució.
I se'n va anar per tota la fórmula de com calcular els temps d'execució.
No et preocupis per això.
Si vostè és realment curiós sobre com funciona,
no dubti en parlar amb mi després de la secció.
Podem caminar a través d' les fórmules junts.
Però tots vostès tenen per realment saber és que n al quadrat més de 2
és el mateix que n al quadrat.
A causa que el nombre més gran, l'exponent, més creix.
I així, per als nostres propòsits, tots ens preocupem per
és aquest nombre gegant que està creixent.
>> Llavors, quin és el millor dels casos temps d'execució de l'ordenació per selecció?
Si vostè va a tenir per recórrer una llista
i després recórrer la resta de la llista,
Quantes vegades es vostè va a probablement
en el pitjor cas-- al millor dels casos, sorry-- executar a través de?
Potser la millor pregunta és preguntar, quin és el pitjor dels casos
temps d'execució de l'ordenació per selecció.
AUDIÈNCIA: n al quadrat.
ANDI Peng: Ha n al quadrat, dreta.
Així que una manera fàcil de pensar en això és com, qualsevol moment tens dues niat per als bucles,
que serà n al quadrat.
Perquè no només és vostè corrent a través un cop més,
vostè ha de tornar volta i córrer a través d'ell
un cop a l'interior de cada valor.
Així que en aquest cas, s'està executant n temps n al quadrat, que aquests: ho sento,
n vegades n, que és igual a n al quadrat.
>> I espècie és també una mica únic en el sentit
que no importa si aquests valors ja estan en ordre.
Encara va a executar a través de totes maneres.
Diguem que aquest va ser d'1, 2, 3, 4.
Independentment de si era o no en fi, encara hauria córrer a través de
i encara comprovat el valor mínim.
Hi hauria fet el mateix nombre de xecs
cada vegada, fins i tot si en realitat no tocar res.
>> Així doncs, en aquest cas, el millor i el pitjor temps d'execució són en realitat equivalents.
Així que el temps d'execució esperat d'ordenació per selecció,
que designem pel símbol de theta, theta, en aquest cas,
també seria n al quadrat.
Els tres d'ells serien n al quadrat.
Està clar per què tothom la durada és n al quadrat?
>> Tot bé.
Així que només vaig a córrer ràpidament per la resta dels gèneres.
L'algoritme per bombolla sort-- recordi,
aquesta va ser la primera David es va acostar a la conferència.
Essencialment, vostè camina a través de la llista sencera
i que acaba de swap-- comparar els dos alhora.
I si un és més gran, el que només els intercanviar.
Així que si aquests són majors, que canviaria.
Tinc oficial aquí.
>> Així que anem a dir que tenia 8, 6, 4, 2.
Es podria comparar el 8 i un 6.
Vostè necessitaria per intercanviar-les.
Es podria comparar el 8 i un 4.
Vostè necessitaria per intercanviar-les.
Si ha de canviar el 8 i el 2, canviï ells també.
Així doncs, en aquest sentit, es pot veure, jugat a terme durant un llarg període de temps,
com els valors de tipus de bombolla els extrems, la qual cosa és per això que en diuen
ordenament de bombolla.
>> Ens agradaria simplement executar a través de nou en la nostra segona passada, i el nostre tercer pas,
i el nostre quart passi.
Essencialment, bombolla espècie només s'executa fins que no faci més swaps.
Així que en aquest sentit, això és només el pseudocodi general per a això.
No es preocupi, aquests seran tots en línia.
No hem d'anar realment sobre això.
>> Acabem inicialitzem un comptador variable que comença en 0.
I recórrer tota la matriu.
I si un valor és-- si això valor és més gran que aquest valor,
ves per intercanviar-les.
I llavors no ets més que seguirà endavant.
I vas a explicar.
I només continuarem fent això mentre que el comptador és més gran
que 0, el que significa que cada vegada que ha de canviar,
vostè sap que vol anar esquena i pots tornar a intentar-ho.
Vostè vol mantenir la comprovació fins que vostè sàpiga que vostè no ha de canviar ja.
>> Llavors, què són els millors i pitjors cas els motors d'execució d'ordenament de bombolla?
I hint-- això és realment diferent des de la selecció del tipus en el sentit
que aquestes dues respostes no són iguals.
Penseu en el que succeiria en un cas si ja es va solucionar.
I pensar en el Què passaria si fos
en el cas en què no es va solucionar.
I vostè pot classe de córrer a través de per què està succeint.
Et vaig a donar els nois, com, 30 segon per pensar en això.
>> D'ACORD.
Algú té una pista sobre el que el pitjor dels casos el temps d'execució de la bombolla de tipus és?
Sí.
>> AUDIÈNCIA: Seria, com, n vegades n almenys 1 o alguna cosa així?
Igual que, cada vegada que s'executa, és només, com, un intercanvi menys
que tot el que era.
>> ANDI Peng: Sí, així vostè és del tot encertada.
I aquest és un cas en què el resposta era en realitat més complexa
que el que hem de donar.
Així que va a run-- estic va a esborrar tot això aquí.
És bo tothom?
Puc esborrar això?
D'ACORD.
Vostè va a executar a través de n vegades la primera vegada, oi?
I ells van a executar a través de n almenys 1 la segona vegada, oi?
I després vas a mantenir va, n mina 2, etcètera.
David va fer això en una conferència, en què, si s'ha afegit a tots aquests valors,
vostè aconsegueix una cosa que és com-- yeah-- més de 2, el que redueix essencialment només
cap avall per n al quadrat.
Vostè va a obtenir una fracció rar aquí.
I així, només sé que el n al quadrat sempre
té prioritat sobre la fracció.
I així, en aquest cas, el pitjor temps d'execució seria n al quadrat.
Si va ser en descens ordre, crec, que
haver de fer un intercanvi cada vegada.
>> Quin seria, potencialment, el millor temps d'execució cas?
Diguem, si la llista ja estava per tal, quin seria el temps d'execució?
>> AUDIÈNCIA: n.
ANDI Peng: És n, exactament.
I per què és n?
AUDIÈNCIA: Com que vostè acaba de haurà de comprovar en cada vegada.
ANDI Peng: Exactament.
Així doncs, en la millor execució possible, si aquesta llista ja estava
sorted-- diguem 1, 2, 3, 4-- vostè acaba de passar, que li tira,
veuries, oh, tots ells resulten.
Jo no havia de canviar.
He acabat.
Així que en aquest cas, és només n o el nombre de passos que acaba de
haver de comprovar en la primera llista.
>> I després, ara colpegem ordenació per inserció, on
l'algoritme és essencialment divideix en una part ordenada i sense classificar.
I llavors un per un, els valors no classificats són
inserit en el seu apropiada posicions en el principi de la llista.
>> Així, per exemple, tenim una Llista de 3, 5, 2, 6, 4 de nou.
Sabem que és actualment sense classificar perquè acabem de
començat mirar-lo.
Fem una ullada i sabem que el primer valor s'ordena, oi?
Si només està buscant en una sèrie de mida d'un, vostè sap que està ordenada.
>> Així que sabem que el altres quatre són sense classificar.
Anem a través i veiem aquest valor.
Tornem.
Veure que el valor de 5?
Fem una ullada.
Comparem a 3.
Sabem que és més gran que 3, pel que sabem que això està solucionat.
Així que ara sabem que els dos primers s'ordenen i els tres últims no ho són.
>> Fem una ullada a 2.
En primer lloc, comprovem amb 5.
És menor que 5?
No ho es.
Així que hem de seguir mirant cap avall.
Després de comprovar març 2.
És menor que?
No.
Així que ja saps una 2 ha d'ésser inserit a la part davantera i 3 i 5
tots dos han de ser expulsats.
Feu això de nou amb 6 i 4.
I nosaltres només seguim comprovant en essència, on acabem de comprovar, verificar, comprovar.
I fins que estigui a la dreta posició, tipus de sol
inserir-lo en la posició correcta, que és on el nom del vi.
>> Així que això és només l'algorisme, pseudocodi per se, una mena de,
sobre com anàvem a posar en pràctica un tipus d'inserció.
Pseudocodi és aquí.
Tot està en línia.
No us preocupeu si vostès són tractant de copiar això.
Així que una vegada més, el mateix pregunta-- seria el millor i el pitjor dels temps d'execució
per a l'ordenació per inserció?
És molt similar a l'última pregunta.
Et vaig a donar els nois, com, 30 segon per pensar en això també.
>> OK Algú vol dóna'm el pitjor temps d'execució?
Sí.
>> AUDIÈNCIA: n al quadrat.
>> ANDI Peng: Ha n al quadrat.
I per què és n al quadrat?
>> AUDIÈNCIA: Perquè en ordre invers, vostè té
de passar per n vegades n, que aquests:
ANDI Peng: Sí, exactament.
Així mateix que en l'ordenament de bombolla.
Si aquesta llista està en ordre descendent, ets
va a haver de comprovar primer una vegada.
I a continuació, amb cada valor addicional, vostè és
va a haver de comprovar que en contra cada valor únic, no?
I així, en conjunt, que faràs un moment n passar a un altre n passen, que
està n al quadrat.
I el millor dels casos?
Sí.
>> AUDIÈNCIA: n menys 1, ja que el primer ja s'eleva al quadrat.
>> ANDI Peng: Així, a prop.
La resposta és en realitat n.
Perquè si bé la primera és ordenats, pot ser que no es actually--
només vam tenir sort, en aquest exemple, que 2
va passar a ser el número més petit.
Però això no sempre serà el cas.
Si 2 ja és ordenat al principi però et veus i hi ha un 1 aquí,
l'1 va topar.
I que va a acabar sent copejat de totes maneres.
>> Així que en el millor dels casos, en realitat és només serà n.
Si vostè té 1, 2, 3, 4, 5, 6, 7, 8, ets
va executar a través de aquesta llista tota vegada
comprovar per veure si tot està bé.
Estan tots clar en funcionament temps de la selecció així?
Sé que estic passant aquests realment ràpid.
Però només sé que si es coneix el conceptes generals, ha de ser bo.
D'ACORD.
Així que només et donaré nois potser, com, un minut per parlar amb els seus veïns
en el que són només algunes de les principals diferències
entre aquests tipus de classes.
Anem a repassar que aviat.
AUDIÈNCIA: Oh, OK.
ANDI Peng: Sí.
D'ACORD.
Fresc, anem novament les com a classe.
D'ACORD.
Així que això era una mena de pregunta oberta en el sentit
que hi ha un munt de respostes a ells.
I anem a repassar alguns d'ells breument.
Jo només volia aconseguir que els nois pensant en el diferenciat
els tres tipus de classes.
I vaig sentir, també, una gran pregunta-- què ordenament per barreja fer?
Molt bona pregunta, perquè això és el que estem cobrint següent.
>> Així ordenament per barreja és la un tipus que funciona
molt diferent als altres tipus.
Com vostès poden veure- va fer David aquesta demo
on tenia tot el fresc sorolls de veure com es fusionen
espècie va córrer, com, infinitament més ràpid que els altres dos tipus?
D'ACORD.
Així que això és degut a la fusió classe implementa aquesta bretxa
i conquerir el concepte que hem parlat molt en conferència.
En aquest sentit que ens agrada treballar més intel·ligent, no més difícil, quan es divideix
i conquerir problemes, i trencar- baix, i després posar-los junts,
bones coses sempre succeeixen.
>> Així que la forma en què es fusionen treballa espècie essencialment
és què es divideix una array sense ordenar a la meitat.
I llavors té dues meitats de matrius.
I simplement ordena aquestes dues meitats.
Simplement segueix dividint a la meitat, en mitjana, enmig fins que tot s'ordena
i després recursivament posa tot junt.
>> Així que això és molt abstracte.
Així que això és només una mica de pseudocodi.
¿Això té sentit en la forma en què s'està executant?
Així que diguem que vostè té una arranjament de n elements, oi?
Si n és menor que 2, pot tornar.
Perquè vostè sap que si hi ha només una cosa, ha de ser ordenada.
Si no, s'ordena la meitat esquerra, i després ordenar la meitat dreta,
i després combinar.
>> Així, mentre que es veu molt fàcil, en la realitat, pensant que és
una mica difícil. Perquè vostè és com, bé, això és una cosa que s'executa en si mateix.
Oi?
S'executa en si mateix.
Així que en aquest sentit, David va tocar sobre la recursivitat a classe.
I això és un concepte parlarem més.
És que això, aquestes dues línies aquí, en realitat és només el programa
dient que s'executi en si amb diferent entrada.
Així que en lloc de córrer en si amb la totalitat de n elements,
es pot descompondre en el meitat esquerra i la meitat dreta
i després tornar a executar.
>> I després veurem visualment, perquè sóc un aprenent visual.
Funciona millor per a mi.
Així que anem a veure un exemple visual aquí.
>> Diguem que tenim una matriu, de sis elements, 3, 5, 2, 6, 4, 1, no ordenats.
Molt bé, hi ha molt en aquesta pàgina.
Així que si vostès poden mirar el primer pas aquí, 3, 5, 2, 6, 4, 1,
es pot dividir per la meitat.
Vostè té 3, 5, 2, 6, 4, 1.
Vostè sap que aquests aren't-- vostè no sé si estan ordenats o no,
de manera que mantenir el seu desglossament, al mig, al mig, al mig, fins que finalment,
només té un element.
I un element sempre està ordenada, oi?
>> Així que sabem que 3, 5, 2, 4, 6, 1, per si mateixos, són ordenats.
I ara podem tornar a posar-los junts.
Així sabem que el 3, 5.
Posem les juntes.
Sabem que és ordenada.
Els 2 segueix allà.
Podem posar el 4 i el 6 junts.
Sabem que això es va solucionar, així que vam posar que junts.
I l'1 és allà.
>> I llavors vostè acaba de veure aquestes dues meitats aquí.
Vostè té el 3, 5, 2, 2, 3, 5.
Només pot comparar la a partir de tot.
Perquè vostè sap que això està ordenada i vostè sap que això està solucionat.
Així que vostè ni tan sols ha de comparar el 5, que acaba de comparar el 3.
I el 2 és menor que 3, per la saps 2 han d'anar al final.
>> El mateix allà.
L'1 ha d'anar aquí.
I després quan es posarà aquests dos valors junts,
vostè sap que això està ordenada i vostè sap que el que es va solucionar.
Així llavors l'1 i el 2, l'1 és inferior a 2.
Això et diu que l'1 ha d'anar al final d'aquest
sense mirar si més no a 3 o 5.
I després el 4, només pot xec, que va a la dreta aquí.
Vostè no ha de mirar el 5.
El mateix amb el 6.
Vostè sap que el 6-- només no necessita ser mirat.
>> I així, d'aquesta manera, vostè és simplement estalviant-
una gran quantitat de passos quan vostè està comparant.
Vostè no ha de comparar cada element contra altres elements.
Vostè acaba de comparar contra els que vostè necessita per comparar contra.
Així que això és una cosa d'un concepte abstracte.
No us preocupeu si no és bastant colpejar la seva dreta encara.
Però, en general, això és com una combinació de tipus funciona.
Preguntes, preguntes ràpides, abans de passar?
Sí.
>> AUDIÈNCIA: Llavors vostè diu que vostè pren l'1, i després el 4 i el 6
i posar-los en.
Així que no són those-- no estan que mirar-los
com a elements separats, no com el tot?
ANDI Peng: Sí.
Així que el que està passant és que, bàsicament,
estan creant una nova gamma de la marca.
Així que ja saps que, aquí, tinc dues matrius de mida 3, oi?
Així que ja saps que el meu matriu ordenada necessita tenir 6 elements.
Així que vostè acaba de crear una nova quantitat de memòria.
Així que vostè és una mena sent un malbaratament de la memòria,
però això no importa perquè és molt petita.
Així que ens fixem en l'1 i ens fixem en el 2.
I vostè sap que l'1 és inferior a 2.
Així que ja saps que 1 ha d'anar en el començament de tot això.
>> Ni tan sols necessita mirar el 3 i el 5.
Així que ja saps gener hi va.
Llavors, bàsicament, tallar l'1.
És, com, mort per a nosaltres.
Llavors només tenim 2, 3, 5, i després 4 i 6.
I llavors vostè sap això, comparar el 4 i el 2,
oh, el 2 ha d'entrar aquí.
Així que vostè plop del 2 a baix, vostè avantatge apagat.
Llavors només ha el 3 i el 5 en el 4 i el 6.
I et quedes picat fora fins que se'ls posa a la matriu.
>> AUDIÈNCIA: Llavors, no ets més que sempre comparant el [inaudible]?
>> ANDI Peng: Exactament.
Així que en aquest sentit, vostè és simplement comparant, en essència,
un nombre contra l'altre nombre.
I perquè saps que ha ordenat, que
no han de mirar a través de tots els números.
Només has de mirar a la primera.
I llavors vostè pot simplement plop cap avall, perquè saps
pertanyen on han de pertànyer.
Sí.
Bona pregunta.
>> I a continuació, si algun de vostès són una mica ambiciós,
no dubti en mirar aquest codi.
Això és en realitat la implementació física
de com escriuríem fusió tipus.
I vostè pot veure, és molt curt.
Però les idees que hi ha darrere que són bastant complexos.
Així que si tens ganes de dibuixar això en la seva tasca aquesta nit, no dubteu en.
>> D'ACORD.
David també es va acostar això en conferència.
Quins són el millor cas temps d'execució, pitjors temps d'execució de casos,
i els temps d'execució previstos de fusió tipus?
Un parell de segons per pensar.
Això és bastant difícil, però una mica intuïtiva si es pensa en això.
Tot bé.
>> AUDIÈNCIA: És el pitjor dels casos n log n?
ANDI Peng: Exactament.
I per què és n log n.
>> AUDIÈNCIA: ¿No és perquè es converteix en exponencialment més ràpid,
així que és com una funció de la qual en comptes de ser n
quadrat o alguna cosa així?
ANDI Peng: Exactament.
Així que la raó per què el temps d'execució en aquest registre és n
n és porque-- ho estàs fent en tots aquests passos?
No ets més que tallar per la meitat, no?
I així, quan estem fent registre, tot el que està fent
es dividir un problema en un mitjà, al mig, en un mitjà, en més de meitats.
I en aquest sentit, pot espècie d'eliminar el model lineal
que hem estat utilitzant.
Perquè quan picar coses de la mitjana, que és un registre.
Això és només la matemàtica manera de representar-lo.
>> I, finalment, al final, ets només fer una última passada a través
posar tot en ordre, no?
I pel que si vostè només ha de comprovar una cosa, això és n.
I pel que és classe de multiplicant els dos junts.
Així que és com si tinguessis aquesta final comprovar N aquí amb un registre de n
fins aquí.
I si es multiplica ells, això és n log n.
>> I així, el millor dels casos i el pitjor cas i espera que es tot n log n.
És també com una altra espècie.
És com una mena de selecció en el sentit que
no importa el que el seu llista és, que només va
a fer el mateix cada vegada.
D'ACORD.
Així com vostès poden veure, tot i que els gèneres que ens hem anat through-- n
quadrat, no és molt eficient.
I fins i tot aquest n log n és no és el més eficient.
Si vostès són curiosos, hi ha mecanismes d'ordenació
que són tan eficients que són gairebé essencialment pla en temps d'execució.
>> Tens algun log n de.
Tens algun registre de log n de.
No toquem sobre ells en aquesta classe en aquest moment.
Però si vostès són curiosos, no dubti a google, el que és
els mecanismes de classificació més eficient.
No ho sé, hi ha alguns realment divertits,
com-- hi ha alguna cosa de veritat els divertits que la gent fa.
I un es pregunta com Alguna vegada has pensat en això.
Així google, si tens una mica de recanvi temps, d'ara endavant, quins són algunes maneres divertides
que persones--, així com persones ways-- eficients
han estat capaços de posar en pràctica les classes.
D'ACORD.
I aquí és només una mica de pràctica taula.
Sé que tots vostès, abans d'aquesta prova 0, estarà a la seva habitació, probablement tractant
memoritzar això.
Així que això és bo aquí per a vostès.
Però no us oblideu la lògica que made-- ¿Per què aquests números estaven passant.
Si sempre estàs perdut, simplement fer Assegureu-vos de saber el que els tipus són.
I es pot executar a través de en la teva ment
esbrinar per què els respostes són aquestes respostes.
>> Tot bé.
Així que anem a moure en, finalment, a la recerca.
Perquè com els de vostè que han llegit el conjunt de processadors,
la recerca és també part de El problema d'aquesta setmana posa.
Se li demanarà a aplicar dos tipus de cerques.
Es tracta d'una recerca lineal i un és una recerca binària.
>> Així que la recerca lineal és bastant fàcil.
El que desitja és buscar elements d'una llista per veure si vostè ho aconsegueix.
Només has de recórrer.
I si és igual a alguna cosa, vostè pot tornar-lo, oi?
Però el que estem més interessat en parlar de
és la recerca binària, la dreta, que és el dividir i conquerir mecanisme que
David estava demostrant en la conferència.
>> Recordeu l'exemple guia de telèfons que segueix l'educació de,
la qual ell va lluitar tipus de una mica en aquest últim any,
on es divideix el problema en el medi, al mig, al mig, una i altra vegada,
fins a trobar el que estàs buscant?
I tens la temps d'execució d'això també.
I vostè pot veure, és significativament més eficient
que qualsevol altre tipus de cerca.
>> Així que la forma en que anàvem a anar sobre la implementació d'una recerca binària
És a dir, si teníem una matriu, índex de 0 a 6, set elements,
podem mirar al medi, dreta- ho sento, si la nostra pregunta primer--
si volem fer la pregunta de, té la matriu conté l'element de 7,
òbviament, sent els éssers humans, i que té com un petit arsenal, és fàcil per a nosaltres
dir que sí.
Però la manera d'implementar un binari Cerca seria buscar en el medi.
>> Sabem que l'índex 3 és el medi, ja que
saben que hi ha set elements.
Quin 7 dividit per 2?
Vostè pot tallar aquest extra 1.
Tens 3 en el medi.
Així que és conjunt de 3 igual a 7?
No es tracta, no?
Però podem fer un parell de xecs.
És gamma de 3 a menys de 7 o és gamma de 3 més gran que 7?
>> I sabem que és menys de 7.
Així que sabem que, oh, ha no estar a la meitat esquerra.
Sabem que ha de ser en la meitat dreta, no?
Així que només podem tallar la meitat de la matriu.
Ni tan sols hem de veure-ho mai més.
Perquè sabem que la meitat del nostre problema--
sabem que la resposta està en la meitat dreta del nostre problema.
Així que només ens fixem en això ara.
>> Així que ara ens fixem en el mitjà del que queda.
Aquest índex maig.
Fem el mateix xec de nou i veiem que és més petit.
Així que mirem a l'esquerra d'això.
I llavors veiem que xec.
És el valor de la matriu en índex de 4 igual a 7?
Ho és.
Així que podem tornar cert, perquè trobem el valor a la nostra llista.
La manera en què jo vaig passar per Això té sentit per a tothom?
D'ACORD.
Et vaig a donar nois potser, com, tres, quatre minuts per esbrinar
com això en pseudocodi.
>> Així que imagino que et vaig demanar que escriure una funció anomenada de recerca () que retorna
un valor, un valor booleà, això era cert o false-- com,
cert si vostè va trobar el valor, false si no ho vas fer.
I llavors eres aprovada en el valor que
estaves buscant en valors, que és la array-- oh, definitivament vaig posar
que en el lloc equivocat.
D'ACORD.
De tota manera, això hauria de tenir estat a la dreta dels valors.
I després int n és el nombre d'elements en la matriu.
Com faria vostè per tractar pseudocodi per a aquest problema en?
Et vaig a donar a tipus com tres minuts per fer això.
No, crec que hi ha only-- sí, n'hi ha un just aquí.
AUDIÈNCIA: Puc?
ANDI Peng: Sí, el tens.
És que el treball?
D'acord, guai.
>> D'ACORD.
Totes les persones adequades, estem frenarà en.
D'ACORD.
Així que suposem que tenim aquesta bella petita matriu amb n valors en el mateix.
Jo no dibuixar les línies.
Però, com podem anar sobre tractant d'escriure això?
Algú vol dóna'm la primera línia?
Si vol donar-me la primera línia d'aquest pseudocodi.
>> AUDIÈNCIA: [inaudible]
AUDIÈNCIA: El que vol iterar through--
AUDIÈNCIA: Només un altre bucle for?
AUDIÈNCIA: --per.
>> ANDI Peng: Així que aquest és una mica complicat.
Penseu sobre-- desitja per seguir funcionant aquest bucle
una i altra vegada fins quan?
>> AUDIÈNCIA: Fins al [inaudible] valor és igual a aquest valor.
ANDI Peng: Exactament.
Així que vostè pot en realitat només write-- fins i tot podem simplificar més.
Només podem fer un bucle while, oi?
Així que vostè pot simplement tenir loop-- sabem que es tracta d'un temps.
Però per ara, em vaig dir "bucle" - a través de què?
Loop until-- ho és la nostra condició de finalització?
Crec que el vaig escoltar.
Vaig sentir a algú dir que.
>> Audiència: Els valors equivalen a mitjà.
ANDI Peng: Digues-ho una altra vegada.
AUDIÈNCIA: O bé, fins que el valor que està buscant
per és igual al valor mitjà.
>> ANDI Peng: ¿I si no hi és?
Què passa si el valor que està buscant per no és en realitat en aquesta sèrie?
AUDIÈNCIA: Tornarà 1.
>> ANDI Peng: Però, què és el que volem bucle fins si tenim una condició?
Sí.
>> AUDIÈNCIA: Fins que no hi hagi un sol valor?
ANDI Peng: Vostè pot recórrer until-- així que vostè sap que vostè és
tindrà un valor màxim, no?
I saps que tenir un valor mínim, no?
Perquè també, això és una cosa Em vaig oblidar de dir abans,
que alguna cosa que és crític sobre la recerca binària
és que la matriu ja està ordenat.
Perquè no hi ha forma de fer això si que són valors simplement a l'atzar.
Vostè no sap si un és més gran que l'altra, no?
>> Així que ja saps que el seu màxim i seus minuts són aquí, oi?
Si vostè va a ser l'ajust el seu màxim en els seus minuts i els mid--
anem a suposar que la seva mitjans valor és aquí-- dret
vas a bàsicament bucle fins al seu mínim és
gairebé el mateix que el seu màxim, a la dreta, o si el seu màxim no és el mateix que el min.
Oi?
Perquè quan això passa, vostè sap que que finalment ha colpejat el mateix valor.
¿Així que vols bucle fins el min és menor o igual A-- perdó,
no menys d'o igual a, l'altra forma és around-- max.
>> ¿Això té sentit?
Vaig prendre un parell d'intents per obtenir aquest dret.
Però bucle fins al seu valor màxim és essencialment gairebé menys
o igual que el mínim, no?
Això és quan vostè sap que ha convergit.
AUDIÈNCIA: Quan el seu màxim valor sigui inferior al mínim?
ANDI Peng: Si es manté ajustant-, que
és el que ens anem estar fent en aquest.
Això té sentit?
Mínim i màxim són només sencers que som, probablement,
voldrà crear per mantenir la pista d'on estem buscant.
A causa de que existeix la matriu independentment del que estem fent.
Igual, que no som en realitat físicament tallant la matriu, no?
Estem ajustant on estem buscant.
Això té sentit?
>> AUDIÈNCIA: Sí.
>> ANDI Peng: OK.
Així que si aquesta és la condició per al nostre bucle, ¿Què és el que volem dins d'aquest bucle?
Què anem a voler fer?
Així que ara mateix, tenim un màxim i un mínim, a la dreta,
probablement creat per aquí en algun lloc.
Anem a probable que desitgi trobar un mitjà, no?
Com serem capaç de trobar el mitjà?
Quina és la mathematical--
AUDIÈNCIA: Max plus min dividit per 2.
ANDI Peng: Exactament.
Això té sentit?
I és el que vostès veig per què no acaba de servei- per què vam fer això
en lloc de fer simplement n dividit per 2?
És perquè n és un valor això seguirà igual.
Oi?
Però a mesura que ens adaptem la nostra mínim i valors màxims, que canviaran.
I com a resultat, la nostra mitjana canviarà també.
Així que per això volem per fer això aquí.
D'ACORD.
>> I després, ara que que hem trobat our-- si.
>> AUDIÈNCIA: Només un pregunta-- ràpida quan dius mínim i màxim,
estem assumint que ja està ordenada?
>> ANDI Peng: Sí, això és en realitat un condició prèvia per a una recerca binària,
que vostè ha de saber que està ordenada.
Quina és la raó per classe, vostè escriu en el seu problema ja davant de la seva recerca binària.
D'ACORD.
Així que ara que sabem que el nostre punt mig És a dir, què és el que vols fer aquí?
>> AUDIÈNCIA: Volem comparar que a l'altra.
ANDI Peng: Exactament.
Així que anem a comparar mitjan valor, no?
I què diuen nosaltres quan comparem?
Què és el que volem fer després?
>> AUDIÈNCIA: Si el valor és més gran dels mitjans, volem tallar-lo.
ANDI Peng: Exactament.
Així que si el valor és més gran dels mitjans, estem
voldrà canviar aquests Maxes mínim i, oi?
Què és el que volem canviar?
Així que si coneixem el valor està en algun lloc aquí, el que hem de fer per canviar?
Volem canviar la nostra mínima per a ser intervinguts, oi?
I després una altra cosa, si és en aquest mitjà, ¿què és el que volem canviar?
>> AUDIÈNCIA: La seva màxima.
ANDI Peng: Sí.
I després et vas mantenir bucle, oi?
Perquè ara, després d'una iteració a través, tens un màxim aquí.
I llavors vostè pot tornar a calcular una mitjana.
I llavors vostè pot comparar.
I seguiràs endavant fins que els minuts i els Maxes
essencialment han convergit.
I això és quan se sap que has arribat a la final de la mateixa.
I ja sigui que ho hagis trobat o vostè no té en aquest punt.
>> Té això sentit per a tothom?
D'ACORD.
Això és molt important, ja que tindrà
escriure això en el codi d'aquesta nit.
Però vostès tenen una molt bona sentit del que hauria d'estar fent,
la qual cosa és bo.
D'ACORD.
Així que tenim al voltant de set minut secció esquerra.
Així que anem a parlar de aquest conjunt de processadors que farem.
Així que el conjunt de processadors es divideix en dues meitats.
La primera mitja implica la implementació d'una troballa
en el qual s'escriu una recerca lineal, 1 recerca binària, i un algoritme de classificació.
>> Així que aquesta és la primera temps en un conjunt de processadors, on
estarem donant-li nois el que es diu codi de distribució, que és el codi
que hem pre-escrita, però només va deixar algunes peces fora
perquè vostè pugui acabar d'escriure.
Així que vostès, si ens fixem en aquest codi, és possible que es realment espantat.
Si acaba agrada, ahh, jo no saben el que està fent,
No sé, com, això sembla tan complicat, ahh, relaxar-se.
Està bé.
Llegir l'especificació.
L'especificació li explicarà exactament el que tots aquests programes estan fent.
>> Per exemple, és un programa generate.c que vindrà amb el seu conjunt de processadors.
En realitat no cal tocar-lo, però vostè ha d'entendre el que està fent.
I generate.c, l'únic que està fent és ja sigui generació de nombres aleatoris
o pot donar-li una llavor, com un nombre preestablert que es necessita,
i genera més números.
Així que hi ha una forma específica de aplicar en el qual generate.c
vostè pot fer un munt de nombres per fer realitat els teus altres mètodes successivament.
>> Així que si vostè volia, per exemple, prova de la seva troballa,
que es vol executar generate.c, generar un munt de nombres,
i després executar la seva funció d'ajudants.
La funció dels seus ajudants és on estàs escriure realment físicament codi.
I pensar ajudants com un arxiu de biblioteca que està escrit que troballa està trucant.
I així dins helpers.c, podràs fer recerca i classificació.
>> I després vas a essencialment només cal posar a tots plegats.
L'especificació li dirà com ja que en la línia d'ordres.
I podràs provar si o no és el seu tipus i de recerca estan treballant.
Fresc.
Algú ha començat i problemes o dubtes plantejats
que tenen ara amb això?
D'ACORD.
>> AUDIÈNCIA: Espereu.
Tinc una pregunta.
>> ANDI Peng: Sí.
>> AUDIÈNCIA: Així que vaig començar a fer la recerca lineal en helpers.c
i no va ser realment funciona.
Però més tard, vaig saber que només que eliminar-lo i fer recerca binària.
Així que què importa si no funciona?
>> ANDI Peng: Resposta curta és no.
Però ja que estem no--
AUDIÈNCIA: Però ningú de realitat de xecs.
ANDI Peng: Mai estem va a veure això.
Però és probable que vulgui fer Assegureu-vos que la cerca està treballant.
Perquè si la seva lineal cerca no funciona,
llavors és probable que el seu binari cerca no funcionarà tan bé.
A causa que té similars lògica en tots dos.
I no, no importa.
Així que els únics que convertiran en to de classificació i recerca binària.
Sí.
>> I també, una gran quantitat de nens estaven compilar helpers.c.
No està realment permès per fer això, perquè helpers.c
no té una funció principal.
I pel que només ha ser en realitat la compilació
generar i trobar, perquè trobar trucades helpers.c i les funcions que la integren.
Així que fa la depuració un dolor al cul.
Però això és el que hem de fer.
AUDIÈNCIA: Vostè acaba de fer de tot, no?
ANDI Peng: Vostè pot simplement fer tot així, si.
D'ACORD.
Així que és això en termes del el conjunt de processadors està demanant a tots a fer.
Si vostè té alguna pregunta, lliure de preguntar després de la secció.
Vaig a ser aquí per com 20 minuts.
>> I sí, de el joc de paràmetres no està tan malament.
Vostès haurien d'estar bé.
Aquests, només has de seguir les directrius.
Classe de tenir un sentit de, lògicament, el que hauria d'estar succeint i se li multa.
No sigui massa espantada.
Hi ha una gran quantitat de codi ja escrit allà.
No sigui massa espantat si no ho fa entendre el que tot això significa.
Si és molt, és totalment bé.
I arribat a les hores d'oficina.
Nosaltres l'ajudarem a fer una ullada.
>> AUDIÈNCIA: Amb l'extra funcions, què busquem els de dalt?
>> ANDI Peng: Sí, aquestes són en el codi.
En el joc de 15, la meitat de ja està escrit per a vostè.
Així que aquestes funcions estan Ja en el codi.
Sí.
Tot bé.
Bé, millor de les sorts.
És un dia fastigós.
Així que espero que vostès no se senten massa mal per romandre dins i codificació.