Warum sind Pythons for-Schleifen für große Eingaben nichtlinear?

Question

Ich war Benchmarking einige Python-Code bemerkte ich etwas seltsam. Ich habe die folgende Funktion zu messen, wie schnell es durch eine leere for-Schleife zu durchlaufen hat:

def f(n): 
    t1 = time.time() 
    for i in range(n): 
     pass 
    print(time.time() - t1) 

f(10**6) Prints 0.035, f(10**7) über 0.35, f(10**8) über 3.5 und f(10**9) über 35. Aber f(10**10)? Weit über 2000. Das ist sicherlich unerwartet. Warum sollte es mehr als 60 Mal so lange dauern, um 10 mal so viele Elemente zu durchlaufen? Was ist mit Pythons For-Schleifen, die das verursacht? Ist das Python-spezifisch, oder tritt das in vielen Sprachen auf?

Answer 1

Wenn Sie über 10^9 erhalten Sie aus dem 32-Bit-Ganzzahlbereich. Python3 bewegt Sie dann transparent auf arbitrary precision integers, die viel langsamer zuzuweisen und zu verwenden sind.

Im Allgemeinen ist das Arbeiten mit solchen großen Zahlen einer der Bereiche, in denen Python3 viel langsamer ist als Python2 (der zumindest auf vielen Systemen schnelle 64-Bit-Integer hatte). Auf der anderen Seite macht es Python einfacher zu verwenden, mit weniger Fehlern overflow.

Answer 2

Einige genauen Timings timeit Verwendung zeigen die Zeiten in Zeile tatsächlich erhöhen etwa mit der Eingangsgröße, so dass Ihre Timings scheinen aus recht weit zu sein:

In [2]: for n in [10**6,10**7,10**8,10**9,10**10]: 
       % timeit f(n) 
    ...:  
10 loops, best of 3: 22.8 ms per loop 
1 loops, best of 3: 226 ms per loop # roughly ten times previous 
1 loops, best of 3: 2.26 s per loop # roughly ten times previous 
1 loops, best of 3: 23.3 s per loop # roughly ten times previous 
1 loops, best of 3: 4min 18s per loop # roughly ten times previous 

Mit xrange und python2 wir das Verhältnis in etwa gleich sehen offensichtlich python2 ist viel schneller insgesamt aufgrund der Tatsache, python3 int durch lange ersetzt wurde:

In [5]: for n in [10**6,10**7,10**8,10**9,10**10]: 
       % timeit f(n) 
    ...:  
100 loops, best of 3: 11.3 ms per loop 
10 loops, best of 3: 113 ms per loop 
1 loops, best of 3: 1.13 s per loop 
1 loops, best of 3: 11.4 s per loop 
1 loops, best of 3: 1min 56s per loop 

der tatsächliche Unterschied in der Laufzeit scheint als direkt auf die Größe der window's long eher verwandt zu sein ly verwandt mit Python 3. Der Unterschied ist marginal, wenn man unix benutzt, das sehnt sich viel anders als Windows, so ist dies ein plattformspezifisches Problem, wenn nicht mehr als ein Python.