[SCRÂȘIT]
[FOȘIT]
[CLIC]
JASON KU: Bine.
Bun venit tuturor.
Toți sunt pregătiți pentru test?
PUBLIC: Nu.
JASON KU: Test săptămâna viitoare.
Da.
Sper că sunteți cu toții
aici pentru că știți
că va avea loc un test săptămâna viitoare.
BINE.
Deci despre ce este acest test?
Este vorba despre ceea ce
am vorbit până
acum în această clasă, desigur.
Despre ce este această clasă?  Îți
amintește cineva de la
prima mea prelegere?
Despre ce este această clasă?
Ce încercăm să
vă testăm în această clasă?
PUBLIC: algoritmi.
JASON KU: Algoritmi.
Grozav.
De asemenea, structuri de date.
Dreapta?
Asta este prima
parte a acestui lucru.
Dar într-adevăr este pentru a te face să
rezolvi probleme de calcul.
Acesta este primul lucru.
Fii capabil să-i argumentezi pe altcineva
că tu chiar ai rezolvat-o.
Dreapta?
Este corect.
Dreapta?
Că ai ales ceva
mai bun decât alte lucruri,
că este eficient.
Dreapta?
Și că poți comunica
aceste lucruri altor oameni.
Dreapta?
Aceștia sunt cei patru ai mei mari pe care încerc
să vă fac să vă interiorizați.
Și pentru asta
vor
încerca să te evalueze chestionarele noastre.
BINE.
Și așadar, în afară de niște
chestii esențiale pe
care le facem la
începutul termenului,
cum ar fi să vorbim despre
modelul nostru de calcul.
Dreapta?
Modelul nostru... și asimptotice.
Asym-- simtomatici.
Este corect?
Recidive nu?
Pe lângă aceste elemente de
bază, ne
aprofundăm direct în algoritmi.
Dreapta?
Acestea sunt cam ca niște
definiții.
Nu ne bazăm
foarte mult pe aceste lucruri.
Adică, ne bazăm pe aceste
lucruri tot timpul.
Dar este un fel de
matematică pe care o
folosim pentru a vorbi despre lucruri.
Dreapta?
Cum putem spune
cât de mult durează aceste lucruri,
dacă nu putem raționa --
putem abstrage un mod în
care aceste lucruri nu sunt
pe un computer real.
Acest lucru este cam în
mintea noastră, într-un computer.
Și raționăm
despre aceste lucruri pe baza
numărului de
operațiuni în timp constant pe care le

poate avea acest computer magic,
care este o reprezentare destul de bună
a oricăruia
dintre computerele pe care le aveți
pentru anumite ipoteze.
Dreapta?
Nu suntem... Adică, nu sunt
prea multe întrebări despre setul de probleme despre care v-am
spus.
Aceste lucruri -- în
mod specific -- de obicei
făceau parte dintr-o altă problemă.
Dreapta?
Trebuia să descrii
timpul de rulare al acestui lucru.
Și s-ar putea să fi trebuit să
rezolvi o recidivă.
Și s-ar putea să aveți
teorema principală a utilizărilor.
Acel tip de lucru.
Dreapta?
Sau folosești asimptotice
tot timpul.
Sau trebuie să vă
amintiți în modelul nostru,
oh, contează
cât de mare
pot stoca și pot face aritmetică
în timp constant.
Dreapta?
Deci, pentru acea întrebare p-set
3 pe care ați avut-o
la sfârșitul
întrebării de codare,
ați vrut să ștergeți lucrurile.
Și trebuie să argumentați
că acele lucruri se potrivesc
într-un număr constant
de cuvinte, astfel încât să se
poată face în timp constant.
Mulți dintre voi, băieți, au
găsit că canonicalizările se
raportează practic la lucruri
care erau exponențial de mari.
Deci, poate înmulțirea unui
produs de numere prime sau ceva de
genul ăsta.
Și asta nu ar fi
o reprezentare bună.
BINE.
Așadar, aceste lucruri apar, dar
nu sunt punctul central
al problemelor pe care le rezolvăm.
Care sunt obiectivul principal al...
cum rezolvăm o
problemă de calcul în această clasă?
Ți-am oferit două moduri la
începutul trimestrului.  Vă
amintiți băieți?
Putem rezolva -- cum să rezolvăm o problemă de
calcul -- de calcul
.
Una e calea grea.
Una este calea ușoară.
PUBLIC: Forța brută.
JASON KU: Forța brută.
BINE.
Deci îmi descrii
o tehnică
pentru a-ți crea propriul algoritm.
Dreapta?
Îmi pot crea noul
algoritm de la zero.
Un mod în care aș putea face
asta este forța brută.
Dreapta?
Uitați-vă la toate
ieșirile posibile și vedeți care funcționează.
Dreapta?
Sau m-aș putea reduce la ceva de
genul divide and cuquer
sau ceva de genul ăsta.  În
general, este un
lucru greu de făcut -
să-ți faci propriul algoritm.
Dreapta?  De
aceea nu vă cerem
să o faceți mult la această clasă.
Este un fel de lucru 046.
Dreapta?
Deci, primul lucru pe care l-ați putea face
este să scrieți proiectarea unui nou algoritm
de la zero.
De obicei nu este de la zero.
Dreapta?
De obicei, vă reduceți la
un fel de paradigmă de proiectare algoritmică
de care
poate ați auzit.
Veți vorbi mult mai multe despre asta
în 046 și la sfârșitul acestui
termen când vorbim despre
programare dinamică.
Dar, în general, este
un lucru greu de făcut.
Dreapta?
Încercați să vă gândiți
la un algoritm recursiv.
Dreapta?
Încercați să demonstrați
că este corect --
toate aceste lucruri serioase -- de
fapt,
în cursul
cursului, v-am
arătat
algoritmii.
Dar nu ne așteptăm cu adevărat
să faci acei algoritmi.
Ce ne așteptăm
să faceți de cele mai multe ori.
Da?
Pentru a o reduce la o problemă pe care
v-am arătat cum să o rezolvați.
Dreapta?
O să spun
ceva aici, dar ceea ce vreau să
spun este un algoritm pe
care te-am învățat să-l învețe--
practic aici-- redus
la un lucru cunoscut--
la un lucru cunoscut.
De obicei, asta înseamnă că există
o problemă sau o interfață
pe care ți-am oferit-o.
Și, în general, v-am arătat
mai multe moduri diferite
de a rezolva acea
problemă sau interfață.
Dreapta?
Așa că ți-am arătat multe
modalități de a sorta lucrurile.
Și v-am arătat multe
modalități de implementare a
secvenței și a setării interfețelor.
Tine minte?
Și de multe ori
tipurile de probleme pe
care ți le cerem să le faci
este să folosești doar ca o cutie neagră
unele dintre lucrurile pe care le-am făcut.
Dar ai nevoie, ca programator,
ca informatician,
trebuie să-mi spui când
ar trebui să folosesc ceea ce a mers.
Dreapta?
Da?
PUBLIC: Ați putea clarifica ce
înțelegeți prin utilizarea ca cutie neagră?
JASON KU: Utilizați ca o cutie neagră.
Exact.
Dreapta.
Deci aceasta este o expresie pe care o
folosesc și o mulțime de oameni
din informatică.
Practic, importi
o bibliotecă în codul tău.
Dreapta?
Ce am eu?
Am un API.
Am o modalitate de a
interacționa cu acel cod.  De
fapt, nu
știu ce se întâmplă în
interiorul acelei biblioteci.
Îl folosesc ca o cutie neagră.
E opac pentru mine.
Nu pot să mă uit înăuntru,
probabil că aș putea să mă
uit înăuntru care este codul lor,
dar nu o voi face.
Lucrul care
mi-l face util
este că are acest
API util în care am
încredere că va face
lucrurile pe care mi-ați spus
că va face.
Dreapta?
Și așa că există un fel de--
O să sar
puțin aici, de fapt,
pentru că asta este o întrebare grozavă.
Așa că aici mă gândesc că sunt trei
tipuri diferite de probleme despre
care vorbim, pe care
vi le prezentăm în această clasă.  S-
ar putea să fi văzut
asta pe setul de probleme.
Dreapta?
Îmi place să le clasific aici în
trei categorii diferite
.
Una este că trebuie să înțelegeți elementele
interne ale unei
structuri de date, un
algoritm pe care îl cunoaștem.
Trebuie să poți să te uiți
înăuntru și, nu știu,
având în vedere un nod într-un
arbore de căutare binar echilibrat --
un arbore AVL --
cum pot face o rotație?
Dreapta?
Sau cum fac o inserare?
Sau ceva despre
structura acestui lucru --
un heap binar --
unde sunt primele k
lucruri dintr-un heap binar maxim,
care se află în setul dvs. de probleme.
Aceste lucruri îmi cer foarte
mult să nu încadrez aceste
structuri de date.
Este o cutie albă.
Dreapta?
Trebuie să știu ce este înăuntru ca să
răspund la acea întrebare.
Dreapta?
Trebuie să știu despre
elementele interne ale acelei
structuri de date.
Dreapta?
Și există și alte tipuri de
probleme în care este ca, oh,
nu am nevoie să știu care este
interiorul acestei
structuri de date.
Pot doar să operez cu
cunoștințe despre API
și să încerc să-l conectez la
problema de care am nevoie.
Și asta numesc o
problemă de tip reducere.
Așa funcționează materialul de bază pe care

