Czego to nie zrobią popularne serwisy, aby przyciągnąć rzesze fanów, i by zostali oni na stronie na dłużej . Nudzi Cię oglądany właśnie filmik na YouTube? Pograj w Węża!

Serwis YouTube wprowadził nową funkcjonalność przy odtwarzaniu filmów tam wrzuconych. Otóż jest nią słynna gra w Snake’a.
Można ją aktywować poprzez przyciśnięcie przez dłuższy czas lewej strzałki (kursora), podczas oglądania filmiku. Wtedy na ekranie odtwarzacza pojawi się wspomniany wąż i można już zaczynać zabawę.

Czym jeszcze zadziwi nas Google?

A teraz konkurs: kogo wąż będzie najdłuższy na tak „rozpraszającym” tle ?

Wczorajszego wieczoru odkryłam jak wiele nowości mogą przynieść nieznaczne porządki w zakładkach przeglądarki i rss-ach.

Otóż jak zapewne niektórzy już wiedzą, gdyż donosi o tym wiele portali z nowinkami technologicznymi – legendarna gra PAC-MAN świętuje swoje 30. urodziny.

Google postanowiło uczcić je w sztandarowy dla siebie sposób i umieścić Google doodle tematycznie z tym faktem związane. Jednak jak to szanowne Google ma w zwyczaju, nie przestaje zadziwiać. Otóż jego logotyp jest… interaktywny! Jeśli o mnie chodzi to naprawdę rzecz godna podniecenia .

Jak donosi Dziennik Internautów współtwórcom doodle jest Polak – Marcin Wichary. Także mamy być z czego dumni. I jeszcze cytując za DI:

PAC-MANowy doodle ma być dostępny przez 48 godzin, ale jako że mój news jest dość mocno spóźniony, czasu pozostało już nie wiele. Tym którzy z jakiś powodów jeszcze na Google nie zajrzeli (lub tak jak ja są szczęśliwymi posiadaczami iGoogle jako strony startowej i mają małe pojęcie co dzieje się „poza”), polecam, aby szybko swój błąd naprawili .

Spóźnialskim na otarcie łez oferuję screena upamiętniającego tą rocznicę .

UPDATE: Ponieważ Google’owy PAC-MAN bardzo mi się spodobał, szukałam i znalazłam. Kochane Google udostępnia wciąż swoją wersję gierki pod adresem http://www.google.com/pacman/.
P.S. Dla par żądnych pac-manowych wrażeń radzę kliknąć w „Insert Coin” .

Sortowanie to problem, z którym programiści stykają się niejednokrotnie. Z racji ludzkiej chęci do życia w skatalogowanym, uporządkowanym świecie, algorytmy sortowania odgrywają dużą rolę wśród operacji stosowanych na danych. Jednak zwykle przy porządkowaniu danych pojawiają się pytania. Jaką metodę sortowania zastosować? Czy ma być ona szybka, czy można pozwolić sobie na dokładne, ale wolniejsze sortowanie? Dla jakich tablic, jaki algorytm będzie najbardziej optymalny?

Ze względu na dużą różnorodność tego typu algorytmów, najłatwiej przeprowadzić wybór wśród tych najpopularniejszych, biorąc za kryterium ich złożoność czasową i stopień trudności w implementowaniu, pamiętając jednocześnie o wielkości tablicy i ilości danych do posortowania. Jest to bardzo istotny fakt, weźmy dla przykładu sortowanie mieszkańców większego miasta wg ich numeru PESEL.
Z roczników statystycznych wiadomo, że liczba mieszkańców Gliwic na rok 1998 to 215 658. Drugą wartością, która przyda się w przykładzie, to prędkość z jaką mój komputer (na którym oczywista prowadziłam te testy) przelicza operacje elementarne, a jest to (przy średnio obciążonym systemie, procesor z zegarem 2GHz).

Na dane posortowane algorytmem o klasie złożoności O(N²) (jakim jest np. sortowanie bąbelkowe) trzeba czekać , natomiast, gdy klasa złożoności wynosi O(N logN) (jak w Quicksorcie)

Pierwszy trwa niecałą godzinę, drugi – niecałą dziesiętną część sekundy. To chyba spora różnica.

