[es] - Hard Core programing

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.dial.InfoSky.Net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Hard Core programing

^{04.11.2002. u 16:39 - pre 261 meseci}

Evo mene, kako sam i obećao, sa rešenjem.
U istom kodu je običan primer koji radi, ali veoma sporo, i jednostavna optimizacija koja se pokazala kao vrlo uspešna za dati problem: samo se pamte vrednosti F(i) u nizu, i ukoliko su već izračunate, ne računaju se ponovo. Zbog osobina izabranog algoritma, broj poziva F(i) je eksponencijalan (čini mi se 3^n), ali na ovaj način se smanjuje na polinomijalan broj.

Program je sledeći (zagrade.c):

Code:

#include <stdio.h>

#ifdef BRZO
#define vrati(x) { niz[n]=x; return x; }
#else
#define vrati(x) return x
#endif

typedef long long BROJ;

BROJ *niz;

BROJ F(int n) {
  BROJ br,i;
#ifdef BRZO
  if (niz[n]) return (niz[n]);
#endif
  if ((n==0) || (n==1)) vrati(1);

  br=F(n-1);
  for (i=1;i<n;i++)
    br+= ((F(i-1))*F(n-i));

  vrati(br);
}

int main(void) {
  int i;
  scanf("%d",&i);
#ifdef BRZO
  niz=(BROJ *)calloc(i+1,sizeof(BROJ));
#endif
  printf("%d: %lld\n",i,F(i));
  return 0;
}

Varijanta Zagrade.c je

Code:

#define BRZO
#include "zagrade.c"

Razlika u brzini se jasno vidi:

Code:

ponedeljak u 16:27 : danilo@avet : ~/rad/razvoj > time echo 20 | ./zagrade
20: 6564120420

real    2m2.100s
user    2m2.080s
sys     0m0.010s

ponedeljak u 16:29 : danilo@avet : ~/rad/razvoj > time echo 20 | ./Zagrade
20: 6564120420

real    0m0.024s
user    0m0.000s
sys     0m0.010s
ponedeljak u 16:29 : danilo@avet : ~/rad/razvoj >

E, problem je što broj mogućnosti prevazilazi opseg int64-a već na 36, a ,,brzi'' program kvadratno usporava, i tada i dalje ima neprimetno vreme izvršavanja. Nadam se da se slažete da je O(n^2) prilično dobar rezultat za ovakav program (nisam dokazao, ali rast utrošenog CPU vremena mi ukazuje na to, a ne rešavaju mi se rekurentne jednačine :).

I primetite da ovaj program vraća pogrešnu vrednost za nula zagrada, ali to se lako proveri posebno (vraća 1, umesto 0). Razlog za to provalite sami :)

Nadam se da će neko uraditi bolje! (npr. bez upotrebe O(n) memorije, a ista složenost; ili manja složenost).

Toliko

PS. Nadam se da je program ispravan :)

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.tehnicom.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com

+75 Profil

Re: Hard Core programing

^{05.11.2002. u 11:18 - pre 261 meseci}

Citat:

