In sfarsit Google lanseaza Chrome , un browser open source.

Lansarea a fost anuntata prin un comic book foarte misto facut, ce sumarizeaza bine feature-urile interesante ale acestui produs.

Chestia ce mi se pare mie cea mai utila este faptul ca fiecare tab este independent de celelalte ruland in un "proces" diferit. Asta inseamna ca daca un tab iti crapa poti sa il inchizi fara sa inchizi restul taburilor.

Browserul este construit peste WebKit un layout engine open source folosit de Safari (browserul Apple). Acest engine este destul de rapid si din cate am inteles e mult mai curat si mai usor de folosit pentru programatori, decat Gecko (layout engine-ul folosit de FireFox).

De asemenea Chrome are integrat un javascript engine numit V8 care se lauda cu o performanta foarte buna.

Eu consider ca acest proiect va fi un pas important in fata pentru lumea browserelor, o data prin cresterea concuretei si apoi prin faptul ca proiectul e open source iar ideile bune vor putea fi copiate si integrate rapid in celelalte broswere.

Radu Berinde, care vara asta face un internship la VMware, va scrie un guest post despre programarea templateurilor in C++. Despre Radu am mai vorbit aici si aici .

Am inceput sa citesc o carte interesanta - "Modern C++ Design", numita si "the crack book" din motive ce devin evidente inca de prin capitolul 2. Intamplator, e scrisa chiar de un roman, Andrei Alexandrescu, care e unul dintre cei mai mari experti pe C++ din lume. Cartea arata cum se pot face lucruri foarte interesante si/sau ciudate cu template-uri. Mi-am amintit de ceva ce am auzit acum mult timp: despre cineva care facuse un program C++ care nu compila, dar mesajele de eroare aratau numerele prime. Mi se parea ceva de-a dreptul bolnav, insa - comparativ cu ce se intampla prin cartea mentionata - acum pare trivial un astfel de program. Si de fapt chiar este destul de simplu, asa ca m-am gandit sa fac un mic "tutorial" in care sa explic cum se face.

Principiul de baza

Poate stiti ca in STL exista o implementare generala pentru vector, insa exista si o implementare speciala numai pentru vector<bool>, care foloseste doar cate un bit pentru fiecare valoare. Idioma C++ care permite asa ceva este "template specialization" si este un mecanism foarte puternic (mult mai puternic decat vom vedea aici). Practic, compilatorul are mai multe definitii din care alege una anume. Folosind acest lucru putem sa "trucam" compilatorul in a face un "if".

De exemplu, sa zicem ca vrem sa facem o asertie la timpul compilarii. Avem o expresie statica (care poate fi calculata la compilare) si vrem sa primim o eroare daca aceasta expresie nu se evalueaza la true. Putem sa folosim aceasta idee de template specialization:

template<bool> struct CompileTimeError {};
template<> struct CompileTimeError<true> { enum { Cool = 1 }; };

Am definit un tip CompileTimeError care in general este gol. Insa daca parametrul bool se intampla sa fie true, compilatorul foloseste definitia specializata a tipului. Daca avem o expresie expr, sa ne gandim la urmatoarea expresie:

CompileTimeError<expr>::Cool

Daca expr = true, s-ar evalua la 1. Insa daca este false, vom avea o eroare de compilare - definitia generala nu include identificatorul Cool. Am reusit sa facem compilatorul sa evalueze doua lucruri diferite in functie de o expresie - un "if" daca vreti.

Recursivitate

Pentru ca tipurile sunt prin definitie imutabile, nu vom putea face compilatorul sa ruleze algoritmi iterativi - nu avem cum sa il facem sa mentina o stare. Va trebui sa convertim orice lucru iterativ in ceva recursiv, cum am face la un limbaj functional (in stil lisp). Cum determinam daca un numar este prim fara sa mentinem stare? Putem sa definim o "functie" HasDivisors cu doi parametri, N si K. HasDivisors returneaza true daca vreun numar intre 2 si K il divide pe N. Astfel, un numar este prim daca HasDivisors este true pentru parametrii N si N-1. Putem implementa aceasta idee cu template-uri:

template <int N, int K>
struct HasDivisors
{
    enum { Result = (N % K == 0) || HasDivisors<N, K-1>::Result };
};

template <int N>
struct HasDivisors<N, 1>
{
    enum { Result = 0 };
};

template <int N>
struct IsPrime
{
    enum { Result = !HasDivisors<N, N-1>::Result };
};

Observam recursivitatea din HasDivisors; conditia de oprire este implementata prin specializarea partiala HasDivisors<$N$, 1>

Putem combina acestea cu definitiile de mai sus pentru a genera erori pentru numerele prime:

template <int N>
struct PrimeErrors
{
    enum { Result = CompileTimeError<!IsPrime<N>::Result>::Cool +
                      PrimeErrors<N-1>::Result };
};

template <>
struct PrimeErrors<1>
{
    enum { Result = 0 };
};

Prima parte a expresiei din PrimeErrors este doar o asertie la timpul compilarii. Operatia de adunare e folosita doar pentru recursivitate. Din nou, specializarea ne da voie sa definim conditia de oprire a recursivitatii. In final nu mai avem nevoie decat de o instructiune care sa faca compilatorul sa evalueze PrimeErrors:

PrimeErrors<100>::Result x;

Daca compilam acest program, vom primi erori ca mai jos (am taiat din liniile repetitive):

templates.cpp: In instantiation of 'PrimeErrors<2>':
templates.cpp:25:   instantiated from 'PrimeErrors<3>'
templates.cpp:25:   instantiated from 'PrimeErrors<4>'
templates.cpp:25:   instantiated from 'PrimeErrors<5>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'
templates.cpp: In instantiation of 'PrimeErrors<3>':
templates.cpp:25:   instantiated from 'PrimeErrors<4>'
templates.cpp:25:   instantiated from 'PrimeErrors<5>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'
templates.cpp: In instantiation of 'PrimeErrors<5>':
templates.cpp:25:   instantiated from 'PrimeErrors<6>'
templates.cpp:25:   instantiated from 'PrimeErrors<7>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'

Daca filtram doar liniile cu In instantiation of ..., vedem frumos rezultatul dorit:

root@slack ~# gcc templates.cpp 2>&1 | grep "In in" 
templates.cpp: In instantiation of 'PrimeErrors<2>':
templates.cpp: In instantiation of 'PrimeErrors<3>':
templates.cpp: In instantiation of 'PrimeErrors<5>':
templates.cpp: In instantiation of 'PrimeErrors<7>':
templates.cpp: In instantiation of 'PrimeErrors<11>':
templates.cpp: In instantiation of 'PrimeErrors<13>':
templates.cpp: In instantiation of 'PrimeErrors<17>':
templates.cpp: In instantiation of 'PrimeErrors<19>':
templates.cpp: In instantiation of 'PrimeErrors<23>':
templates.cpp: In instantiation of 'PrimeErrors<29>':
templates.cpp: In instantiation of 'PrimeErrors<31>':
templates.cpp: In instantiation of 'PrimeErrors<37>':
templates.cpp: In instantiation of 'PrimeErrors<41>':
templates.cpp: In instantiation of 'PrimeErrors<43>':
templates.cpp: In instantiation of 'PrimeErrors<47>':
templates.cpp: In instantiation of 'PrimeErrors<53>':
templates.cpp: In instantiation of 'PrimeErrors<59>':
templates.cpp: In instantiation of 'PrimeErrors<61>':
templates.cpp: In instantiation of 'PrimeErrors<67>':
templates.cpp: In instantiation of 'PrimeErrors<71>':
templates.cpp: In instantiation of 'PrimeErrors<73>':
templates.cpp: In instantiation of 'PrimeErrors<79>':
templates.cpp: In instantiation of 'PrimeErrors<83>':
templates.cpp: In instantiation of 'PrimeErrors<89>':
templates.cpp: In instantiation of 'PrimeErrors<97>':

Dragut, nu?