vi l-am prezentat în curs?
Așa aplic
acel material de bază?
Și mai greu decât
ambele lucruri
este ceea ce aș putea numi un
tip de modificare a...
acestea nu sunt nume chiar bune.
Am venit cu
astea azi dimineață.
Dar încearcă
să ajungă la ideea
că este posibil să ai
nevoie să știi ce este API-ul
și să știi ce se
întâmplă în interior pentru a
putea răspunde la problemă.
Lucruri precum adaptarea unui
algoritm de împărțire și cuceri.
Sau a face -- în loc să
folosesc o matrice dinamică care
are spațiu suplimentar la
un capăt, poate că trebuie să
pun spațiu suplimentar în
mijloc sau ceva de genul ăsta.
Dreapta?
Adaptez ceva care a
fost din materialul de bază.
E destul de aproape.
Dar trebuie să-l modific
într-un fel.
Augmentare nu?
Trebuie să iau
arborele AVL pe care v-am
dat-o și să pun o
altă proprietate pe noduri
și trebuie să-mi spuneți
cum să o întrețin.
Cum pot calcula acea
proprietate subarboresc din copiii săi?
Are sens?
Deci acesta este cel
mai greu dintre lucruri.
Dreapta?
Dacă puteți identifica
care dintre acestea--
o problemă pe care o
priviți la un examen--
[INAUDIBLE] sub--
poate asta vă poate ajuta să
conceptualizați ce ar trebui să folosesc.
Pentru o problemă de tip reducere --
voi vorbi despre
asta într-o secundă --
dar de multe ori este
util să o reduceți
la o problemă sau la o interfață
mai degrabă decât la un algoritm
sau o structură de date.
Ce înseamnă asta?
Dacă pot rezolva problema
spunând reducerea la sortare,
vă pot argumenta că
acel algoritm este corect.
Folosesc sortarea doar
ca o cutie neagră.
Acum s-ar putea să nu fie eficient.
Alegerea mea de
algoritm de sortare pe care l-am ales contează
pentru eficiență.
Dar pentru corectitudine,
nu contează.
Dreapta?
Pentru o problemă cu structurile de date, s-
ar putea
reduce la utilizarea a două
structuri de date setate și a unei
structuri de date secvențe sau
ceva de genul acesta.
Dar va fi corect dacă o
reduc la acele lucruri.
Pot defini operațiunile
în termenii acelor interfețe.
Nu trebuie să fac
această alegere până nu
vorbesc despre timpul de funcționare.
Dreapta?
Până să vorbesc despre eficiență.
Și numele jocului
din test pentru a obține puncte...
nu vă putem oferi puncte
pentru un algoritm incorect
sau ceva care este
destul de aproape de corect.
Dreapta?
Și nu
vă putem oferi puncte complete
decât dacă algoritmul corect pe care ni-l
oferiți este eficient
și că ați argumentat lucruri
precum corectitudinea și
timpul de funcționare și lucruri de genul.
Algoritmul dvs. ar putea fi
corect și eficient,
dar ați analizat
incorect timpul de rulare,
așa că vă notăm
punctele pentru acolo.
Sau de cele mai multe ori ceea ce
faci este să ne prezinți
un algoritm ineficient.
Și apoi analizezi
timpul de funcționare
ca și cum ar fi timpul de funcționare țintă
pe care ți l-am oferit.
Dreapta?  Asta e
rău pe două fronturi.
Dreapta?
BINE.
Asa ca incearca sa nu cazi
in aceste capcane.
BINE.
Așadar, câteva strategii generale de testare
atunci când
vă uitați la testul dvs.  Vă
îndemn cu tărie să
citiți întregul examen
înainte de a începe, deoarece
unele dintre probleme vă
vor fi mai ușoare
decât altele.
Și dacă încercați
să maximizați punctele
aici, așa cum sunt
sigur că încercați să faceți cu toții,
este util să faceți acea primă
trecere prin probleme
pentru a vedea care
sunt cele mai ușoare pentru dvs.
Și apoi le poți aborda
în ordinea
în care ai încredere.
Acum, în realitate, media la
testul 1 din această clasă
tinde să fie în jur, nu
știu, între 60 și 80.
Nu cred că a fost vreodată 80.
Dar nu este 100.
Deci, făcând 50% din
problemele bine, probabil că va
fi mai bine pentru tine
în ceea ce privește gestionarea timpului
și astfel de lucruri
decât să faci toate -- să
încerci toate
problemele și să nu te
descurci grozav în niciuna dintre
ele în ceea ce privește punctul --
trebuie să,  în
informatică,
trebuie să fii destul de aproape de
un răspuns corect pentru a obține puncte.
Dreapta?
Practic, trebuie să fie aproape
corect sau nu înțelegeți --
dacă ați văzut cum
sunt evaluate seturile dvs. de probleme --
uneori, gradatorii
noștri seturi de probleme
greșesc.
Uneori îți oferă puncte
pentru o soluție incorectă.
Dreapta?
Depinde de tine să arunci
o privire asupra setului de probleme pe
care ni le-ai oferit și
soluțiilor noastre pe care ți le-am oferit.  Am
petrecut mult timp scriind
soluții bune pentru voi, băieți.
Trebuie să vă asigurați
că materialul.
Nu veni la noi
la sfârșitul unui examen
și spune, oh, am spus același
lucru pe setul meu de probleme.  A
fost marcat corect și voi
băieți l-ați marcat greșit.
Pai da.
Personalul știe puțin
mai multe
despre algoritmi decât
elevii tăi despre seturile de probleme.
Și vă notăm examenele.
Deci, din păcate,
asta nu este o scuză.
Depinde de tine să
cunoști materialul.
Da?
PUBLIC: Deci, cele
mai multe dintre problemele
de la examene sunt lucruri în mai multe
părți în care
trebuie să avem o
bună înțelegere
și să facem primele
părți pentru a
obține credit chiar și parțial
pentru celelalte părți?
Sau este ca [INAUDIBIL]?
JASON KU: Da.
Deci întrebarea
este, întrebările sunt
construite una peste alta, astfel încât
să fii cam la un perete
dacă ai ratat prima parte?
Încercăm să nu proiectăm
astfel examenele.
BINE.  De
fapt, puteți arunca o
privire la examenul de practică
care a fost deja postat.
Problemele noastre tind să
fie de sine stătătoare.
Și dacă sunt mai multe
părți, părțile
sunt de obicei independente.
De obicei, nu trebuie să fi
făcut A corect pentru a
face B corect.
În regulă?
Și așa
încearcă să fie scrise și seturile noastre de probleme.
Pentru ultima dvs.
întrebare de codificare și 4
ați avut această problemă
în care a trebuit să
proiectați această structură de date.
Dar C a spus că folosește
asta ca o cutie neagră
în esență și
rezolvi problema.
Dreapta?
Deci, de fapt,
nu trebuie să arătați... v-am
oferit această interfață.
Puteți doar să utilizați
acea interfață pentru a
putea răspunde la C, la
întrebarea algoritmilor,
fără să rezolvați
corect întrebarea privind structurile de date.
Are sens?
Și de fapt,
întrebarea despre algoritmi
a fost cea mai ușoară acolo,
cred, din câte îmi amintesc.
Da?
PUBLIC: Trebuie să
scriem cod la examen?
JASON KU: Trebuie să
scrieți cod la examen?
Nu am dat niciodată un examen în care să fi trebuit să
scrii cod.  Am
scris examene în care
trebuie să citești cod.
BINE?
Deci pseudocod sau Python--
deoarece Python este o
condiție prealabilă pentru această clasă,
este un joc complet corect să
vă oferim
mici fragmente de
cod Python și
trebuie să puteți
înțelege ce se întâmplă.
Da?
PUBLIC: Ați
enumerat amortizarea
la modificarea
[INAUDIBIL]..
Înseamnă asta că folosim
un [INAUDIBIL] amortizat?
JASON KU: Da.
Ceea ce vreau să spun aici--
amortizarea cu siguranță
apare aici sau aici--
astfel de lucruri.
Adesea, dacă
folosesc o matrice dinamică,
dacă folosesc un heap binar,
dacă folosesc un tabel hash,
amortizarea va apărea
aici în timpul nostru de rulare
pentru acele operațiuni dinamice.
La ce mă refer aici
la amortizare,
vreau să spun dacă vă cer
să generalizați ceva
ce am făcut, cum ar fi cu
matricele dinamice, unde în loc să
adaug
spațiu suplimentar la sfârșit,
pun
spațiu suplimentar la mijloc
sau la  început sau
ceva de genul ăsta.
Și trebuie să faci un
fel de analiză amortizată.
Acum, de multe ori
nu este necesar să facem asta în--
când am vorbit despre
o problemă în care ne-am
făcut propria
analiză amortizată
și am făcut un pachet dublu--
Adică o coadă dublă--
ai putea de fapt să
o rezolvi prin reducerea
la utilizarea  două matrice dinamice.
Dreapta?
Deci, există o mulțime de
moduri prin care te
poți reduce la utilizarea lucrurilor.
Dar s-ar putea să trebuiască să faceți
o contabilitate suplimentară
la sfârșit.
Dar ceea ce spune asta
este că acestea sunt mai mult...
nu folosești
lucrurile ca o cutie neagră.
Schimbați ceva la
cutiile pe care vi le-am dat.
Dreapta?
Are sens.
Da?
PUBLIC: Dacă ne spuneți să
scriem un algoritm care face
ceva de genul O(log n)
timp, și ne putem gândi doar
la un algoritm care face
ceva ineficient ca
O(n) la timpul final.
JASON KU: OK.
PUBLIC: Atunci are
rost să scriu asta?
JASON KU: Sigur.
Deci, să
trecem de fapt mai departe pentru o secundă.  De
fapt... Am de gând să-ți
răspund la întrebare foarte curând.
BINE.
Dar o să ajung
la el într-o secundă.
BINE?
Dacă nu răspund la această întrebare
în cinci minute, vă rog să-mi
spuneți.
BINE?
Deci, primul lucru,
când abordez
o problemă la
examen, aș putea încerca
să pun câteva întrebări
despre problemă.
BINE.
Mă va ajuta să
decid ce să folosesc.
Dreapta?
Diferit de
problemele tale.
Problemele tale se stabilesc --
practic, ce
folosești este despre ce am vorbit
în prelegerea în acea săptămână.
La un test aveți
opt prelegeri despre
care ați vorbit.
Și așa că acesta va
fi un lucru mai greu
pentru tine, deoarece nu
știi care dintre cele opt
materiale de curs se va
aplica acestei probleme.
Și ar putea fi
de fapt o combinație a acestora.
Așa că încerc să
vă ofer modalități de a răspunde
mai repede la această întrebare.
BINE?
Deci aceasta este o
reducere mecanică
sau o problemă de tip modificare?
Asta mă va ajuta doar să
determin
nivelul de dificultate a ceea ce este asta.  S-ar
putea să nu
poți răspunde.
Dar vă poate da o idee
despre ce fel de problemă este.
Este aceasta o problemă legată de
sortarea structurilor de date pe ambele?
Dreapta?
Dacă este vorba despre
structuri de date,
trebuie să suport
operațiuni de tip secvență
sau trebuie să stochez o
ordine extrinsecă pe ceva?
Sau este un lucru în care îmi pasă de
ceea ce sunt obiectele?
Încerc să caut lucrurile
după ceea ce sunt.
Sau poate ambele?
Sau poate vreo combinație?
Dacă am o grămadă de
tipuri diferite de chei
pe care aș putea dori
o interogare, ar putea fi necesar să
folosesc cel puțin două
tipuri de structuri de date.
Dreapta?  Te-ai
putea
complica foarte mult cu aceste lucruri.
Dar punând-o în
termeni de bine,
va trebui să fac acest tip
de operație pe aceste nume.
Atunci mă pot gândi, oh, am nevoie de
o structură de date stabilită acolo.
Mă voi gândi cum să
implementez asta mai târziu.
Ar trebui să folosesc o tabelă hash?  Ar
trebui să folosesc o matrice sortată?
Ar trebui să folosesc un arbore AVL?
Dar gândirea la asta mai întâi
la nivel abstract de Am
nevoie de o structură de date setată aici
vă poate ajuta să compartimentați
corectitudinea versus eficiență.
Are sens?
BINE.
Dacă ești blocat, aceasta
este întrebarea ta.
Dacă ești blocat,
notează un algoritm corect
care este ineficient.
Vă putem oferi puncte pentru
un algoritm corect care este
ineficient.
Cel puțin este un
algoritm corect.  Asta e
mai bine decât alte lucruri.
Dreapta?
Acum, dacă este
timpul exponențial, s-
ar putea să fii limitat la 10%
sau 20% din puncte.
Dar dacă este un factor log--
mai rău, sau un factor liniar-- mai rău.
Poate că e în regulă.
În cazul unei probleme cu structurile de date,
dacă orice operațiune are ordine n
timp, probabil că nu
vă va oferi prea multe puncte,
deoarece scopul
structurii de date
este să faceți acele
operațiuni rapide.
Dar dacă rezolvă problema,
vei obține câteva puncte.
Nu vei primi 0 puncte.
Da?
PUBLIC: Vom
primi întrebări, cum ar fi
cât de repede
poți face asta?
Faceți acest lucru cât mai repede posibil.
JASON KU: Da.
Deci de multe ori vom spune,
dă-ne un algoritm eficient.
BINE.
E ca, uau, nu știu
dacă este eficient sau nu.  Ei
bine, asta înseamnă doar că
timpii de rulare mai rapidi îți vor
oferi mai multe puncte.
BINE?
Așadar, în astfel de întrebări
, se încearcă în mare parte
să se joace acest joc de--
de obicei, vom pune
unul eficient, nu în ceea ce privește
structura de date, deoarece, de obicei,
problema structurilor de date--
este important în
implementarea dvs.
ca aceste date
operațiunile de structură să fie rapide.
Și vrem să
vă spunem cât de rapid este.
Dreapta?
Deci, întrebările privind structurile de date
în general, există
de obicei un compromis
între timpii de rulare
a acestor operațiuni diferite.
Și este foarte important modul în care se
relaționează unul cu celălalt.
Și, așadar, pentru
problema structurilor de date,
este un fel de a obține
acei timpi de funcționare.
BINE?
Cu o problemă de algoritmi în
care îți cerem să faci un lucru
și încercăm să o facem
cât mai repede posibil,
încercăm să obținem timp liniar.
Dreapta?  De cele
mai multe ori nu puteți
obține mai bine decât timpul liniar
dacă trebuie să citiți
întreaga intrare la un moment dat
dacă vreau să găsesc
lucrurile din datele mele.
Și dacă nu vă puteți gândi la
un algoritm de timp liniar,
gândiți-vă la un lucru n pătrat
sau gândiți-vă la n log n lucru.
Dreapta?
Poate că vă este puțin greu să vă
gândiți acum.
Dar de aceea spun că începeți
cu orice algoritm corect
și apoi poate puteți optimiza.
Poate că puteți folosi o
structură de date mai bună
pentru a o face mai eficientă.
Are sens?
Alte intrebari?
BINE.
Mișcându-ne chiar de-a lungul.
BINE.
Iată câteva dezavantaje.
BINE.
Dacă te trezești că faci unul
dintre aceste trei lucruri,
fă un pas înapoi.
Probabil că faci
ceva greșit.
BINE?
Așa că întrebați-vă dacă
încercați să calculați zecimale,
raționale sau numere reale.
Nu pot stoca
acele lucruri pe...
Adică, pot stoca zecimale
cu precizie finită.
Dar dacă faceți o
precizie finită,
ați putea la fel de bine să vă înmulțiți
numerele cu acea precizie fixă
și să vă ocupați de numerele întregi.
Dreapta?  Te-am
învățat doar
cum să faci față
numerelor întregi din această clasă.
Dreapta?  Nici măcar
nu ți-am arătat
cum să calculezi eficient
pe numere raționale și reale.  V-am
spus că dacă aveți
un numitor și un numărător
al unei fracții, pot
lua două fracții
și le pot compara
în timp constant
făcând înmulțiri încrucișate.
Dar dacă încerc să
fac această împărțire cu o
precizie arbitrară, nu este
fericit pentru că nici măcar nu pot
reprezenta asta pe
computerul meu într-un număr finit
de puncte zecimale pentru
unele dintre aceste lucruri.
Dacă încercați să utilizați
sortarea Radix pentru fiecare răspuns,
probabil că este greșit.
Unul dintre lucrurile pe care
încercăm să le facem la chestionare--
nu vă oferim doar o
grămadă de probleme aleatoriu.
Probabil că
facem probleme care
acoperă materialul într-un fel.
Vrem să vă testăm cu privire
la toate lucrurile.
Și, așadar, dacă descoperiți că
utilizați același lucru de
patru sau cinci ori
la examen, acesta
ar putea fi un semn că
îl utilizați de prea multe ori.
Nu este întotdeauna cazul.
Dreapta?
Uneori, hashingul
este foarte util,
așa că doriți să
îl folosiți tot timpul.
Dar, în special,
toată lumea încearcă
să folosească sortarea Radix atunci când
este nepotrivit.
Și ei iubesc pentru că
devine timp liniar.
Dreapta?
Dar dacă scrieți sortare de îmbinare pentru
ceva în care se va aplica sortarea Radix
, veți obține câteva puncte
pentru că este corectă, dar nu
eficientă.
Și este ineficient
printr-un factor log.
Dreapta?
Dacă încercați să utilizați
sortarea Radix într-o situație în
care comparațiile sunt
răspunsul și nu aveți
o limită pentru numerele întregi,
dacă nu am
o limită pentru dimensiunea
numerelor întregi,
atunci aceasta poate fi nevoie de
o limită.  uriașă perioadă de timp.
Așa că s-ar putea să nu
cred că asta
este corect, deoarece
ar putea fi timp exponențial.
Adică, nu știu.
Nu știu cât de
mare este dimensiunea cuvântului meu.  Ar
putea fi arbitrar rău.
BINE.
Și apoi, dacă
încerci să mărești
un arbore binar cu ceva
care nu este o proprietate subarbore--
ceva care nu poate fi
calculat din creșterile celor
doi copii ai săi--
faci ceva rău.
Fiecare examen pe care îl avem,
30% dintre studenți
spun că crește cu indicele meu în
întregul arbore sau mărește prin --
iată unul care este distractiv --
crește cu dimensiunea
subarborelui meu din stânga --
numărul de noduri
din subarborele meu stâng.
Cum pot...
Nu sunt sigur cum pot menține
asta cu rotații și lucruri de
genul ăsta.
Să vedem.
Pentru ca eu să țin
evidența creșterii
arborelui meu stâng de la
creșterea arborelui stâng,
trebuie să fac o
plimbare logaritmică până la capăt
pentru a-mi da seama câte
lucruri au fost acolo.
Deci nu este un lucru care poate fi întreținut
în timp constant.
Dacă vreau să măresc
ceva din subarborele meu stâng,
doar mărește lucrul
în sine și uită-te doar
la subarborele tău din stânga și
uită-te la creșterea lui.
Are sens?
Da?
PUBLIC: Dacă ați spune,
măriți-l cu un subarboresc
și apoi măriți-l din nou cu
subarborele [INAUDIBLE] și apoi
folosiți asta...
JASON KU: Ai putea face asta.
PUBLIC: --asta
mai contează ca...
JASON KU: Ai putea să faci asta.
Da.
Deci, ați putea face asta
în timp constant
prin mărirea dimensiunii subarborelui.
Dreapta?
PUBLIC: Și apoi ai o altă
creștere în [INAUDIBLE]..
JASON KU: Ai putea avea o altă
mărire pentru că atunci ai
putea doar să te uiți la... dar apoi doar să te
uiți la subarborele tău din stânga,
te rog.
Da.
Nu există niciun motiv să-l depozitezi din nou.
Dreapta?
Faci doar o singură dată constantă...
uită-te în stânga ta.
BINE.
Nu face asta.
BINE.
Deci asta este... cool.
Nu sunt atât de în urmă.
Acestea sunt sfaturile mele pentru
a rezolva întrebările.
Oh, mai este o pagină.
Da?
PUBLIC: Deci, atunci când
definiți o creștere,
[INAUDIBIL] faceți formula și
argumentați că este [INAUDIBIL]..
JASON KU: Exact.
Dreapta.
Așa că ideea este că dacă dai o
creștere care nu este o...
vom vorbi
despre lucrurile noastre standard la care
poți reduce într-o secundă.
Dacă spui, voi
lua un arbore AVL setat
sau un arbore AVL secvență -
și, de exemplu, la
sfârșitul prelegerii, am
vorbit despre cum
ar putea fi modificat un arbore AVL secvență
pentru a
sprijini operațiunile prioritare în coadă.
în aceiași
timpi de rulare ca și heap-urile binare.
Dreapta?
Și asta spunea că
stocăm maximele noastre subarbore--
lucrul maxim din subarborele meu.
Dreapta?
Și, deci, este o
creștere diferită
față de ceea ce este deja augmentat
în arborele AVL de secvență.
Care sunt creșterile
pe un arbore AVL de secvență?
PUBLIC: Mărime.
JASON KU: Mărimea.
PUBLIC: Count.
JASON KU: Deci numărătoarea este
același lucru cu câte noduri
sunt în subarborele meu.
Și?
PUBLIC: Înălțime.
JASON KU: Înălțime.
Corect pentru că este un arbore AVL.
Dreapta?
Deci, dacă măresc
cu max în subarborele meu,
asta nu face parte din
interfața mea standard.
Deci trebuie să-mi spui asta.
Chiar dacă am mai
făcut-o înainte, ar
trebui să fie foarte ușor pentru tine.
Spune doar, mă
sporesc cu maximul meu.
Max poate fi calculat
ca maxim între mine
și subarborele meu din stânga și din dreapta
dacă există.
Terminat.
Dreapta?
Dar doar fă asta.
Trebuie să-mi spui...
și este nevoie de
timp constant, astfel încât să
poată fi menținut la
timp constant când îmi fac treaba.
Are sens?
BINE.
Deci, ultimul lucru,
cred că mai ales
în ceea ce privește
problemele structurilor de date,
aș sugera să
abordați aceste lucruri
prin rezolvarea acestor probleme mai întâi
în ceea ce privește interfețele
.
Pentru că atunci măcar
obțineți ceva corect.
Și apoi alegeți
algoritmii sau structurile de date pe
care le utilizați pentru a implementa
acele interfețe ulterior.
Unul te duce la un
algoritm corect.
Celălalt este pentru eficiență.
Decuplarea acestora vă poate ajuta
să rezolvați problema.
Dacă nu te ajută, nu.
Dacă vă place, ori de câte ori
văd o structură de date setată,
probabil că voi folosi un
tabel hash, probabil că este în regulă.
Dar dacă căutăm
limite de timp în cel mai rău caz,
probabil că nu este distractiv.
Deci doar... Vă
sugerez să separați
aceste lucruri, astfel încât să vă
concentrați
mai întâi pe rezolvarea problemei
și apoi să o optimizați mai târziu.
Da?
PUBLIC: Doar o întrebare
în ceea ce privește limitele de timp în cel mai rău caz
.
JASON KU: Mm-hmm.
PUBLIC: Deci pentru o masă hash.
JASON KU: Mm-hmm.
PUBLIC: Având în vedere că este
un cod de așteptat.
JASON KU: Mm-hmm.
PUBLIC: Asta implică, de asemenea,
că este O din n cel mai rău caz.
Așa că ați putea - din punct de vedere tehnic
JASON KU: Nu implică asta.
Este asta.
Deci, vreau să spun, ați putea avea
o structură de date a cărei
limită de timp așteptată este constantă,
dar cel mai rău caz
este n log n.  Se
întâmplă să fie
faptul că pentru un tabel hash,
acele operațiuni din cel mai rău caz
sunt liniare.
Dar dacă am avut o
întrebare aici în prealabil,
dacă aveam un timp de rulare
limitat că am făcut ceva
la o tabelă hash în
timpul așteptat constant, am căutat în sus
și apoi am întrebat un arbore AVL
pentru  predecesorul unui nod
sau ceva de genul
acesta, și am făcut
asta în O de log n timp,
care este cel mai rău caz de
timp de rulare al acestuia?
PUBLIC: O din n.
JASON KU: O din n.
Care este
timpul de funcționare așteptat al acestui lucru?
PUBLIC: Log n.
JASON KU: Jurnalul nr.
Jurnalul așteptat n.
Pentru că e posibil
ca în cel mai rău caz să
fie mai mare.
Are sens?
BINE.
--deci bine.
Al doilea punct este doar
configurarea unei probleme de structuri de date
.
Sunt multe piese mobile.
Vom rezolva două
probleme de structuri de date
la sfârșitul acestei sesiuni.
Descrieți toate
structurile de date pe care le utilizați,
inclusiv ceea ce stochează acestea.
Dacă stocați o
structură de date setată,
mai bine spuneți-mi pe ce