W dalszej części tekstu zajmę się bardziej szczegółowym omówieniem tych, można powiedzieć, sztandarowych algorytmów sortowania. Przedstawię ich implementację w języku C++^[1], złożoność czasową i postaram się określić wydajnościowe plusy i minusy.

Sortowanie przez wstawianie

„Ulubiona” metoda sortowania graczy w karty, podczas układania kart tuż po rozdaniu. Ogólna idea algorytmu jest następująca: w danym momencie w ręku trzymamy zarówno karty posortowane, jak i przygotowane do sortowania. Z tych nieposortowanych bierzemy pierwszą z brzegu kartę i wstawiamy w odpowiednie miejsce w grupie posortowanych. Jak można się łatwo domyśleć, czynność tą powtarzamy aż do skończenia się kart w pakiecie nieposortowanych.
Proces ten zobrazuję paroma rysunkami krokowymi.

[kliknij obrazek, aby powiększyć]

• Implementacja algorytmu

• Złożoność algorytmu

W pesymistycznym wypadku każdy element będziemy przesuwać na pierwszą pozycję.
Przesunięcie jednego elementu wykona się n razy. Dla n elementów złożoność będzie wynosić n ∙ n.
Z tego wynika, że algorytm sortowania przez wstawianie jest klasy O(n²).

• Podsumowanie

Ze względu na dużą złożoność algorytmu, zupełnie nie nadaje się on do sortowania większych tablic (jak można sobie wyobrazić na przykładzie porządkowania liczby mieszkańców Gliwic), gdyż trwałoby to stanowczo za długo. Jednak wydaje się być wymarzony do sortowania mniejszej ilości danych – przy jego implementacji trudno jest o pomyłkę i jest doskonały w swej prostocie.

Sortowanie bąbelkowe

Swoją intrygującą nazwę wzięło z analogii do pęcherzyków powietrza. Poziomo ustawiona tablica to pojemnik z wodą, a wpisane w nią dane to pęcherzyki powietrza. Najlżejsze bąbelki – czyli najmniejsze liczby, ulatują do góry, podczas gdy te cięższe – pozostają na końcu.

• Przypatrzmy się implementacji

Dla przykładu przedstawię analizę sortowania algorytmem bąbelkowym 7-elementowej tablicy. Zacieniowany element, to ten który w pojedynczym przebiegu głównej pętli „uleciał” do góry. W algorytmie zawsze analizowane są dwa sąsiadujące elementy (przebieg pętli j). Jeśli element niżej jest mniejszy niż wyżej, następuje ich zamiana. Operacja ta jest za pierwszym razem wykonywana na całej długości tablicy – i za każdym kolejnym razem zmniejsza się o 1 (o element, który został ustawiony jako najmniejszy na początku tablicy w poprzednim przebiegu pętli i).

• Złożoność algorytmu

Możemy przyjąć, że operacją dominującą w algorytmie jest operacja porównania dwóch elementów. W pierwszym wywołaniu pętli głównej porównań tych jest n. W następnej n-1 (tak jak wspominałam wcześniej – liczba porównań została zmniejszona o element, który został już uporządkowany), potem n-2 itd. aż do n-(n-1), czyli przedostatniego elementu tablicy
Wyprowadzamy zatem wzór ogólny:
.
Jak widać operacji wykonywanych w pętli głównej w sumie jest n, a za każdym razem liczba porównań jest zmniejszana o pewne zmienne C.

• Podsumowanie

Jak i w algorytmie sortowania przez wstawianie, złożoność czasowa jest bardzo duża. Jest także parę kwestii, które działają na niekorzyść algorytmu.

• Są to na przykład „puste przebiegi” – kiedy nie jest dokonywana żadna zamiana, bo dane są już posortowane.

• Algorytm jest także bardzo wrażliwy na konfiguracje danych:
  • 4 | 2 | 6 | 18 | 20 | 39 | 40 // ta tablica będzie wymagała jednej zamiany sąsiadujących elementów
  • 4 | 6 | 18 | 20 | 39 | 40 | 2 // a ta aż sześciu

Plusem algorytmu jest natomiast jego prostota.

Quicksort – szybkie sortowanie

Jak sama nazwa wskazuje, dzięki tej metodzie sortowania operacja ta znacznie zyskała na szybkości. Ogólna procedura dzieli się na dwie części: część do właściwego sortowania, której zadaniem jest wywoływanie samej siebie, i część do rozdzielania elementów tablicy względem wartości pewnej jej komórki (będącej osią podziału). Rozdzielanie dokonuje procesu sortowania, natomiast proces rekurencji służy poskładaniu wyników cząstkowych w całą posortowaną tablicę.
Jak to działa? Najpierw następuje odczyt elementu, który będzie służył za oś podziału P – najczęściej jest to pierwszy element analizowanej tablicy. Następnie po lewej stronie od P ustawiają się wszystkie elementy mniejsze od P, po prawej – większe. Symbolicznie:

< P || P || ≥ P

Kolejnym etapem jest po prostu rekurencyjne odtworzenie procedury na elementach z lewej i z prawej strony. Wynikiem – posortowana tablica

• Implementacja

• Dla zobrazowania działania algorytmu, jego przykład dla tablicy
  3 | 2 | 0 | 5 | 8 | 3 | 4 | 1 | 3 | 2

[kliknij obrazek, aby powiększyć]

• Złożoność algorytmu

W przypadku optymistycznym, gdy za każdym razem wybieramy medianę tablicy, liczbę porównań
można opisać rekurencyjnym wzorem

dla dużych n:

co daje

Przypadek pesymistyczny zakłada wybieranie zawsze najmniejszego/największego elementu w sortowanym fragmencie tablicy

stąd wynika

• Podsumowanie

Mimo swojego rodzaju trudności w implementacji i wielu rekurencji, Quicksort jest w praktyce bardzo dobrym algorytmem do stosowania na dużych tablicach, ze względu na swoją małą złożoność czasową i co za tym idzie – szybkość sortowania. Niech liczby powiedzą same za siebie. Czas wykonywania algorytmu dla zbioru 10 000 danych (przeprowadzono 6 prób) na komputerze o procesorze 2.4GHz wynosił 0,911 ± 0,018 [s].

Heap Sort – sortowanie przez kopcowanie

Algortym sortowania przez kopcowanie wykorzystuje strukturę zwaną kopcem lub stertą. Struktura ta jest drzewem binarnym zawierającym liczby zbioru, gdzie możliwe jest ich uporządkowanie. Pewną cechą szczególną kopca jest jego kształt przypominający lekko wybrakowaną piramidkę.

Kolejną cechą kopca jest uporządkowanie – wartości w węzłach niższych są mniejsze od tych w wyższych węzłach. Czyli T[ojciec(i)] ≥ T[i].
Zawartość kopca układa się w następujący sposób:

• wierzchołek kopca wstawiamy do T[0]

• dla dowolnego węzła w T[i] jego lewy syn jest w T[2i+1], a prawy w T[2i+2]

• Reprezentacja graficzna kopca

[kliknij obrazek, aby powiększyć]

• Algorytm sortowania

1. Ułóż dane w kopiec (dane znajdują się w tablicy o rozmiarze n)
2. Usuń wierzchołek kopca, poprzez zamianę go z ostatnim liściem drzewa (n- -)
3. Przywróć uporządkowanie kopca dla pozostałych elementów, czyli

a) Jeśli wierzchołek jest większy od obojga dzieci – KONIEC
b) Zamień wierzchołek z większym dzieckiem
c) Przywróć własność kopca w tej części kopca, w której nastąpiła zamiana

4. Idź do pkt 2.

Dla większego zobrazowania sobie procedury z punktu 3, podaję przykład jej działania na poniższych rysunkach. Jak łatwo zauważyć, pogrubiony węzeł zaburza warunek T[ojciec(i)] ≥ T[i], zatem trzeba go uporządkować.

• Implementacja

• Złożoność

Algortym w wewnętrznej pętli for wykonuje co najwyżej porównań pomiędzy elementami danego ciągu, a w sumie daje to
.
Zatem złożoność czasowa algorytmu to .

• Podsumowanie

Choć w praktyce algorytm jest wolniejszy od Quicksorta, jego zdecydowanym atutem jest to, że nawet w pesymistycznym wypadku, wciąż ma złożoność . Z tego jasno wynika, że algorytm ten jest dobrym wyborem do sortowania dużych ilości danych.

Wnioski