Concursul Junior Challenge 2008, un concurs marca infoarena ajuns deja la editia a doua, se va desfasura online sambata, 5 iulie. Pagina concursului se gaseste aici.
Castigatorii concursului care sunt elevi in ciclul primar sau gimnazial vor primi cate un tricou infoarena. Va invitam sa participati insa pe toti, deoarece subiectele sunt cu adevarat provocatoare. Mult succes celor care vor participa si nu uitati sa va inscrieti daca doriti sa vi se modifice ratingul.

Dupa o pauza de un an, concursul Google Code Jam se relanseaza. Inregistrarea este deschisa pe siteul concursului tuturor celor peste 18 ani. De data asta nu va fi folosita platforma Topcoder ci concursul va avea personalitate lui. In loc sa trimiteti surse la un evaluator online automat, va trebui sa rezolvati niste seturi de date si sa trimiteti fisierele de ouput. Formatul acesta e destul de misto pentru ca va permite utilizatorilor sa foloseasca orice limbaj sau tooluri software pentru a rezolva problemele.
Proiectul a fost construit pe platforma Google App Engine ca parte a filozofiei "eat your own dog food". Aceasta are la baza ideea ca pentru a face un produs bun pentru clienti, primul client trebuie sa fii chiar tu. Pentru a gasi probleme interesante pentru Google Code Jam, s-a organizat un concurs intern de propus de probleme la care am participat cu destul entuziasm si sper ca din problemele mele sa se selecteze cateva care vor fi folosite. Au participat la concursul intern o gramada de nume cunoscute dintre topcoderii cunoscuti ce lucreaza la Google. Asa ca nu am nici un dubiu ca problemele din concurs vor fi deosebite si interesante.
Mars si-a folosit parte din timpul lui de 20% de la Google pentru a ajuta la partea de infrastructura a proiectului si la evaluarea calitatii problemelor, daca nu va place ceva el e de vina :), sau daca va intereseaza Google App Engine tot pe el il puteti lua la intrebari. Proiectul e foarte misto ca realizare si din prisma oamenilor care au lucrat la el, nu va pot spune mai multe nume, dar e un fel de "who's who" a concursurilor de programare din ultimii ani.

Sper sa participati si sa va vad in toamna pe cat mai multi dintre voi la finala din Mountain View!

Nu am mai scris de ceva vreme si ca sa nu va plictisiti in lipsa de un post mai destept va sugerez niste articole interesante:

PayPal mafia Un articol despre fondatorii si cei ce au lucrat la PayPal. Multi dintre ei au plecat si au creat la randul lor cateva firme software de succes cum ar fi Slide, Yelp, Digg sau YouTube. E interesant ca nu se aud succese asa rasunatoare de la oameni plecati din Google. Deocamdata ar fi doar FriendFeed care e pe un trend ascendent, iar Twitter e facut de cei ce au facut Blogger, dar pe acestia nu ii putem considera de la Google pentru ca Blogger a fost o achizitie.

Google spotlights data center inner workings Jeff Dean, care e un super inginer de la Google, explica modul de functionare a unui data center de la noi. E destul de interesant articolul, mai ales in contextul postului lui Vivi despre scalabilitate 50 de servere vs. 10.000 .

Introduction to Google Search Quality? In acest articol Udi Manber, care e seful pe Search Quality la Google, explica putin din procesul de imbunatatire a algoritmilor de cautare. Poate numele Udi Manber va e cunoscut pentru ca e autorul paperului Suffix Arrays: A new method for on-line string searches

Pe curand!

Problema curenta a fost rezolvata de urmatorii Alexandru Mosoi, Bogdan Dumitru, Mihai Patrascu, Mihai Stroe, Delia David, Dumitru Ciubatii, Teodorescu Andrei-Marius, Dobrota Valentin Eugen, Ghitulete Razvan, Savin Tiberiu, Nicolae Titus, Adrian Vladu, Catalin Tiseanu. Oare a fost problema simpla sau se apropie vacanta?

Problema suna asa:

Sa se determine produsul maxim a unor numere reale pozitive a caror suma e 100.

Am primit si cateva solutii care presupuneau ca numerele sunt intregi sau in care se considera ca am cerut produsul maxim pentru exact doua numere. Mie textul mi s-a parut destul de clar si se pare ca a fost la fel de clar pentru majoritatea celor ce mi-au trimis solutia buna.

