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