B-drzewo w Pythonie
wodzik
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
Łukasz Rekucki
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()
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
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
Jan Kaliszewski
> 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)
Radomir Dopieralski
>> 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
i0cus
> 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?
>
>
> >> 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