Warum erstellt einen Bereich von 0 bis log (len (Liste), 2) so langsam?

Question

Ich habe keine Ahnung, warum das passiert. Ich habe einige Listen durcheinander gebracht, und ich brauchte eine for Schleife von 0 bis log(n, 2), wobei n die Länge einer Liste war. Aber der Code war erstaunlich langsam, also habe ich nach ein wenig Recherche herausgefunden, dass das Problem in der Bereichserzeugung liegt. Beispielcode für die Demonstration:

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1 
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2 

Der Ausgang

2 loops, best of 3: 2.2 s per loop 
2 loops, best of 3: 3.46 µs per loop 

Die Anzahl der Tests ist gering (ich wollte nicht, dass dies mehr als 10 Minuten zu laufen), aber es zeigt bereits, dass range(log(n, 2)) ist Größenordnungen langsamer als das Gegenstück nur mit dem Logarithmus einer ganzen Zahl. Das ist wirklich überraschend und ich habe keine Ahnung warum dies passiert. Vielleicht ist ein Problem auf meinem PC, vielleicht ein Sage-Problem oder ein Python-Bug (ich habe es bei Python nicht gleich versucht).

Die Verwendung von xrange anstelle von range hilft auch nicht. Wenn Sie die Nummer mit .n() erhalten, wird Test 1 mit der gleichen Geschwindigkeit von 2 ausgeführt.

Weiß jemand, was passieren kann? Danke!

Answer 1

Gute Trauer - ich erkenne diese. Es ist mit einem von mir verwandt, traC#12121. Zunächst holen Sie zusätzlichen Aufwand aus einem Python int wie langweilig Gründe zu einer Sage Integer Gegensatz:

sage: log(8, 2) 
3 
sage: type(log(8, 2)) 
sage.rings.integer.Integer 
sage: log(8r, 2) 
log(8)/log(2) 
sage: type(log(8r, 2)) 
sage.symbolic.expression.Expression 
sage: %timeit log(8, 2) 
1000000 loops, best of 3: 1.4 us per loop 
sage: %timeit log(8r, 2) 
1000 loops, best of 3: 404 us per loop 

(Die r Suffix bedeutet „raw“, und verhindern, dass die Sage preparser von den wörtlichen 2 in Integer(2) Verpackung)

Und dann wird es komisch. Um einen Int für range zu produzieren, muss Sage herausfinden, wie man log(8)/log(2) in 3 verwandelt, und es stellt sich heraus, dass sie das Schlimmste macht, was möglich ist. Plagiieren meiner ursprünglichen Diagnose (mutatis mutandis):

Zuerst überprüft sie, ob dieses Objekt seinen eigenen Weg hat, einen Int zu erhalten, und es tut es nicht. Also baut sie ein RealInterval-Objekt aus log (8)/log (2), und es stellt sich heraus, dass dies das Schlimmste ist, was sie tun kann! Sie überprüft, ob die unteren und oberen Teile des Intervalls übereinstimmen [auf dem Boden, meine ich] (damit sie sicher weiß, was der Boden ist). Aber in diesem Fall, weil es wirklich eine ganze Zahl ist! dies wird sehen immer wie:

sage: y = log(8)/log(2) 
sage: rif = RealIntervalField(53)(y) 
sage: rif 
3.000000000000000? 
sage: rif.endpoints() 
(2.99999999999999, 3.00000000000001) 

Diese beiden Grenzen Etagen haben, die nicht nicht gleich sind, so Sage entscheidet sie das Problem noch nicht gelöst hat, und sie hält die Präzision 20000 Erhöhung Bits, um zu sehen, ob sie beweisen kann, dass sie sind .. aber durch die Konstruktion wird es nie funktionieren.Schließlich gibt sie auf und versucht, es zu vereinfachen, die erfolgreich ist:

sage: y.simplify_full() 
3 

ohne Worte Nachweis, dass es sich um eine perverse Eigenschaft des genau teilbar Fall ist:

