DOGS LOIDS: Tātad CS50 mēs esam aptvēruši daudz dažādu datu
struktūru, vai ne?
Mēs esam redzējuši masīvus un saistītos sarakstus, un jaukšanas
tabulasjaucējtabulas, un mēģinājumusdigitālos kokus, skursteņusstekus
un rindas.
Mēs arī nedaudz uzzināsim par kokiem un kaudzēm, taču patiesībā tas
viss ir tikai tēmas variācijas.
Patiešām ir šādas četras pamatidejas, uz kurām var attiekties viss
pārējais.
Masīvi, saistītie saraksti, hash tabulasjaucējtabulas un
mēģinājumidigitālie koki.
Un, kā jau teicu, tiem ir dažādas variācijas, taču tas apkopos
gandrīz visu, par ko mēs runāsim šajā klasēkursā/nodarbībā attiecībā
uz programmēšanas valodu C.
Bet kā tas viss tiek novērtēts, vai ne?
Par katra priekšrocībām un mīnusiem esam runājuši atsevišķos
videoklipos par tiem, taču ir daudz dažādu skaitļu.
Ir daudz vispārīgu domuuzskatu, kas tiek izmētātas.
Mēģināsim to apvienot tikai vienā vietā.
Izvērtēsim plusus un mīnusus un apsvērsim, kura datu struktūra varētu
būt īstā datu struktūra jūsu konkrētajai situācijai neatkarīgi no
glabājamo datu veida.
Jums ne vienmēr ir jāizmanto īpaši ātra mēģinājumadigitālā koka
ievietošana, dzēšana un uzmeklēšana, ja jums patiešām nav pārāk
svarīgi ievietot un dzēst.
Ja jums ir nepieciešama tikai ātra nejauša piekļuvebrīvpiekļuve,
iespējams, masīvs ir labāks.
Tātad destilēsimizvērtēsim to.
Parunāsim par katru no četriem galvenajiem datu struktūru veidiem,
par kuriem mēs runājām, un vienkārši redzēsim, kad tās varētu būt
labas un kad tās varētu nebūt tik labas.
Tātad sāksim ar masīviem.
Tātad ievietošana, tas ir slikti.
Ievietošana masīva beigās ir piemērota, ja mēs veidojam masīvu darba
gaitā.
Bet, ja elementi ir jāievieto vidū, atcerieties ievietošanas
kārtošanu, jo ir daudz pārbīdes, lai tajā ievietotu elementu.
Un tāpēc, ja mēs ievietosim jebkur, izņemot masīva beigas, tas,
iespējams, nav tik lieliski.
Tāpat arī dzēšana, ja vien nedzēšam no masīva beigām, iespējams, arī
nav tik lieliska, ja nevēlamies atstāt tukšas atstarpes, ko parasti
nedarām.
Mēs vēlamies noņemt elementu un pēc tam kaut kā padarīt to atkal
pieguļošuto atkal sakārtot.
Un tāpēc elementu dzēšana no masīva arī nav tik lieliska.
Tomēr uzmeklēšana ir lieliska.
Mums ir brīvpiekļuve, pastāvīga laika meklēšana.
Mēs vienkārši sakām septiņi, un mēs ejam uz masīva pārvietošanu
septiņi.
Mēs sakām 20, ar pāreju uz masīva pārvietošanu 20.
Mums nav jāatkārtojāveic iterācija.
Tas ir diezgan labi.
Masīvus ir arī salīdzinoši viegli kārtot.
Katru reizi, kad mēs runājām par šķirošanas algoritmu, piemēram,
atlases kārtošanu, ievietošanas kārtošanu, burbuļu
kārtošanuburbuļkārtošanu, sapludināšanas kārtošanu, mēs vienmēr
izmantojām masīvus, jo masīvus ir diezgan viegli kārtot, salīdzinot
ar līdz šim redzētajām datu struktūrām. .
Tie ir arī salīdzinoši mazi.
Tur nav daudz papildu vietas.
Jūs vienkārši atliekat malā tieši tik daudz, cik nepieciešams datu
glabāšanai, un tas arī viss.
Tātad tie ir diezgan mazi un efektīvi.
Taču vēl viens mīnuss ir tas, ka tie ir fiksēti pēc izmēra.
Mums ir precīzi jāpaziņo, cik lielu masīvu mēs vēlamies, lai mūsu
masīvs būtu, un mēs to iegūstam tikai vienu reizi.
Mēs nevaram to augtpalielināt un samazināt.
Ja mums tas jāpalielina vai jāsamazina, mums ir jādeklarē pilnīgi
jauns masīvs, jākopē visi pirmā masīva elementi otrajā masīvā.
Un, ja mēs nepareizi aprēķinājām šo laikutoreiz, mums tas jādara
vēlreiz.
Ne tik lieliski.
Tātad masīvi nedod mums iespēju izmantot mainīgu elementu skaitu.
Izmantojot saistīto sarakstu, ievietošana ir diezgan vienkārša.
Mēs vienkārši uzkāpjam uz priekšpusipievienojam sākumam.
Dzēšana ir arī ir diezgan vienkārša.
Mums ir jāatrod elementi.
Tas ietver meklēšanu.
Bet, kad esat atradis meklēto elementu, viss, kas jums jādara, ir
jāmaina rādītājs, iespējams, divi, ja jums ir saistīts saraksts —
drīzāk divkārši saistīts saraksts — un pēc tam varat vienkārši
atbrīvot mezglu. .
Jums nav viss jāpārvieto apkārt.
Jūs vienkārši mainietmaināt divus rādītājus, tāpēc tas ir diezgan
ātri.
Tomēr meklēšana ir slikta, vai ne?
Lai mēs varētu atrast elementu saistītajā sarakstā neatkarīgi no tā,
vai tas ir saistīts atsevišķi vai divreizdivkārši, mums tas ir
jāmeklē lineāri.
Mums jāsāk no sākuma un jāpārvieto beigasuz beigām, vai jāsāk beigās,
pārejietpārejot uz sākumu.
Mums vairs nav nejaušas piekļuvesbrīvpiekļuves.
Tātad, ja mēs veicam daudz meklēšanu, iespējams, saistītais saraksts
mums nav tik labs.
Tos ir arī ļoti grūti šķirot, vai ne?
Vienīgais veids, kā jūs patiešām varat kārtot saistīto sarakstu, ir
kārtot, to veidojot.
Bet, ja kārtojat to konstruēšanasveidošanas laikā, jūs vairs
neveiksit ātrusātru ievietošanu.
Jūs ne tikai uzlīmējatievietojat lietas uz priekšpusisākumā.
Jums ir jāatrod īstā vieta, kur to ievietot, un tad jūsu ievietošana
kļūst tikpat slikta kā ievietošana masīvā.
Tāpēc saistītie saraksti nav tik lieliski piemēroti datu kārtošanai.
Tie ir arī diezgan mazi, pēc izmēraizmēra ziņā.
Divkārši saistītie saraksti ir nedaudz lielāki nekā atsevišķi
saistītie saraksti, kas ir nedaudz lielāki par masīviem, taču tas nav
liels izniekotas vietas apjoms.
Tātad, ja vieta ir ļoti dārgasvarīga, bet ne pārāk intensīvatik ļoti
svarīga, tas varētu būt pareizais ceļš.
Hash tabulasJaucējtabulas.
Ievietošana hash tabulājaucējtabulā ir diezgan vienkārša.
Tas ir divpakāpju process.
Vispirms mums ir jāpalaiž savi dati, izmantojot jaucējfunkciju, lai
iegūtu jaucējkodu, un pēc tam mēs ievietojam elementu jaucēja tabulā
jaucējtabulā šajā jaucējkoda vietā.
Dzēšana, līdzīgi kā saistītajam sarakstam, ir vienkārša, tiklīdz
atrodat elementu.
Vispirms tas ir jāatrod, bet pēc tam, kad to izdzēšat, jums vienkārši
jāapmainās ar pāris norādesjāapmaina pāris rādītāju, ja izmantojat
atsevišķu ķēdi.
Ja izmantojat zondēšanu/izpēti vai jauktabulājaucējtabulā vispār
neizmantojat ķēdi, dzēšana patiesībā ir ļoti vienkārša.
Viss, kas jums jādara, ir jaukt datuspievienot tēmturi datiem un pēc
tam doties uz šo vietu.
Un, pieņemot, ka jums nav nekādu sadursmju, jūs varēsit dzēst ļoti
ātri.
Tagad meklēšana ir vieta, kur lietas kļūst nedaudz sarežģītākas.
Tas ir vidēji labāksKopumā tā ir labāka nekā saistītie saraksti.
Ja izmantojat ķēdes savienojumu, jums joprojām ir saistīts saraksts,
kas nozīmē, ka meklēšana joprojām kaitē saistītajam sarakstam.
Bet, tā kā jūs izmantojat saistīto sarakstu un sadalāt to pa 100 vai
1000 vai n elementiem savā jaukšanas tabulā, visi saistītie saraksti
ir n-tā izmēra.
ViņiTie visi ir ievērojami mazāki.
Jums ir n saistīti saraksti, nevis viens saistīts saraksts ar izmēru
n.
Un tāpēc šis reālās pasaules nemainīgais faktors, par kuru mēs
parasti nerunājam par laika sarežģītībulaika sarežģītības kontekstā,
tas patiesībā šeit rada atšķirību.
Tātad uzmeklēšana joprojām ir lineāra meklēšana, ja izmantojat ķēdes
savienojumu, taču salīdzinājumam meklētā saraksta garums salīdzinoši
ir ļoti, ļoti īss.
Atkal, ja kārtošana ir jūsu mērķis šeit, iespējams, hash tabula
jaucējtabula nav pareizais ceļš.
Vienkārši izmantojiet masīvu, ja kārtošana jums ir patiešām svarīga.
Un tie var darboties dažādu izmēru diapazonā.
Ir grūti pateikt, vai hash tabulajaucējtabula ir maza vai liela, jo
tas tiešām ir atkarīgs no tā, cik liela ir jūsu jaucēj
tabulajaucējtabula.
Ja jaukšanas tabulājaucējtabulā glabāsit tikai piecus elementus un
tajā ir 10 000 elementu, jūs, iespējams, tērējat daudz vietas.
Pretstatā tam, ka jums var būt arī ļoti kompaktas jaucēj
tabulasjaucējtabulas, taču, jo mazāka kļūst jaucēj
tabulajaucējtabula, jo garāks kļūst katrs no saistītajiem sarakstiem.
Tāpēc īsti nav iespējams precīzi definēt jaukšanas tabulas lielumu,
taču droši var teikt, ka tas parasti būs lielāks par saistīto
sarakstu, kurā tiek glabāti tie paši dati, bet mazāks par
mēģinājumudigitālo koku.
Un mēģinājumidigitālie koki ir ceturtā no šīm struktūrām, par kurām
mēs runājām.
Ievietošana trijādigitālajā kokā ir sarežģīta.
Ir daudz dinamiskas atmiņas piešķiršanas, it īpaši sākumā, kad sākat
veidot.
Bet tas ir pastāvīgs laiks.
Tikai cilvēka elementscilvēciskais faktors šeit padara to sarežģītu.
Ja jums ir jāsastopas ar nulles rādītāju, malloc atstarpi, dodieties
uz turieni, iespējams, no turienes vēlreiz ar mallocatvēliet
atstarpi.
NorādītājuRādītāju iebiedēšanaspakļaušanas faktors
dinamiskajādinamiskās atmiņas piešķiršanā ir šķērslis, kas jānovērš.
Bet, kad esat to notīrījissakārtojuši, ievietošana patiesībā notiek
diezgan vienkārši, un tas noteikti ir nemainīgs laiks.
Dzēšana ir vienkārša.
Viss, kas jums jādara, ir jānovirza pāris norādesrādītāji uz leju un
jāatbrīvo mezgls, tāpēc tas ir diezgan labi.
Uzmeklēšana ir arī arī ir diezgan ātra.
TasTā ir balstītsbalstīta tikai uz jūsu datu garumu.
Tātad, ja visi jūsu dati sastāv no piecām rakstzīmju virknēm,
piemēram, jūs savā mēģinājumādigitālajā kokā glabājat piecas
rakstzīmju virknes, nepieciešamas tikai piecas darbības, lai atrastu
to, ko meklējat.
Pieci ir tikai nemainīgs faktors, tāpēc arī šeit ievietošana, dzēšana
un meklēšana ir nemainīgs laiks.
Vēl viena lieta ir tāda, ka jūsu mēģinājumsdigitālais koks faktiski
jau ir sakārtots, vai ne?
Pamatojoties uz to, kā mēs ievietojam elementus, pārejot burtu pēc
atslēgas burta vai ciparu pēc atslēgas ciparaizmantojot atslēgas
burtus vai atslēgas ciparus, jūsu mēģinājumsdigitālais koks parasti
tiek sakārtots, veidojot to.
Nav īsti jēgas domāt par kārtošanu tādā pašā veidā, kā mēs par to
domājam ar masīviem, saistītiem sarakstiem vai jaucēj
tabulāmjaucējtabulām.
Taču zināmā mērā jūsu mēģinājumsdigitālais koks tiek sakārtots.
Negatīvā puse, protams, ir tāda, ka mēģinājumsdigitālais koks ātri
kļūst milzīgs.
No katra savienojuma punkta jums var būt — ja jūsu atslēga sastāv no
cipariem, jums ir vēl 10 vietas, kur varat doties, kas nozīmē, ka
katrā mezglā ir informācija par datiem, ko vēlaties saglabāt šajā
mezglā, kā arī 10 norādesrādītāji.
Kas CS50 IDE ir 80 baiti.
Tātad katram jūsu izveidotajam mezglam ir vismaz 80 baiti, un tas pat
neskaitapat neskaitot datus.
Un, ja jūsu mezgli ir burti, nevis cipari, tagad jums ir 26
norādesrādītāji no katras atrašanās vietas.
Un 26 reiz 8, iespējams, ir 200 baiti vai kaut kas tamlīdzīgs.
Un jums ir lielie un mazie burti — jūs varat redzēt, kur es eju ar
šo, vai ne?
Jūsu mezgli var kļūt ļoti lieli, un tādējādi arī pats
mēģinājumsdigitālais koks kopumā var kļūt ļoti liels.
Tātad, ja jūsu sistēmā ir daudz vietasvietai ir liela nozīme,
mēģinājumsdigitālais koks var nebūt pareizais ceļš, lai gan tiek
izmantotas citas tāstā priekšrocības.
Es esmu Dags Loids.
Šis ir CS50.