[SCRÂȘIT]
[FOSȘIT]
[CLIC]
ERIK DEMAINE: Bună dimineața.
PUBLIC: Buna dimineata!
ERIK DEMAINE: Bun venit la 006,
Introducere în algoritmi,
cursul doi.
Sunt Erik Demaine și
iubesc algoritmii.
Esti cu mine?
[Aplauze]
Da.
Astăzi, nu
facem algoritmi.
Nu, facem structuri de date.
E bine.
Există o mulțime de algoritmi
în fiecare structură de date.
Este ca și mai mulți
algoritmi gratuit.  Vom
vorbi
despre secvențe
și seturi,
liste legate și tablouri dinamice.  Structuri de
date destul de simple
astăzi.
Acesta este începutul
mai multor structuri de date
despre care vom vorbi
în următoarele câteva prelegeri.
Dar înainte de a
începe cu unul,
permiteți-mi să vă spun/
vă reamintesc de diferența dintre
o interfață, pe care o
puteți numi API
dacă sunteți programator sau
ADT dacă sunteți o
persoană cu algoritmi antici ca mine.  --
versus o structură de date.
Acestea sunt distincții utile.
Ideea este că o interfață
spune ce vrei să faci.
O structură de date
spune cum o faci.
Așa că ați putea numi
asta o specificație.
Și în contextul
structurilor de date,
încercăm să stocăm unele date.
Deci, interfața va specifica
ce date puteți stoca,
în timp ce
structura de date vă va oferi
o reprezentare reală și
vă va spune cum să le stocați.
Acest lucru este destul de plictisitor.
Doar stocarea datelor
este foarte ușoară.
Doar o arunci într-
un dosar sau ceva de genul ăsta.
Ceea ce îl face interesant este să
faci operațiuni pe acele date.
În interfață, specificați
ce fac operațiunile,
ce operațiuni sunt
acceptate și, într-un anumit sens,
ce înseamnă acestea.
Și structura de date
vă oferă de fapt algoritmi -
aici
intervin algoritmii -
pentru cum să susțineți
acele operațiuni.  În
regulă.
În această clasă, ne vom
concentra pe două interfețe principale
și pe diverse dintre ele speciale.
Ideea este să separă ceea ce
vrei să faci de cum să faci.
Pentru că... te poți gândi la
asta ca la afirmația problemei.
Ieri... sau, ultima clasă,
Jason a vorbit despre probleme
și a definit ce este o problemă
versus soluții algoritmice
ale problemei.
Și aceasta este noțiunea analogă
pentru structurile de date, în care
dorim să menținem
unele date în funcție
de diverse operații.
Aceeași problemă poate fi
rezolvată prin multe structuri de date diferite
.
Și asta o să vedem.
Și diferite
structuri de date vor
avea avantaje diferite.  S-
ar putea să suporte unele
operațiuni mai rapid decât altele.
Și în funcție de
ceea ce utilizați de fapt
acele
structuri de date,
alegeți structura de date potrivită.
Dar puteți menține
aceeași interfață.  Ne vom
gândi
la două structuri de date.
Una se numește mulțime și
una se numește secvență.
Aceștia sunt termeni foarte încărcați.
Set înseamnă ceva
pentru un matematician.
Înseamnă altceva
pentru un programator Python.
Secvență, la fel.
Bănuiesc că nu există un
tip de date de secvență Python încorporat.
Ideea este că vrem
să stocăm n lucruri.
Lucrurile vor fi
destul de arbitrare.
Gândiți-vă la ele ca
numere întregi sau șiruri de caractere.
Și, pe de o parte, ne
pasă de valorile lor.
Și poate că vrem să
le menținem în ordine sortată
și să putem căuta
o anumită valoare, pe care o
vom numi cheie.
Și pe de altă parte, ne
pasă să reprezentăm
o anumită secvență la
care ne pasă.
Poate că vrem să reprezentăm
numerele 5, 2, 9,
7 în acea ordine și să le stocăm.
În Python, puteți stoca
asta într-o listă, de exemplu.
Și va
urmări această ordine.
Și acesta este primul articol,
al doilea articol, ultimul articol.
Astăzi, ne vom
concentra pe această structură de date secvențe
, deși
la sfârșit, voi
menționa interfața pentru seturi.
Dar
astăzi vom rezolva secvențe.
Și în următoarele
câteva prelegeri,
vom reveni
între acestea.
Sunt strâns legate.
Destul de abstract momentan.
Pe de altă parte, vom
avea două principale - să
le numim
instrumente sau abordări ale structurii datelor.
Unul este matrice, iar
celălalt este pointeri -- structuri de date
bazate pe pointeri sau
legate.  S-
ar putea să le fi văzut pe acestea.
Sunt foarte folosiți în
programare, desigur.
Dar le vom vedea pe amândouă
astăzi.
Voi reveni la acest tip
de moment.  Să
intrăm în
interfața de secvență, din care
am convenabil o parte aici.
Există câteva
niveluri diferite de secvențe
care ne-ar putea interesa.
Voi începe cu
interfața de secvență statică.
Aici numărul
de articole nu se modifică,
deși elementele reale s-ar putea.
Aici avem n articole.
Le voi eticheta x 0
la x n minus 1, ca în Python.
Deci numărul de articole este n.
Și operațiunile pe care vreau
să le susțin sunt construirea,
lungimea, iterația, obținerea și setarea.
Deci ce fac acestea?
Construirea este modul în care începeți.
Pentru a construi o structură de date
în această interfață,
apelați build of x.
Exact modul în care specificați x nu este
prea important, dar ideea este că
vă dau câteva
articole într-o anumită ordine.
În Python, acesta
ar fi un iterabil.  O sa
vreau sa
stiu si lungimea lui.
Și vreau să fac o nouă
structură de date de dimensiune
și o nouă
secvență statică de dimensiune n
care are acele
elemente în acea ordine.
Deci așa
construiești unul dintre acestea.
Pentru că într-un fel,
trebuie să specificăm n
acestei structuri de date,
deoarece n nu i se va
permite să se schimbe.  Îți voi
da
o metodă de lungime.
Metodele sunt
modul orientat pe obiect
de a gândi operațiunile pe
care le acceptă interfața dvs.
Length va returna doar
această valoare fixă ​​n.
Iter secvență.
Acesta este sensul în care
dorim să menținem ordinea.
Vreau să pot scoate
x 0 prin x n minus 1
în ordinea secvenței,
în ordinea specificată în care
au fost încorporați
sau în care a fost schimbat.
Aceasta va repeta
prin toate elementele.
Deci, va dura cel puțin
timp liniar pentru a scoate asta.
Dar mai interesant este că
putem accesa dinamic oriunde
în mijlocul secvenței.
Putem obține al i-lea element,
x i, având în vedere valoarea i,
și putem schimba x i
într-un nou element dat.
BINE.
Deci asta se numește
get_at și set_at.
Destul de direct.
Acest lucru ar trebui să vă reamintească
foarte îndeaproape de ceva --
o structură de date.
Deci aceasta este o interfață.
Acesta este ceva ce
poate vreau să rezolv.
Dar care este
structura de date evidentă
care rezolvă această problemă?
Da?
PUBLIC: O listă.
ERIK DEMAINE: O listă.
În Python, se numește listă.
Prefer să-i numesc o
matrice, dar fiecare a lui.
Vom folosi „listă”.
Lista ar putea însemna multe
lucruri, dar soluția
la această problemă de interfață -
soluția naturală - este
ceea ce voi numi o matrice statică.
Jason le-a menționat
în prima lecție.
Este puțin
complicat pentru că
nu există matrice statice în Python.
Există doar
matrice dinamice,
lucru la care vom ajunge.
Dar vreau să vorbesc despre ce
este o matrice statică, de fapt?
Și asta se referă
la noțiunea noastră despre...
modelul nostru de calcul,
despre care a vorbit și Jason, pe
care îl numim
cuvântul RAM, îți amintești?
Ideea, în cuvântul RAM,
este că memoria ta
este o matrice de cuvinte pe w-biți.
Acesta este un pic circular.
Voi defini o matrice
în termenii cuvântului RAM, care
este definit în termeni de matrice.
Dar cred că știi ideea.
Deci avem o memorie mare care
se extinde la infinit, poate.
Este împărțit în cuvinte.
Fiecare cuvânt aici este lung de w biți.
Acesta este cuvântul 0, cuvântul 1, cuvântul 2.
Și puteți accesa
această matrice aleatoriu--
memorie cu acces aleatoriu.
Așa că vă pot da numărul
5 și obține 0 1, 2, 3, 4,
5, al cincilea cuvânt din această memorie RAM.
Așa funcționează amintirile reale.
Puteți accesa oricare dintre
ele la fel de rapid.
OK, deci asta e memoria.
Și deci ceea ce vrem să facem
este, când spunem o matrice,
vrem ca aceasta să fie o
bucată consecutivă de memorie.
Lasă-mă să iau culoare.  Să
presupunem că am o serie
de mărime 4 și locuiește aici.
Jason nu poate scrie,
dar eu nu pot număra.
Deci cred că sunt patru.
Avem... așa că matricea începe
aici și se termină aici.  Are
dimensiunea 4.
Și este consecutiv,
ceea ce înseamnă că,
dacă vreau să accesez
matricea la poziția--
la indexul i, atunci acesta
este același lucru cu
accesarea matricei mele de memorie
la poziția--
oriunde
începe matricea, ceea ce eu"  Voi
apela adresa matricei --
în Python, acesta este ID-ul matricei --
plus i.
BINE.
Aceasta este doar o simplă
aritmetică offset.
Dacă vreau să știu al
0-lea element al matricei,
este chiar aici, de
unde începe.
Primul articol este
unul după aceea.
Al doilea articol
este unul după aceea.
Deci, atâta timp cât îmi stochez
matricea consecutiv în memorie,
pot accesa matricea
în timp constant.
Pot să fac get_at și
set_at cât de repede pot să
accesez aleatoriu
memoria și să obțin valoare--
sau să setez o valoare-- care
presupunem că este un timp constant.
Accesul meu la matrice
este în timp constant.
Acesta este ceea ce permite
unui tablou static
să rezolve de fapt această problemă
în timp constant pentru
operația get_at și set_at.
Acest lucru poate părea simplu, dar
chiar vom avea nevoie de acest model
și ne vom baza cu adevărat pe acest model din ce în ce
mai mult pe măsură ce ajungem la
structuri de date mai interesante.
Este prima dată când
avem nevoie de el.
Să vedem.
Lungimea este, de asemenea, timp constant.
Vom
stoca acel număr
n, împreună cu adresa lui.
Și construirea va
dura timp liniar.
Iterația va dura timp liniar.
Destul de direct.
Bănuiesc că un lucru
aici, atunci când definesc
construcția, trebuie să introduc
puțin mai mult
din modelul nostru de
calcul, și
anume cum se creează o
matrice la început?
Susțin că aș putea face acest lucru
în timp liniar,
dar asta este doar o
parte a modelului.
Acesta se numește
modelul de alocare a memoriei.
Există câteva
opțiuni posibile aici,
dar cea mai curată
este doar să presupunem
că puteți aloca o matrice
de dimensiune n în timp theta n.
Deci este nevoie de timp liniar pentru a
face o matrice de dimensiunea n.  Vă
puteți imagina că
acest lucru este constant.  Nu prea
contează.
Dar este nevoie de muncă.
Și în special, dacă alocați doar
o bucată de memorie,
nu aveți idee dacă
este inițializată.
Deci, inițializarea acelei matrice
la 0 va costa timp liniar.
Nu va conta cu adevărat,
constant versus liniar,
dar un efect secundar frumos al
acestui model este că spațiul --
dacă doar alocați
matrice,
cantitatea de spațiu pe care o utilizați
este, cel mult, cantitatea de timp pe care o
folosiți.
Sau, cred, marele O din asta.
Deci, aceasta este o caracteristică frumoasă.
Este destul de ciudat
dacă vă imaginați--
este nerealist să vă imaginați că
puteți aloca o matrice de
dimensiune infinită și apoi
utilizați doar câteva elemente din ea.
Asta nu vă va oferi o
structură de date bună.
Deci vom presupune că costă
alocarea memoriei.
Bine, minunat.
Am rezolvat problema secvenței.
Foarte simplu, cam plictisitor.
Acestea sunt timpii optimi de rulare.
Acum, haideți să o facem interesantă--
asigurați-vă că nu am ratat
nimic--
și vorbiți despre-- oh, este
un lucru despre care vreau
să vorbesc în cuvântul RAM.
Un efect secundar al acestei presupuneri
că accesul la matrice ar trebui să
dureze timp constant și că
accesarea acestor poziții
din memoria mea ar trebui să ia
timp constant
este că trebuie să presupunem că
w este cel puțin log n sau cam asa ceva.
w, amintiți-vă, este
dimensiunea cuvântului mașinii.
În computerele reale,
acesta este în prezent 64--
sau 256, în unele
instrucțiuni bizare.
Dar, de obicei, nu ne
gândim la mașină
ca fiind mai mare în timp, dar ar
trebui să vă gândiți la mașină
ca fiind mai mare în timp.
Aceasta este o afirmație
care spune că
dimensiunea cuvântului trebuie să crească cu n.
Ar putea mai repede
decât log n, dar
trebuie să crească cel puțin la fel de
repede ca log n.  De
ce spun asta?
Pentru că dacă am n lucruri cu
care mă confrunt... n,
aici, este dimensiunea problemei.
Poate că este matricea pe care
încerc să o stochez... orice.
Dacă trebuie să mă ocup de
n lucruri din memoria mea,
cel puțin, trebuie să
le pot aborda.  Ar trebui să
fiu în stare să
spun, dă-mi i-a
și reprezint acel
număr i într-un cuvânt.
În caz contrar, deoarece mașina
este proiectată să funcționeze numai
cu cuvinte de pe w biți
în timp constant,
vor dori să poată
accesa al-lea
cuvânt în timp constant,
am nevoie de o dimensiune a cuvântului
care să fie cel puțin log n doar
pentru a rezolva asta.  și n lucruri
din intrarea mea.
Deci aceasta este o
presupunere total rezonabilă.
Poate părea ciudat pentru că
te gândești la o mașină reală
ca având
dimensiune constantă, dar o mașină reală
are și RAM de dimensiune constantă.
Aparatul meu are 24 de giga
de memorie RAM sau orice altceva.
Acel laptop are 8.
Dar nu crezi că
asta se schimbă în timp.
Dar, desigur, dacă doriți
să proceseze o intrare mai mare,
ați cumpăra mai multă RAM.
Deci, în cele din urmă, când
n-urile noastre devin foarte, foarte mari,
va trebui să
creștem w doar
ca să putem aborda RAM-ul respectiv.
Aceasta este intuiția aici.
Dar aceasta este o modalitate de a
pune realitatea, care sunt
mașini fixe, cu teoria.
În.
Algoritmi, ne pasă de
scalabilitate pentru n foarte mari.
Vrem să știm care
este acea funcție de creștere și să ignorăm
factorul constant de plumb.

