🚀 go-pugleaf

On 4 Sty, 17:22, Radomir Dopieralski <n...@sheep.art.pl> wrote:
> At Sun, 03 Jan 2010 17:28:23 +0100, Jan Kaliszewski wrote:
>
> >> I jak zoptymalizować ten kawałek z append i sort? czy wyszukać miejsce  
> >> gdzie ma się znaleźć liczba i użyć insert?
>
> > Patrz np. :http://docs.python.org/library/bisect.html(być może
>
> >> W sumie to podczas pisania nawet specjalnie się nie zastanawiałem nad  
> >> wydajnością, tylko moją wygodą ;]
>
> > I słusznie (przedwczesna optymalizacja to źródło [prawie] wszelkiego zła,
> > jak uważa np. GvR), ale bez przesady -- nie należy używac antyoptymalnych
> > konstrukcji, które mogą spowolnić program o rząd wielkości...
>
> Akurat pythonowy sort jest zoptymalizowany dla tego przypadku (prawie
> posortowana lista), wiec nie ma sie co tym za bardzo przejmowac.
> Wstawianie w srodek listy moze byc bardziej kosztowne niz sort ;)

Hmm, akurat optymalizacja optymalizacją, sortowanie posortowanej listy
nigdy nie wygra z bisekcją. Ale spójrzmy na liczby. Próba dla 100
elementowej, posortowanej listy, wstawienie 10 elementów w (powiedzmy)
środek. Potem to samo dla 10k i 100k elementów.

>>> import bisect, timeit
>>> def naive(seq):
...	for i in xrange(len(seq)/2, len(seq)/2+10):
...		seq.append(i)
...		seq.sort()
...
...
>>> def bisecting(seq):
...	for i in xrange(len(seq)/2, len(seq)/2+10):
...		bisect.insort_left(seq, i)
...
...
# 100 elementów, 3 powtórzenia x 1000 iteracji
>>> s_n = timeit.Timer('naive(range(100))', 'from __main__ import naive')
>>> s_n.repeat(number=1000)
[0.10980892822999522, 0.063997798602940748, 0.041371738586803986]

>>> s_b = timeit.Timer('bisecting(range(100))', 'from __main__ import bisecting')
>>> s_b.repeat(number=1000)
[0.027691228913226951, 0.027691228912772203, 0.027354035219559591]

>>> s_0 = timeit.Timer('range(100)')
>>> s_0.repeat(number=1000)
[0.0013677716024176334, 0.0013529652510442247, 0.001442362087800575]

# 10000 elementów, 3 powtórzenia x 1000 iteracji
>>> s_n = timeit.Timer('naive(range(10000))', 'from __main__ import naive')
>>> s_n.repeat(number=1000)
[3.1164896655859593, 3.1417747227651489, 3.121320447151902]

>>> s_b = timeit.Timer('bisecting(range(10000))', 'from __main__ import bisecting')
>>> s_b.repeat(number=1000)
[0.22504703810091087, 0.22329150771929562, 0.21956449772278575]

>>> s_0 = timeit.Timer('range(10000)')
>>> s_0.repeat(number=1000)
[0.15361896553895349, 0.15845170266038622, 0.15496019745523881]

# 100000 elementów, 3 powtórzenia x 1000 iteracji
>>> s_n = timeit.Timer('naive(range(100000))', 'from __main__ import naive')
>>> s_n.repeat(number=1000)
[35.27313806643042, 35.755941048373188, 35.417473449837871]

>>> s_b = timeit.Timer('bisecting(range(100000))', 'from __main__ import bisecting')
>>> s_b.repeat(number=1000)
[2.46779213559239, 2.477303120927445, 2.4755632349924781]

>>> s_0 = timeit.Timer('range(100000)')
>>> s_0.repeat(number=1000)
[1.664749011396907, 1.5594118805602193, 1.5986207744281273]

Na wykresie wyglądałoby to ładniej, ale na służbowym sprzęcie nie mam
odpowiednich bibliotek. Wniosek? Jeśli lista jest posortowana, to
wstawianie bisekcyjne jest bardzo tanie. Nawet tuningowane sortowanie
Pythona się nie umywa. Czyli posortować raz i wstawiać z głową. LOC
per 1 użycie pozostaje bez zmian (append+sort vs import i insort). ;-)

Chyba, że się mylę, wtedy proszę mnie poprawić. :)

--
pozdrawiam
i0 //SMG