Reljam:
[Sve ovo jeste tacno, ali je uglavnom vise nebitno. MSVC automatski generise upravo ovakav kod kada se ukljuce optimizacije. Znaci delenje u petlji biva zamenjeno mnozenje sa reciprocnim brojem, 2*n biva zamenjeno sa n<<1, itd. Pogledajte disassembly neke matematicke operacije kada se program iskompajlira sa optimizacijama (obicno release profile), i iznenadicete se sta sve MSVC kompajler radi. Zakljucak: lepo je znati te stvari, ali gledajte da ih ne primenjujete u kodu jer cete uglavnom da pokvarite citljivost koda zarad necega sto bi kompajler ionako sam uradio.

Pa ukoliko gledas da pises program nezavisno od kompajlera pitanje sta svaki kompajler radi na polju optimizacija, ne kazem da ta oblast nije napredovala, ali neke stvari kompajleri josh uvek ne mogu da "vide" ovo sa racunanjima kvadrata je bilo dato samo kao primer pitanje je da li takve neke konstrukcije kompajler zna da izvuce, ali recimo ne mora se ici do optimizacija na krajnjem nivou da se pise siftovanje, ali opet ljudi za sta postoje komentari, po meni dobar kod je onaj koji na svake dve tri linije bude lepo iskomentarisan da se zna sta program gde radi. Evo vam primer pogledajte an sta mislim pod time komentari kako i koliko
http://www.matf.bg.ac.yu/r3nm/vjezbe/libnumerics.tar.gz

Tada i sve moguce vratolomije koje pisem mogu lepo u svakoj liniji da iskomentarisem, mozda ce neko reci da pisem komentare izmedju koda. Ali rezultat je kod dobro optimizovan i olaksan kompajleru, a sa druge strane razaumljiv.

http://speedy-order.com

Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.tehnicom.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com

+75 Profil

Re: Hard Core programing

^{05.11.2002. u 11:24 - pre 261 meseci}

Citat:

silverglider:
Hm, slazem se sa Tatkom :D Pokusavanje ovakvog optimizovanje ne moze da se generalizuje na sve profile programera (i samim time, velicati ga kao "jedini, pravi, istinski, hard-core, itd" programming). Mozda je vazno nekome ko radi na kompajleru, low-level biblioteci i slicno, ali ne i ostalima. Kada i hocu da nacrtam nesto, uzecu i koristiti taj moveTo i lineTo sasvim spokojno, jer je armija programera vec pretresla podlogu i njihovu optimizaciju kroz niz godina i ne pada mi na pamet da smisljam rupu na saksiji. Uostalom, zato od pocetka i postoji koncept biblioteka - ko ce sve da pise od pocetka ? Slazem se posebno i sa delom oko citljivosti koda - kada se radi u timu (uz podrazumevanu fluktuaciju programera), to moze biti zlata vredno.

Da ako planiras da budes programer gotovan i planiras da koristis samo gotove stvari tako reci slazes kockice od drugih programera to je ok onda ,ali ako budes nekada razvijao nove tehnologije i biblioteke koje ce koristiti drugi progrtameri onda se zna sta je prioritet.

http://speedy-order.com

Odgovor na temu

aster

Član broj: 1565
Poruke: 197
*.ptt.yu

Profil

Re: Hard Core programing

^{05.11.2002. u 12:11 - pre 261 meseci}

Ako sa 4 para zagrada postoji 14 kombinacija koje su to jos 3 kombinacije od ovih:

1. () () () ()
2. ( () ) () ()
3. ( () () ) ()
4. ( () () () )
5. () ( () () )
6. () () ( () )
7. ( ( ( () ) ) )
8. ( ( () ) ) ()
9. () ( ( () ) )
10. ( () ) ( () )
11. () ( () ) ()

osim ako se ne ukjlucuju i
))))((((
i njegove varijacije gde one ne zatvaraju zagrade, ali mislim da to nije u opisu zadatka?

Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.tehnicom.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com

+75 Profil

Re: Hard Core programing

^{05.11.2002. u 13:03 - pre 261 meseci}

Citat:

tOwk:
Evo mene, kako sam i obećao, sa rešenjem.
U istom kodu je običan primer koji radi, ali veoma sporo, i jednostavna optimizacija koja se pokazala kao vrlo uspešna za dati problem: samo se pamte vrednosti F(i) u nizu, i ukoliko su već izračunate, ne računaju se ponovo. Zbog osobina izabranog algoritma, broj poziva F(i) je eksponencijalan (čini mi se 3^n), ali na ovaj način se smanjuje na polinomijalan broj.

Program je sledeći (zagrade.c):

Varijanta Zagrade.c je

Code:

#define BRZO
#include "zagrade.c"

Razlika u brzini se jasno vidi:

Mislim da je to maksimum sa programerske strane, koji moze da se dobije, primenom grube sile, peca je dobro osetio jadac ;)), pravo resenje dolazi uz matematiku naime radi se o Katalanovim brojevima

E sada moze mala optimizacija tog izraza da se uradi u samom programu, ali nadam se da ce ljudi shvatiti i videti razliku u brzini oba izracunavanja, narocito kada trebaju da se racunaju vrednosti preko 20 :))), ali opet mi je drago sto je barem neko pokusao :)))