Despre asta este notarea asimptotică.
Și pentru asta, avem nevoie de o noțiune
a mărimii cuvântului care se schimbă și
în acest mod asimptotic.  În
regulă.
Acest lucru ar fi mai
important săptămâna viitoare,
când vorbim despre
hashing și de ce hashingul
este un lucru rezonabil de făcut.
Dar să trecem la
secvențe dinamice, care este
locul în care lucrurile devin interesante.
Am actualizarea aici.
Începem cu secvențe statice.
Toate aceste
operațiuni sunt încă
ceva pe care vrem să le susținem
într-o secvență dinamică,
dar adăugăm două
operațiuni dinamice - operații
oarecum controversate
, foarte interesante.
Vreau să pot introduce
în mijlocul secvenței mele
și vreau să pot șterge
din mijlocul secvenței mele.
Iată secvența mea, la care mă voi
gândi într-o imagine.  O să-l
desenez ca
o matrice.
Dar este stocat
oricum este stocat.  Nu
știm.
Aceasta este o interfață,
nu o implementare.
Deci avem x 0, x 1, x 2, x 3.
Și să presupunem că
inserez la poziția 2.
Poziția 2 este aici.
Așa că vin cu
noul meu x și
aș vrea ca x să fie
noul x 2, dar nu
vreau să pierd nicio informație.
Dacă aș face set_at 2, atunci l-
aș șterge și l-aș înlocui
cu x.
Dar vreau să fac insert_at,
ceea ce înseamnă că toți acești tipi,
conceptual, se
vor schimba
cu 1 în ceea ce privește indicii lor.
Apoi, aș obține această
imagine care este una mai mare.
Și acum am noul x.
Am ceea ce era
vechiul x 2, pe care nu--
ezit să-l numesc pe x 2 pentru că
acesta este numele său vechi, nu
numele său nou.
Voi desena săgeți pentru a
spune că tipii ăștia sunt copiați.
Acestea sunt cu
siguranță neschimbate.
Noul nostru x 2, care
prim este x Acesta
este x3 prim, 4 prim și așa mai departe.
Vreau să fiu atent aici--
și, desigur, noul n prim
este n plus 1.
Vreau să fiu atent la
etichetare, deoarece cheia--
ceea ce face ca insert_at să fie interesant
este că, mai târziu, când apelez la
get_at, este  cu
noua indexare.
Deci, anterior, dacă aș obține_at
la 2, aș obține această valoare.
Și după aceea, dacă
aș obține_at la 2,
aș obține noua valoare.
Dacă aș ajunge_at
la 3 aici jos,
aș obține valoarea
care era X 2.
Poate că este greu de urmărit.
Dar acesta este un
lucru foarte util din punct de vedere conceptual
, mai ales când
inserați sau ștergeți
la capete.
Deci vom defini, în
special, inserarea și ștergerea
primul și ultimul.
Acestea sunt uneori date --
dacă aveți o inserție,
aceasta are un x.
Dacă faci o ștergere, nu
are niciun argument.
Aceasta înseamnă inserare_la
începutul matricei, ceea ce
ar fi ca și cum l-ați adăuga aici.
Și insert_last înseamnă să-l
adaugi aici.
insert_last nu
modifică indicii
niciunuia dintre elementele vechi.
Aceasta este o caracteristică frumoasă
a insert_last.
Inserați-mai întâi le
modifică pe toate.
Toate sunt mărite cu 1.
Și ne interesează, de asemenea,
lucrurile similare aici.
Am putea face get-first sau
-last sau set-first sau -last,
care sunt cazurile speciale evidente
de get_at și set_at.
Acum, aceste
cazuri speciale sunt deosebit de
interesante într-un
context de algoritmi.
Dacă ai fi matematician,
ai spune, ei bine,
de ce mă deranjez?
Aceasta este doar prescurtarea unui
anumit apel de primit sau stabilit.
Dar ceea ce îl face interesant
din perspectiva structurilor de date
este că ne pasă
de algoritmi pentru susținerea
acestor operațiuni.
Și poate,
algoritmul pentru sprijinirea
get-first sau set-first, sau în
special, insert-first sau
insert_last, ar putea
fi mai eficient.
Poate că putem rezolva
această problemă mai bine
decât putem rezolva insert_at.
Deci, deși, în mod ideal,
am putea rezolva
întreaga
interfață dinamică a secvenței de pregătire a timpului constant
, acest lucru
nu este de fapt posibil.
Poți dovedi asta.
Dar cazuri speciale în care
doar
introducem și conducem de la
sfârșit, să zicem, putem face asta.  De
aceea este interesant să
introducem cazuri speciale la care ne
pasă.
Misto.
Aceasta este definiția
interfeței secvenței dinamice.
Acum,
chiar o vom rezolva.
Prima noastră structură de date pentru
aceasta se numește liste legate.
Ați luat, probabil... probabil că ați mai
văzut liste legate
la un moment dat.
Dar partea principală nouă
aici este că
le vom analiza de fapt
și vom vedea cât de eficient
implementează toate aceste
operațiuni care ne-ar putea interesa.  În
primul rând, revizuiește.
Ce este o listă legată?
Ne stocăm articolele
într-o grămadă de noduri.
Fiecare nod are un element
în el și un câmp următor.
Deci, vă puteți gândi la
acestea ca obiecte de clasă
cu două variabile de clasă,
elementul și indicatorul următor.
Și le asamblam într-un
astfel de tip de structură
în care stocăm --
în câmpurile articolului, vom
stoca valorile reale
pe care vrem să le reprezentăm
în succesiunea noastră, de la x 0
la x n minus 1, în ordine.
Și apoi vom folosi
următorii indicatori pentru a le lega pe
toate împreună în această ordine.
Deci următoarele indicații sunt cele care
ne dau de fapt ordinea.
Și în plus, vom
urmări ceea ce se
numește capul listei.
Structura datelor va
fi reprezentată de un cap.
Dacă doriți,
puteți stoca și lungimea.
Aceasta ar putea fi
structura de date în sine.
Și indică toate
aceste tipuri de structuri de date.
Observați, tocmai am văzut o
structură de date bazată pe matrice,
care este doar o
matrice statică, și am
văzut o
structură de date bazată pe pointer.
Și ne bazăm pe faptul
că pointerii pot fi stocați
într-un singur cuvânt, ceea ce înseamnă că
le putem dereferenția--
putem vedea ce se află de
cealaltă parte a pointerului--
în timp constant în
modelul nostru cu cuvântul RAM.
În realitate, fiecare dintre aceste
noduri este stocat undeva
în matricea computerului.
Deci poate că fiecare
are două cuvinte,
deci poate un nod este--
primul nod este aici.
Poate cel de-al doilea nod este aici.
Al treilea nod este aici.
Sunt într-o ordine arbitrară.
Folosim acest fapt, că
putem aloca o matrice de dimensiune n
în timp liniar --
în acest caz, vom
avea matrice de dimensiunea 2.
Putem spune doar, oh, vă rog să-
mi dați o nouă matrice de  mărimea 2.
Și asta ne va face
unul dintre aceste noduri.
Și apoi stocăm indicii.
Pointerii sunt doar indici
în matricea gigantică de memorie.
Ei doar, care este
adresa acestei mici matrice?
Dacă v-ați întrebat vreodată cum
sunt implementați indicatorii,
sunt doar numere care
spun unde, în memorie, este
chestia asta aici?
Și în memorie, sunt
în ordine arbitrară.
Acest lucru este foarte frumos, deoarece
este ușor să manipulați
ordinea unei
liste legate fără a
muta fizic nodurile,
în timp ce matricele sunt problematice.
Poate că merită menționat.
Să începem să analizăm lucrurile.
Deci ne pasă de aceste
operații de secvență dinamică.
Și am putea încerca să
o aplicăm structurii de date a matricei statice
sau am putea încerca
să implementăm aceste operații
într-o matrice statică.
Este posibil, doar că nu va
fi foarte bun.
Și putem încerca să-
l implementăm cu liste legate.
Și nici nu va
fi atât de grozav.
Să mergem aici.
Scopul nostru este
următoarea structură de date,
care este matrice dinamică.
Dar listele legate și
matricele statice
au fiecare avantajele lor.  Să
analizăm mai întâi
operațiile de secvență dinamică,
mai întâi pe un tablou static
și apoi pe o listă legată.
Pe o matrice statică,
cred că vedeți cu toții,
dacă încerc să inserez la
începutul matricei static--
acesta este cel mai rău caz.
Dacă introduc mai întâi, atunci
toată lumea trebuie să se schimbe.
Dacă am de gând să
mențin acest invariant,
că al-lea element din
matrice reprezintă--
Presupun că nu
l-am scris nicăieri aici.
Poate aici.
Matrice statică.
Vom menține
acest invariant că a din i
reprezintă x i.
Dacă vreau să mențin
asta în orice moment, când
introduc un
lucru nou în față,
deoarece indicii tuturor
articolelor anterioare se modifică,
trebuie să petrec timp
pentru a le copia.  O
poți face în
timp liniar, dar nu mai bine.
Matrice statică.
Inserarea și ștergerea oriunde
costă mult timp -
de fapt, din două motive.
Motivul numărul unu este că,
dacă suntem aproape de front,
atunci trebuie să facem schimbarea.
Ce zici de inserarea sau ștergerea
ultimului element al unui tablou?  E mai
ușor?
Pentru că atunci, dacă introduc
chiar ultimul element,
niciunul dintre indici nu se schimbă.
Adaug doar un element nou.
Deci nu trebuie să fac schimburi.
Deci, pot să inserez și să
șterg ultimul în timp constant
într-o matrice statică?
Da?
PUBLIC: Nu, pentru că
dimensiunea este constantă.
ERIK DEMAINE: Nu, pentru că
dimensiunea este constantă.
Așadar, modelul nostru este că
rețineți că modelul de alocare este
că putem aloca o
matrice statică de dimensiunea em,
dar este doar o dimensiune
n. Nu pot spune doar, vă
rugăm să o măriți
cu 1. Am nevoie de spațiu
pentru a stoca acest element suplimentar.
Și dacă te gândești unde
sunt lucrurile în memorie, când
apelezi la acest
alocator de memorie, care
face parte din
sistemul tău de operare,
spui, te rog să-
mi dai o bucată de memorie.  Îi va
plasa în
diferite locuri în memorie,
iar unele dintre ele ar putea
fi unul lângă celălalt.
Deci, dacă încerc să măresc
această matrice cu 1,
ar putea
fi deja ceva acolo.
Și asta nu este posibil
fără o schimbare mai întâi.
Deci, deși, în
matrice, nu
trebuie să fac nicio
schimbare, în memorie, s-
ar putea să trebuiască să fac deplasare.
Și asta este în afara modelului.
Așa că vom rămâne
la acest model de doar...
poți aloca memorie.  De
asemenea, puteți dezaloca memoria,
doar pentru a menține spațiul redus.
Dar singura modalitate
de a obține mai mult spațiu
este să ceri o nouă matrice.
Și acea nouă matrice nu va fi
învecinată cu cea veche.
Întrebare?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Care
este matricea dinamică
va fi următorul subiect, așa că
poate vom reveni la asta.
Da?
Într-o matrice statică, pur și simplu
nu ai voie să o faci mai mare.
Și deci trebuie să
alocați o nouă matrice, despre care
spunem că ia timp liniar.
Chiar dacă alocarea noii
matrice nu a durat timp liniar,
trebuie să copiați toate
elementele
din vechea matrice
în cea nouă.
Apoi îl poți
arunca pe cel vechi.
Doar copierea
dintr-o matrice de dimensiune
n într-o matrice de dimensiune n plus
1, care va dura timp liniar.
Deci, matricele statice sunt foarte
proaste pentru operațiuni dinamice -
nicio surpriză.
Dar le-ai putea face.
Acesta este un tablou static.
Acum, listele legate vor
fi aproape opusul -- ei
bine, aproape.
Dacă stocăm lungimea, OK,
putem calcula lungimea
matricei foarte rapid.
Putem insera și șterge în
față foarte eficient.
Dacă vreau să adaug un articol nou ca
prim articol nou, atunci ce fac?
Aloca un
nod nou, pe care îl voi numi x.
Acesta este primul inserat din x.
Voi aloca o nouă
matrice de dimensiunea 2.
O să schimb --
lasă-mă să o fac în roșu.
Am de gând să schimb
acest indicator de cap.
Poate ar trebui să fac asta mai târziu.
Voi seta următorul
indicator aici la acesta
și apoi voi
schimba acest
indicator de cap pentru a indica aici.
Și, bum, acum
am o listă legată.
Din nou, nu știm nimic
despre ordinea și memoria
acestor liste.
Ne pasă doar de
ordinea care este
reprezentată implicit,
urmărind în mod
repetat următorii indicatori.
Acum, am o nouă listă care
are x în față, apoi x 0,
apoi x 1 și așa mai departe.
Deci insert- și delete_first,
cel puțin sunt cu adevărat eficiente.
Nu vom obține mult mai
mult decât atât,
dar lista legată, insert- și
delete_first sunt timp constant.
Deci e misto.
Totuși, totul va fi
lent.
Dacă vreau să obțin al 10-lea
articol dintr-o listă legată,
trebuie să urmăresc aceste
indicatoare de 10 ori.
Eu merg 0, 1, 2, 3 și așa mai departe.
Urmează următoarele 10 indicații
și voi primi al 10-lea articol.
Accesarea celui de-al al-lea articol va
lua comanda i timp.
Get- and set_at need i time,
care, în cel mai rău caz,
este theta n.
Avem un fel de
structuri de date complementare aici.
Pe de o parte, o
matrice statică poate face timp constant
get_at/set_at.
Deci este foarte rapid la
aspectul cu acces aleatoriu
pentru că este o matrice.
Listele legate sunt foarte
proaste la acces aleatoriu,
dar sunt mai bune
la a fi dinamice.
Putem insera și șterge--
la început, cel puțin--
în timp constant.
Acum, dacă vrem să
inserăm și să ștergem într-adevăr într-
o anumită poziție,
este încă greu,
pentru că trebuie să
mergem până la acea poziție.
Chiar și inserarea și conducerea
la sfârșitul listei
este dificilă, deși
asta se poate repara.
Și poate voi lăsa asta pentru
sesiunea cu probleme sau pentru setul de probleme.
Dar un simplu... iată
un mic puzzle.  Să
presupunem că doriți
să rezolvați eficient get-last
într-o listă legată.
Cum ai rezolva
asta în timp constant?
Da?
PUBLIC: Listă dublu legată.
ERIK DEMAINE:
Listă dublu legată.
Este o idee bună, dar
de fapt nu este răspunsul corect.
Acesta este un răspuns la
următoarea întrebare pe care aș putea să o pun.
Da?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: [INAUDIBIL]
indicator către ultimul element.
Asta e tot ce avem nevoie aici.
Și adesea, o
listă dublu legată are asta.  Ei de
obicei numesc asta
coada - cap și coadă.
Și dacă stocăm întotdeauna
un pointer către ultima listă -
asta este ceea ce numim
creșterea structurii de date,
în care adăugăm câteva
informații suplimentare structurii de date
și --
trebuie să o ținem
la zi tot timpul.
Deci, dacă facem un
insert_last sau ceva,
insert_last devine, de asemenea,
ușor, deoarece pot doar să
adaug un nou nod aici și să
actualizez indicatorul aici.
delete_last este mai complicat.  De
aici obțineți
o listă dublu legată.
Dar ori de câte ori adaug ceva
la sfârșitul acestei liste,
trebuie să actualizez
și indicatorul de coadă.
Atâta timp cât mențin asta,
acum, dintr-o dată get-last
este rapid în timp constant.
Deci listele legate sunt grozave dacă
lucrați la capete,
chiar și dinamic.
Matricele sunt grozave dacă
faci acces aleatoriu și nimic
dinamic -
nimic nu se adaugă sau șterge
la capete sau la mijloc.
Scopul nostru final pentru
astăzi este să obținem ce este
mai bun din ambele
lumi cu matrice dinamice.
Vom încerca să obținem
toți timpii buni de rulare
a listelor conectate și toți
timpii buni de funcționare
a matricelor statice.
Nu le vom primi pe toate
, dar pe majoritatea.
Și, într-un anumit sens, un
alt mod de a descrie despre
ce sunt aceste prelegeri introductive

