drzewa w sql’u – wstęp

jakiś czas temu zainteresowała mnie metoda przechowywania wszelkiego rodzaju struktur drzewiastych w bazach danych.
dla wyjaśnienia – struktura drzewiasta jest to taki uporządkowany zbiór danych gdzie każdy element ma swój element nadrzędny, chyba, że jest elementem najwyższego rzędu.
dając przykłady z życia – drzewami są opisane wszelkiego rodzaju hierarchie – służbowe, kategorie (np. w sklepie internetowym), różnego rodzaju podziały. drzewami są też wiadomości na forach dyskusyjnych – a dokładniej – w drzewa są poukładane wątki z tych wiadomości.
ogólnie – struktury drzewiaste mają sporo zastosowań.
z tego powodu stały się one obiektem mojego zainteresowania, testów i badań. o struktury drzewiaste pytam potencjalnych pracowników na rozmowie kwalifikacyjnej.
w czasie swojej pracy z "drzewami" wyodrębniłem kilka metod które kiedyś już opisałem (link do http://www.dbf.pl/faq/tresc.html?rozdzial=1#o1_9), ale tu postaram się opisać je dokładniej i podając przy okazji wyniki pewnych testów na wydajność.
ze względu na obfitość materiału tekst ten podzielę na kilka wpisów: wstęp (to co czytacie), następnie po jednym wpisie na każdą z opisywanych metod, potem jakieś podsumowanie i na koniec kilka uwag praktycznych do wybranej przeze mnie metody.
ponieważ testowanie wydajności powinno odbywać się na sporych zestawach danych, a jednocześnie pokazywanie "o co mi chodzi" powinno być na możliwie małych ilościach – na potrzeby tego tematu przygotowałem 2 zupełnie różne zestawy danych:

1. małe drzewko w celach dydaktycznych:

to drzewko, zgodnie z konwencjami stosowanymi w tym dokumencie, ma następujące elementy:

  • sql
  • sql.oracle
  • sql.oracle.linux
  • sql.oracle.linux.glibc2
  • sql.oracle.linux.glibc1
  • sql.oracle.solaris
  • sql.oracle.windows
  • sql.postgresql
  • sql.postgresql.linux

2. spory zestaw danych  pobrany z katalogu dmoz – lista kategorii

dane z dmoza poddałem obróbce usuwając z nich znaki spoza zestawu A-Za-z0-9_, i ustawiając separator elementów drzewa na ".".
powstała lista elementów ma 478,870 elementów.
ścieżki z dmoz zawierają od 3 do 247 znaków, największe zagłębienie w drzewo jest w elemencie Regional.North_America.United_States.New_York.Localities.N.New_York_City.Brooklyn.Society_and_Culture.Religion.Christianity.Catholicism.Eastern_Rites.Maronite

w celu porównania wydajności różnych metod zapisu drzew będę testował następujące scenariusze testowe:

  1. pobranie listy elementów głównych (top-levelowych)
  2. pobranie elementu bezpośrednio "nad" podanym elementem
  3. pobranie listy elementów bezpośrednio "pod" podanym elementem
  4. pobranie listy wszystkich elementów "nad" danym elementem (wylosowanym)
  5. pobranie listy wszystkich elementów "pod" danym elementem (wylosowanym)
  6. sprawdzenie czy dany element jest "liściem" (czy ma pod-elementy)
  7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

dodatkowo zostanie sprawdzona wielkość tabel i indeksów na założonej strukturze danych.

dla porównania – zapis w postaci takiej jak w pliku źródłowym zajmuje:
– tabela dmoz: 57,319,424 bajtów
– index pkey: 8,609,792 bajtów
– unikalny indeks ścieżki: 51,888,128 bajtów

tak więc – w ciągu najbliższego czasu będę pokazywał kolejne metody oraz wyniki ich testów.

eksperymenty kuchenne – kurczak w porach

od poprzedniego wpisu kuchennego minęło już trochę czasu (w międzyczasie udoskonaliłem przepis na zupę, ale o tym opow iem innym razem).
tym razem inspiracją był post na newsach.
opis jest zasadniczo jasny, ale jeśli ktoś z czytających nie wie jak do tego podejść – poniżej opis ze zdjęciami co i jak.
najpierw kilka uwag ogólnych:

  1. używamy piersi kurczaka, ale one nie będą "suche" jak to zazwyczaj bywa. zdecydowanie nie.
  2. w żarciu jest sporo porów, ale smakują one rewelacyjnie – zupełnie inaczej niż się spodziewałem. naprawdę
  3. przygotowanie żarcia w/g tego co poniżej to około doby, z tym, że to czas oczekiwania. samej roboty jest około 15 minut.
  4. podane ilości są orientacyjne. jak zamiast 4 piersi zrobicie 2, to trzeba też zmniejszyć ilość porów.

ok. jak już podstawy są jasne, to lecimy.
zaczynamy od porów:

na zdjęciu są 2, ale finalnie dałem 3 sztuki.
pory kroimy w tzw. talarki:

taka uwaga – z pora zdejmuje sie zewnetrzna warstwe, potem odkrawa korzonki i tnie na talarki. tniemy pora na takiej długości by talarki wychodziły "spójne". potem znowu zdzieramy warstwę, i dalej kroimy. ze standardowego pora wykorzystuje około 60% jego długości na talarki.
pory wrzucam do garnka:

i solę. ilość soli – w/g uznania. na 3 pory wsypałem do środka mniej więcej 1 łyżeczkę soli.
garnek (czy cokolwiek tak naprawdę) wstawiam do lodówki. na kilka godzin.

realnie – pory "robię" wieczorem – i na następny wieczór je używam. czyli w lodówce spędzają około 20 godzin.
następnego dnia rano wyciągam z lodówki kurczaki – piersi, i rozmrażam. jeśli masz rozmrożone, to ten etap można pominąć 🙂
po rozmrożeniu (w moim przypadku to koło 12:00 jest – co utrudnia robienie tego dania w czasie chodzenia do pracy), wykładamy kurczaki na deskę:

jak widać – oddzieliłem z piersi mniejsze kawałki tak aby były "luzem". nie jest to konieczne – tak mi po prostu było wygodniej przygotować.
nasŧępnie – biorę czosnek

wyłuskuję z niego ząbki – mniej więcej po dwa ząbki na pierś.

tu uwaga – w oryginalnym przepisie czosnku nie było. ja dodałem i sobie chwalę. można dodać więcej jak ktoś lubi, jak nie – bez czosnku też smakuje super.
czosnek zgniatam:

i wcieram w kurczaki:

następnie, biorę "warzywko" (inne nazwy: wegeta, kucharek, pewnie są też inne):

i lekko obsypuję nim kurczaki:

nastepnie, biorę sporą miskę i układam w niej kurczaki:

w międzyczasie podsypuję warzywko, tak aby każdy kurczak był z obu stron obsypany.

po wrzuceniu wszystkich kurczaków do miski wstawiam ją do lodówki:

i mam znowu kilka godzin wolnego. ciąg dalszy następuje wieczorem – można o 16, można później. im później tym zasadniczo lepiej dla smaku, gorzej dla zdrowia (bo kto późno je i potem idzie spać …). jak już mnie najdzie głód, nastawiam piekarnik na 180 stopni, i biorę brytfannę:

tu uwaga – ja mam taką szklaną, ale każda może być. w szczególności – pierwsze 2 "iteracje" robienia kurczaka robiłem w takich jednorazowych foremkach "jana niezbędnego" z supermarketu.
nastepnie, biorę masło:

i smaruję dno i boki, aż całość będzie wysmarowana:

tu kolejna uwaga – tych jednorazowych nie trzeba smarować. a przynajmniej – ja nie smarowałem i wyszło ok.
następnie – do brytfanny wrzucam pory z lodówki. jak coś z nich "wyciekło" – to też wlewam:

pory układam równo i na nich kurczaka. jeśli jest możliwość – dobrze jest zostawić trochę miejsca między kurczakami – ja nie miałem takiej możliwości:

następnie, biorę majonez – sam używam kieleckiego, ale pewnie na każdym wyjdzie dobrze:

i układam grubą warstwę na kurczakach (jeśli są przerwy między kurczakami, to w nich nie dajemy majonezu):

następnie na to – tzn. na majonez, czyli w moim przypadku na całą powierzchnię, układamy plasterki (nie za grube, takie standardowe, kanapkowe) żółtego sera. ser musi być bez-dziurkowy. innych specjalnych życzeń nie ma – sam użyłem morskiego:

gotowe. w międzyczasie piekarnik powinien się już dobrze rozgrzać. więc przykrywam brytfannę (ale np. tych jednorazowych nie przykrywałem, a jak raz przykryłem to wyszło nie za dobrze) i wsadzam do piekarnika – tak po środku:

i czekam godzinę. po godzinie całość wygląda tak:

po wyłożeniu na talerz wygląda w ten sposób – może mało apetycznie, ale to naprawdę jest fenomenalnie dobre:

i to wszystko. całość przygotowań trwała krócej niż pisanie tego wpisu 🙂
smacznego.

grafika komputerowa

rendering. raytracing. cg. wiele nazw, ta sama (mniej więcej) technologia.
technologia używana od dawna służyła w założeniach do tworzenia foto-realistycznych grafik w komputerze. rozmieszczamy kilka obiektów na scenie, nadajemy im tekstury, światło, umieszczamy kamerę i robimy "zdjęcie".
jak to wyglądało widać było w filmach – terminator 2, jurrasic park. są filmy gdzie ta grafika z definicji ma wyglądać nierealistycznie (toy story i inne filmy dla dzieci), są takie gdzie ma wyglądać jak najlepiej (final fantasy). są też takie – i jest ich najwięcej, gdzie grafika komputerowa daje tylko efekty. coś dodatkowego, trudnego, bądź nierealnego do zrobienia – day after tomorrow, harry potter.
zawsze jednak przy dokładniejszym przyjrzeniu można się dopatrzyć gdzie jest granica między rzeczywistością, a wykreowanym sztucznie światem 3d.
czy jednak zawsze? autodesk pokazał krótki test – 10 zdjęć. trzeba tylko wybrać które z nich są zdjęciami, a które grafiką komputerową. mnie poszło podobno nie źle – 8 trafień. ale nie było to zbyt łatwe

arabski tuning

arabowie potrafią. robią różne dziwne rzeczy. zapewne 70% internetu widziało film z pokazami driftingu. może z 30% widziało film pokazujący co się dzieje jak taki drift nie wychodzi.
ale dziś zobaczyłem coś nowego – nie film. serię zdjęć hondy accord ztuningowanej wizualnie przez arabów. zasadniczo – nie da się tego opisać. nie będę próbował. obejrzyjcie sami.

koncert zespołu znajomego

"znajoma" grupa death metalowa "sphere" będzie uczestniczyła za 2 tygodnie (12 stycznia) w "maagal fest" w warszawskim klubie progresja.
gdybyście byli zainteresowani – polecam. aby zobaczyć co grają zapraszam na ich stronę na myspace – są tam 4 kawałki do odsłuchania, przy czym 3 to stare, sprzed 2 lat, natomiast utwór "saved from heaven" to cudo z pierwszego albumu który będzie miał premierę 3 dni po koncercie w progresji.
nie jest to może muzyka dla wszystkich, ale brzmi nieźle.

matematyka być trudna język?

przeczytałem właśnie na onecie, że brytyjski rząd (?) chce wysyłac do sklepów specjalne ekipy które mają pomagać ludziom nie rozumiejącym zapisów typu:

  • 20% obniżka
  • kup sztukę, druga dostaniesz za pół ceny

do tego będą rozdawane kalkulatory umożliwiające łatwe policzenie obniżek.
powiem szczerze – jestem przerażony. ci sami ludzie którzy w sklepie nie rozumieją co znaczy "20% obniżka" podejmują potem decyzje które dają wieloletnie efekty (wybory, posiadanie dzieci, metoda wychowania dzieci).
to tak jakby dać neandertalczykom młoty pneumatyczne. co gorsze – mam wrażenie, że o ile ten tekst był o anglikach, to u nas nie jest inaczej 🙁

sun cluster obsługuje postgresa!

jak donosi devrim, wersja 3.2 oprogramowania sun cluster obsługuje klastrowanie postgresql'a – a przynajmniej zestawianie par active/passive przy pomocy dzielonej macierzy dyskowej. nie jest to w sumie nic ultra-przełomowego, ale dobrze wiedzieć, że sun dodaje obsługę postgresa do swoich narzędzi.

golf z nagrodami pieniężnymi

wow. pierwszy w historii (a przynajmniej pierwszy o którym wiem) perlgolf z którym można wygrać kasę! fonality – twórcy kmercyjnego rozwiązania telefonicznego stworzonego w oparciu o asterisk'a, zaprezentowali zadanie i nagrodzą pierwsze 20 osób.
zadanie – napisać kalkulator działający w notacji liczb rzymskich. prosty – od 1 do 3999, tylko 2 operatory (minus i plus).
na wypadek jeśli nie wiecie co to golf: konkurs perlowy w którym wygrywa osoba która napisze najkrótszy kod realizujący daną funkcjonalność. większość golfów ma rozwiązania w granicach do 100 znaków. jak na razie w tym golfie prowadzi "alien" ton hospel – już ma 100 znaków, i jeszcze prawie tydzień na wymyślenie optymalizacji.

wordpress na postgresie

jak może wiecie wordpress od zawsze był na mysql'u.
dodatkowo – team wordpressa nigdy nie wykazał się chęcią modyfikacji kodu aby działał na innych platformach bazodanowych – w szczególności na postgresie. a byli pytani/proszeni przez ludzi z okolic core-teamu postgresa!
ostatnio przeczytałem na blogu drixtera, że aure zrobił nieoficjalny port wordpressa na postgresa. i to nie jakąś prehistoryczną wersję tylko 2.0.4! tak więc – zachęcam do testowania 🙂

artystyczne monitory

benq – znany producent sprzętu, wyprodukował serię (na razie 2 modele) monitorów lcd ozdobionych reprodukcjami tradycyjnej sztuki chińskiej.
prace zostały wybrane w ramach współpracy z muzeum "national palace" na tajwanie.
jeśli chodzi o kwestie techniczne, to nie jest źle – takie bardziej standardowe parametry:

  • 17 cali
  • 1280×1024 pikseli
  • 6 milisekund – czas reakcji
  • złącza zarówno d-sub jak i dvi

cena pewnie będzie spora, głównie dlatego, że modele te wypuszczono w mocno limitowanych seriach – po 1300 egzemplarzy.