sage: %timeit range(log(8r, 2)) 
1 loops, best of 3: 2.18 s per loop 
sage: %timeit range(log(9r, 2)) 
1000 loops, best of 3: 766 us per loop 
sage: %timeit range(log(15r, 2)) 
1000 loops, best of 3: 764 us per loop 
sage: %timeit range(log(16r, 2)) 
1 loops, best of 3: 2.19 s per loop 

Answer 2

Vielleicht mit log(x, 2) (aka ld()) ist nicht eine gute Idee an erster Stelle. Ich würde vorschlagen, die int-Werte verwenden Verschiebung der ld() zu implementieren:

n = len(array) 
while n: 
    n >>= 1 
    # perform the loop stuff 

Auf diese Weise können diese Häßlichkeiten alle mit dem range() und der log() könnten vermieden werden.

In normalen Situationen sollte der Aufruf von log() mehr Zeit in Anspruch nehmen als einfaches Bit-Shifting auf einem int. Beispiele:

>>> timeit('for i in range(int(math.log(8, 2))): pass', setup='import math') 
0.6762251853942871 
>>> timeit('n = 8\nwhile n:\n n >>= 1') 
0.24107813835144043 

Bei größeren Werten für n die Differenz kleiner wird. Für n = 10000 habe ich 0.8163230419158936 und 0.8106038570404053, aber das sollte sein, weil dann der Schleifenkörper den Großteil der Zeit benötigt, verglichen mit der Schleifeninitialisierung.

Answer 3

Python 2 erlaubt Bereich (some_float), aber seine veraltet und nicht in Python funktioniert nicht 3.

Der Code Probe nicht den Ausgang geben spezifiziert. Aber wir können hindurchgehen. Erstens muss timeit eine vollständige Skript, der Import im Skript Aufruf timeit nicht verwendet wird:

>>> timeit('range(log(8,2))') 
    Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/usr/lib64/python2.6/timeit.py", line 226, in timeit 
    return Timer(stmt, setup, timer).timeit(number) 
    File "/usr/lib64/python2.6/timeit.py", line 192, in timeit 
    timing = self.inner(it, self.timer) 
    File "<timeit-src>", line 6, in inner 
NameError: global name 'log' is not defined 

Wenn Sie den Import in das Skript hinzuzufügen getaktet wird, ist es die Rüstzeit umfasst:

>>> timeit('from math import log;range(log(8,2))') 
3.7010221481323242 

wenn Sie den Import in das Setup zu bewegen, ist es besser, aber eine One-Shot-Timing ist notorisch ungenau:

>>> timeit('range(log(8,2))',setup='from math import log') 
1.9139349460601807 

Schließlich ist es ein paar mal laufen und Sie erhalten eine gute Anzahl:

>>> timeit('range(log(8,2))',setup='from math import log',number=100) 
0.00038290023803710938 

Answer 4

Das sieht aus wie ein Sage-Bug.

habe ich ein neues Notebook und tat dies:

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1 
timeit('range(log(len([1,2,3,4,5,6,7,8]), 2))', number=2, repeat=3) # Test 1.5 
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2 

-Test 1.5 nur so langsam wie Test ist 1. Aber wenn Sie es brechen in irgendeiner Art und Weise nach unten-nehmen Sie die range oder sogar hinzufügen m=n+0 aus und Verwenden Sie m statt n, fällt es auf Mikrosekunden.

Also, Sage versucht hier etwas kompliziert zu machen, während er den Ausdruck bewertet und verwirrt wird.

---

Um dies zu überprüfen, in plain old ipython:

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
%timeit 'range(log(n, 2))' 
%timeit 'range(log(len([1,2,3,4,5,6,7,8]), 2))' 
%timeit 'range(log(k, 2))' 

Sie sind alle gleich schnell, wie man erwarten würde.

---

Also ... was machst du da?

Nun, vielleicht möchten Sie versuchen, den Sage-Bug aufzuspüren und ihn upstream zu archivieren. In der Zwischenzeit möchten Sie wahrscheinlich eine Problemumgehung in Ihrem Code.

Wie oben erwähnt, nur m = n+0 tun und mit m statt n scheint es zu beschleunigen. Sehen Sie, ob das für Sie funktioniert?