Forumul organizatiei Pontes - www.pontes.ro

Probabil ca pentru testarea vitezei ar trebui utilizat acelasi algoritm de random pornind de la acelasi seed, acelasi cod etc.

In fine, nu prea conteaza, pana la urma sunt relative masuratorile, le facem si noi asa mai mult de dragul de a ne juca cu mici secvente de coduri paralele.

Ca sunt utilizate optimizari reiese si din faptul ca durata de executare a unei bucle care contine un algoritm nu pastreaza raportul egal cu numarul de iteratii. un miliard de repetari nu dureaza de o mie de ori mai mult decat un milion de repetari. Cel putin la exemplul de mai sus asa se intampla, si asa s-ar explica.
Astfel de teste poate sunt mai nimerite, daca raportul intre durata si numar repetari este egal, asta fiind in acelasi limbaj. Cu cat ar scadea timpul per iteratie la marirea numarului de repetari, limbajul ar fi mai optimizat pentru asa ceva.
O sa ma ocup sa vad de curiozitate comparand repetarea de un milion de ori fata de cea de un miliard de ori pentru un algoritm oarecare.

Se pare ca exista o predilectie pentru sirul Fibonacci, vara asta la examenul de admitere la Facultatea de Informatica din Cluj s-a dat ca prim subniect sa se creeze in orice limbaj un algoritm care sa determine valoarea de pe pozitia k intr-un sir Fibonacci, fara utilizarea tablourilor.

"Ca sunt utilizate optimizari reiese si din faptul ca durata de executare a unei bucle care contine un algoritm nu pastreaza raportul egal cu numarul de iteratii.".

Intr-adevar. Din asta reiese ca limbajul nu creaza programe in general mai rapide, ci doar atunci cand se intampla sa fie nevoie de repetarea unui numar mare de operatii similare care pot fi optimizate, dar daca ar trebui sa faca nu acelasi lucru de un miliard de ori, ci un miliard de lucruri diferite, atunci optimizarea nu ar mai functiona, iar limbajul ar fi evident muult mai lent decat C.

Dar de unde sti despre examenul de la facultatea de info? Vrei sa devi din nou student?

La ala m-am uitat de curiozitate.
S-ar putea insa sa devin si student, la Politehnica se fac cursuri pentru cei care au deja o facultate, doar doi ani si se recunoaste nivel licenta. Deci se poate obtine o a doua licenta.
Am vazut cursurile si examenele la altcineva care a facut in cei doi ani trecuti si... nimic deosebit, PHP si Java.
Anul trecut am vrut sa ma inscriu la Info la Babes, dar... dupa ce am platit taxa de inscriere si am dat dosarul frumos aranjat, mi s-a spus ca totusi nu se poate, nu aveam bac din matematica si unul dintre criteriile de departajare era si nota la matematica, cu conditia sa fie minim 5. Deci, cu toate ca as fi fost oricum la taxa, era acolo i imposibilitate de care si-au dat si ei seama. Au si schimbat intre timp, au bagat iar examen scris. Mi-au dat banii de inscriere inapoi, s-a putut anula chitanta.
Bine ca s-a ivit posibilitatea cu aceste cursuri, aici e programare aplicata, teoretic ceva mai bine decat Info unde e multa teorie, cel putin asa stiu eu. E si mai ieftin si ia mai putin timp. Desigur, totul daca nu intervine ceva neprevazut.
Stiu ca nivelul meu e inca departe de a fi foarte bun in ceea ce priveste programarea, si mai departe in ceea ce priveste teoria, dar... daca nu ai hartie, se pare ca nu te crede nimeni ca l-ai avea nici pe ala.
Ar fi si o multumire a mea sa am o licenta in domeniu.

IonPop scrie: Mai demult am discutat cu cineva despre viteza unor limbaje de programare si am facut niste teste cu generarea unui sir Fibonacci, ca o metoda clasica de testare.
In C a iesit foarte rapid, evident. In Java a iesit daca mai tin bine minte mai rapid decat in C. Am facut si un test in Perl dar a iesit extrem de lent.

Am facut si eu un test pe sirul Fibonacci in Java, C++ si BGT.
Ai avut dreptate, la asta Java e mai rapid se pare.

Practic am creat functia de determinare a valorii de pe pozitia k in sirul Fibonacci, unde k am spus sa fie 1000, iar cum acest calcul nu poate trece nici in BGT de o milisecunda, am pus sa repete calculul de 10000 de ori.
Am mers pe variabile double ca sa incapa mai mult, eu fiind pe un sistem de 32 de biti, mi-ar fi iesit valoarea pozitiei k=1000 din 2 la puterea 32.

Am considerat ca rezultat cea mai mica durata din cateva zeci de incercari:
Java - 32 ms.
C++ - 50 ms;
BGT 1500 ms;

Asadar, codul Java, care se potriveste in toate cele trei limbaje, sub forma metodei extrase din clasa ar fi:
Pentru rezultatele amintite, am chemat functia de mai sus de 10000 ori intr-o bucla, avand ca parametru 1000 si atribuind de fiecare data valoarea returnata unei variabile declarata anterior.

Probabil ca algoritmul de mai sus ar fi cel mai bun si pentru punctul 1 din examenul de admitere amintit.
Daca ar fi si alt algoritm mai elegant sau recomandabil dintr-un motiv sau altul, as fi curios.

"S-ar putea insa sa devin si student, la Politehnica se fac cursuri pentru cei care au deja o facultate, doar doi ani si se recunoaste nivel licenta. Deci se poate obtine o a doua licenta.".

Dupa cate am vazut eu, si in Romania e cam ca si prin alte tari europene sau SUA, adica doar un numar destul de redus de firme cer sa ai neaparat o diploma. In primul rand conteaza sa sti ce trebuie sa faci.
Evident, nu ma refer la marile firme de software ca Google, Microsoft sau altele de genul asta, fiindca acolo se inghesuie multi asa ca ei trebuie sa gaseasca tot felul de metode de departajare, si studiile ar putea fi unul dintre ele.

"Am vazut cursurile si examenele la altcineva care a facut in cei doi ani trecuti si... nimic deosebit, PHP si Java.".

Pai cam asta este motivul pentru care cred ca nu merita studiile oficiale in sistemul nostru falimentar de invatamant, fiindca poti invata foarte bine pe cont propriu. Dar ma rog, asta nu este general valabil, fiindca fiecare persoana isi are propriul stil de invatare. Unii prefera sa invete o gramada de teorie inainte de a o aplica in practica, altii prefera sa testeze ei in practica incontinuu, altii prefera sa invete din exemple practice facute de altii, altii prefera sa le spuna cineva pas cu pas ce trebuie sa faca, altii sa studieze pe cont propriu etc.

In SUA unele universitati chiar isi promoveaza stilul de invatare care este aplicat in cadrul lor, asa ca studentii pot alege universitatea si in functie de acest aspect.

"Bine ca s-a ivit posibilitatea cu aceste cursuri, aici e programare aplicata, teoretic ceva mai bine decat Info unde e multa teorie, cel putin asa stiu eu. E si mai ieftin si ia mai putin timp.".

Eu nu am absolvit nici facultatea de mate-info de la Babes si nici pe cea de calculatoare de la Politehnica, asa ca nu pot spune ca stiu in cunostinta de cauza, insa exact asa am auzit de la multe persoane care au studiat in ambele locuri.
Mi s-a povestit si despre genii in domeniul programarii de la Babes care au ramas repetenti fiindca nu si-au luat un examen la matematica unde ar fi trebuit sa cunoasca o gramada de teorie, am avut si colegi de camera de la Babes care erau in ultimul an dar eu invatasem mai multa programare decat ei pe cont propriu in cateva luni.

"Stiu ca nivelul meu e inca departe de a fi foarte bun in ceea ce priveste programarea, si mai departe in ceea ce priveste teoria, dar... daca nu ai hartie, se pare ca nu te crede nimeni ca l-ai avea nici pe ala.".

Eu nu pot dovedi cu hartii nici ca stiu sa utilizez programul Notepad.
E drept, nici nu am fost interesat sa pot dovedi asa ceva, fiindca intotdeauna am crezut ca o firma de specialisti in iT care nu poate evalua singura daca sti ce trebuie sa faci, ci trebuie sa se bazeze doar pe verificarile de proasta calitate facute in sistemul de invatamant, este o firma de calitate proasta, de la care te poti astepta si la alte lucruri neplacute.
Pentru nevazatori insa este drept ca nu mai este la fel, fiindca cum noi suntem discriminati la greu, este o mare bucurie cand reusesti totusi sa convingi o firma ca esti bun la ceva, fara sa conteze prin ce mijloace, fie ele si cu diplome de calitatea celor ECDL.

"Ar fi si o multumire a mea sa am o licenta in domeniu.".

Pentru mine nu a fost niciodata o multumire sa am vre-un fel de dovezi atestate de sistemul de invatamant de proasta calitate din Romania. Ar fi fost o multumire sa fi fost vorba despre o diploma acordata de Harvard, Yale, Stanford, MIT...
De ce sa fiu multumit ca un profesor de doi lei care poate in anumite domenii nu se pricepe la programare cat mine sa isi puna el stampila si sa aprecieze cat de bine ma pricep eu la domeniul iT.
(Fiindca in domeniul iT, spre deosebire de multe alte domenii, profesorii sunt in general cei care ori prefera povestile si teoria in detrimentul practicii, ori nu au fost suficienti de buni in domeniul practic pentru a isi gasi de lucru.)

In legatura cu functia fibonacci, eu doar am copiat exemplul din documentatia modulului Memoize si am vazut ca se foloseste o metoda recursiva. Nu stiu la ce sunt utilizate sirurile fibonacci si nici care este metoda teoretica de calcul, insa ce e clar este ca acea functie da un rezultat foarte diferit de metoda iterativa pe care ai pus-o mai jos.

Acel exemplu este intr-adevar mult mai elegant si mai simplu:

sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}

Am modificat functia pe care ai creat-o in Java si am testat-o si in Perl. Codul ei este:

sub fib {
my $k = shift;
my $x = 0; my $y = 1; my $z = 0;
for ( my $i = 1; $i <= $k; $i++ ) {
$z = $x;
$x = $y;
$y = $x + $z;
}
return $z;
}

Am adaugat si modulul Memoize in program astfel:

use Memoize;
memoize('fib');

Am rulat-o intr-un loop de 10000 de ori, iar cea mai buna viteza a fost de mai putin de 15 ms.
Ca sa testez mai bine fara sa rulez programul de zeci de ori, am creat o alta bucla pe care am executat-o de 1000 de ori, adica am facut 1000 de rulari ale programului, iar programul consta in rularea de 10000 de ori a functiei fib() cu parametrul 1000.
Dar oricum, de obicei nu se ia de buna cea mai scurta perioada de rulare, ci perioada care rezulta de cele mai multe ori, asa ca am pus vitezele intr-un hash si am sortat rezultatele, iar rezultatul arata ca de cele mai multe ori programul a terminat de rulat in mai putin de 31 ms.
Deci daca se foloseste modulul Memoize pentru optimizare in Perl, la fel cum Java face aceasta optimizare in mod implicit, programul in Perl ruleaza mai rapid decat cel in Java.

Am testat si viteza celeilalte functii fib() dar rezultatele au fost extrem de apropiate. Asta arata cat de putin important este acest test pentru determinarea vitezei unui limbaj, fiindca am vazut ca atunci cand nu se foloseste Memoize pentru optimizare, functia fib() recursiva este mult mai lenta decat functia fib() iterativa, dar cand programul este optimizat, ruleaza aproape la fel de repede.
Or un test de viteza nu ar trebui sa depinda de optimizarile facute implicit sau explicit, insa de fapt doar acele optimizari sunt cele care conteaza, fiindca altfel, daca un program in Perl ii da procesorului de lucru un milion de operatii, iar un alt program in Java ii da tot un milion de operatii, viteza de executie va fi evident la fel de mare, si atunci doar smecheriile care fac ca numarul de operatii necesare sa fie mai redus fac diferenta.

Diferenta cu adevarat nu consta in viteza de executie, fiindca rareori trebuie sa faci optimizari de viteza prin modificarea algoritmilor, asta daca nu lucrezi la proiecte foarte avansate, cum ar fi motoare de baze de date, motoare de cautare, driveri, dar atunci te intereseaza in primul rand viteza si atunci sigur alegi limbajul C sau chiar limbajul de asamblare si nu un limbaj de nivel inalt ca Java sau Perl.
Diferenta consta in usurinta de utilizare si resursele consumate. Daca vrei sa creezi un site web care sa ruleze pe un VPS cu 512 MB de memorie atunci nu prea iti vine sa alegi Java, chiar daca trebuie sa faci optimizari si ele trebuie facute manual, iar daca nu ai astfel de limitari atunci este posibil sa vrei sa nu iti mai bati capul macar cu optimizarile de baza pe care le face Java in mod implicit.

Iata rezultatele rularii programului de 1000 de ori:
0.0309999999999988 secunde de 231 ori
0.032 secunde de 211 ori
0.0310000000000006 secunde de 146 ori
0.0310000000000024 secunde de 86 ori
0.0309999999999997 secunde de 71 ori
0.016 secunde de 61 ori
0.0150000000000006 secunde de 52 ori
0.0310000000000001 secunde de 34 ori
0.0159999999999982 secunde de 29 ori
0.0160000000000018 secunde de 18 ori
0.031 secunde de 18 ori
0.0309999999999999 secunde de 17 ori
0.0149999999999997 secunde de 9 ori
0.0149999999999988 secunde de 8 ori
0.0150000000000001 secunde de 6 ori
0.0149999999999999 secunde de 2 ori
0.0319999999999999 secunde de 1 ori
0.015 secunde de 1 ori

Daca ai pomenit de metoda recursiva, m-am apucat sa mai fac un test si poate cu asta inchei masuratorile pentru o vreme, ca se pare ca o intind cam mult.

Am vrut sa vad daca o metoda recursiva e mai inceata decat una iterativa, pentru ridicarea la putere, de asemenea la care dintre cele doua metode se castiga timp cand e vorba de multe repetitii.

Asadar, am scris doua functii, una care ridica la putere in mod recursiv, alta iterativ.

S-a dovedit ca varianta recursiva e mai inceata decat cea iterativa, atat in C++, cat si in Java.
S-a mai dovedit ca din nou, Java e mai rapid cand e vorba de calcule repetate.

Durata pentru 2 ridicat de 100000 de ori la puterea 64:

Varianta recursiva:
Java - 25 ms,
C++ - 70 ms;

Varianta iterativa:
Java - 15 ms,
C++ - 35 ms;

Functiile native Math.pow(), respectiv pow():
Java - 35 ms,
C++ - 1 ms;
Aici devine treaba mai ciudata, se pare ca functia nativa din C++ are ceva ce se misca extrem de repede, probabil are procesorul posibilitatea de a face direct si calcul de putere, asa cum face adunare, inmultire etc.
Ce au ajuns procesoarele din ziua de azi, sa poata intr-o secunda ridica pe 2 la 64 de milioane de ori, asta in conditiile in care 2 la 64 pana nu foarte demult era un numar greu de patruns, vezi faza cu hartia impaturata in 64...


