Muutoslista

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, joka kasvattaa tehokkaasti kaikkia listan lukuja halutun verran.

Toteuta tiedostoon changelist.py luokka ChangeList, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• get(index): hae luku listalta
• change_all(amount): kasvata kaikkia listan lukuja halutun verran

Metodissa change_all parametri amount ilmaisee, paljonko listan lukuja tulee kasvattaa. Parametri voi olla myös negatiivinen, jolloin lukuja vähennetään. Kaikkien metodien tulee toimia ajassa $O(1)$.

class ChangeList:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def get(self, index):
        # TODO

    def change_all(self, amount):
        # TODO

if __name__ == "__main__":
    numbers = ChangeList()

    numbers.append(1)
    numbers.append(2)
    numbers.append(3)

    print(numbers.get(0)) # 1
    print(numbers.get(1)) # 2
    print(numbers.get(2)) # 3

    numbers.change_all(2)
    print(numbers.get(0)) # 3
    print(numbers.get(1)) # 4
    print(numbers.get(2)) # 5

    numbers.append(8)
    numbers.change_all(-1)
    print(numbers.get(0)) # 2
    print(numbers.get(1)) # 3
    print(numbers.get(2)) # 4
    print(numbers.get(3)) # 7

Tässä listalle lisätään ensin luvut $1$, $2$ ja $3$, minkä jälkeen listan sisältö on $[1,2,3]$. Sitten listan kaikkiin lukuihin lisätään luku $2$, minkä jälkeen listan sisältö on $[3,4,5]$. Lopuksi listalle lisätään luku $8$ ja kaikkiin lukuihin lisätään luku $-1$, minkä jälkeen listan sisältö on $[2,3,4,7]$.

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

    numbers = ChangeList()
    total = 0
    for i in range(10**5):
        numbers.append(i + 1)
        numbers.change_all(i % 11 - 5)
        total += numbers.get(i // 2)
    print(total) # 2500049970