Ventura je ipak izvalio da jeste neka kombinatorika u pitanju ;))

[Ovu poruku je menjao Dejan Lozanovic dana 05.11.2002. u 15:12 GMT]

http://speedy-order.com

Odgovor na temu

silverglider

Član broj: 651
Poruke: 218
*.batalpha.de

Sajt: www.benchmark.co.yu

Profil

Re: Hard Core programing

^{05.11.2002. u 13:07 - pre 261 meseci}

Citat:

Dejan Lozanovic:
Da ako planiras da budes programer gotovan i planiras da koristis samo gotove stvari tako reci slazes kockice od drugih programera to je ok onda ,ali ako budes nekada razvijao nove tehnologije i biblioteke koje ce koristiti drugi progrtameri onda se zna sta je prioritet.

Dejane, hvala na komplimentu. Mislio sam da smo se malcice bili razumeli nakon prvog 'nesporazuma', ali ocigledno da nismo. Dacu kratak primer radi ilustracije; recimo da pises neki program za komunikaciju (ovo je proizvoljan primer). Potrudicu se da dobro razradim protokol, enkripciju, portovanje medju OSovima, solidan GUI i slicne stvari. Medjutim, uz sam taj 'core', program treba da ima niz 'dodataka' - recimo da imam neki addressbook u tom programu i da mi treba format za export/import tako necega; odlucim se da bude XML baziran, recimo. Situacija je sledeca: rok je bio relativno kratak - deadline ti dise za vratom, placaju se fini penali za kasnjenje - da li ces za tako nesto **sta nije kljucno** uzeti gotovu, proverenu XML komponentu za $50 i utrositi dobijeno vreme na testiranje i sredjivanje paketa, ili ces se kockati sa vremenom i odvojiti jednog programera da pise XML komponentu, s tim da njegov radni sat kosta $25 (verujem da ne moze da napise jednu ili vise komponenti tog tipa za dva sata, zajedno sa testiranjem i debuggingom) ?? Ja to ne shvatam kao 'gotovanstvo', a ni mnogo vece firme od moje, koliko mogu da vidim. Nadam se da je primer dobro ilustrovao ono na sta sam mislio celo vreme. Ako nije, onda j....

I tu je, sto se mene tice, kraj ovoj polemici - vratite se temi koju je covek postavio.

P.S.
Towk, stvar u redu, covek.

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.InfoSky.Net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Hard Core programing

^{06.11.2002. u 00:59 - pre 261 meseci}

Citat:

Dejan Lozanovic:
Mislim da je to maksimum sa programerske strane, koji moze da se dobije, primenom grube sile, peca je dobro osetio jadac ;)), pravo resenje dolazi uz matematiku naime radi se o Katalanovim brojevima

Zanimljivo. Retko kad naiđem na probleme ovog tipa (domaći, takmičenja) koji zaista mogu da se lepo izračunaju, pa i ne pomišljam da to pokušam.

Citat:

E sada moze mala optimizacija tog izraza da se uradi u samom programu, ali nadam se da ce ljudi shvatiti i videti razliku u brzini oba izracunavanja, narocito kada trebaju da se racunaju vrednosti preko 20 :))), ali opet mi je drago sto je barem neko pokusao :)))

Pa nisi potpuno u pravu. Ono vreme dato za moj primer za 20 je ,,user'' vreme: 0.000s, tj. manje od milisekunde. Zbog toga bi osetnije razlike mogle da se primete tek za možda vrednosti od nekoliko stotina na modernijim procesorima (naravno, na 286 bi to bilo mnogo pre; moj procesor PIII Celeron 700MHz je sada u nekoj srednjoj kategoriji, ako ne već i slabijoj).