Pun mai jos si cele doua metode care returneaza ca double rezultatul ridicarii la putere a primului parametru la cel de-al doilea:
Nu ma pot abtine sa nu o iau si pe o latura didactica si sa spun ca cine patrunde functia recursiva de mai sus are o logica buna. Cea iterativa este de sigur foarte usor de urmarit.

Cum spuneam in topicul Procesare cuvinte din dictionar, teste, algoritmi, coduri, pun mai jos codul care sta la baza unui mic simulator de scriere T9 Dictionary.
Este o simpla interfata care afiseaza cele 12 taste ale unui bloc numeric de telefon.
Metoda TGui a singurei clase numita T9 creaza interfata cu valori absolute, dar in asa fel incat daca se schimba doar 3 valori totul sa fie redimensionat corespunzator.
Practic valori literale sunt doar pentru latimea, inaltimea butoanelor si distanta intre acestea. Modificand sa zicem latimea unui buton in codul sursa, automat se va schimba si latimea ferestrei mari JFrame in asa fel incat sa le incadreze respectand simetria.
Daca avem variabilele width pentru latime si spacing pentru distanta intre butoane, atunci latimea intregului JFrame ar fi logic 3 ori width, plus 4 ori spacing, asta pentru ca e nevoie de aceeasi distanta ca intre butoane si intre acestea si marginea ferestrei parinte.
A mai fost insa nevoie de o mica ajustare, un plus la latimea JFrame-ului pentru ca desi butonul este definit sa zicem de 100 de pixeli, tot mai ocupa putin in plus, atunci am pus sa fie inca plus un spacing si jumatate.

T9Simulator.zip este o arhiva care contine fisierul sursa T9.java, fisierul compilat T9.class si fisierul Romanian.txt care contine cuvintele limbii romane.

T9.txt este un fisier cu codul sursa vizibil instant, format text.

T9Simulator.jar este un pachet standalone care ruleaza pe cele trei sisteme de operare fara sa mai fie necesar altceva, decat executarea cu un enter sau dublu click.
Desigur ca e nevoie de Java instalat, mai ales pe Windows unde nu vine implicit. Pentru utilizatorii de JAWS mai e nevoie si de activarea Java Access Bridge, a se vedea al doilea mesaj al acestui topic pentru instructiuni in acest sens.

In caz ca cineva vrea sa invete Java, sursa de mai sus poate fi utila, cel putin mie mi-ar fi prins bine pentru ca e putin cod si sunt suficiente comentarii pentru intelegere si orientare.

Am verificat si eu pe mac. Totul functioneaza in regula inclusiv scurtaturile de taste.

Da, si din cate am inteles, etichetele (label) sunt citite cu cursorul standard; Voice Over se misca peste tot intr-o interfata, ajunge pe orice element GUI, chiar daca nu se poate interactiona la propriu cu el.
Asta e foarte bine, la Windows pot citi cele doua etichete doar cu JAWS Cursor, asta pentru ca nu am gasit inca o solutie sa se opreasca cursorul PC si pe labels. Cu windows API exista posibilitatea activari TAB_STOP, adica apasand tasta Tab sa se opreasca si acolo cursorul.
Daca stam sa ne gandim, logic ar fi sa nu aiba de-a face cursorul implicit cu un label, este vorba doar de o informatie afisata, nu se interactioneaza cu elementul. Dar in cazul utilizatorilor de screen reader trebuie si un fel de interactiune: citirea etichetei.
E bine ca merg si mnemonic keys, am inteles ca tot cu Alt plus alte taste, deci ca la Windows, nu in stil specific Mac cu asa-zisa tasta Windows plus cele definite.
Ce e interesant ca in cazul Windows, pe butoanele grayed, unavailable sau estompate (vorba Voice Over-ului) ajunge si cursorul implicit, nu sunt ignorate ca in cazul unei interfete create cu Windows API.

Astfel putem vedea in timp ce si cum, cum trebuie alese mai bine solutiile pentru a fi o cale de mijloc, incat sa fie in regula si pentru utilizatorii de Windows si pentru cei de Mac.