Dlaczego tworzenie zakresu od 0 do dziennika (len (lista), 2) jest tak wolne?

Question

Nie mam pojęcia, dlaczego tak się dzieje. Zmywałem niektóre listy i potrzebowałem pętli for przechodząc od 0 do log(n, 2), gdzie n było długością listy. Ale kod był niesamowicie powolny, więc po odrobinie badań odkryłem, że problemem jest generowanie zasięgu. Przykładowy kod do demonstracji:

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 

Wyjście

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

Liczba badań jest mała (nie chciałem to być uruchomiony więcej niż 10 minut), ale już pokazuje, że jest range(log(n, 2)) o rząd wielkości wolniej niż odpowiednik, używając tylko logarytmu liczby całkowitej. To naprawdę zaskakujące i nie mam pojęcia, dlaczego tak się dzieje. Być może jest to problem na moim komputerze, może problem z Sage'em lub bug Pythona (nie próbowałem tego samego na Pythonie).

Używanie zamiast range również nie pomaga. Ponadto, jeśli otrzymasz numer z .n(), test 1 działa z tą samą prędkością 2.

Czy ktoś wie, co może się dziać? Dzięki!

Answer 1

Dobry żal - rozpoznaję to. Jest to związane z jednym z moich, traC#12121. Po pierwsze, można uzyskać dodatkowy narzut z użyciem Pythona int w przeciwieństwie do Sage Integer powodów wytaczarki:

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 

(r przyrostek oznacza „surowy” i zapobiega preparser Sage od owijania dosłownym 2 w Integer(2))

A potem robi się dziwnie. Aby wytworzyć int do range do konsumpcji, Sage musi wymyślić, jak zmienić log(8)/log(2) na 3, i okazuje się, że robi najgorszą możliwą rzecz. Plagiowanie mojej oryginalnej diagnozy (mutatis mutandis):

Najpierw sprawdza, czy ten obiekt ma własny sposób na uzyskanie int, a nie. Więc ona buduje obiekt RealInterval z log (8)/log (2) i okazuje się, że jest to najgorsza rzecz, jaką mogła zrobić! Sprawdza, czy dolna i górna część przedziału zgadzają się [na podłodze, mam na myśli] (tak, że ona wie na pewno, co to jest podłoga). Ale w tym przypadku, , ponieważ tak naprawdę jest liczbą całkowitą! to zawsze będzie wyglądać tak:

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

Te dwie granice mają podłogi, które nie są nie są równe, więc Sage postanawia ona nie został jeszcze rozwiązany problem, a ona trzyma zwiększając precyzję 20000 bity, żeby sprawdzić, czy potrafi udowodnić, że są ... ale przez konstrukcję nigdy nie zadziała.W końcu poddaje się i próbuje go uprościć, który powiedzie:

sage: y.simplify_full() 
3 

Dowód bez słów, że jest to przewrotny własność dokładnie podzielna przypadku:

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

Może użycie log(x, 2) (alias ld()) nie jest dobrym pomysłem. Chciałbym zaproponować, aby korzystać przesunięcie wartości int do wdrożenia ld():

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

W ten sposób można uniknąć tych wszystkich uglinesses z range() i log().

W normalnych sytuacjach dzwonienie pod numer log() powinno zająć więcej czasu niż zwykłe przełączanie bitów w int. Przykłady:

>>> 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 

Przy większych wartościach dla n różnica maleje. Dla n = 10000 uzyskałem 0,8163230419158936 i 0,8106038570404053, ale powinno to być spowodowane tym, że korpus pętli zajmie większość czasu w porównaniu do inicjowania pętli.

Answer 3

Pythona 2 umożliwia zakres (some_float), ale jest przestarzała i nie działa w pytona 3.

Próbka kod nie daje wyjście określono. Ale możemy przez to przejść. Po pierwsze, timeit potrzebuje pełnego scenariusza, import w skrypcie nazywając timeit nie jest używany:

>>> 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 

Jeśli dodać import do skryptu jest planowane, obejmuje on również czas instalacji:

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

Jeśli przesuniesz import do instalacji, jej lepiej, ale timingowanie One-Shot jest notorycznie niedokładne:

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

Wreszcie, uruchom go kilka razy i masz dobry numer:

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

Answer 4

Wygląda na to, że to błąd Mędrca.

stworzyłem nowy notebook i to zrobił:

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 

testowa 1.5 jest tak powolny jak teście 1. Ale jeśli rozbicie go w żaden sposób, zdjąć range, lub nawet dodać m=n+0 i użyj m zamiast n, spada do mikrosekund.

Tak więc, Sage próbuje zrobić coś skomplikowanego podczas oceniania wyrażenia i dezorientacji.

---

Aby to sprawdzić, w zwykły stary 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))' 

Oni wszyscy są równie szybko, jak można się spodziewać.

---

Więc ... co z tym zrobić?

Cóż, możesz spróbować wyśledzić błąd Sage'a i zarchiwizować go. Ale tymczasem prawdopodobnie potrzebujesz obejścia w swoim kodzie.

Jak wspomniano powyżej, po prostu wykonanie m = n+0 i użycie m zamiast n wydaje się przyspieszyć. Sprawdź, czy to działa dla Ciebie?