Hash funkcija-losa improviyacija- pomoc

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.

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.

Potpis

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

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

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

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


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


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

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


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

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.

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

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.

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

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.