🚀 go-pugleaf

On Jan 3, 2:23 am, wodzik <wod...@noreply.com> wrote:
> Witam
>
> W ramach nauki Pythona postanowiłem ze zaimplementuje sobie b-drzewo w
> Pythonie. Wszystko fajnie, wstawianie zajmuje jakieś 100 linii bez
> komentarzy (2-3 razy mniej niż w c++), ale elementy nie są wstawione po
> kolei. Nie wiem czy źle coś zaimplementowałem, czy zrobiłem gdzieś jakiś
> głupi błąd, czy może nie do końca rozumiem działanie Pythona. Link do
> kodu:http://www.wklej.org/id/254477/
>
> Pozdrawiam wodzik

Najłatwiej to sprawdzić debuggerem. Twój błąd (możliwe, że nie jedyny)
znajduję się w tu:

brat.wskazniki = tmp.wskazniki[self.MAX + 1:]
tmp.wskazniki = tmp.wskazniki[:self.MAX + 1]

Węzły które były na liście "wskazniki" pamiętają rodzica swojego
rodzica, więc oprócz przypisania bratu części wskaźników, powinieneś
zrobić jeszcze, np.:

for item in brat.wskazniki:
    item.rodzic = brat


PS. Ogólnie twój kod nie jest zbyt pythoniczny (sposób użycia for ..
in, nazwy metod), a miejscami dość nieoptymalny, np:

self.tablica.append(liczba)
self.tablica.sort()

On 2010-01-03 03:34, Łukasz Rekucki wrote:

> Najłatwiej to sprawdzić debuggerem. Twój błąd (możliwe, że nie jedyny)
> znajduję się w tu:
>
> brat.wskazniki = tmp.wskazniki[self.MAX + 1:]
> tmp.wskazniki = tmp.wskazniki[:self.MAX + 1]
>
> Węzły które były na liście "wskazniki" pamiętają rodzica swojego
> rodzica, więc oprócz przypisania bratu części wskaźników, powinieneś
> zrobić jeszcze, np.:
>
> for item in brat.wskazniki:
>      item.rodzic = brat

Niby banał, a sam bym chyba w życiu na to nie wpadł. Przeglądałem ten 
kod z 100 razy i za każdym razem wydawało mi się ok.

Dzięki wielkie.


> PS. Ogólnie twój kod nie jest zbyt pythoniczny (sposób użycia for ..
> in, nazwy metod), a miejscami dość nieoptymalny, np:
>
> self.tablica.append(liczba)
> self.tablica.sort()


Pewnie dlatego, że dopiero zaczynam kodowanie w Pythonie, ale będę 
wdzięczny za wszelkie sugestie.
Rozumiem, że lepiej używać for coś in coś? I jak zoptymalizować ten 
kawałek z append i sort? czy wyszukać miejsce gdzie ma się znaleźć 
liczba i użyć insert?

W sumie to podczas pisania nawet specjalnie się nie zastanawiałem nad 
wydajnością, tylko moją wygodą ;]

Pozdr wodzik

<wodzik@noreply.com> napisał:

> On 2010-01-03 03:34, Łukasz Rekucki wrote:

>> PS. Ogólnie twój kod nie jest zbyt pythoniczny (sposób użycia for ..
>> in, nazwy metod), a miejscami dość nieoptymalny, np:
>>
>> self.tablica.append(liczba)
>> self.tablica.sort()

> Pewnie dlatego, że dopiero zaczynam kodowanie w Pythonie, ale będę  
> wdzięczny za wszelkie sugestie.
> Rozumiem, że lepiej używać for coś in coś?

Tak, np.:

     def Print(self):
         if self.lisc:
             for wartosc in self.tablica:
                 print wartosc
         else:
             for i, wskaznik in enumerate(self.wskazniki):
                 wskaznik.Print()
                 if i < len(self.tablica):
                     print self.tablica[i]

Lub nawet:

     def Print(self):
         if self.lisc:
             print '\n'.join(map(str, self.tablica))
         else:
             for wskaznik, wartosc in itertools.iziplongest(
                                      self.wskazniki, self.tablica):
                 wskaznik.Print()
                 if wartosc is not None:
                     print wartosc


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

pozdr.
*j

-- 
Jan Kaliszewski (zuo)

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

-- 
Radomir Dopieralski, http://sheep.art.pl

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