Namų darbas

Ką atiduoti

algo su history ir queue, praeinantį go test ./..., ir matavimų lentelę.

1. Kvadratinė kreivė

Pamatuok copy-down pastūmimus, n = 1 000 … 200 000:

n	pastūmimai	pastūmimai ÷ n²

Paskutinis stulpelis turi būti beveik pastovus (~0,5). Paaiškink kodėl.

2. Nutekėjimo riba

3 žingsnis parodė 7 034 KB prie n = 100 000.

Rask mažiausią n, kuriam nutekėjimas viršija 1 MB. Tada suskaičiuok, kiek baitų užima vienas Item, ir patikrink savo skaičių prieš matavimą.

3. Kiek kainuoja žiedas

Žiedinis buferis reikalauja iš anksto žinoti dydį.

Pamatuok, kiek atminties sunaudoja Ring, paruoštas 100 000 įrašų, kai eilėje vidutiniškai laikoma 10. Palygink su q[1:] variantu tam pačiam darbui. Kuris blogesnis ir kada?

4. Undo su riba

Tikros programos neriboja atšaukimų iki begalybės. Pridėk History viršutinę ribą: pasiekus max, seniausias įrašas išmetamas.

Kuriuo galu jį išmesi? Realizuok ir suskaičiuok kainą. Jei tavo atsakymas O(n) — perskaityk 3 pamokos taisyklę dar kartą ir pasiūlyk struktūrą, kuri tai padaro pigiau.

5. Sprendimas

Vienas pastraipos atsakymas: tavo „kas toliau" eilei — q[1:], copy-down ar žiedas?

Pagrįsk skaičiais iš 1 ir 3 punktų. Nurodyk, kokį eilės dydį ir kokį naudojimo ritmą prielaidauji — nes atsakymas nuo jų priklauso, ir teisingo atsakymo be jų nėra.