Welche Optimierungen werden durchgeführt, damit dieser Code schnell abgeschlossen wird?

Question

Ich war ein Problem zu lösen stieß ich auf, was die Summe der Leistungen von 3 0-2009 mod 8.

ich eine Antwort mit Stift und Papier bekam und versuchte es mit einigen einfachen Python zu überprüfen

print(sum(3**k for k in range(2010)) % 8) 

Ich war überrascht, wie schnell es eine Antwort zurück gab. Meine Frage ist, welche Optimierungen oder Tricks der Dolmetscher benutzt, um die Antwort so schnell zu bekommen?

Answer 1

Keine ausgefallenen Optimierungen sind verantwortlich für die schnelle Reaktion, die Sie beobachtet haben. Computer sind in absoluten Zahlen viel schneller als erwartet.

Answer 2

Keine, es ist nur nicht viel Rechenleistung für einen Computer zu tun.

Ihr Code entspricht:

>>> a = sum(3**k for k in range(2010)) 
>>> a % 8 
4 

a ist eine 959-stellige Zahl - es ist einfach nicht eine große Aufgabe, einen Computer zu fragen.

Versuchen Sie, zwei Nullen am Ende des 2010 anzubringen, und Sie werden sehen, dass es eine beträchtliche Menge an Zeit in Anspruch nimmt.

Answer 3

Die einzige Optimierung bei der Arbeit ist, dass jede Instanz von 3**k ausgewertet wird eine Anzahl von Multiplikationen unter Verwendung von proportional zur Anzahl der Bits in k (es macht nicht multiply 3 von selbst k-1 mal).

Wie bereits erwähnt, wenn Sie 2010 bis 20100 oder 201000 oder ... steigern, dauert es viel länger, weil 3**k wird sehr groß. in diesen Fällen jedoch Sie es, wie es enorm wieder durch Umschreiben beschleunigen können, zum Beispiel

print(sum(pow(3, k, 8) for k in range(201000)) % 8) 

Intern tut pow(3, k, 8) noch eine Reihe von Multiplikationen proportional zu der Anzahl der Bits in k, muss aber nicht beibehalten alle ganzen Zahlen größer als etwa 8 ** 2 (das Quadrat des Moduls).