este să vă spună despre cum
este implementat Python.  Despre
ce vom vorbi în
continuare, matricele dinamice,
am făcut aluzie de multe ori.
Dar acestea sunt ceea ce
Python numește liste.
Nu trebuie să implementați
manual o matrice dinamică,
deoarece este deja încorporată gratuit
în multe limbi noi
, pentru că
sunt atât de utile.
Această prelegere este despre cum
acestea sunt implementate de fapt
și de ce sunt eficiente.
Și în
nodurile de recitare, veți vedea
cum să
le implementați de fapt dacă tot ce ați
avut ar fi matrice statice.
Dar, din fericire,
avem matrice dinamice,
așa că nu trebuie să
le implementăm efectiv.
Dar în interiorul
interpretului Python,
asta este exact
ceea ce se întâmplă.
Ideea este să relaxăm
constrângerea --
sau invariantul, indiferent --
că dimensiunea
matricei pe care o folosim este
egală cu n, care este numărul
de elemente din secvență.
Amintiți-vă, în
problema secvenței,
ar trebui să
reprezentăm n elemente.
Cu o matrice statică, am
alocat o matrice de dimensiune
exact n.
Deci hai să ne relaxăm.  Să
nu facem exact n.  Să o
facem aproximativ n.
Cât de aproximativ, te poți
gândi o vreme.
Dar din
perspectiva algoritmilor,
de obicei, când spunem
aproximativ, ne referim la aruncarea
factorilor constanți.
Și acesta se dovedește a fi
răspunsul corect aici.
Nu este întotdeauna
răspunsul corect.
Dar vom impune
ca dimensiunea matricei să
fie theta n --
probabil, de asemenea, mai mare
sau egală cu n.
0,5 n nu ar fi de mare ajutor.
Deci va fi
cel puțin n și va
fi cel mult
niște ori constanti n.
2n, 10n, de 1,1 ori n.
Oricare dintre aceste
constante va funcționa.  Voi
folosi 2n aici, dar
există o mulțime de opțiuni.
Și acum, lucrurile
funcționează aproape gratuit.
Va fi
o subtilitate aici.
Și mă voi concentra pe-- vom
menține în continuare
că al-lea element al matricei
reprezintă x i.
Această structură de date...
permiteți-mi să fac o imagine.
Avem o serie de o anumită dimensiune.
Primele câteva elemente sunt
folosite pentru a stoca secvența.
Dar apoi, vor fi
unele goale la sfârșit.
Poate că vom ține evidența asta --
așa că structura de date în sine
va avea o matrice și va
avea o lungime.
Ceva de genul.  De
asemenea, vom
urmări lungimea.
Deci știm că
primele elemente de lungime
sunt acolo unde sunt datele, iar
restul sunt lipsite de sens.
Deci, acum, dacă vreau să merg și să fac
un insert_last, ce să fac?
Trec doar la a de
lungime și îl setez pe x.
Și apoi cresc lungimea.
Bum.
Uşor.
Timp constant.
Da?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Cum
ai loc suficient?
Într-adevăr, nu.
Acesta a fost un algoritm incorect.
Dar de obicei este corect.
Atâta timp cât am
spațiu suplimentar, asta
este tot ce trebuie să
fac pentru insert_last.
Dar voi
stoca și dimensiunea matricei.
Aceasta este adevărata...
toată chestia asta este dimensiunea,
iar această parte este lungimea.
Lungimea va fi întotdeauna
mai mică sau egală cu dimensiunea.
Și deci există o problemă.
Dacă lungimea este egală cu dimensiunea, atunci
nu am spațiu.
Doar adăugați până la sfârșit,
cu excepția cazului în care n este egal cu dimensiunea.
Folosesc n lungime
pentru același lucru.
Deci lungimea aici este aceeași cu n.
Acesta este numărul nostru real
de lucruri pe care
încercăm să le reprezentăm.
Și mărimea... aceasta este grozavă.
Aceasta este dimensiunea interfeței.
Aceasta este ceea ce
încercăm să reprezentăm.
Și aceasta este
dimensiunea reprezentării.
Aceasta este dimensiunea matricei mele.
Acestea sunt
numărul de articole pe care
încerc să le stochez în acea matrice.
Aceasta este interfața
versus structura de date.
Iată interfața.
Iată structura datelor.
Bine, in regula.
Ce fac în
cazul în care n este egal cu dimensiunea?  Va
trebui să-
mi fac matricea mai mare.
Acest lucru ar trebui să sune la fel
ca matrice statice.
Pentru matricele statice, ne-am
mărit matricea de fiecare dată când
am inserat.
Și acesta a fost acest
cost liniar de alocare.  O să
facem
asta uneori.
Cu matrice statice, a trebuit să
o facem de fiecare dată,
deoarece dimensiunea a egalat n.
Acum, avem o oarecare flexibilitate.  O vom