sunt introduse lucrurile pe care le stocați.
De obicei, lucrurile pe care le
stocăm
conțin o grămadă de
informații, iar dacă
spui doar că stochez toate
toppingurile pizza mea
în structura de date setată
și asta e tot ce îmi spui,
habar n-am ce
ai"  vorbesc despre asta
pentru că nu știu care este
semantica structurii tale de date
.
Pe ce este tastată?
Trebuie să spun,
oh, este tastată,
nu știu y-urile
sau ceva de genul ăsta.
BINE.
Și există invarianți.
Cum configuram aceste
probleme cu structurile de date,
de obicei cum le rezolv atunci când
scriu soluțiile,
am configurat o stare a ceea ce
ar putea fi această structură de date
la un moment dat.
Voi spune că
această structură de date
stochează toate
lucrurile mai puțin decât --k
cu cheia mai mică decât
k, bla, bla, bla.
Și acesta stochează
ordinea extrinsecă
a articolelor pe baza
bla, bla, bla.
BINE.
Deci, de fapt, afirmând
ceea ce stochează în acest fel, de
fapt impun un fel
de invariant asupra acestor
structuri de date pe care
vreau să le mențin.
Dar ceea ce trebuie să fac pentru a dovedi
că acest lucru este corect
este că se bazează pe presupunerea
că acele invarianți au avut loc
înainte de operația mea.
Apoi pot dovedi că
o operație este corectă
dacă toate acele invariante
sunt menținute înainte, apoi
după operație.
Cam așa demonstrez
că acest lucru este corect.
Și apoi, când interog,
fac un fel de căutare
pe această structură de date, mă
pot baza pe acele invariante.
Știu că acele
lucruri sunt bune,
acele lucruri au
fost întreținute
și așa că mă pot baza pe
ele pentru a căuta care este
cel mai mare k din acest lucru.
Are sens?
Dacă acest lucru este foarte
abstract, vom
deveni puțin mai
concret într-o secundă.
Și apoi implementați
fiecare operațiune.
Habar nu ai
câte soluții
citim la chestionare, pe
care îți dăm
trei operațiuni de implementat
și nici măcar nu menționezi una.
Și de obicei este
cea mai ușoară.
Este ca și cum ar fi inserat în
structura ta de date.
E ca,
haide, spune doar asta.
Nu vă putem oferi puncte decât dacă
menționați acea operațiune.
Are sens?
Și apoi va
ajuta - noi, cei fericiți,
vă oferim mai multe puncte.
Nu chiar, dar dacă
soluția dvs. este
bine organizată și bine etichetată
și lucruri de genul acesta,
atunci vom putea
înțelege mai bine soluția dvs.
și
vă vom putea oferi mai multe puncte.
Amintiți-vă, o parte a acestui curs
este despre comunicare.
Dacă lucrul tău este corect, dar
nu putem spune ce spui,
atunci nu este corect.
BINE.  În
regulă.
Deci acum ajungem la
orice întrebări despre asta?
Da.
PUBLIC: Doar o
întrebare despre invarianți.
Deci, una dintre
structurile de date pe care le-am
discutat
anterior în clasă
pentru a spune care
sunt invarianții,
cum ar fi regula arborelui AVL set.
JASON KU: Corect.
Deci, dacă sunt
lucrurile standard,
urma să vorbim despre ceea ce
sunt lucrurile standard acum.
Atunci nu trebuie să
reargumentezi sau --restate,
adică poți
spune, practic, ca,
pentru că interfețele set și secvență
sunt definite în
acest fel, aceste
lucruri sunt corecte,
cum ar fi --aproape
poți --practic
tu'  Încerc să
ne convingă de ce este corect.
Dacă utilizați corect
o structură de date set sau secvență
în aceste
probleme de tip structuri de date, atunci
dacă nu o utilizați
într-un mod neobișnuit,
de obicei vă puteți
baza doar pe proprietățile structurilor
de date set și secvență
care  ti-am dat.
Vreau să menționați că
v-ați gândit la corectitudine.
Ca această structură de date
este corectă deoarece.
Doar scrieți o propoziție care
spune asta și susține
că,
practic, mențineți
invarianța
structurii dvs. de date
la un nivel superior.
Ce fel de lucruri
stochează această structură de date?  Pe
ce lucruri despre
structura globală de date ne
bazăm pentru a
efectua operațiuni de interogare?
Atâta timp cât sunteți convingător
că după o operațiune dinamică la
modificarea
structurii de date, acele invariante
rămân la fel - aceleași care sunt
încă satisfăcute, atunci
asta este cu adevărat tot ce
trebuie să spuneți.
Acești invarianți sunt
satisfăcuți datorită
definițiilor unei
structuri de date de set și secvență.  De multe
ori nu
necesită multă gândire
pentru -- nu suntem -- să întrebăm
motivul pentru care
facem
probleme de reducere este astfel încât să
nu trebuie să depui multă
muncă pentru a ne demonstra că este
corect.
Avem aceste
cutii negre foarte frumoase.
Sunt corecte.  V-am
demonstrat
că sunt corecte
și, astfel, nu trebuie să
repetați acea lucrare.
Așa că acum vom trece
prin materialul de bază la care îmi place
să mă gândesc în această clasă.
Prima parte a
acestei clase, pe lângă
aceste
instrumente matematice pe care le-am dezvoltat
la începutul
cursului, se referă
mai ales la rezolvarea problemelor care
implică structuri de date.
Și am motivat această
problemă de sortare
spunând că o matrice sortată
este o structură de date care este
de fapt destul de utilă.
Dar cum sortăm aceste lucruri?
Ei bine, ți-am arătat o
grămadă de modalități de a face asta.
Și aceasta este masa aceea drăguță.  O
mulțime de lucruri.
De ce vă arătăm atât de
mulți algoritmi de sortare?
De ce nu
vă dăm un singur algoritm?
Hmm?
Da?
PUBLIC: --timpii de rulare.
JASON KU: Timp de rulare diferit.
PUBLIC: Mai bine pentru --diferit
JASON KU: Mai bine pentru
diferite scenarii.
PUBLIC: Da.
Fiecare are
propriile puncte individuale,
apoi se descurcă mai bine.
JASON KU: Da.
Veți observa în
acest tabel că
nu există albastru pe tot drumul
pentru niciunul dintre aceste lucruri.
Deci unele dintre ele sunt mai bune
pentru diferite scenarii.
Și, de fapt, aceste comentarii
enumera câteva cazuri speciale în care
aceste lucruri ar putea fi mai bune.
De fapt, acest
lucru ultra-albastru
spune că acesta
ar putea fi timp liniar.
Asa e mai bine.
Dar, în unele cazuri, acest lucru este mai rău
decât toate celelalte lucruri.
Așa că fiți puțin atenți la
această culoare albastră aici.
În general, încercăm să
vă ducem mai jos în acest grafic
dacă puteți.
Și în general, cum ar fi, de
exemplu, sortare de îmbinare, sortare AVL,
acestea sunt într-adevăr aceleași în
ceea ce privește complexitatea asimptotică
și modul în care
interacționați cu aceste
camere de sortare.
Dar există
cazuri speciale în care
ați putea folosi sortarea prin inserare
sau selecția --sortați de fapt,
nu sunt sigur despre
sortarea prin inserare.  Ați
avut în
recitarea voastră în urmă cu două zile... Cred că ați

