Etäisyydet

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, jolla voidaan laskea tehokkaasti tietyn luvun kaikkien parien etäisyyksien summa listassa.

Esimerkiksi kun lista on $[1,2,1,3,3,1,2,1]$, luvun $1$ parien etäisyydet ovat:

• kohdat $0$ ja $2$: etäisyys $2$
• kohdat $0$ ja $5$: etäisyys $5$
• kohdat $0$ ja $7$: etäisyys $7$
• kohdat $2$ ja $5$: etäisyys $3$
• kohdat $2$ ja $7$: etäisyys $5$
• kohdat $5$ ja $7$: etäisyys $2$

Tästä tulee etäisyyksien summaksi $2+5+7+3+5+2=24$.

Toteuta tiedostoon distances.py luokka DistanceTracker, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• sum(number): laske yhteen luvun kaikkien parien etäisyydet listassa

Kummankin metodin tulee toimia ajassa $O(1)$.

class DistanceTracker:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def sum(self, number):
        # TODO

if __name__ == "__main__":
    tracker = DistanceTracker()

    tracker.append(1)
    tracker.append(2)
    tracker.append(1)
    tracker.append(3)
    tracker.append(3)
    tracker.append(1)
    tracker.append(2)
    tracker.append(1)

    print(tracker.sum(1)) # 24
    print(tracker.sum(2)) # 5
    print(tracker.sum(3)) # 1

    tracker.append(1)
    tracker.append(2)
    tracker.append(3)

    print(tracker.sum(1)) # 42
    print(tracker.sum(2)) # 16
    print(tracker.sum(3)) # 14

Jos lukua ei esiinny listalla tai se esiintyy vain kerran, haluttu tulos on $0$:

    tracker = DistanceTracker()
    print(tracker.sum(1)) # 0
    tracker.append(1)
    print(tracker.sum(1)) # 0

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

    tracker = DistanceTracker()
    total = 0
    for i in range(10**5):
        tracker.append(1)
        total += tracker.sum(1)
    print(total) # 4166749999583325000