Neliösumma

Kun aineistossa on havainnot $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ ja suoraa $y=ax+b$ sovitetaan aineistoon, virhe voidaan laskea neliösummana kaavalla $$\sum_{i=1}^{n}(y_i-(ax_i+b))^2.$$ Esimerkiksi kun aineisto on $(1,1),(3,2),(5,3)$ ja suoran parametrit ovat $a=1$ ja $b=-1$ (eli suora on $y=x-1$), virhe on $$(1-(1-1))^2+(2-(3-1))^2+(3-(5-1))^2=2.$$ Toteuta tiedostoon squaresum.py luokka DataAnalyzer, jossa on seuraavat metodit:

• add_point(x, y): lisää havainto aineistoon
• calculate_error(a, b): ilmoita sovitettavan suoran virhe neliösummana aineistossa

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

class DataAnalyzer:
    def __init__(self):
        # TODO

    def add_point(self, x, y):
        # TODO

    def calculate_error(self, a, b):
        # TODO

if __name__ == "__main__":
    analyzer = DataAnalyzer()

    analyzer.add_point(1, 1)
    analyzer.add_point(3, 2)
    analyzer.add_point(5, 3)
    print(analyzer.calculate_error(1, 0)) # 5
    print(analyzer.calculate_error(1, -1)) # 2
    print(analyzer.calculate_error(3, 2)) # 293

    analyzer.add_point(4, 2)
    print(analyzer.calculate_error(1, 0)) # 9
    print(analyzer.calculate_error(1, -1)) # 3
    print(analyzer.calculate_error(3, 2)) # 437

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

    analyzer = DataAnalyzer()
    total = 0
    for i in range(10**5):
        analyzer.add_point(i, i % 100)
        total += analyzer.calculate_error(i % 97, i % 101)
    print(total) # 25745448974503313754828