arătat cum să procedați
dacă aveți o matrice k-proximată
în care lucrurile nu sunt la mai mult
de k distanță unele de altele.
Sortarea prin inserție rulează de fapt
de n ori k,
și deci, dacă k este mic,
atunci este foarte bun,
este un fel de liniar.
Dar te poți
descurca și mai bine
cu o grămadă binară, pe care ai
văzut-o în recitare, sperăm,
unde poți reduce asta la
n log k, menținând
o grămadă pe măsură ce treci și
găsind maximul în acest fel.
Deci, sortarea prin inserție
poate nu este atât de grozavă.
Dar sortarea de selecție,
numele jocului
este că, dacă
citirile mele sunt ieftine,
dar scrierile mele sunt
scumpe, sortarea de selecție se
descurcă de fapt destul de
bine, pentru că doar am... îmi pare
rău.
Citirile sunt ieftine, iar
scrierile mele sunt scumpe.
Sortarea selecției face un
număr liniar de schimburi.  Se
uită în jos, găsește
maximul, îl schimbă
și continuă.
Și așa că, în astfel de cazuri,
este de fapt
mai bun decât oricare dintre acești
algoritmi pe care îi avem.
Da?
PUBLIC: Acele grămadă --sortează
JASON KU: Mm-hmm.
PUBLIC: --timpul, cel mai rău
caz sunt de așteptat.
JASON KU: Acesta este cel mai rău caz.
Așa că este puțin greu să... au
fost o mulțime de
părți mobile pentru a ajunge la această legătură
în prelegerea de marți.
Practic, ceea ce am
făcut, v-am arătat
cum să vă gândiți la o
matrice ca la o grămadă,
ca la un arbore binar.
Arborele binar complet.
Nu este un arbore AVL--
Adică, este un
arbore AVL, dar arborii AVL
sunt mai slabi decât un arbore complet.
Echilibrul înălțimii este o proprietate mai slabă
decât un complet.
Motivul pentru care folosim
complete este că este
unic pentru un număr de noduri.  În
acest fel, când vă ofer o
matrice cu o lungime fixă,
știu exact despre ce arbore
vorbiți,
pentru că acolo există o
mapare unu-la-unu.
Dacă ar exista o oarecare ambiguitate cu privire la
ce copac vorbeam,
eu nu ar fi grămada, pur și
simplu nu ar funcționa.
Deci ceea ce face sortarea heap este că
are această corespondență
între matrice și arbori binari.
Și apoi ceea ce
face este că oferă
aceste operațiuni care
fac operațiuni doar la sfârșit.
Și apoi
optimizarea la loc
este că, ei bine, în loc să-l
scot de fapt sau să-
l împing pe spatele
unei matrice, mă voi
gândi doar la un
subset al matricei mele ca pe o grămadă
și apoi întotdeauna să fac
caca  maxim până la capăt.  L-am
lăsat în urmă
și mă gândesc la grămada mea
ca la un subset mai mic.
Și așa am înțeles că
de fapt nu a
folosit nicio amortizare.
Pentru limitele de timp,
limitele de timp, ați putea
face acest lucru cu versiunea de
matrice dinamică amortizată
a acesteia.
Limitarea de timp
nu se bazează pe asta.  Pe
loc se bazează pe cheile
rămânând toate într-o singură matrice.
Are sens?
Faceți o grămadă de
operațiuni amortizate,
astfel încât acest lucru
realizează cel mai rău caz n log n.
Da?
Publicul: Se pare că
lucrurile pe care le-am învățat...
JASON KU: Mm-hmm.
PUBLIC: --nu ca--
JASON KU: Mm-hmm.
PUBLIC:
Tind să fie mai buni.
Așa că presupunem că majoritatea algoritmilor
decât ne dorim să fie...
JASON KU: Uh huh.
PUBLIC: --mai repede.
Se pare că oamenii
nu vor folosi atât de des, mai ales
în aceste
inserții și selecție [INAUDIBILE].
JASON KU: Corect, da.
Deci, există aceste
cazuri speciale în care sunt bune,
dar, vreau să spun, în general,
acestea sunt
structuri de date generale mai bune
pentru majoritatea situațiilor pe
care le întâlniți.
Adică, există cazuri în care
celelalte lucruri sunt bune,
așa că nu vrei să
le ignori complet,
dar, în general, da,
încerci să fii limita inferioară
în această diagramă.
PUBLIC: Ceea ce vreau să spun este că,
dacă nu am niciun --legat ca și cum
le-aș folosi pe toate, cu excepția
sortării de selecție--
JASON KU: Deci sunt
prea multe lucruri aici
pentru ca noi să le testăm pe toate
la un examen  .
Deci nu vă fie teamă dacă nu
totul este acoperit.
Vă faceți griji când lucrurile sunt
acoperite de 18 ori la examen,
asta nu este bine.
BINE.
Deci, pentru sortarea radix,
există situații în care
obțineți timp liniar.
Este atunci când ești
delimitat de polinomi.
Există momente în
care vreau să folosesc
sortarea radix când
nu sunt mărginit de polinomi
în numerele mele întregi?
PUBLIC: Ei bine, dacă
nu ești delimitat de polinomi,
atunci asta ar putea dura
foarte mult.
JASON KU: Sigur, da.
Dar cum ar fi unde este - asta
va fi mai rău decât n log n când?
Este cu siguranță
mai bun decât n log n
când u este mărginit polinomial.
Pentru că este liniară.
Da?
PUBLIC: [INAUDIBIL]
de la n la n.
JASON KU: de la n la n.
BINE.
Deci, dacă pun n la
n aici,
primesc un factor n
care iese aici.
Asta îmi oferă un
timp de rulare pătratic,
ceea ce nu este grozav.
Dar când va fi
mai bine decât n log n?
Da?
PUBLIC: n la c,
pentru că este mai puțin n la c.
JASON KU: de la n la c--
deci asta ne va
oferi cu siguranță timp liniar.
Asta se spune.
Dar putem face de fapt
mai bine decât n log n
dacă acest u este n la c
ori log n pentru unele c.
Dacă --este ca și cum ar fi
n pentru c log log n,
acesta este mai mic decât log n.
Deci, acesta este un algoritm mai bun.
Acesta este un algoritm mai rapid.
Vedeți de ce am
scris aceste lucruri în acest fel?
Este pentru a
vă oferi o mai -- precisă,
acest lucru este mai important pentru a
înțelege ce înseamnă aici
decât că acest lucru
se desfășoară uneori în timp liniar.
Vrem să știm când
rulează în timp liniar.
Are sens?
Sau când rulează mai repede
decât sortarea de îmbinare.
Are sens?
BINE.
Deci asta e sortare.
Avem
structuri de date de tip secvență.
Avem liste legate,
avem matrice dinamice,
avem AVL-uri secvențe.
AVL-urile de secvență sunt grozave.
Nu știu de ce nu o
predă nimeni.
Ei sunt grozavi.
Ei nu o predau probabil
pentru că de fapt nu sunt
atât de utile.
De fapt, nu folosești
foarte mult inserția din mijloc
în codare.
Deci, de obicei, te poți
descurca cu cum ar fi să schimbi
ceva până la sfârșit și să faci
operațiuni dinamice acolo,
și acestea sunt multe dintre jocurile
pe care încerci să le joci, astfel încât să
nu fii nevoit să-ți faci
propriile structuri de date
și poți  Folosiți doar
lista Python care este în dvs.
ca nativ pentru lucrul dvs.
Dar are un
interes teoretic
pentru că primește astfel
de limite echilibrate
dacă trebuie să inserați la
mijlocul acestei secvențe.
Acum, unii dintre voi mă uitați la mine
și aveau o întrebare înainte de asta
, dar Jason,
cum se efectuează operațiunile cu listele legate
la
sfârșitul unei liste legate,
de ce durează timp liniar?
Pentru că, la prelegere, ți-am
prezentat ce?
O listă unică.
Avea doar indicii
către următorul lucru.
Și dacă am doar indicii către
următorul lucru și un indicator
către cap, pentru ca
eu să găsesc sfârșitul,
trebuie să merg până la capăt în
listă.
Acum să presupunem că îmi țin indicatorul
la coadă, apoi să găsesc că
și n1 este în regulă, dar eliminarea
ei necesită încă timp liniar,
pentru că nu știu
ce a apărut înaintea mea.
Și de aceea, în
p-set orice, 1, 2,
nu-mi amintesc, ați
stocat un pointer înapoi
la cea anterioară care
v-a dat liste dublu legate.
Da, nu?
Deci, de fapt,
extinzând acest tabel,
puteți face referire la o
listă dublu legată aici și o puteți obține
ca timp constant.
Are sens?
Și acesta este
încă timp liniar.
BINE.
Dar acesta este
încă timp liniar.
De fapt, v-am
arătat și cum să faceți
acest lucru în mod constant amortizat.
Vă amintiți asta, băieți?
Asta a fost în
sesiunea cu probleme 2 sau 1?
Nu-mi amintesc.  A
fost orice am vorbit
despre chestii amortizate.  De