Dla porównania algorytm O(n²) przy tych samych danych (10 000 elementów, procesor 2,4GHz) wykonywałby się szacunkowo 2,89 godzin. Wniosek nasuwa się prosty, o czym wspominałam już we wstępie – algorytmy sortowania należy dobierać indywidualnie do swoich potrzeb, biorąc za wyznacznik wielkość/ilość danych do posortowania i czas, który możemy na to sortowanie zagospodarować (wszak mogą istnieć osoby lubujące się w długich, ciągnących się w nieskończoność programach sortowania ☺).

Jednak diabeł zawsze tkwi w szczegółach – Quicksort, mimo pozornego zwycięstwa nad sortowaniem bąbelkowym czy przez wstawianie, ma swoje mankamenty. Może wystąpić przepełnienie stosu dla ogromnej liczby danych – algorytm wykorzystuje proces rekurencji. Także jeśli nieszczęśliwie trafimy na pesymistyczny przypadek sortowania, czas, jaki komputer poświęci na uporządkowanie danych, nie wiele będzie się różnił niż jak w bąbelkowym. Algorytmy, które przedstawiłam są, jak mówiłam, sztandarowe, tak też istnieje ich wiele, wiele więcej. W gestii programisty pozostaje, który z nich dobrać, jako optymalny, w swoim programie.

[1] W domyśle, w każdym kodzie umieszczone jest const int n=wartosc określające rozmiar tablicy do posortowania

Jak kilka osób mogło już zauważyć, od paru dni podniecam się moją nową książką „Photoshop CS4. Pikantne efekty specjalne” Scotta Kelby. Jest naprawdę genialnie napisana, zawiera masę przykładów, pomysłów, a spora doza humoru autora i prostota opisu efektów sprawia, że książka jest przestępna dla szerszego grona grafików lub amatorów.

Przedstawiam Wam moje najnowsze dzieło, stworzone z pomocą i pomysłem właśnie tej książeczki. Jest to efekt wykorzystany między innymi w plakacie filmu „Słaby punkt” („Fracture„). Więcej (choć na razie niewiele więcej) można znaleźć na moim deviantarcie ( http://nibinlondien.deviantart.com ), a z czasem wszystkie projekty ukażą się w dziale „Galeria” dostępnym na górze strony.

Jako że ludzie w moim wieku są na etapie wylatywania spod rodzinnych skrzydeł do własnych gniazdek, to o takiej mojej dziupli słów kilka. W opinii wielu moich rówieśników, którzy wciąż żyją na rodzicielskim garnuszku, a i też mojej z okresu, gdy jeszcze wizja własnego domu mnie nie dotyczyła, mieszkanie na swoim jawi się jako coś przecudnego. Otóż moi drodzy, macie prawie rację. A ja niestety właśnie o tych przypadkach, w których racji nie macie, będę pisać.

Pierwsze chwile w świeżo zakupionym mieszkaniu nie są zbyt podniecające. Puste to to, ponure, zupełnie bez życia. Na bóle przeprowadzki, łącznie z pakowaniem mebli na czwarte piętro bez windy, jak to było w moim wypadku, też zrzućmy zasłonę milczenia. O wiele ciekawszym zdaje się być to, czego nowo usamodzielniony może nauczyć się już w pierwszych tygodniach pełnoprawnego mieszkania samopas. Pominę również podstawy takie jak odkrycie faktu, że żywotność szynki w lodówce przelicza się w dniach, nie tygodniach (nie daj Bóg miesiącach) lub znaleziska w postaci połaci kurzu w dziwnych miejscach, a narastających wprost proporcjonalnie do czasu upływającego od ostatniego sprzątania i odwrotnie proporcjonalnych do częstości użytkowania danego miejsca. Pierwszym questem, z którym user nowego serwera własny-dom musi zmierzyć się najczęściej najpierw, to nauka skilla Gotowanie. Nie wątpię, są wśród Was pewnie te wybitne jednostki, które w umiejętnościach kucharskich przeganiają swoją matkę, a nierzadko szefa lokalnej pięciogwiazdkowej restauracji, ale nie łudźmy się – stereotypowe danie studenckie to chleb posmarowany nożem.

Z powyższego wynika, że, jak to w pewnym programie telewizyjnym zwykło się mówić, „drugie danie to wyzwanie”. Na początek zwykle wystarcza proste rozbicie jajek na jajecznicę i posiekania kurczaka na potrawkę do obiadu. Jednak, jak to w życiu bywa, nic nie trwa wiecznie i po około miesiącu takiej diety, słowo „kurczak” jest jedyną rzeczą, która z całego obiadu przejdzie przez gardło.

Aby trochę złagodzić szok pokurczakowy proponuję przepis prosty na sycące danie jakim jest Naleśnik z szynką i ziołami.

Należy zaopatrzyć się w:

• 1 patelnia
• 1 łopatka do przewracania naleśnika (uwaga: wymasterowanie sztuki odwracania naleśnika w całości daje +10 do efektów specjalnych w kuchni)

ciasto do naleśnika, które składa się z (proporcje na 8 naleśników, choć i tak każdy sypie na oko):

• 12,5 dag mąki
• 1 jajko
• 300 ml mleka
• szczypta soli
• mix przypraw

składniki do dania głównego:

• oliwa
• por
• zielony groszek
• szparagi bądź fasolka szparagowa
• szynka
• ser ementaler
• sól i pieprz
• w przepisie jest jeszcze cukinia, ale jak do tej pory nie udało mi się jej zdobyć – ktoś zrobi z nią, ma kolejną misję: podzielić się wrażeniami

Ciasto w telegraficznym skrócie to wrzucenie wszystkich składników do miski i wymieszanie dokładnie, tak aby nie zostały żadne grudki.

Na patelni rozgrzać oliwę i podsmażyć warzywa, aż zmiękną. W celu sprawdzenia czy są miękkie można je skosztować. Uwaga! Gorące!
Ewentualnie można przyjąć iście NIE empirycznym sposobem, że miękną po 5 minutach.

Na koniec dolewamy przygotowane wcześniej ciasto. Ruchem kolistym najlepiej, tak aby rozlało się po całej patelni i przykryło wszystkie warzywa i szynkę. Teraz można wreszcie iść nabić level na WoWie, bo ciasto musi się tak smażyć, aż do ścięcia (i znów info dla tych z nurtu racjonalizmu: ok 12 minut). Gdy już będzie przypieczone, przewietrz kuchnię, bo pewnikiem po wciągnięciu się w MMO przypaliłeś ciasto, a następnie przewróć je na drugą stronę używając łopatki. Tutaj przyda się jakiś buff w postaci innego sztućca, gdyż przewracanie ciasta jest sztuką dość ciężką, jak już wcześniej nadmieniłam.

OK, skoro przewróciłeś już ciasto, to może sobie dodać statystyki, a naleśnika smażyć jeszcze 5 minut. Na koniec, gdy już zdejmiejsz go z patelni, połóż/zetrzyj na niego ser i wsadź do rozgrzanego piekarnika/mikrofalówki na 3 minuty, aż ser się stopi. Ufff… koniec. Jeśli do tej pory nie padłeś z głodu, to teraz właśnie jest czas, abyś zaczął jeść swe dzieło.

Naciesz się swoją nową umiejętnością, a może i nacieszysz nią też żołądki współlokatorów/gości/przerażonych rodziców, przyjeżdżających do Ciebie ze słoikiem zupy?

I przygotuj się na wyższy stopień wtajemniczenia: Mięso w piwie, czyli co zrobić z rozgazowanym złotym trunkiem na drugi dzień po imprezie. Ale o tym, jak i o innych mieszkaniowych przeciwnościach już w następnych odcinkach.

W głowie wciąż jeszcze huczą wystrzały fajerwerków minionego sylwestra, a już czas najwyższy na rozpoczęcie nowego roku, i to z tą werwą jaką sobie założyłam. Plany, formułujące się przez ostatnie miesiące gdzieś w zakątkach umysłu, nareszcie będą miały swoją okazję, by ujrzeć światło dzienne. W produkowaniu postanowień noworocznych zawsze byłam kiepska, więc tym razem pójdę w długofalowe cele, jakim między innymi jest ten projekt. I mam nadzieję, że nowy blog będzie przypieczętowaniem nowego rozdziału w pracowitym życiu i przyszłości.

Stronka ta niech służy uciesze Waszej i mojej, już niedługo zagości tu trochę działów, podstron i, co jest oczywiste, treści .

Wszystkiego dobrego w Nowym Roku życzę Wam, sobie i nowonarodzonemu blogowi.