Optimizing QuickSort and staff

Frunzaream recent revista celor de la codexpert.ro. Cum ce revista? Pai si-au lansat revista! E scrisa de un bot. In fine!

Evenimentul lansarii a fost unul sters, ca sa nu mai zic de lipsa totala a fundamentului ideologic. Dat fiind ca sintem familiari cu curentul codexpertian, ne-am zis sa incropim noi doua trei rinduri despre necesitatea si misiunea acestui ziar in lume, si nu numai. Asadar:

Pentru noi, cei care am supravietuit prigoanei, raspunderea pentru idealurile miscarii codexpertiste este atit de mare incit de multe ori simtim ca este o povara care ne copleseste si, daca n-ar fi legatura tainica cu C++-ul, poate demult s-ar fi stins nadejdea in sufletele noastre.

Profesorii Ardelean, Cucu si Bancila ne-au invatat sa gindim. Dupa cum Capitanul Bjarne a despartit hotarele lumii vechi de lumea noua, cei trei au despartit lumea formelor sterpe de lumea cugetarii realiste.

Dar cugetatorii si-au sacrificat darul mintii pentru adincul omenesc.

De cind au luat la cunostinta de C++, limbaj atit de apropiat de conceptia lor de viata, nu s-au putut desparti de drumul lui. Si si-au inceput viata intr-o apoteoza de neinchipuita frumusete morala. Ziarul trebuie sa pastreze nealterat spiritul miscarii si sa-l exprime in linia de cugetare a celor trei.

Un ziar de lupta si de idei, dar fara verbalism si entuziasm usor!
Fiecare cuvint trebuie sa se nasca din adincurile sufletului si sa fie insotit de intreaga raspundere a celui care il scrie.

“Ziarul Codexpert” este o batalie si pornim la ea cu aceeasi incredere in Victorie!

Acum ca avem si sprijinul ideologic, putem porni la drum sa ne scaldam printre titlurile care ne sint supuse atentiei in ziar.

Gasim o optimizare de quicksort. Gasim la autor si justificarea ideologica pentru batutul din taste:

“The idea for doing this is that instead of each new recursion copying the same code and using up more memory, it reuses the same code.”

Deja vu. Zbucium. Silviu Ardelean nu este un om, este o modalitate de a vedea lumea.

Ridicam bezmetici capul si privim codul in ochi. 10 numere sint torturate si fortate sa se alinieze de la mic la mare, in numele unei noi ideologii optime, acest pleonasm minier. Luam codul si-l virim sub nas, linie cu linie. Tragem incet si simtim cum ne ia cu ameteala. Trebuie sa gasim o modalitate de a salva numerele din mina ideologiei mirsave! Pregatim siringa pe care sta scris Array.sort() si batem incet vena. Milioane de numere ne trec prin fata ochilor. Eminescu. Truda. Pierdem vena. Intepam de 10 ori si ne intindem pe spate cu ochii tintiti la tavan. Senzatia de timp dispare. Ceasul numara de la kilometrul zero, over and over:

Optimized QuickSort: 00:00:01.2692034
Array sort: 00:00:01.1664805
Optimized QuickSort: 00:00:01.2490031
Array sort: 00:00:01.1632019
Optimized QuickSort: 00:00:01.2463744
Array sort: 00:00:01.1634480
Optimized QuickSort: 00:00:01.2695249
Array sort: 00:00:01.1568251
Optimized QuickSort: 00:00:01.2440373
Array sort: 00:00:01.2517662
Optimized QuickSort: 00:00:01.2694608
Array sort: 00:00:01.1581570
Optimized QuickSort: 00:00:01.2646042
Array sort: 00:00:01.1657108
Optimized QuickSort: 00:00:01.2499172
Array sort: 00:00:01.1557011
Optimized QuickSort: 00:00:01.2406120
Array sort: 00:00:01.1544470
Optimized QuickSort: 00:00:01.2434693
Array sort: 00:00:01.1576033

Tags: , , , , , , , , , , , , , ,

