[es] - Hash funkcija-losa improviyacija- pomoc

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Hash funkcija-losa improviyacija- pomoc

^{28.04.2013. u 15:44 - pre 133 meseci}

Napravio sam u DELPHI-ju neki kompajler.

Postoje deklarisana imena (konstante, tipovi, varijable..) koja se nalaze u zapisu koji sadrzi pomenuto ime i niz drugih podataka koji definišu samo ime (tip, adresa, skup mogućih vrednosti tipa i t. d.).

Imam niz od ovih zapisa i ona se puni u deklaracijonoj sekciji, a koristi tokom daljeg kompajliranja.

Podaci o nekom imenu se nalaze u više zapisa. Na primer: varijabla sadrži mesto u nizu zapisa gde je definisan tip, sam tip je. recimo, složen, pa se njegova definicija nalazi u jednom ili više zapisa u nizu zapisa. Imena može biti i par hiljada, pa je dugačko pretraživanje niza zapisa da bi se pokupili svi potrebni podaci. Sortiranje zapisa po imenu bi napravilo konfuziju jer se menja redni broj svakog zapisa, a on je osnova za pristup određenom zapisu.

Da bih ubrzao pretraživanje, uradio sam ovo: napravio sam tabelu od 256 dinamičkih niziva. U dinamičke nizove upisujem redni broj zapisa određenog imena. Od samog imena preko neke kvazi heš funkcije generišem vrednost tipa byte koja određuje u koji dinamički niz će biti upisan redni broj njenog zapisa u nizu zapisa.

Pristup je sada brži: kada nađem dinamički niz (preko kvazi heš funkcije) onda pretražujem samo njega. U idealnom slučaju dinamički niz treba da ima 256-ti deo ukupnog broja imena.

Međutim, to nije baš tako. Kvazi heš funkcija (zovem je tako jer sam je ja pisao) ne daje ravnomernu raspodelu. Nisam radio statističku obradu da bih prezentirao kakvu sam raspodelu dobio.

Ako me neko razume, i ako mu je ova problematika bliska, bio bih vrlo zahvalan ako me uputi na neku heš funkciju koja bi bila primenljiva za ovo što mi treba.

Pozdrav.

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{28.04.2013. u 18:44 - pre 133 meseci}

Da ne izmisljas toplu vodu, pogledaj JclStrHashMap unit iz JEDI biblioteke, dobar je i vrlo brz...
Takodje postoji i slična (sporija) Delphi klasa THashedStringList iz IniFiles unita.

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{29.04.2013. u 00:12 - pre 133 meseci}

Hvala probacu.
Naravno, uporedicu i sa onim sto sam ja napravio.

Odgovor na temu

salaczr

Član broj: 160654
Poruke: 103
*.dynamic.isp.telekom.rs.

+5 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{29.04.2013. u 09:21 - pre 133 meseci}

Obavezno probaj i TurboHashedStringList klasu iz uHashedStringList (http://www.delphigeist.com/2010_02_01_archive.html).
U vecini nasih projekata koristimo ovu klasu i veoma smo zadovoljni brzinom pretrage.

pozdrav

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
..ppoe.dyn.broadband.blic.net.

+62 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{29.04.2013. u 11:44 - pre 133 meseci}

Citat:

Sortiranje zapisa po imenu bi napravilo konfuziju jer se menja redni broj svakog zapisa, a on je osnova za pristup određenom zapisu.

U ovome je koska. Pod 'niz' pretpostavljam da mislis na staticki array, a pod 'zapis' na record. Kako bih ja to uradio:

1) definisi pointer na tvoj record, ovako nesto

Code:

type
  PMyRec = ^TMyRec;
  TMYRec = record
     // neki podaci o vezanim/zavisnim recordima
    SubRec: PMyRec;
  end;

2) umesto niza, koristi listu i u nju ubacuj novokreirane recorde

Code:

var
  NewRec: PMyRec;
begin
  MyList := TList.Create; // ovo ne ide ovde, pojasnjavamo STA JE
  // dodajemo novi record
  new(NewRec);
  MyList.Add(NewRec); // ili Insert, kako god
end;

3) umesto rednih brojeva upisuj upravo pointere na recorde iz liste (mozes napraviti neke metode za to)

Code:

var
OldRec, NewRec: PMyRec; // takodje ne ide ovde, cisto da se zna sta je sta
begin
OldRec^.SubRec := NewRec; // umesto rednog broja stavljamo pointer
end;