fapt, am primit pe ambele
la unul singur amortizat folosind
conceptele matricei dinamice.
Și apoi am mai
făcut-o încă o dată,
când am obținut un
lucru bun, cu un capăt dublu.
Ce a fost asta?
Își amintește cineva?  Am
mers la sesiunea cu probleme 3.
Da?
PUBLIC: Oh.
Probabil că greșesc, acesta este...
JASON KU: OK.
PUBLIC: --problemă sesiunea 3.
Dar cum ar fi chestii de tip q dq?
JASON KU: Deci q dq,
aia vorbesc
despre lucruri dublu.
Acestea sunt implementate într-un
anumit fel, care este de fapt
unul dintre aceste lucruri.  De
fapt, cred că este
acesta în Python.
Dar există... am folosit o
structură de date diferită
pentru a obține ceva care
a fost foarte bun.  A
avut foarte bune
pop și append
și prima și ultima
operație dinamică.  Vă

amintiți cineva de sesiunea 3?
PUBLIC: [INAUDIBIL]
PUBLIC: Nu este
matrice dinamică [INAUDIBIL]?
JASON KU: Asta a fost.
BINE.
Avem unul care se
aștepta la limite.
Ajută asta?
Ce?
Am auzit pe cineva spunând-o.
Tabel de hash.
Da.
Deci, practic, ceea ce ai
făcut, în schimb --acesta
este o chestie de secvență.
Aceste lucruri nu au chei.
Dar m-am putut identifica
cu fiecare articol
pe măsură ce îl înfig, o cheie
reprezentând indexul său.
Și aș putea folosi o
tabelă hash așa.
Acum au fost unele dificultăți
dacă am eliminat primul lucru.
Pentru că, de fapt, cum
- aceștia sunt toți indicii mei s-
au schimbat acum.
Dar dacă stochez doar care
este cel mai mic indice din chestia mea,
atunci sunt de aur,
pentru că pot calcula
care ar trebui să fie acel indice,
schimb lucrurile din față.
BINE.
Deci, există
trei moduri diferite în care
v-am arătat de a obține
timp constant în fața
și în spatele acestui lucru.
Deci, de fapt, te poți gândi
la asta ca la un material standard la care
te poți reduce.
Aceasta este singura
excepție a lucrurilor pe
care nu le arăt
în acest grafic,
dar este un bonus dacă
urmăriți această sesiune cu probleme.
Da?
PUBLIC: Deci, un tabel hash nu este
o structură de date setată, totuși?
JASON KU: Este.
Dar l-am folosit pentru a implementa
o structură de date secvențială.
Așa că vă voi trimite la
acea sesiune cu probleme
dacă doriți să
aflați mai multe despre ea.
Deci, vreo întrebare despre
structurile de date secvențiale?
Da?
PUBLIC: Eu--
JASON KU: Da, uh huh.
Publicul: Ar trebui să
fim... sau... da.
Ar trebui să putem căuta să dovedim
tabelele care ni se oferă?
JASON KU: Așa că aș sper--
sper-- că dacă ți-aș da
un tabel gol, ai
putea să-l completezi.
Atât de bine
vreau să știți cum
sunt implementate aceste lucruri.
Nu vom
avea asta la examen.
Este o
întrebare plictisitoare.
PUBLIC: Dar este
important de știut?
JASON KU: Da.
Aș... e bine să te
gândești,
cum ar fi, oh, dacă voi
folosi un arbore AVL,
operațiunile vor
fi în general log n.
Acesta este un lucru cu adevărat util --
sau, dacă voi
folosi un tabel hash,
operații de tip dicționar,
găsirea, inserarea și
ștergerea, acestea sunt rapide.
Efectuarea operațiunilor de tip ordine
pe tabelele hash este rău,
este greu de făcut pentru că
practic trebuie să mă uit
prin toate lucrurile mele.
Știind că operațiunile dinamice
pe o matrice sortată este rău.
Sau știind că... trebuie să vă
gândiți aici la ce ne referim
când spunem listă legată și
matrice dinamică în acest tabel,
deoarece...
PUBLIC: Legături individual.
JASON KU: Da, exact.
Implicăm
linkuri unice aici
pentru că asta v-am
prezentat în prelegere.
Și deci acestea sunt
lucrurile standard la
care vrem să le reduceți.
Da?
PUBLIC: --trei
lucruri standard modificate sunt
listele dublu legate,
cele cu două terminații...
JASON KU: Da.
Practic, puteți
presupune că aveți...
acesta este cel pe care
probabil doriți să îl utilizați,
deoarece obțineți
indexare constantă.
Și apoi destul de
bine la ambele capete.
Dar dacă aveți nevoie de
un Q cu două capete,
îl puteți reduce și la a avea
două matrice dinamice spate în spate
atunci când mergeți în acest fel,
când mergeți în acest fel.
Și așa că există o mulțime de--
nu vă vom oferi asta
ca o metodă standard,
deoarece există literalmente
patru metode pe care v-am arătat
cum să faceți.
Deci tu alegi unul.
BINE.
Da?
PUBLIC: În interesul
de a economisi timp la examen,
dacă vrem să spunem, cum ar fi, facem
acest lucru cu secvența
AVL și este nevoie de log n timp.
Trebuie să spunem
propoziția ca, pentru că aceasta
este secvența AVL, durează
mai mult timp pentru că aceasta?
Sau putem spune ca,
pentru masa pe care o cunoaștem?
JASON KU: Da, nu.
Dacă mi-ai spus că
stochezi lucrurile într-o secvență
AVL și doar spui...
practic spui ce îi faci și spui,

