Namų darbas

Ką atiduoti

algo su playlist komanda, praeinantį go test ./..., ir sprendimo pagrindimą.

1. Lūžio taškas

Perkėlimui iš pozicijos i į j rask, kada sąrašas pradeda laimėti prieš masyvą, jei mazgo neturi.

Pamatuok su i ir j deriniais ir užpildyk:

perkėlimas	masyvo pastūmimai	sąrašo šuoliai	kas laimi
47 → 3
500 → 499
99 000 → 50
tavo pasirinktas

Vienu sakiniu: ar apskritai yra derinys, kuriame sąrašas laimi be turimo mazgo?

2. Rodyklių kaina baitais

Suskaičiuok, kiek atminties sunaudoja 100 000 įrašų Playlist prieš []Item — įskaityk Prev ir Next (po 8 baitus) ir tai, kad kiekvienas mazgas skiriamas atskirai.

Nurodyk santykį. Susiek jį su 2 pamokos slice antraštės skaičiavimu.

3. Turimas mazgas — iš kur

3 žingsnis parodė, kad sąrašas laimi 24 000 kartų, jei mazgą jau turi.

Aprašyk, kaip programa jį gauna. Konkrečiai: kokia struktūra laiko pavadinimas → *Node atvaizdį, kiek ji kainuoja atminties, ir ką reikia atnaujinti kiekvieno įterpimo metu.

(Tai 10 pamokos aprašymas. Parašyk jį savais žodžiais dabar — grįši ir palyginsi.)

4. Vienpusis prieš dvipusį

Ką prarastum, jei Node turėtų tik Next?

Nurodyk kiekvieną playlist.go funkciją, kuri nustotų veikti arba pablogėtų, ir naują jos sudėtingumą. Kiek atminties sutaupytum?

5. Sprendimas

Vienas pastraipos atsakymas: tavo grojaraščio funkcijai — masyvas ar susietas sąrašas?

Pagrįsk skaičiais iš 1 ir 2 punktų, ne bendromis frazėmis. Jei atsakymas „masyvas", tai teisingas atsakymas — pasakyk, kodėl.