Obrati paznju kako prilazis dinamicki kreiranom recordu iz liste - dereferenciranjem (OldRec^.)

Kod je malo nabacan, ali ideja je sledeca. Sa listom mozes da radis sta hoces, pointeri/elementi liste uvek zadrzavaju svoje vrednosti, sto ce reci da se ne gube veze koje si vec napravio. A to nije slucaj kad radis sa statickim nizom recorda i rednim brojevima recorda.

Ako ne volis da radis sa pointerima, onda umesto recorda koristi klase. Delphi automatski radi dereferenciranje objekta. Znaci ono pod 1) i 2) bi bilo nekako ovako

Code:

type
  TMyZapis = class
    // neki podaci o vezanim/zavisnim objektima
    SubZapis: TMyZapis;
  end;

// ----------------------------

var
  NewZapis: TMyZapis;
begin
  // dodajemo novi record
  NewZapis := TMyZapis.Create;
  MyList.Add(NewZapis); // ili Insert, kako god
end;

// ----------------------------
  OldZapis.SubZapis := NewZapis; // umesto rednog broja stavljamo objekat

U oba slucaja, moras da radis sam unistavanje zauzete memorije - bilo recorda (sa Dispose(AnyRec)) bilo objekata (sa AnyZapis.Free).

Uh... mozda te ovo malo zbuni, ako nisi pre radio dinamicki sa memorijom. Ali ovako nekako funkcionise citav Delphi, i nije tako slozeno kako se cini.

Pozz

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 01:02 - pre 133 meseci}

Problem je što sam pomenuti kompajler napisao odavno u TURBO PASCAL-u, pa sam ga pojavom DELPHI-ja prepravio jer sam imao na raspolaganju niz komponenata sa kojima sam dobio mnogo bolje razvojno okruženje. Samu funkciju kompajliranja sam malo menjao. Doduše stari je bio jednoprolazni, a ovaj troprolazni (radi izbacivanja imena koja se ne koriste) što nije velika izmena.

Zapise čuvam u nizu, doduše dinamičkom što ništa posebno ne znači. Kada kompajler naiđe na neko ime, on preko jedne funkcije (tu se petlja moja kvazi heš funkcija) dobija redno mesto zapisa, u nizu zapisa, sa tim imenom. Nadalje radi samo sa tim rednim brojem.

Nije problem da umesto sa rednim brojem radim sa pointerom, ali bi to izazvalo izmene na mnogo mesta i ponovno testiranje.

Dakle, radi se o kompajleru za jedan mikrokontroler. On pripada klasi asemblera, ali je napravljen kao PASCAL, jedino umesto PASCAL iskaza ima asemblerske iskaze. Sa njim sam napisao stotine hiljada redova programskih linija i duplo više bajtova izvršnog koda. Sada mi je posao stao, pa koristim pauzu od par meseci da uvedem i PASCAL iskaze. A, onda mi pade napamet da testiram moju heš funkciju, i eto pitanja.

Zahvalan sam i tebi i drugima na odgovorima, bili su jako korisni.

Sa dinamičkim varijablama sam radio, naročito u TURBO PASCAL-u koji je imao ograničenja u pogledu memorije.

Ono što mi nedostaje to je iskustvo sa objektnim programiranjem, ne da ga nisam koristio, razumem ga, ali da budem iskren nisam toliko iskusan da ga mogu iskoristiti kao olakšanje u programiranju.

Evo na primer: nemam ideju kako bi mi pomoglo objektno programiranje da smanjim posao oko implementacije PASCAL iskaza, a time i oko njegovog testiranja. A, imam osećaj da bi mi pomoglo, samo ne mogu da ga koncipiram.

Za sada sam napravio prevod iskaza dodele u binarno stablo, gde su u čvorovima matematički, logički ili relacioni operatori, kao i znak dodele. Kod iskaza se generiše na osnovu ovog stabla. Takođe sam napravio i nalaženje čvora od kojeg treba početi prevošenje u kod da bi se imao što manji broj međurezultata koji se moraju odlagati na stek.

Nastojim da se držim Referentne definicije PASCAL-a koju je napisao Nikolas Virt, ali imam nedoumica oko uvođenja i drugih celobrojnih tipova, ne sviđa mi se ono što je datu u kasnijim standardima raznih verzija PASCAL-a.