ceea ce ia bla, bla, bla
, bla, timp,
nu trebuie să spui
pentru că  este o secvență AVL,
pentru că deja
ne-ai spus că este o secvență AVL.
Cred că
probabil ai scris diagrama
pe foaia de cheat
și ai căutat-o.  În
regulă.
Alte întrebări despre asta?
Nu.
Da?
PUBLIC: Asigurați-vă că
listele dublu legate
vor face inserarea
pe [INAUDIBIL]..
Este singura modificare?
JASON KU: Da.
Această listă dublu legată îi
oferă acestui tip timp constant.
Și de fapt, există
două operații aici,
inserare, ștergere și...
Presupun că există
și o găsire aici.
Dacă doar stochez
indicatorul de coadă,
acesta devine definit
la timp constant.
dar nu le aduce pe cele
dinamice la timp constant.
Trebuie să stochez
indicatorii anterioare și la fiecare nod.
Are sens?
BINE.
În sfârșit... sau cred că până la
urmă, setați structurile de date.
Sunt un
pic mai multe dintre acestea.
Nu atât de multe.
Dar da.
Am avut o matrice sortată, o
găsire bună, dar nu este dinamică.
Am stabilit arborele AVL, care
face destul de bine
găsirea și este dinamic.
Din nou, obțineți acest n
log n overhead pentru a construi,
pentru că, în esență, ceea ce
faceți cu ambele
structuri de date este să sortați.
Dar dacă mă uit
la o întrebare teorie,
de parcă nu
vă întreb ceva în mod
specific despre o
matrice sortată, dacă
aveți de ales între această
structură de date și această
structură de date, pe care o
alegeți?
Ei bine, nu prea
știu, pentru că
aproape că ăsta e mai bun în
toate, cu excepția ăsta.
Dar poate cineva să-mi spună cum să
fac și acest timp constant
?
Augmentare.
Aș putea doar să stocheze în
subarborele mele max sau min.
Și îl pot face pe acesta
strict mai bun decât acesta.
Deci, teoretic
, probabil că
vrei să-l folosești pe acesta.
Aici, tabele hash,
matrice cu acces direct,
chiar mai bine pentru
aceste operațiuni.
Grozav.
Dar sunt naibi de astea.
Deci, dacă aveți nevoie de acestea,
nu le folosiți.
Și în codificare reală,
mai ales dacă
codificați într-un limbaj care nu este
Python, ceva care nu vă
oferă automat
un tabel hash,
dacă sunteți în C într-un
laborator de microcontrolere la MIT
aici, luați
6115 sau  orice,
și faci asamblare,
de obicei ceea ce faci
este un lucru cu acces direct.
Pentru că asta
vă oferă săriturile
de care aveți nevoie în
limbajul mașinii
pentru a accesa
acest lucru în timp constant.
Asta, în general, dacă
aveți control asupra cheilor pe
care le puneți - pe care le
introduceți
în structura de date,
nu doriți ca această
suprasarcină de rulare a
cheilor printr-
o funcție hash
să caute aceste lucruri.
Doar stocați
lucrurile într-o matrice.
Folosești
tabelul hash atunci când nu
ai control asupra
cheilor sau cheile tale
sunt ca șirurile sau ceva de genul.
Deci, atunci
utilizați tabelul hash.
Acum, pentru scopurile noastre,
de obicei o tabelă hash
este la fel de bună, cu excepția cazului în care
vă cerem
limite pentru cel mai rău caz.
Și vom face asta
când vom vorbi despre
problema structurilor de date.
Dacă vă oferim o situație în care
nu ne interesează dacă obțineți
cel mai rău caz sunt
așteptate sau amortizate
sau oricare dintre aceste
lucruri, vă vom
spune doar, asigurați-vă că spuneți
care dintre ele îl obțineți.
Și atâta timp cât ai analizat
corect în ceea ce privește
structurile tale de date,
atunci ești bine.
Dar dacă spunem că ar fi bine să
faci cel mai rău caz aici, o să
te plesnesc.
Atunci, vă rog, obțineți acele limite.
Nu utilizați
tabelul hash în acest caz.
Are sens?
BINE.
În cele din urmă, avem
cozi prioritare despre care am vorbit.
Nu o să trec
prea mult prin asta.
Practic este doar
adăugarea acestui lucru la lucru.
Dar, în realitate, puteți
obține toate aceste limite
cu un AVL set --
mă refer la un arbore AVL secvență
cu creșterea maximă sau minimă,
care nu este pe această listă pentru că
nu am vorbit cu adevărat despre asta,
dar sperăm că puteți  --
dacă aveți nevoie de aceste limite
fără amortizare,
atunci le puteți atinge.  În
regulă.
Deci, acesta este, practic,
tot ce am
vorbit în clasă.
Vom petrece restul
timpului lucrând la câteva
probleme legate de structurile de date.
Nu sunt -- există o serie de
tipuri diferite de întrebări pe care le
veți
vedea de fapt la test --
testul de practică pe care
vi l-am oferit de la trimestrul trecut.
Există unele dintre ceea ce eu numesc
întrebări de tip mecanic
în partea din față.
Apoi, de obicei, unele
probleme de tip reducere
în care vă reduceți la
utilizarea unor algoritmi de sortare
sau a unor structuri de date.
Și apoi, de obicei, cele din
urmă sunt
acelea în care trebuie să faci
ceva suplimentar,
cum ar fi o creștere sau
un divide și cuceri
sau ceva de genul ăsta.
BINE.
Așa că vom
merge mai departe și vom petrece
restul timpului lucrând la
câteva dintre aceste probleme.
Acestea au fost din primăvara
lui 2019 la examen.
Și, de fapt, unul dintre
AT care ne face TA pentru noi
acum a fost și TA
pentru noi în primăvara anului 2019. A
notat problema
numărul 2 aici, problema de
cercetare ploioasă
, și m-a urât,
pentru că nimeni nu a făcut-o bine.  În
regulă.
Deci, să încercăm să
rezolvăm aceste probleme.
Deci problema 1 este
despre restaurant...
restaurant, da, OK.  În
regulă.
Deci, practic, ce se întâmplă?
Un restaurant popular,
Criminal Seafood.
Care este referința?
Fructe de mare legale.
Da, invers.
Nu acceptă rezervări,
dar menține o listă de așteptare
în care clienții care au
fost mai mult pe lista de așteptare
sunt așezați mai devreme.
Uneori, clienții decid
să mănânce în altă parte,
așa că restaurantul trebuie să
îi elimine de pe lista de așteptare.
BINE.
Să presupunem că un client
are un alt nume.
Nu sunt adăugați doi clienți
pe lista de așteptare
exact în același timp.
Deci există un fel de
ordine în care oamenii sunt
adăugați pe această listă de așteptare.
Are sens?
Proiectați o bază de date pentru a ajuta
Criminals Seafood să-și mențină
listele de așteptare care
să susțină următoarele
operațiuni, fiecare
în timp constant.
OK, deci aici, am refactorizat
timpul de rulare până sus.
Și este o... oh, îmi pare rău.
Am adăugat construcția aici.
Cred că este
încă timp constant.
E în regulă, OK.
PUBLIC: Am timp d--
JASON KU: Da.
Indicați dacă fiecare
operațiune de funcționare este cazul cel mai rău,
amortizat, așteptat.
Deci, când vezi acea
afirmație, spui: OK,
am voie să folosesc un
tabel hash dacă vreau.
Trebuie doar să mă
asigur că, dacă folosesc unul,
îmi etichetez operațiunile așteptate
și amortizate atunci când au loc.
Ce operațiuni sunt așteptate?
Practic toate.
Ce operațiuni sunt amortizate?
Cele care au schimbat ce este
în structura de date, inserează,
șterg.
BINE.
Deci avem niște operațiuni,
construind un lucru gol.
Adăugarea unui nume, deci acest nume este
x în spatele listei de așteptare.
Ce știu despre x?
Ce știu despre
nume conform presupunerilor noastre
din această clasă?
PUBLIC: Sunt unici,
deci pot fi o cheie.
JASON KU: Sunt unici,
deci pot fi o cheie.
Și se potrivesc într-un
număr constant de cuvinte,
după presupunerea noastră.
Așa că pot compara
două dintre ele în...
sau pot hash unul
în timp constant.
Acesta este un fel de presupunerea pe care o
facem pe aceste intrări,
sunt șiruri.
Și nu ți-am atribuit
o limită pentru lungimea lor,
așa că probabil că nu este ceva de care
trebuie să-ți faci griji.
OK eliminați un nume.
Deci deja am
senzația că trebuie să
pot găsi
lucruri după numele lor.
BINE.
Și apoi așezați
următoarea persoană la rând.
Are sens?
Deci, ce fel de lucruri
trebuie să întrețin aici?
Am oameni.  Au
nume și
au un fel de locuri,
ora la care au venit.
Dar mi se dau orele?
Nu. Nu
mi se dau ori nicăieri.
Nu este pe intrările
pentru operațiunile mele.
Așa că nu aș
putea să tastez la timp.
Are sens?
Care este
partea importantă despre vremuri?
Ordinea.
PUBLIC: Și ți se oferă asta.
JASON KU: Da.
Practic oricând... În
principiu,
încerc să mențin o
secvență pe tipii ăștia.
Există unul din față și
unul din spate și oameni în mijloc.
Și vreau să mă asigur
că ordinea rămâne aceeași,
altfel oamenii se vor
supăra pe mine,
pentru că ah, au venit aici
după mine și am primit...
da.
Ai fost în acea situație.
BINE.
Deci, încercăm să menținem
un fel de secvență,
o ordine extrinsecă
asupra acestor lucruri.
Dar trebuie și să putem
căuta oamenii
după numele lor, pentru că vreau să
pot schimba chestia asta.
Poate sună acest lucru familiar
unei alte probleme pe care le-am avut
în seturile de probleme ale acestui termen?
Da, cred că a fost
o problemă în care...
PUBLIC: Chatul.
JASON KU: Chatul.
Trebuia să stocați o secvență.
Dar aveai și acest dicționar
pe care trebuia să cauți lucrurile.
Acum, lucrul bun
la acea situație
este că lucrurile pe care
trebuia să le cauți
erau statice.
Și ce aș putea
folosi pentru dicționarul meu,
structura de date a setului meu pentru asta?
Îți amintește cineva?
Ai putea folosi doar
o matrice sortată.
Deoarece este
static, aceste lucruri
nu se actualizează tot timpul
și, prin urmare, a fost bine pentru mine
să folosesc doar o matrice statică.
Aici... și ți-am dat
timpi de căutare care
au fost logaritmici în cel mai rău caz.
Aici, cer
timp constant.
Matricea sortată nu o va
tăia,
setați AVL-ul nu o va tăia
, deci ce voi folosi?
PUBLIC: Dynamic--
JASON KU: O
matrice dinamică sau un tabel hash.
Acum, matricea dinamică ar putea să nu fie
grozavă, deoarece nu am de fapt
o limită numerică privind
cât de mari sunt aceste chei,
știu doar că
se potrivesc în cuvinte.
Deci, nu pot face de fapt
o matrice cu acces direct,
deoarece acele cuvinte --
deși se potrivesc într-un
număr constant de cuvinte,
nu știu dacă
reprezentarea întregului acestora
este mărginită de polinomi.
Are sens?
Deci vreau să folosesc
hashing în acest caz.
Și ce
vreau să întrețin?
Vreau să mențin o
structură de date secvențe asupra clienților.
Clienți.  E
un U acolo undeva?
Nu.
Este corect, nu?
BINE.
Și un set de cartografiere.
Deci, de obicei, așa fac.
De parcă aș vrea să spun un
set așezat pe ceva.
Dacă este doar un set,
atunci am doar cheia lui.
Pot să mă uit dacă acel
lucru este acolo sau nu.
Dar când îl fac de fapt
mapat la altceva, voi
spune, mapând o cheie, un spațiu,
la altceva, de obicei
elementul pe care îl
stochez sau poate
o proprietate a
elementelor pe care le stochez.
Are sens?
BINE.
Deci cartografierea, ce cartografiez aici?
Nume.
Pentru... oh.
La ce?
Vreau să fac o hartă?
Publicul: La timp...
JASON KU: Timpul.
Ora la care au intrat.
Vreau să fac asta?
PUBLIC: Ei bine, nu o puteți
face exact cu ora la care au
intrat, dar
secvența clienților
va arăta ce urmează în rând.
JASON KU: Da.
Vreau să-l stochez acolo unde
este în această secvență.
Așa că voi stoca indexul
acolo unde este în secvență
și îl pot căuta.
Sunt sunete... da?
Asta este...
PUBLIC: Am crezut că
indicii se schimbă.
JASON KU: Da.
Indicii se schimbă de fiecare dată când
adaug sau elimin lucruri.
PUBLIC: [INAUDIBIL]
JASON KU: Ah, da.
Stocați un indicator.
Indicatorul de plasat în succesiune.
Acum, este
puțin ciudat să spun,
pentru că nu ți-am spus cum
am reprezentat această secvență.
Dar din punct de vedere conceptual, pot
spune că desenez un indicator
către un loc în
asta care reprezintă locul în care se
află, mă voi ocupa de
detaliile despre asta mai târziu.
Dar, în general, o numesc
o structură de date legată,
pentru că fac legătura
între două structuri de date,
astfel încât să pot face o interogare într-una, să
zicem, și să aflu unde este
și cealaltă.
Sau faceți o interogare în
celălalt, așa ceva.
Deci, toată lumea înțelege
de ce am ales aceste lucruri?
Cum am abordat această problemă?
Da?
PUBLIC: Nu sunt sigur cum
un pointer rezolvă problema
stocării unui index.
Locul în care se află o persoană
în secvență se
va schimba în timp.
JASON KU: Mm-hmm.
PUBLIC: - presupunând că un
indicator se actualizează, s-ar
schimba asta?
JASON KU: Deci... OK.
Deci, să spunem dacă de fiecare dată--
deci să spunem că stochez-- să spunem că
stochez această
secvență într-o listă legată, să
spunem doar,
pentru că știu că va trebui să

