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