Iz ovoga što sam napisao vidi se da imam dosta pitanja i nedoumica - ali šta da radim, ako je neko slobodan da pomogne hvala mu.

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
..ppoe.dyn.broadband.blic.net.

+62 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 09:59 - pre 133 meseci}

Priznajem da mi sad nije najjasnije koji te problem muci... :)
Zasto sam ti pominjao listu i pointere? Prosto, lista se ponasa kao array, mozes je sortirati (recimo po imenima varijabli). Rekao si da je problem sto se tad gube originalni redni brojevi zapisa (itema liste). Da, ali kome trebaju redni brojevi, ako koristimo pointere? Kapiras, sortiranjem liste se vrednosti pointera NE menjaju; i dalje imas najbrzi moguci pristup trazenom zapisu. Ili ja i dalje ne razumem tacno sta te muci..?

Sto se tice OOP-a, pa evo ti plastican primer. Kazes da si ubacio tvoj kompajler/unit u vizuelnu Delphi aplikaciju (formu). Pretpostavljam da kompajler radi tako sto pozivas vidljive (interface section) funkcije iz tog unit-a. Sta ako se ukaze potreba u istoj aplikaciji da na DVA ili vise mesta treba da koristis kompajler? Verovatno bi imao problema, jer su u tvom unit-u sve varijable i funkcije globalne, odnosno deklarisane kao javne, ne kao members od klase. Ovo sad dotice dve tekovine OOP-a: scope/enkapsulaciju i portabilnost. Prvo znaci da ceo kompajler/unit zamotas u klasu - kod postaje robustan, klasa radi unutar sebe sve sto treba, sa SVOJIM setom varijabli, nizovima, stablom, internim flagovima/stanjima itd.itd. Drugo proistice iz prvog - kompajler sad mozes instancirati proizvoljan broj puta, bilo gde i bilo kad.

Pomenuo si TurboPascal... eh. Ako me secanje jos sluzi, Delphi 4 ili 5 je imao internu oznaku (makro $DEFINE xx ; ko zna, zna) 14 ili tako nekako. Pogodi odakle vuce ta numeracija ;) ; da, jos od TurboPascala. Opet kazem, najpostenije uradjen COMPILER ikada :) .

Drago mi je da smo ti (ako) pomogli. I da, blago tebi, radis prave stvari.

Pozz

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 12:24 - pre 133 meseci}

Možda se malo ne razumemo, ili ja mnogo ne razumem.

U TURBO PASCAL verziji sa jednoprolaznim kompajliranjem mi je bilo neophodno očuvanje redosleda unošenja zapisa u niz. Razlog je taj što kada kompajlira lokalni blok, onda u niz upiše deklaracije lokalnog bloka, a kada završi prevod lokalnog bloka, oneda pomenute deklaracije skine sa niza - prostim pomeranjem pointera na element niza na poziciju koja je bila pre prevođenja lokalnog bloka. Dakle. to je bio prost mehanizam.

Po inerciji to je ostalo do danas. Mada za time sada nema potrebe, jer ne brišem lokalna imena, več ih proširujem imenima lokalnih blokova kako bi bila jedinstvene. Ne brišem ih jer se mogu koristiti u dibagiranju i u još nekim slučajevima.

Koliko sam mogao da te razumem, ti predlazeš listu od parova: ime i pointer na zapis. Lista je sortirana po imenima, pa kada kompajler naiđe na ime varijable brzo ga pronađe u listi. Tada uzima pointer i dobija sve podatke o varijabli. Među tim podacima se nalazi i pointer na zapis koji definiše tip te varijable, pa se lako dobiju i podaci o tipu. U podacima o tipu je i pointer na zapis koji gradi taj tip što takođe koristi kompajler. Sve je ovo brzo i logično, a i sviđa mi se. Pitam se da li se uništavanjem liste, uništavaju svi pointeri i oslobađa memorija.

Međutim ima jedan vrlo ozbiljan problem. Na primer, kada definišem funkciju, u niz upisujem podatke o funkciji (adresa, da li je forward, i neke druge manje važne ali potrebne podatke), potom sledi niz zapisa za formalne parametre i na kraju return parametar. U zapisu za funkciju upisujem redni broj na kojem je zapis o return parametru, tako da imam definiciju funkcije sa skupom zapisa koji slede jedan iza drugog. Sortiranjem bi se ovo poremetilo. Ovo svakako može da se prevaziđe i tvojim pristupom uz dodatne komplikacije. Morao bih mnogo izmena da uradim u programu.