face doar uneori.
Parcă, prăjiturile sunt
uneori un aliment, aparent,
potrivit
Cookie Monster modern.  Nu
înțeleg.
Dar dacă n este egal cu
dimensiunea, vom
aloca o nouă
matrice de dimensiuni -
vreo sugestie?
PUBLIC: Mai mare.
ERIK DEMAINE: Mai mare.
Imi place.
Mai mare decât dimensiunea.
Cât mai mare?
PUBLIC: De două ori.
ERIK DEMAINE: De două ori.
JASON KU: Cinci lucruri.
ERIK DEMAINE: Cinci lucruri.
Marimea plus 5?
Haide, Jason.
Troling-mă.  În
regulă.
Există câteva
opțiuni naturale aici.
Unul este un factor constant mai mare.
Puteți folosi 1.1, sau
1.01, sau două, sau 5 sau 10.
Toate vor funcționa.
Sau ai putea folosi
răspunsul de trolling al lui Jason cu dimensiunea
plus o constantă, cum ar fi 5.
De ce este rău?
Da?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Va
trebui să o faci din nou.  Va
trebui să
redimensionați frecvent.
Când?
Cinci pași mai târziu.
În
matricea statică originală,
realocam de fiecare dată.
Este ca n plus 1.
Dacă facem n plus 5, asta
chiar nu schimbă lucrurile
dacă ignorăm factorii constanți.
Acum, va trebui să petrecem
timp liniar la fiecare cinci pași în loc
de timp liniar la fiecare pas.
Acesta este încă timp liniar
per operație, doar că
schimbăm
factorul constant.
În timp ce de 2 ori
mărimea, ei bine, acum
trebuie să ne gândim
puțin mai mult.  Să ne
gândim doar
la cazul în care
inserăm la
sfârșitul unui tablou.  Să
presupunem că facem n insert_lasts
dintr-o matrice goală.
Când redimensionăm?
Ei bine, la început...
Cred că nu am spus ce
facem pentru o matrice goală.  Să
presupunem că dimensiunea este egală cu 1.
Putem introduce un articol gratuit.
De îndată ce inserăm al doilea
element, atunci trebuie să redimensionăm.
Asta pare rău.
Imediat, trebuie să redimensionăm.
Apoi introducem al treilea articol.
OK, acum hai să facem o imagine.
Așa că începem cu un articol.
Îl umplem.
Apoi, creștem la mărimea 2,
pentru că este de două ori 1.
Apoi o umplem.
Imediat, trebuie să
redimensionăm din nou.
Dar acum începem să
obținem unele beneficii.
Acum, avem dimensiunea 4 și
astfel putem insera două elemente
înainte de a trebui să redimensionăm.
Și acum, avem
mărimea 8 și putem
introduce patru articole
înainte de a reumple.
Aceasta se va redimensiona -
și din nou, redimensionările
sunt costisitoare atât
pentru că trebuie să plătim pentru a
aloca noua matrice - l-am
desenat ca doar extinzând-
o, dar de fapt,
creăm o
matrice complet nouă și apoi
am  trebuie să copiați toate
elementele.
Deci, există costul de alocare
și apoi costurile de copiere.
Este liniar în orice caz.
Dar vom redimensiona
la n egal cu 1, 2, 4, 8,
16 -- știți această secvență.
Toate puterile lui 2,
pentru că ne dublem.
Aceasta este exact puterile lui 2.
Deci plătim un cost liniar.
Acest cost de redimensionare,
alocarea și copierea,
va fi -- este
liniar de fiecare dată.
Deci este 1 plus 2 plus
4 plus 8 plus 16.
Într-adevăr, ar trebui să scriu
asta ca suma de la i
este egală cu 1 la aproximativ log n.
Baza logaritmică 2 a lui n este
lG de 2 la i.
Dacă vrei un terminus
aici, este aproximativ n.
Este de fapt următoarea--
puterea anterioară a lui
2 din n, sau ceva.
Dar asta nu va conta.
Asta va afecta
lucrurile printr-un factor constant.
Care este suma lui 2 la i?
Aceasta este o serie geometrică.
Stie cineva raspunsul?
Da?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: 2 până la
limita superioară plus 1 minus 1.
Da.
Deci aceasta este identitatea.
Suma lui 2 la i de la i este egală cu
1 la k este 2 la k plus 1,
plus 1 minus 1.
Deci plus 1 este la etaj.
Cel minus este la parter.
O modalitate ușoară de a vă aminti acest lucru
este dacă gândiți în binar -
așa cum ar trebui cu toții.
Suntem informaticieni.
2 la i înseamnă că
setați bitul i la 1.
Iată un șir de biți.
Acesta este al-lea bit.
Acesta este 2 la i.
0 este aici jos.
Dacă le rezum pe toate, ceea ce
înseamnă asta este că pun 1 aici.
Și dacă te gândești la ce
înseamnă asta, aceasta este până la k de la 0-- îmi pare
rău, ar trebui să
fac 0 pentru a fi corect.
Dacă scriu... asta e
partea stângă.
Partea dreaptă este 2 față de
k plus 1, care este un 1 aici,
iar restul 0.
Deci, dacă vă cunoașteți
aritmetica binară,
scadeți-- dacă adăugați
1 la aceasta, obțineți asta.
Sau dacă scazi 1
din aceasta, obții asta.
Acesta este motivul pentru care această identitate păstrează.
Sau lucrul de nivel superior
este să spunem, oh,
aceasta este o serie geometrică.
Deci știu... ar
trebui să știi asta.
iti spun acum.
Seriile geometrice sunt dominate
de ultimul termen, cel mai mare
termen.
Dacă aveți vreo serie pe care o puteți
identifica ca fiind geometrică, ceea ce
înseamnă că crește cel
puțin exponențial,
atunci în ceea ce privește
notația theta,
puteți doar să vă uitați la ultimul termen
și să puneți un theta în jurul lui
și gata.
Deci acesta este theta
al ultimului termen,
ca 2 la log
n, care este theta n.
Misto.
Timp liniar.
Timp liniar pentru toate
operațiunile mele.
Fac n operațiuni aici
și am petrecut timp total liniar
pentru a face toate redimensionările.  Asta e
bine.
E ca o constantă
fiecare, cam.
„Tipul de” este
o noțiune importantă pe
care o numim amortizare.
Vreau să spun că o
operație durează t din n
timp amortizat dacă, să spunem,
oricare k dintre acele operații
durează, cel mult, k
ori t din n timp.
Acest lucru este puțin
neglijent, dar fiți suficient de bun.
Ideea este aici, dacă
acest lucru funcționează pentru n sau k,
pentru a face n operațiuni dintr-
o matrice goală aici
necesită timp liniar,
ceea ce înseamnă că aș
numi această constantă amortizată.
Amortizat înseamnă un anumit
tip de mediere - o
medie pe
secvența de operațiuni.
Deci, în timp ce
operațiunile individuale vor fi costisitoare,
una aproape de sfârșit, când
trebuie să redimensionez matricea,
va dura timp liniar
doar pentru acea operație.
Dar majoritatea
operațiunilor sunt ieftine.
Cele mai multe dintre ele sunt constante.
Așa că mă pot gândi să
taxez acel cost ridicat
pentru toate celelalte operațiuni
care au făcut acest lucru să se întâmple.
Aceasta este o medie pe
secvența de operare.
Fiecare insert_last de acolo
durează doar timp constant,
în medie, peste secvența
de operații pe care le facem.
Și așa este aproape constantă.
Nu este la fel de bun
ca constant, cel mai rău caz,
dar este aproape la fel de bun.
Și este la fel de bun pe cât ai
putea spera
să faci în acest
model dinamic de alocare a matricei.
Lasă-mă să pun asta într-un tabel.
Și le veți găsi
și în notele de curs.
Avem, în partea de sus,
principalele operațiuni
ale interfeței secvențe, pe care le
vom revedea în prelegerea a șaptea.
Vom vedea alte
structuri de date pentru aceasta.
Get_at și set_at
în prima coloană.
Insert_ și delete_first,
insert_ și delete_last,
insert_ și delete_într-o
poziție arbitrară.
Am văzut
acum trei structuri de date.
Array-urile au fost foarte
bune la get_at/set_at.  Au
luat timp constant.
Acesta este cel albastru.
Omitem thetas-urile aici.
Toate celelalte operațiuni
au durat timp liniar,
indiferent unde se aflau.
Listele legate au fost foarte bune
la insert- și delete_first.  Au
luat timp constant,
dar totul
a luat timp liniar,
în cel mai rău caz.
Aceste noi tablouri dinamice
realizează get_at și set_at
în timp constant, deoarece
mențin acest invariant aici
că a din i este egal cu x i.
Deci putem încă să facem get-
și set_at rapid.
Și tocmai am
arătat că insert_last
este amortizat constant.
delete_last, nu
trebuie să redimensionați matricea.
Ai putea doar să scazi
lungimea și, boom,
ai șters ultimul element.
Nu este atât de satisfăcător,
pentru că dacă inserați n elemente
și apoi ștergeți n
elemente, veți avea în continuare
o matrice de dimensiune theta n,
chiar dacă valoarea dvs. actuală
a lui n este 0.
Puteți ocoli asta
cu puțin mai multă
șmecherie.  , care sunt descrise
în notele de curs.
Dar este dincolo de --
vom face doar o analiză amortizată foarte simplă

în această clasă --
pentru a demonstra că acel
algoritm este, de asemenea,
amortizat constant, ceea ce este.
Veți vedea în 046, sau
îl puteți găsi în cartea CLRS.
Asta e pentru azi.