Ni moj program nije baš toliko loš. Naime, kvadratna složenost u odnosu na linearnu i nije toliko loša za manje vrednosti. Pored toga, imam osećaj i da bi se program mogao srediti da radi u linearnoj složenosti ako bi se eliminisao ,,call overhead'', i koristile zapamćene vrednosti bez poziva funkcije (zato što se svaka nova vrednost dobija od prethodnih, a ta ubrzo biva zapamćena, i ne treba je ponovo tražiti). Uostalom, proveriću, pa ću i javiti.

Na primer, kod mene vreme od 1 sekunde dozvoljava rad sa približno vrednostima do 4000 (ali je tada problem što moj primer vraća

, umesto

, ali to je do izbora unutrašnjeg zapisa brojeva, i isti problem bi postojao i sa računanjem faktorijela na jednostavan način --- prosto, rezultat za n veće od 35 ne staje u opseg od 64 bita.

Toliko

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost

+5 Profil

Re: Hard Core programing

^{06.11.2002. u 02:59 - pre 261 meseci}

Citat:

Dejan Lozanovic:
ali opet ljudi za sta postoje komentari, po meni dobar kod je onaj koji na svake dve tri linije bude lepo iskomentarisan da se zna sta program gde radi. Evo vam primer pogledajte an sta mislim pod time komentari kako i koliko
http://www.matf.bg.ac.yu/r3nm/vjezbe/libnumerics.tar.gz

Tada i sve moguce vratolomije koje pisem mogu lepo u svakoj liniji da iskomentarisem, mozda ce neko reci da pisem komentare izmedju koda. Ali rezultat je kod dobro optimizovan i olaksan kompajleru, a sa druge strane razaumljiv.

(prvo da se ogradim da nisam gledao primer, ali komentarisem ono sto si ti opisao)

ma daj. pa ne treba ja da objasnjavam svaku (drugu, trecu) liniju koda. pa taj ko ce da cita moj kod ce da bude programer prilicno slicnog nivoa kao ja, ili bolji/gori programer od mene, ali svakako ne amater. jedan od velikih magova programiranja (ne secam se tacno, Wirth cini mi se) je jedared rekao da je najbolji komentar prazna linija u kodu.

i tu se poprilicno slazem. prazna linija u smislu da odvaja logicne celine i postupke u kodu.

dovoljno je recimo na pocetku svake metode napisati red-dva (tri) komentara o tome sta ta funkcija radi, koji su ulazni, koji izlazni parametri. i toliko. tek ako funkcija ne radi svoj posao, covek treba da ulazi u njene detalje.

drugo, imenovanje promenjivih. tu postoje dva stila. prvi je davanje_dugackih_i_opisnih_imena_promenjivima, a drugi je koriscenje a, b, c, x, y, i, j, k, sx, sy, ex, ey, etc. ovaj drugi podrazumeva kratak komentar pri deklaraciji promenjivih (sta cemu sluzi...)

i to je to. onda josh treba gledati da metode mogu da stanu na jedan ekran, (30-40 linija koda) jer je to neka zgodna merka zbog vise razloga. i dodati tome onaj prazan red svuda gde je to logicno, i to je to...

ovo sto ti opisujes je preterano. to se obicno radi u knjigama koje objasnjavaju neku tematiku, ili u kodu koji se koristi na predavanjima (to sto si ti naveo kao primer) ali u stvarnom zivotu, to je veci smor nego pomagalo.

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.191.EUnet.yu

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Hard Core programing

^{07.11.2002. u 02:58 - pre 261 meseci}

Treba da je to to. Može se naravno optimizovati tako da je zahtev za memorijom

a ne

, preciznije

ali to zaista ne mogu sada da radim, iskočio sam iz kreveta u 4 ujutro sa rešenjem.

f

Code:

/* Gets number of pairs of valid bracket expressions */
/* stdin -- number of pairs */
/* stdout -- number of valid bracket exps */
#include <stdio.h>
#include <stdlib.h>

#define geta(x,y) (*(a + cells*(x) + (y)))
int main(void)
{
    unsigned long *a;
    unsigned long pairs, cells;
    unsigned long i,j,k,m;

    scanf("%lu", &pairs);
    cells = 2 * pairs + 1;
    a = malloc((size_t) sizeof(unsigned long) * cells * cells);

    geta(0,0) = 1;
    geta(0,1) = 0;

    for(i=1; i < cells; i++) {
        for(j=0; j< i+1; j++) {
            m = (j == 0) ? 0 : geta(i-1,j-1);
            k = (j == i) ? 0 : geta(i-1,j+1);
            geta(i,j) = m+k;
        }
    }

    printf("%lu\n", geta( cells-1,0) );

    free( a);
    return 0;
}

Hm, jutro je izgleda pametnije od večeri...

Code:

/* Gets number of pairs of valid bracket expressions */
/* stdin -- number of pairs */
/* stdout -- number of valid bracket exps */
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned long *a, *b;
    long pairs, cells;
    long i,j;

    scanf("%ld\n", &pairs);
    cells = 2 * pairs + 1;
    b = calloc( cells + 2, sizeof(unsigned long));

    a = b + 1;
    a[0] = 1;

    i = 1;
    while(i < cells) {
        j = 0;
        while(j< i) {
            a[j] = a[j] + a[j+1];
            j++;
        }
        i++;
        while( j >= 0 ) {
            a[j] = a[j] + a[j-1];
            j--;
        }
        i++;
    }

    printf("%lu\n", a[0] );

    free( b);
    return 0;
}