Aveti aici solutia lui Mihai Patrascu:

1. Arati convexitate: daca a+b=S, max(a*b) = S²/4. Deci daca doua numere sunt inegale, le faci egale pastrand suma si marind produsul. Deci ca sa optimizezi pt k numere, optimul e (100/k)^k

2. Ca sa optimizezi dupa k, iei logaritm: k(ln 100 - ln k). Derivata e: ln 100 - ln k - k*(1/k) = ln(100/e) - ln k. Vedem ca functie e creascatoare pana la k=100/e si descrescatoare dupa. Deci optimul e k = floor(100/e) sau k=ceil(100/e).

3. Folosind Google :)
(100 / 36)³⁶ = 9.39961298 * 10¹⁵
(100 / 37)³⁷ = 9.47406172 * 10¹⁵

Ajuta Firefox sa stabileasca un record mondial Guiness pentru cel mai downloadat pachet software in 24h.

In timpul facultatii aveam colegi care se intrebau daca diverse certificari, cum ar fi cele date de Microsoft sau Sun, sunt utile intr-un CV. Eu nu am crezut niciodata ca ar fi bune sau folositoare. Mi s-au parut o modalitate relativ simpla de a mai scrie o linie in CV daca el e cam gol.

Acum sunt si mai convins de inutilitatea lor, nu conteaza deloc ca apare o certificare sau alta, sau chiar zece certificari in CV. Este mult mai importanta experienta ta, proiectele misto la care ai lucrat decat faptul ca ai studiat cateva zile pentru un examen grila unde inveti diverse detalii exoterice ale limbajului sau tehnologiei in care te certifici. Cand te angajezi undeva esti testat de obicei destul de bine pe partea tehnica si sunt si alte chestii importante cum ar fi abilitatile de comunicare, faptul ca ai sau nu o certificare va fi probabil ultimul lucru la care se va uita cineva.

La Google s-a incercat mai demult abordarea stiintifica a problemei angajarii de personal. Un experiment a fost testarea daca vreun termen sau succesiune de termeni ce apare in CV cum ar fi "programming contest" se coreleaza cu decizia de angajare sau neangajare a cuiva. S-a gasit un singur astfel de termen, acesta era "certified". Iar termenul se corela negativ.

Certificarile nici macar nu sunt greu de obtinut. Ar fi si absurd deoarece companiile ce le ofera vor sa faca bani din asta si vor sa aiba cat mai multi oameni ce le dau. Deci sunt direct interesate ca testele sa nu para usoare (astfel testele dureaza cateva ore si au zeci sau sute de intrebari), dar totusi majoritatea celor ce au depus putin efort sa le treaca cu brio.

Stiu ca la certificarile java 90% din intrebarile de la testele reale le gasesti in teste de pe net. Astfel invatarea pentru examen se trasforma pentru unii in memorarea intrebarilor mai dure pentru a nu le gresi in testul real. Aparitia marii majoritati a intrebarilor din testul grila real in testele de pregature de pe internet nu este ceva normal daca vrei ca rezultatul la acest test sa garanteze un nivel tehnic bun celor l-au trecut. Dar garantarea nivelului tehnic nu este prima prioritate a testului.

Si totusi aceste teste pot fi utile. Incepatorii in un anumit limbaj pot folosi un asemenea test pentru a isi face o imagine mai in detaliu despre limbajul care il studiaza. Dar cred ca sunt si alte tehnici mai bune sa inveti un limbaj nou. De exemplu poti incerca sa faci un mic proiect in acel limbaj, si pe langa ca inveti limbajul ramai si cu ceva util pe urma acestui efort. Din cauza ca certificarile sunt utile doar incepatorilor, cand vad ca un CV are trecut ca lucru important o certificare, imi ridic un semn de intrebare.

Sa se determine produsul maxim a unor numere reale pozitive a caror suma e 100.

Trimiteti-mi solutiile pe privat sau pe cosminn at gmail.com

Imi face placere sa va anunt aparitia la editura ALL a carti "C++, Introducere in Standard Template Library" a carui autor este domnul profesor Constantin Galatan de la Colegiul National "Liviu Rebreanu" din Bistrita. Il cunosc inca de pe vremea liceului pe domnul Galatan care e un profesor de informatica profesionist si dedicat. Mi-as dori ca toti profesorii de informatica din tara sa puna atata suflet in meseria lor. El a fost organizator a partii de informatica a concursului interjudetean "Grigore Moisil" in 2006, a fost in comisiile stiintifice la ONI 2006, ONI 2007, iar in 2008 la ONI fost seful comisiei stiintifice la clasa a 9-a, a facut de asemenea parte din comisie la loturile din 2007 si va face parte din comisia loturilor din 2008, a facut parte din echipa .campion in 2006, 2007 si 2008. De asemenea inaintea cartii pe care v-am anuntat-o, a mai publicat cartea Secrete C++ Va las mai departe cu cateva cuvinte din partea domnului profesor:

La sugestia lui Cristian George Strat de a informa membrii infoarena despre aparitia unei carti de STL, m-am decis in cele din urma sa scriu cateva cuvinte, legate nu doar de STL.

Cred ca nu voi surprinde pe nimeni daca afirm ca ceea ce se petrece pe infoarena se urmareste cu mult interes, nu numai de catre elevi si studenti, ci si de catre alti oameni, printre care multi profesori. Acestia din urma nu activeaza pe forum, insa nu din cauza lipsei de interes. Este mai degraba intelegerea faptului ca pe infoarena elevii si studentii trebuie sa se simta in largul lor, sa discute liber. Desi s-ar putea ca unii sa ma contrazica, eu cred ca in momentul in care un profesor intervine pe un fir de discutie, exista probabilitatea ca o anumita stanjeneala sa se faca simtita.

Infoarena este acum un fenomen care-si manifesta influenta pozitiva asupra celor care studiaza informatica. Ca unul dintre cei care lucreaza efectiv cu elevi ai claselor de mate-info, simt ajutorul tot mai puternic al infoarenei. Nu de la bun inceput l-am simtit. Pana anul trecut, trebuie sa spun ca imi convingeam cu greutate elevii sa intre pe infoarena ca sa participe de pilda, la concursuri. Cineva chiar mi-a spus odata: "domunule profesor, ce rost mai are sa intru pentru 0 sau 10 puncte ?. Sunt prea grele problemele". Am fost nevoit sa admit acest lucru. Chiar pentru copiii cu performante onorabile: calificari la nationale sau mentiuni la ONI, problemele de pe infoarena au fost de multe ori prea dificile. Desigur ca nivelul ridicat de dificultate a contribuit mult la formarea elitelor, a celor super pregatiti, dar hai sa vedem cati elevi super pregatiti avem in tara? Treizeci ? Patruzeci ?

Exista o categorie de elevi la sectiile de mate-info, sa-i spunem prin abuz de limbaj "patura mijlocie", formata din persoane cu multe calitati. Numarul lor este de ordinul sutelor, poate chiar a miilor in aceasta tara. Acesti copii merita tot efortul nostru. Din randurile lor se pot ivi adevarati olimpici iar in viitor, informaticieni valorosi. Au insa nevoie de o mana de ajutor ferma care sa-i sustina si sa-i ridice in stratosfera performantei.

Ultimele initiative ale infoarenei: "Arhiva Educationala", accesul liber la sursele unor probleme, sectiuni de concurs pentru cei mici, si evident forumul, sunt veriga lipsa, legatura dintre infoarena si multimea de elevi.

Cand intru acum in laborator si gasesc cinci, pana la cincisprezece copii care isi cauta ceva de facut pe infoarena, realizez ca cineva mi-a intins si mie o mana in munca cu acesti elevi.

In final, revin la cartea de STL, "C++. Introducere in Standard Template Library" pe care am publicat-o la editura ALL. Lucrarea poate fi utilizata atat ca tutorial cat si ca referinta completa STL. Este de folos celor care utilizeaza deja STL dar vor sa se perfectioneze, dar si incepatorilor. Contine si un capitol special de lucru cu sabloane in C++. Informatii suplimentare gasiti aici

Tucu Galatan