No ipak je ovo manji problem, vuče se još od TURBO PASCAL-a, pronašao sam heš funkciju u modulu uHashedStringList (na koju me je uputio salaczr) pa ću probati direktno sa njom. Problem je što nema dokaza da će heš funkcija vratiti istu vrednost za dva različita stringa, pa se ne može direktno koristiti.

Veći mi je problem implementacija PASCAL iskaza. Tu postoji veliki broj slučajeva za koje treba napisati kod i sve ih testirati. Tu postoji IZRAZ koji se sastoji od dva PROSTA IZRAZA razdvojena relacionim operatorom. Relacionih operatora ima 7. Ako nema relacionog operatora onda je IZRAZ PROST IZRAZ. PROST IZRAZ ima predznak i jedan ili više sabirka razdvojenih opretorima sabiranja (+.-,or), sabirak je jedan ili više činilaca razdvojenih operatorima množenja (*./,div,mod, and, shr, shl). Činilac moće imati predoperator not, a on je konstanta, varijabla, funkcija i drugi izraz (ako je u malim zagradama). Tome dodaj sve tipove koji postoje, i celobrojne tipove dužine 1, 2 i 4 bajta - označene i neoznačene, zatim eksplicitnu promenu tipa i eto sizifovskog posla.

Za sada sam napravio dodelu člana, i višestruko sam više vremena potrošio na testiranju nego na pisanju koda. To je zato što nisam napravio minimalan broj funkcija sa kojima to realizujem, pa kada ih jednom testiram ne moram i za svaki poseban slučaj. Imam osećaj da bi tu pomoglo objektno programiranje.

Poydrav.

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
..ppoe.dyn.broadband.blic.net.

+62 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 13:37 - pre 133 meseci}

Hehe, tacno znam o cemu pricas. :)

Radio sam davno tako nesto. U prvoj fazi je radilo samo kao interpreter algebarskog izraza, a kasnije sam pravio "kompajler", ciji je zadatak bio da poslozi zapise za kasnije izvrsavanje/izracunavanje izraza.
Evo ti hint za pocetak. U zapis koji sadrzi neki argument (bilo sabirak bilo cinilac) uvedi flag da li je isti prost/konacan (nema dalje, varijabla ili konstanta), ili slozen (sledi dalje grananje, nova funkcija ili izraz). U ovom drugom slucaju, ide pointer na novu granu (sta god bilo) itd. Secam se da je ubrzanje izvrsavanja uvodjenjem kompajlera bilo tacno 26 puta(!); neverovatno kako neki detalji prkose godinama :). Pretpostavljam da si uveo rekurziju u funkciju koja pravi niz zapisa, kao i u funkciju koja izvrsava/izracunava izraz..?
U pravu si, zadatak ovog tipa ne trazi nuzno OOP. Ali ako bi ga uveo, onda bi niz/lista bili zamenjeni klasom kontejnerom, koja sve zapise vidi kao skup itema jedne apstraktne klase. Od tog abstract item-a izvedu se descendent klase itd. Time odmah imas info (classtype itema) da li je zapis konacan, ili je putokaz na dalje grananje. Ne secam se bas tacno vise, ali tako nekako sam ja odradio.

Pozz

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 14:44 - pre 133 meseci}

Tako i ja radim, ali predhodno izraz prevedem u binarno stablo, pa njega prevodim. Svaki čvor stabla sadrži operator i tri pointera radi slobodnog kretanja kroz njega. Krajnji čvorovi su vezani za činioce. Prevod počinjem od najdubljeg čvora, jer tada imam najmanji broj međurezultata. Kada prevedem čvor on postaje činilac, i tako do root čvora.

a := b*(c+d)

:=
/ \
a *
/ \
b +
/ \
c d

Počinjem od čvora sa operatorom +

:=
/ \
a *
/ \
b a+b

:=
/ \
a b*(a+b)

i na kraju se dodeljuje izraz odredišnoj varijabli a.

Pozdrav.

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Hash funkcija-losa improviyacija- pomoc

^{30.04.2013. u 14:48 - pre 133 meseci}

Code:

         :=
       /    \
     a      *
           /   \
         b      +
               /  \
              c   d

Počinjem od čvora sa operatorom +

Code:

         :=
       /    \
     a      *
           /   \
         b    a+b

        :=
       /    \
     a    b*(a+b)

i na kraju se dodeljuje izraz odredišnoj varijabli a.

Pozdrav.

Odgovor na temu