inserez și să șterg lucruri
din mijlocul acestui lucru.
Are sens?  În
regulă.
Așa că voi merge
mai departe și voi spune că aceasta
va fi o listă legată.
Acum am această listă legată.
Deci, dacă am spus, în regulă,
structura datelor setului din setul meu
stochează--
sau stochează unde se află
în lista legată, să
presupunem că este stocată
la k, bine?
Misto.
Acum, dacă îl așez pe tipul ăsta,
îl lipesc la masa lui,
fiecare indice s-a schimbat.
Așadar, pentru a actualiza
indicii stocați în această structură de date setată
, trebuie să schimb
fiecare dintre ei.
PUBLIC: Da.
JASON KU: Are sens?
PUBLIC: Da, nu, asta
are mult mai mult sens.
JASON KU: Da.
Deci, într-adevăr, ceea ce vreau, nu să
stochez un număr aici,
ci un indicator real
către nodul care
conține acest lucru,
pentru că nodul
nu se schimbă decât dacă acel
lucru a părăsit structura mea de date.
Nodul, adresa acestui
lucru în memorie, nodul
este doar un mic
container care conține
un element și următorul
pointer și, de fapt,
vom avea nevoie de un
pointer anterior aici.  Vom avea
nevoie de
o listă dublu legată.
Pentru că ceea ce vom
face atunci când scoatem ceva,
trebuie să-l cusăm
înapoi
în timp constant,
ceea ce înseamnă că trebuie
să știm care este cel din fața
noastră și cel din spatele nostru.
Da?
Nu?  În
regulă.
Deci, lista legată aici.  Am
spus deja că poate
folosim un tabel hash aici.
Și așa, OK, grozav.
Acest lucru este, practic,
suficient pentru mine să spun,
aceasta este structura mea de date,
acestea sunt invarianții.
Care sunt invarianții?
Stochează toți clienții.
Acesta este un invariant.
Adică, nu este un
invariant foarte puternic, dar este...
da, vreau să spun, ar trebui să spun asta.
Stoc toți
clienții pentru că
va trebui să mă asigur
că păstrez asta atunci când
fac o interogare.
Și apoi aici, setați
numele de mapare la pointeri.
Locul în chestia asta.
Și pe măsură ce elimin lucruri,
trebuie să mă asigur că
acel invariant rămâne același.
Încă mapează toate
numele clienților pe
care îi am în
treaba mea la nodurile lor.
Deci, atunci când ceva
pleacă, mai bine
trebuie să mă asigur că
ambele lucruri sunt actualizate.
Are sens?
BINE.
Deci, cum întrețin
aceste operațiuni?
Avem un build--
build doar setează
fără aceste lucruri.
E mai ușor să spui asta.
Construiesc o listă goală legată
, liste dublu legate
de clienți
și construiesc un set -
un tabel hash care mapează nimic
cu nimic acum.
BINE.
Deci asta este construirea.  O să
fiu precis
aici și o să
scriu de fapt chestia
pentru că ți-am spus să nu
ignorați o
operație, altfel
nu vă putem da puncte pentru ea.
Următorul... da?
PUBLIC: Prin golire-- prin
construirea unei liste goale conectate--
JASON KU: Mm-hmm.
PUBLIC: --are
ca și capul și coada,
de fapt nu este niciunul,
dar, parcă, există?
JASON KU: Da, corect.
Este un lucru în
memorie pe care îl păstrăm.  Are
un indicator către
un cap și o coadă.
Acestea nu sunt chiar acum.
Dar vom adăuga lucruri la el.
BINE.
Deci, al doilea, adaugă numele.
Ce avem de spus?
Trebuie să actualizăm această
structură de date, astfel încât să
mențină că este o variație.
Trebuie să... de obicei
încep cu unul dintre ei.
Ajung la un punct în care
, o, chiar ar fi trebuit să îl
actualizez pe
celălalt mai întâi.
Așa că uneori este greșit sau ratat.
Ce vreau să fac aici?  Ei
bine, habar n-am unde
este asta în această secvență.
Așa că trebuie
să merg aici mai întâi.
Oh scuze.
Adăugând un tip, aș
putea face oricum.
Știu... unde va
merge?
Sfârșitul listei.
Așa că l-am lipit acolo.
Deci adăugați x la sfârșitul secvenței.
Așa că ajung la un
truc care îmi place.
Secvență, set.
BINE.
În acest caz, am doar
o secvență și un set.
Și așa numirea lor secvență
și set, probabil bine.
Nu am de gând să
încurc cu atât mai mare,
nu mă voi încurca pe mine.
Dar când am mai multe
dintre aceste lucruri,
sau chiar pentru concizie la un examen în
care am timp limitat,
dați un nume acestor lucruri.
Spuneți că aceasta este o secvență
C și M. Nu știu.
Văd un client aici,
văd o hartă aici, deci poate.  Nu
știu.
Dar doar dă-le
o scrisoare, apoi
te putem urmări mult mai
clar și te poți referi
la aceste lucruri mai precis.
Deci sfârșitul lui C.
Atunci ce trebuie să facem?
Îl repar pe tipul ăsta, e bun.
Acum trebuie să-l repar pe tipul ăsta.
Așa că adaug x la set și
îl mapez înapoi la acel nod din
care tocmai am venit.  L-aș
putea stoca într-
o variabilă temporară.
Adăugați x la M indicând
la n nodul v la v. OK.
Misto?
Așa că, am adăugat x-ul meu la sfârșitul lui
C într-un nod v. Sunt cam--
l-am etichetat ca să-
l pot referi mai târziu.
Și în cod, probabil mi-aș
aminti ce era acel nod.
Adăugați x la M indicând
acel nod
și acum mi-am menținut
invarianta.
Grozav.
PUBLIC: Poate [INAUDIBIL].
JASON KU: Adăugați cheia x.
Sau adăugați x la M având
cheia lui x punct la acel nod.
Are sens?
Există o subtilitate acolo.
3 3, avem eliminare...
Nu-mi amintesc
numele, indiferent.
BINE.
Deci aici, trebuie să facem...
ordinea lucrurilor.
Nu știu unde se
află în secvență,
dar o să-
l caut în set
și o voi
elimina din set
și o să mă uit
la orice indică
și  eliminați-l din secvență.  Nu mai am

timp aici,
așa că nu am de gând să
notez toate astea.
Înțelegeți
ce înseamnă asta.
Aici, folosim
faptul că este
o listă dublu legată, astfel încât să
putem reconecta lucrurile împreună.
Nu trebuie să-
mi spui cele trei puncte--
indicatorul anterior al
următorului meu lucru la următorul-- nu-i
așa?
Nu trebuie să-
mi spuneți cum să reconectați
acești indicatori pentru că am făcut
asta deja în setul de probleme 1
sau orice altceva.
Publicul: Doar în general, deoarece
vă aflați într-o situație în care
nu utilizați o
listă dublu legată...
JASON KU: Mm-hmm.
PUBLIC: unde
doar o listă legată
ar fi mai bună decât
o listă dublu legată,
deoarece se pare că
rezolvă întotdeauna problemele.
JASON KU: Da.
Listele dublu legate sunt
aproape întotdeauna strict mai bune
decât o singură legătură
în probleme de teorie.
Deci da, folosește-l.
BINE.
Și apoi scaun, ultimul.
Asta înseamnă doar să ia partea din
față a secvenței, să
o îndepărtezi, să schimbi
capul,
dar înțeleg că
poți șterge mai întâi.
Reduceți la
interfața pe care o aveam noi.  Mai
întâi ștergeți
din secvență.
Dar acum, avem o situație.  L-
am șters pe primul tip.
De unde știu cine
este primul tip?  Ei
bine, îi stochez
numele acolo.
Stoc numele
acestor clienți.
Deci știu cine este în
față, mă uit în această structură de date setată
și
elimin acea intrare.
Are sens?
Pentru că acum, nu mai trebuie
să mențin unde merge el.
Acum, în realitate, pur și
simplu nu aș putea
actualiza această structură de date setată.
Dar dacă fac asta, atunci, ei
bine, timpii mei de rulare
sunt încă timp liniar.
Nu-ți dau
o limitare a spațiului.
Sunt încă timp constant, îmi pare rău.
Deci, de fapt, nu
trebuie să faceți acea eliminare,
dar dacă acel client
se întoarce și dorește
să intre din nou pe lista de așteptare,
există lucruri de luat în considerare.
BINE.
Deci asta e întrebarea.
Următoarea întrebare, ultima
10 minute sau cam asa ceva.
Cercetarea Raniy.
Aceasta este o problemă
despre care oamenii au avut coșmaruri.
Bine, deci practic
avem un Meather Wan.
Este un meteorolog.
Un om de știință care studiază
precipitațiile globale.
Și are o grămadă
de senzori peste tot.
Și fiecare poate posta în
nor sau ceva de genul
o măsurătoare care are
forma unui triplu
de numere întregi r, l
și t unde r este
o cantitate pozitivă de
precipitații, un număr întreg;
o latitudine, iar un întreg
;  si la un moment dat.
Avem trei lucruri
de rezolvat aici.
naiba.
Dar toate sunt numere întregi.
Și nu fi ca,
oh, ei bine, Jason,
latitudinile sunt destul de mici.
Deci pot presupune că aceste
numere întregi sunt mici
și că aceste lucruri
necesită timp constant.
Nu
vă specific o rezoluție la care
măsoară aceste numere întregi.
Și nu ți-am dat o limită
între rezoluția respectivă
în comparație cu numărul de
măsurători pe care le am,
așa că nu joc acele jocuri.
BINE.
Vârful de precipitații
la o anumită latitudine
de la o anumită oră
este precipitația maximă
la orice măsurătoare la acea
latitudine, măsurată la un moment
mai mare sau
egal cu acel moment.
Are sens?
Sau 0 dacă nu există
măsurători la acea latitudine.
BINE.  A
marca după timp... sau
înainte de timp sau orice altceva.
Descrieți o bază de date pe care
o putem construi în timp constant.
Este una goală... L-
am adăugat pe acesta
pentru că nu ne-am simțit
bine cu asta primăvara trecută.
Înregistrați datele.
Vă oferim un triplet.
Și apoi... deci înregistrați datele,
pentru a fi corecte,
trebuie doar să păstrez
acele informații.
Pentru acest tip de
actualizări, nu...
îmi este foarte greu să argumentez
că acest lucru este corect.
Pentru că doar...
îl arunc în
baza de date, baza de date
nu trebuie să-
mi dea nimic înapoi.
Deci, lucrul important
aici despre corectitudine
este că ploile de vârf îmi dă
mie și mi-l oferă
în limita de timp pe
care o caut.
Iar precipitațiile de vârf
returnează precipitațiile de vârf
la o anumită
latitudine începând cu or.
Deci avem trei lucruri.
Da?
PUBLIC: Având în vedere
că nu trebuie să
returnați niciodată o singură măsurătoare,
este că [INAUDIBLE]
aveți o înregistrare a acesteia?
JASON KU: Există
potențialul că
nu aveți nevoie să stocați
toate informațiile
pentru că tot ceea ce
facem este să vă
returnăm R-urile, în esență.
Este posibil să nu fie
nevoie să stocați deloc latitudinile
sau orele.  Nici
măcar nu trebuie
să depozitați tripleții.
Acum, în realitate, mă întreb
despre latitudini și timpi.
Așa că ar trebui să
le depozitez undeva,
dar s-ar putea
să le comprim.
În special, multe lucruri ar putea
fi stocate la aceeași latitudine.
Acesta este un fel de
rostul interogării.
Și așa vrem... Vreau să
spun, s-ar putea să avem nevoie să
stocăm acea latitudine o singură dată.
Are sens?
BINE.  O să
aștept
întrebări până
după pentru că vreau să ajung la
o soluție la această problemă.  În
regulă.
Deci, ce trebuie să facem?
Trebuie să putem
adăuga lucruri.
Și vreau să mă întorc.
Deci reveniți, va
trebui să întreb ceva
și apoi voi
returna ceva.
Deci reveniți la vârful precipitațiilor la
latitudinea l din momentul t.
Ce îmi pasă
într-o anumită interogare?
Îmi pasă doar de toate
lucrurile de la l, la latitudinea l.
Deci, într-adevăr, acesta nu este un
lucru atât de interesant,
dar vreau să pot avea
poate multe structuri de date, câte una
asociată cu fiecare L.
Are sens?
Și cum pot găsi
câte unul în fiecare L rapid?
Pune-l într-un dicționar.
Care este timpul meu legat?
Cel mai rău caz jurnal n.
Deci, ce structură de date folosesc
pentru acea structură de date setată?
Un set AVL.
Deci, mai
întâi veți avea un set AVL-- să
zicem, L-- cartografierea latitudinilor la--
ei bine, acum avem
mai multe structuri de date.
Vreau să stochez o mulțime
de lucruri care
au aceleași latitudini
într-o altă structură de date.
Cei care
stochează probabil timpii
în precipitații ale
tuturor acelor măsurători.
Da?
Da.
PUBLIC: O masă hash.
JASON KU: O masă hash.
OK, deci ce fel
de interogări voi
dori să fac asupra lucrurilor
de la aceeași latitudine?
PUBLIC: Veți
dori să obțineți timpurile.
JASON KU: O să vreau
să aflu orele,
dar mai mult decât atât, fac
o interogare ordonată.
Am nevoie de lucruri mai puțin
de un anumit timp.
Mai mare, scuze.
PUBLIC: Deci este într-adevăr...
JASON KU: Doar o secundă.
PUBLIC: Ați putea să vă
placă un AVL pentru timp
și un AVL pentru ploaie?
JASON KU: OK.
Îmi pasă de un
AVL pentru ploaie?
Adică, privind în sus
la ploaie.
AUDIENTĂ: Nu.
JASON KU: Nu.
Deci voi merge mai departe
și voi stoca aceste lucruri
într-un AVL sortat în timp la
maparea latitudinii l la--
Voi numi această
structură de date o structură de date de timp
.
Am să spun că este t de l.
Pare un fel de
recurență,
așa că
mă enervează puțin acum,
dar nu am
nimic mai bun.  În
regulă.
Deci, acum, fiecare dintre aceste
structuri de date de timp
este un timp stabilit de mapare AVL
la măsurarea precipitațiilor.  În
regulă.
Deci asta va...
dacă întrebarea mea a fost, returnarea
maximă a precipitațiilor...
îmi pare rău.
Întoarceți precipitațiile de lucru
cu latitudinea l și timpul t, am
terminat, cam.
Veți ști cum să
susțineți această interogare.
Pentru a insera lucruri,
inserez lucruri
în ambele structuri de date
și doar le caut.
Singura complicație
aici este că nu
întreb care sunt
precipitațiile la un moment dat.
Vreau să știu care
sunt precipitațiile maxime până la această oră.
BINE.
Deci max heap e bun dacă
vreau să știu valoarea maximă globală.
Dar aici, vreau să știu
maximul delimitat de un anumit interval.
Așa că vom...
poți să-mi pui
întrebări după asta,
rămânem
puțin timp fără timp.
Deci cineva are o idee despre cum...
da?
PUBLIC: Ați putea doar să
măriți AVL cu maxim?
JASON KU: OK.
PUBLIC: Și poți să te
uiți doar la copilul potrivit
și apoi să te uiți la
maxim în acel moment?
JASON KU: Ah, bine.
Deci, ceea ce
spune colegul tău,
dacă creștem cu r
maxim din subarborele meu,
poate că putem folosi asta pentru a
înțelege această interogare.
Pentru că suntem ordonați
pe t,
avem această proprietate monotonă drăguță
că tot ceea ce
va fi în interogarea mea -
totul la dreapta
unui anumit timp -
dacă timpul meu este peste t
la un anumit nod,
în tot ceea ce este în
subarborele din dreapta
este, de asemenea, deasupra acelui t din cauza
ordinii structurii de date a setului meu
, deoarece
sunt ordonat la timp.
Deci, poate există
posibilitatea ca, dacă mă
uit la subarborele meu drept
, să nu pot
lucra peste tot
aici doar privind
maximul din acel subarbor.
deci Aceasta este o idee de, să
spunem, mărită de subarborele max r.
Probabil că vrei să-i
dai și un nume.
Deci, ca v max unde v
este un nod în treaba mea.
Și vreau să arăt cum să
susțin asta, cum pot să calculez
asta din copiii ei.
Deci, cum
suport de fapt această interogare,
mă pot gândi recursiv.
Am câteva cazuri.
Dacă sunt la un v aici, vreau să
definesc o funcție recursivă
care se numește precipitații de vârf
a unui nod dat, mărginit inferior
de un t.
Deci, dacă sunt aici,
sunt două cazuri.
Fie, timpul meu este mai mare
sau mai mic-- este în raza mea de acțiune
sau în afara razei mele.
Dacă este în afara
domeniului meu, ce fac?
Este mai mic decât timpul meu limitat.
Pot apela recursiv
această funcție pe acest nod.
Pentru că știu că

aici va fi orice la
care îmi pasă.
Și acesta este doar un
apel recursiv în jos.
Și așa că, dacă mă limitez
la un singur apel recursiv în
jos, mereu
cobor de fiecare dată.
Acest lucru va dura
timp logaritmic.
Deci, acesta este primul caz,
acesta este cazul ușor.
Acest lucru nu se află în rază,
returnez recursiv lucrul
din dreapta mea.
Care este celălalt caz?
Sunt în raza mea.  Ei
bine, acum aș putea să mă întorc, să
sun recursiv ambele părți.
Pentru că despre asta
vorbește acest vârf.
Care sunt precipitațiile mele maxime?
Dar dacă fac asta, dacă
îl numesc aici recursiv
și îl numesc aici recursiv,
asta ar putea dura timp liniar.  S-
ar putea să ating fiecare
nod din arborele meu.
Deci de ce am făcut
această mărire?
Deci nu trebuie să
lucrez la acest nod.
Pur și simplu returnez
precipitațiile maxime în acest subarbore
și apoi recurg pe această parte.
Așa că am
lucrat constant pe această parte,
am făcut un
apel recursiv aici jos, pe
care ai putea să mergi în
partea de jos, dar este în regulă,
îmi permit să merg în partea de
jos a copacului.
Are sens?
Și dacă nu am niciun
subarbore, atunci am terminat.
Dacă în orice moment.
Nu am nodul pe care ar
trebui
să recurg, iau
maximul acestui subarbore, eu însumi
și oricare ar fi
valoarea de returnare recursivă aici.
Și comparând trei valori,
returnând max.
Are sens?
BINE.
Deci asta este ceea ce numim
o interogare unilaterală.
Deci, în
sesiunea cu probleme 4, la care nu am ajuns,
vă arată o modalitate de a face acest lucru
pentru o interogare pe două fețe,
în care trebuie să știu maximul
dintre toate lucrurile dintre două
lucruri.
Dar nu este cu adevărat mai
dificil decât asta
să găsești o funcție recursivă
care folosește o creștere, astfel
încât să nu fii nevoit să faci
apeluri recursive de ambele părți.
Are sens?
BINE.
Asta va fi deocamdată
și pot răspunde la întrebări după.
Mulțumesc pentru vizită.