12 Responses to “Optimizing QuickSort and staff”

  1. thefatredguy Says:

    “each new recursion copying the same code and using up more memory, it reuses the same code.” – Say what ???? Cum adica se copiaza codul ??? Si vad ca l-a optimizat bine de tot, asa de bine incat merge chiar mai prost :) .

  2. thefatredguy Says:

    Apropo, cate elemente avea array-ul pe care s-a facut testul ?

  3. jos8cal Says:

    Codul lui era pe 10 numere si evident nu era niciun test. Al meu pe 10000000 dupa cum se vede in ce am dat paste.

  4. thefatredguy Says:

    Acum am vazut, eu nu ma uitasem decat la codul lui nenea ala. BTW ziarul are 3 abonati. Oare cine or fi ? :)

  5. Cormen Says:

    Am ras cu lacrimi.
    Excelenta tehnica de optimizare.

  6. Aram Hăvărneanu Says:

    Incredibil, deci cercopitecu ăsta crede că un stack frame conține codul funcției în sine? :D. Incredibil. Se pare că cercopitecul nu știe deloc ce-i aia stivă.

  7. thefatredguy Says:

    S-a lansat standupprogramming.ro :) .

  8. Expert Codat Says:

    Eu cred ca de fapt voi doi, si chiar si voi ceilalti care comentati articolele, muriti de ciuda ca omul are asa un interes in algoritmii de sortare si o intelegere atat de buna a QuickSortului. Ba mai mult, a dat dovada de o dedicatie extraordinara, ajungand sa capete o imagine atat de profunda asupra recursivitatii cum muritorii de rand nu pot spera vreodata nici asupra propriilor buzunare. Dincolo de formalitatile unor notatii matematice, care nu pot arata simultan ambele fete ale monezii (chiar si banda lui Möbius iti arata o singura fata la un moment dat, dar o formalizare de tipul A(i)=A(i-1)+A(i-2) seamana mai mult cu luna, aceeasi fata mereu! Recunoasteti!). Omul traieste acea recursivitate, nu pe stiva se copiaza codul ci chiar pe sufletul lui! Normal ca a optimizat la sange, ca sa nu il oboseasca atatea copieri care de fapt sunt in van, cum v-a si demonstrat.

    P.S. Ati reusit deja sa invatati limbajul ingineresc X3D?

  9. Mihnea Says:

    Recunoastem ca ciuda este seva acestui blog. Cum il vedem pe unul ca atinge un nivel superior al intelegerii in vreun domeniu, ne umplem de pizma. Acest lucru a fost deja dat in vileag de catre Silviu cind ne-a zis ca sintem frustrati si ca psihologii au determinat ca nu-i bine sa fii f(r)ustrat pe interior.

    N-am reusit inca sa invatam X3D pentru ca tov. prof. ing. Boata Cristian (muie Boata) nu mai vrea sa ne raspunda la telefon de cind am facut misto de trenuletele lui BlaxxunRomania (tot din f(r)ustrare, evident). Cum nu stim nici un alt inginer care sa ne poata transmite inginerie pe cale orala, o sa raminem neingineri.

    PS: standupprogramming.ro s-a “lansat” mai demult, dar din pacate nu-i nimic amuzant acolo. Speram sa fie o tribuna de la care expertii sa ne dea replici usturatoare, dar n-a fost sa fie.

  10. DarkByte Says:

    Domeniul .ro cred ca e pentru derutare. X aude de la Y de standupprogramming … uita de .com, intra pe .ro … nu gaseste decat articole (mai mult) tehnice (sau mai putin) si linkuri catre forumuri . Uite-asa, isi cresc traficul si rade mai putina lume de greselile lor.

    Cui i-e dor de Blaxxun ? Mie mi-a fost de ajuns… iar absenta ing. Boata (muie Boata (c)) nu ma deranjeaza :)

  11. thefatredguy Says:

    Blaxxun era simpatic cu transputerele lui. Omul avea capacitatea de a scoate un numar impresionat de aberatii per pixel patrat.

  12. thefatredguy Says:

    Erata : la postul anterior in loc de impresionat se va citi impresionant.

Leave a Reply

Optionally add an image (JPEG only)