, ali od toga ništa ne bi bilo da nije formule...

Code:

/* Gets number of pairs of valid bracket expressions */
/* stdin -- number of pairs */
/* stdout -- number of valid bracket exps */
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
        long p, n, pairs;
        unsigned long f;

    scanf("%ld\n", &pairs);

        p = -1;
        n = 1;
        f = 1;
        while ( n < pairs) {
               p+=2;
               n++;
               f *= 2 * p / n;
         }
    printf("%lu\n", f );
    free( b);
    return 0;
}

I, napokon, prljavi pokvareni udarac kog se neću usuditi da komentarišem jer radi samo na računarima sa beskonačno tačnom floating point aritmetikom.

Naime,

Ali je

što se može izračunati u konstantnom prostoru i linearnom vemenu. Zatim:

f

[Ovu poruku je menjao filmil dana 18.11.2002. u 20:42 GMT]

Odgovor na temu

Pera_Anarhista
Autonomija

Član broj: 3473
Poruke: 113
*.173.202.62.dial.bluewin.ch

Profil

Re: Hard Core programing

^{08.11.2002. u 12:16 - pre 261 meseci}

Hm, ja sam se zezao malo na casu i dosao da je resenje 2^(n-1)... ?! Moze biti da gresim, ali ako sam u pravu:

Code:

long kombinacije( int n ){
  long r = 1;
  r << n-1;
  return r;

}

Mada pretpostavljam da nisamo pogodio... :(

nema mira, nema pravde

http://www.anarchy-serbia.tk

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beotel.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Hard Core programing

^{08.11.2002. u 23:55 - pre 261 meseci}

Citat:

Pera_Anarhista:
....

Mada pretpostavljam da nisamo pogodio... :(

Dokaz da neko tvrđenje nije tačno je izvedeno ako ono nije tačno za jedan primer. Dati primer u prvoj poruci je za n=3, a rezultat je 5.

Pretpostavljam i ja da nisi pogodio :)

A komentar uz moj kod (pre formule): T(n^2), M(n)

Formulu dalje ne komentiram :)

Pozdrav

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu