Ovako na brzinu bih predlozio sledece - Podeli podatke u blokove, od po npr 4kb ili vec koliko ti odgovara, pa te blokove pakuj i sacuvaj u fajlu. Napravi indeks koji pokazuje koji opseg podataka se nalazi u kom bloku. Prilikom pretrage, u indeksu vidis gde se nalazi podatak, raspakujes samo taj blok i izvuces ga.

Da, to je veoma pametno resenje. Da li mozda znas za neku biblioteku koja ce makar delimicno automatizovati ovaj proces? Pokusavao sam sa gzip-om, ali ne mogu bas provaliti kako da izvedem ovo. Pokusacu jos par ideja koje mi padaju napamet, a ako neko ima iskustva sa slicnim problemom, neka se ne libi da uleti sa bilo kakvim savetom, sve je dobrodoslo :)
Kada (ako) napravim ovo, ostavicu kod ovde ako nekome zatreba, jer sam ustanovio da je za ovaj problem jako tesko naci resenje na internetu. Svima je izgleda ideja da raspakuju ceo fajl, pa da ga onda koriste. Cak i ove funkcije koje sluze za random access ustvari rade tako sto otpakuju ceo fajl do trazenog bajta, pa izvade podatak, pa vrate sve kako je i bilo.

A da li podaci bash moraju da budu u komprimovanom fajlu? Cini mi se da bi to mnogo lakse islo sa jednom sqlite bazicom koja je veoma brza. Ali naravno ja ne znam ono sto ti znas pa je moguce da ovo sto sam rekao nema nikakvog smisla

Krenuo sam sa sqlite bazom. Bilo mi je presporo. Sad mi je preveliko. Ne moze mi covek udovoljiti :)

Presporo?? Bas cudno... sqlite je prilicno brz, no pitanje je sta su ti ciljevi i koliko zelis da patis razvijajuci to.

Jesi li probao NexusDB? http://www.nexusdb.com/ Embedded verzija je free.

Ne znam, ali blokovska obrada podataka iz fajla je prilicno standardan pristup. Umesto da citas 20 ili 30 bajtova jednog zapisa iz fajla, ti ucitas blok, pa iz bloka izvuces to sta ti treba. I samo citanje sa diska koje obavlja operativni sistem je ovako odradjeno. Trebalo bi da postoji neka ovakva biblioteka. Mozda treba ponovo da potrazis.
Ovo ne bi trebalo da bude previse tesko za pisanje. Za konkretnije detalje implementacije bih morao znati da li podatke menjas ili samo citas iz ovog fajla.

What he said. :)

Imam skoro istu situaciju i resavam je bas tako kako je obucina predlozio. Za samu kompresiju/dekompresiju koristim http://www.zlib.net/ (free, standardan, testiran, brz, implementacije na raznim platformama, etc).
Sto manje blokove uzmes - to ce ti kompresija biti losija ali ces i imati i manje 'viska' tokom svake dekompresije.
Mozes i da napravis jedan pocetni dictionary za sve blokove (ili vise njih ako grupises blokove po slicnosti podataka) da dodatno optimizujes nivo kompresije.

Potpuno se slazem ... Ako su performanse citanja fajlova jako zahtevne(npr. indeksiranje tih "300000" video fajlova i frameova u real-time ...itd) ne verujem da ces naci besplatno i automatizovano resenje za instant upotrebu vec da zasuces rukave ako ce to na kraju da se isplati ...
Sqlite je dosta brz ...uostalom ne bi ga google toliko sponzorisao.(Mozzila, Firefox,Symbiam...itd)

Tip podataka koji cuvam u fajlu je struktura koja opisuje jednu tacku i njene sukcesore. Radi se o pathfinderu, a meni treba da vadim jedan po jedan takav Junction u zavisnosti od toga gde me put vodi. Zato mi je bitno da citanje jednog podatka bude sto brze, jer u slucajevima jako dugog puta ponekad vadim i hiljade komada bez unapred odredjenog redosleda. Sve je indeksirano unapred (npr. Svi su poredjani po ID komponenti, po kojoj se i traze u fajlu, pa mogu da ih trazim i binarno, a cak sam i to ubrzao tako sto sam napravio nezapakovan fajl u kome cuvam te IDjeve u istom redosledu, pa trazenje obavljam tu - na kraju samo iz fajla procitam podatak na datom mestu). Opet ponavljam - ne mora nista biti besplatno, a ne mora biti ni skroz automatizovano. SQLite3 sam dugo koristio (sa wrapperom CppSQLite3), ali mi se pokazalo presporim za neke druge stvari, pogotovo grafiku, jer u istoj bazi imam i sve ulice Srbije, Crne Gore i Bosne (ali bas sve), pa kada pokusam da procitam ulice koje su mi u ekranu u tom trenutku, moram proci kroz tabelu od 300 000 segmenata. To je uzasno koliko je sporo, pa sam se odlucio da napravim fajlove u kojima sam sortirao ulice po kvadrantima u kojima se nalaze. Mozda bi ovo mogao i sa SQLite-om, ali sam pretpostavio da bi bio problem imati desetine hiljada tabela (za svajki kvadrat po jednu). Ako bih nekako drugacije organizovao podatke, opet nailazim na problem da postavim upit tipa: daj mi sve kojima je x izmedju x1 i x2 i y izmedju y1 i y2.
Na kraju sam zavrsio sa gomilom fajlova specijalizovanih za po jedan zadatak i sve je bilo OK, dok nije ispalo da mi ukupni podaci zauzimaju oko 300 MB, a treba da stanu na karticu od 256. Zato kazem da mi stepen kompresije nije toliko bitan, ali mora da postoji.



Shvatam ja da je obucinin predlog dobar, ali postavljaju se sledeci problemi:
-Meni su svi podaci u fajlu jednake velicine, kada zapakujem komad po komad onda vise nisu jednake velicine i kako da ih opet izjednacim. Na kraju je potrebno da podatak u fajlu trazim tako sto kazem seekg(redniBroj * velicinaJednogPodatka). Ili ima neki drugi nacin koji je meni nepoznat?
-dictionary je kod zliba pomenut informativno. Googlanje me uvek vodi na iste prepisane stranice i nikako ne mogu ustanoviti sta je to uopste. Moze li neki link ili nacin upotrebe ove opcije, jer sam vec ranije pomislio da bi me kontanje toga dovelo do resenja?
- zlib u svim primerima pokazuje otpakivanje celog fajla. Ne sumnjam da se ovo pakovanje komad po komad moze obaviti, ali nigde nisam nasao kako. Cak i shvatam kako bih to odradio, ali ostaje problem zaokruzivanja velicina da budu iste. Pretpostavljam da se moze uzeti jedan podatak, zapakovati, pa smestiti u obican fajl kao binarni podatak i prilikom citanja sve izvesti suprotno. Voleo bih da negde vidim primer toga, jer kad pokusam da izvedem ovo, na kraju zavrsim sa gomilom besmislenih bajtova.

Meni se i dalje cini da bi bilo uputnije potrositi vreme na dizajn adekvatne baze podataka nego na upotrebu zlib biblioteke. Mozda mozemo da pripomognemo u ovom slucaju. Imas li neku shemu baze vec uradjenu pa da krenemo od toga?

Mislim da je njegova stvar previse low-level da bi neka standardna baza podataka mogla to da podrzi. Mislim, ta baza ce ionako biti jos jedan layer iznad neke zlib-like kompresije (ako ne bas i njega) - ako uopste ima kompresiju.
Doduse nisam se odavno bavio time pa mi ne zameri ako je memory overhead baze zanemarljivo mali. Vredi probati? :)



1.) Pakujes blok-po-blok jednake velicine, a output ti je u vidu odvojenih fajlova. Kolika je velicina zapakovanih blokova ti nije bitna.
2.) Kad hoces da dobijes podatke o nekoj tacki, pronadjes u kom bloku je, otpakujes ceo blok i procitas tacku.
3.) Onda napravis caching tako da u svakom trenutku mozes imati n otpakovanih blokova (kolko vec stane u ostatak memorije) tako da ako su uzastopne tacke u istim blokovima ne moras da ih opet otpakujes.

Ako ti sama blok-by-blok kompresija radi posao dovoljno da spakujes sve u 256 - ignorisi custom dictionary - ne znam da ti kazem kako tacno to da uradis, to mi samo stoji u todo listi za neku slicnu stvar koju sam radio, ali jos nisam odradio :)

ps, da li mozes tvoje podatke kompresovati na neki drugi nacin?
Sta tacno ti sadrzi tacka, i sta su tacno 'sukcesori'? Indexi na druge tacke? Koliko tacaka imas sve zajedno? Kako su grupisane?

Naravno ...
jer ako kazes da ti je pod sqlite-om sporo radilo ne znaci da je spor nego je mozda los relacioni model baze koji je za ovakvu vrstu slucaja inace potrebno.
Sigurno da postoji sansa da se negde upiti optimizuju kao i relacije izmedju takvih tabela,pa da se postave indexi kolko god je to moguce ...
Ideja celog tvog projekta je interesantna , tako da podrzavam ideju kiklopa .

Hteo bih jos da se nadovezem na prethodni post .
Sa optimizacijom sqlite-a ces mozda dobiti i do 30% poboljsanja ..



Za ovu pricu bi ti trebao napredniji model algoritma za ponalazenje "suksesora" tj. susednih tacaka koje cine putanju .
Cilj bi bio predikcija sukcesora tj. predvidjanje sledecih tacaka tako da ne treba da vadis jedan po jedan "Junction" i uz koriscenje dvostruko povezanh lista (putanje mogu da imaju 2 smera))
i STL biblioteke mozda ces dobiti poboljsane performanse ....

Malo sam googlao pa sam naleteo na resenje koje MS nudi sa svojim SQL2005
Data Mining model: http://technet.microsoft.com/en-us/library/aa964125.aspx



Da li si probao da u jednu tabelu stavljas vise kvadrata (mislim da je baza ogranicena na neki veliki broj tabela )
i da uz pomocu gore pomenutog algoritma zadas neki upit za dobijanje y(putanja)=f(x1,x2)

Uf... vidim ja da sam vas vise zbunio objasnjavanjem moje "baze" nego sto sam pojasnio. Evo sta ja u stvari imam kao podatak:


Fajl je niz Junctiona. Svaki Junction ima odredjeni broj JuncPtr-ova koji su mu successori. To znaci da se iz njega moze otici na njih, a nikako ne vazi obrnuto. Posto su Juctioni poredjani po ID-ju, ja ih iz programa zatrazim funkcijom
Junction getJunction(int ID);
Kada ga dobijem, pathfinding deo nastavlja da se brine o tome koji successor je pogodniji za nastavljanje puta, a onda se pomocu successorovog ID-ja opet postavi upit za trazenje Junctiona i tako dok jedan od njih nema ID cilja. U pitanju je A* pretrazivanje, ali to nema previse veze sa nasom temom (ali kad vec objasnjavam...).
Ako se pitate zasto sam ovako slozio podatke, odgovor lezi u brzini. Imam u drugim tabelama spisak segmenata koji imaju po dva Junctiona na krajevima, pa se i iz toga moze zakljuciti odakle - dokle postoji put. Ovo je sumanuto sporo, pa sam sve stvari koje se mogu izracunati unapred vec izracunao, da bih u real time-u samo skakutao po fajlu.
Iz gore navedenog se moze zakljuciti da je meni dosta prostora otislo u prazno, jer nema svaki Junction 8 successora, niti svaki successor ima 8 forbidden IDjeva (to su ID-jevi iz kojih je zabranjeno skrenuti). Meni velicina tog fajla ne znaci previse, jer ga i najmanji stepen kompresije smanji za vise od pola usled ovakve gomile nula koje se nalaze u njemu. Jedina stvar koja me interesuje je brzina pristupa jednom elementu.

Ako i dalje postoji jaka struja koja zagovara upotrebu baze u ovom slucaju, iznecu i bazu ovde, nije nikakav problem.

A citajuci vase komentare, pala mi je jedna ideja na pamet:
Jedan po jedan podatak pakujem u memoriji (koristeci zlib). Onda pogledam koliko bajta tezi konkretan spakovan podatak, pa u jedan drugi fajl pisem redni broj i tacnu poziciju i velicinu u bajtovima u spakovanom fajlu (kada kazem spakovanom fajlu, mislim na obican fajl sa spakovanim podacima). Posle se pretraga vrsi po fajlu koji sadrzi indekse i mesta na kojima pocinje i zavrsava trazeni zapakovani podatak i eto ga super brzo citanje.
Sta mislite?

Ne zagovaram "baznu struju" nego onu koja radi posao :)
Ako ne gresim tvoj malo uprosceni algoritam kolko sam shvatio izgleda ovako :

1 uneti pocetnu i krajnju tacku (x1 i x2) tj. zadaj query
2 otvori fajl i nadji blok za tacku tj. Junction strukturu ... X(n) ,X(n+1) ...
3 smesti blok u memoriju i raspakovati ga zlib-om ili cime god ...
4 izvaditi podatak iz raspakovanog bloka
5 staviti nadjeni podatak (ID ili koordinate ) i smestiti ga u listu tacaka putanje
6 proveri da li je nadjena tacka jednaka x2 ako nije onda ->
7 goto 2

Cini mi se da jedan veliki problem koji ovde nazirem je update blokova u odredjenim fajlovima
tj da li imas na umu da ce ti blokovi tj. Junction-i (JuncPtr successor[8];) da se menjaju tj. da dodajes nove putanje ili su samo read-only ?
U svakom slucaju razvijas sopstveni dbms za koji ce ti trebati dosta vremena da ga usavrsis a vec mozda postoje gotova resenja ...
Mozda ne bi bilo lose da probas da iskoristis i jedno i drugo .
Tvoj db sistem u sprezi sa sqlite-om koji bi mozda keshirao rezultate pretrage ili bi posle olaksao nalazenje najkrace putanje u narednim query-ijima


Happy coding !!!

Ja sam veoma low level u ovoj prici, jer mi je mala i memorija i storage i slab mi je procesor i mnogo je podataka (WinCE).
Ceo fajl koji pravim ce biti read only. To je realna mapa sa realnim ulicama, moj softver je cita i kada ti uneses putanju (npr. Od ulice Petra Petrovica u Uzicu do Srpskih vladara u Beogradu) on vidi koji su to Junctioni i onda nadje putanju medju njima. Nacin na koji trazi putanju je prilicno standardan za mnoge oblasti (posebno igre). Ovako bi izgledao precizniji opis algoritma:
1) Imam pocetni i krajnji ID
2) aktivniID = pocetniID
3) izvadi iz baze Junction koji ima isti ID kao i aktivniID
4) izdvoji sve successore aktivnog ID-ja i odredi kojim redom (u odnosu na prioritet i duzinu) se nastavlja putanja
5) ID successora koji je najpogodniji za nastavak puta dobija status aktivnogID-ja i ide se na tacku 3)

Ono sto nije standardno je da sam kompletnu matematiku vec ubacio u "bazu" (duzina, ID segmenta koji je izmedju dva Junctiona, prioritet, od kog parenta postoji zabrana...)
Ne postoji update nikada, ta mapa se samo jednom pakuje, a korisnici sve dobijaju na PNA uredjaju integrisano sa softverom. Sve je vec testirano i radi, a meni ostaje samo da resim jos par problema kao sto je ovo prokleto pakovanje.
Inace, i meni je padalo na pamet resenje sa kombinacijom sqlite-a i mojih specijalnih fajlova, ali to bi zahtevalo jos dosta testiranja. Nekakav sopstveni sistem sam vec napravio i dokazao da moze da radi real time i to radi dobro. Sada sam zapeo na smanjenju velicine fajlova, pa bi mi najdraze resenje bilo ono koje ne zahteva dvonedeljni rad (sefovi vec skacu po glavi, jer razvoj komplet softvera traje vec 10 meseci, a planirano je 6. Doduse, oni su krivi za otezanja, ali je i nervoza jasna jer ne dobijaju ni dinara dok ceo paket ne krene da se prodaje). S druge strane, ako sam pogresio u nekim osnovnim konceptima, i dalje nije kasno za promenu, pa sam otvoren za apsolutno svaki savet koji date. I naravno, takodje sam i zahvalan za isti...

El mozes mozda da probas nesto jednostavno tipa optimizujes podatke u strukturi i/ili ih zapakujes tako da se otpakuju tokom samog procesiranja? Nisam stigao da se udubim u sve sto si napisao, ali pojasni mi par stvari:

Zasto imas JuncPtr i Junction kao odvojene tipove? Sta predstavljaju ID, segmentID, length, frc, fow, xpos, ypos i forbidden[8]?
Sta ti znaci successor? Da li je to nod na koji mozes da ides - da li je to drugi Junction?

Mozda je moguce reorganizovati podatke tako da se izbace viskovi i da se koriste manji tipovi (tipa, ako imas manje od 65k ID-ova ili segmentID-ova, onda mozes koristiti unsigned short umesto int-a).

Svakako da je moguce reorganizovati podatke tako da sve bude nesto manje. Te detalje ostavljam za sam kraj. unsigned short nece raditi posao jer ih samo u Srbiji imam 190 000., a posebno ne mogu garantovati za ubuduce. Za sada se radi o odredjenom broju ulica, ali vec je u planu da se ubacuju mape Madjarske, Makedonije, Hrvatske... Cak nisam siguran da ce u nekoj daljoj buducnosti i int biti dovoljan. Zato izbegavam ovaj tip optimizacije, jer se bojim da mi povecava kolicinu rada na apdejtima programa.
Opis atributa:

successor je nesto na sta mozes otici iz datog Junctiona. On ima svoj ID i negde drugde je opisan kao Junction sa svojim successorima. Kada se gleda situacija u kojoj je on samo successor nekom Junctionu, onda je u njemu opisana putanja izmedju njih.

ID = jedinstvani ID Junctiona. Sluzi da bi se kasnije mogao naci u bazi kao Junction, i da se vide njegovi successori.

segmentID = Svaka dva Junctiona su povezana segmentom. Taj segment je opisan u nekoj drugoj tabeli (fajlu) i tamo imamo razne parametre koji ga konkretnije opisuju. Ovde stoje samo one osobine koje nas zanimaju za pathfinding. Osobine koje omogucavaju crtanje segmenta nas ovde ne zanimaju.

frc, fow = Ovo su osobine tog segmenta koji povezuje te dve tacke. frc i fow su standardizovane velicine i jedna opisuje prioritet puta, a druga tip puta (frc = 1 za autoput, frc = 2 za put sa dve trake fow = 4 za ukljucenje na autoput...)

xpos i ypos = pozicije te tacke u realnom prostoru. Imamo xpos za Junction, i xpos za successor. Ovi podaci nam sluze zbog heuristike, jer se gleda priblizavanje ciljnom Junctinu kada se odlucuje kojim putem se nastavlja.
length - duzinu segmenta koji spaja dve tacke ne mozemo dobiti prostim povlacenjem linije izmedju (xpos, xpos) i successorovih (xpos, ypos) zato sto se moze raditi o krivoj liniji. Ovde je sacuvan jedini podatak koji nas o toj krivoj liniji zanima, a to je njena duzina. Koristi se da bi se dobila cena kostanja putovanja po datom segmentu (uzima se u obzir frc, fow i length, pa u zavisnosti od izbora vozila dobijamo cost).

forbidden = postoje skretanja koja su fizicki moguca, ali su zabranjena. Ja te situacije opisujem tako sto vidim koje tri tacke (Junctiona) obrazuju trojku kojom ne sme da se ide. Zamisli raskrsnicu Kneza MIlosa i Bulevara. Ti mozes ici od te raskrsnice prema Zvezdari ako dolazis iz jednog pravce, ali ne smes ako dolazis od Takvuda. To opisujem tako sto na u forbiddene upisem ID Junctiona iz koga je nemoguce skrenuti u dati segment.

P.S. Sada se bacam na pravljenje pakovanja kakvo sam opisao u prethodnom postu. Nakon toga cu baciti kod ovde, pa ako neko bude imao savet, primedbu ili kritiku bicu zahvalan za istu.

Ne rece mi zasto koristis JuncPtr? Cini mi se kao da su neki podaci duplicirani. Jedan Junction ti je skoro pola kilobajta, a cini se da je mnogo stvari suvisno.
Zasto ulagati resurse u sistem za kompresiju/dekompresiju ako prostom reorganizacijom mozda mozes smanjiti koriscenje memorije par puta i na kraju imati bolje rezultate nego sa kompresijom?

Umesto JuncPtra sam mogao staviti samo IDjeve Junctiona na koje se ide odatle, ali kako bih onda imao sve informacije o segmentu koji ta dva Junctiona cine? Sve vreme se trudim da budem sto brzi, pa ovako postizem da su mi svi potrebni podaci na jednom mestu.

Evo jednog resenja datog problema:
Ideja je da citas iz binarno sortiranog fajla, a da on istovremeno bude spakovan. Stepen kompresije nije toliko bitan, a u mom konkretnom primeru od jednog fajla dobijemo dva, dok velicinu smanjimo za nesto vise od pola. Negativne strane ove metode su da se pakovanje ne vrsi kroz ceo fajl, nego je svaki podatak zapakovan sam za sebe. Time smo mogucu kompresiju smanjili desetak puta (ovo je bazirano na konkretnim merenjima, za razlicite podatke ce se dobijati razliciti podaci).

Funkcija koja pakuje vektor i smesta ga u fajl, dok istovremeno pravi drugi fajl sa elementima koji sluze za pretragu:


Ovde je ubaceno nekoliko nepotrebnih stvari u fPositioner, koje ce sluziti za neke druge stvari, posto mi se ne pravi tona slicnih struktura. Kad smo vec kod toga, ovako izgleda fPositioner:


Naravno, umesto njega se moze koristiti i bilo koja slicna struktura sa nekoliko brojeva u sebi. Isto tako ce raditi i sa nizom intova...


Kad smo zapakovali fajl gornjom funkcijom, ovako pronalazimo element sa trazenim ID-jem:


I to vam je to. Nadam se da ce neko naci poneku glupost u kodu, a nemam nista protiv ni da mi se ukaze na strukturalne nepravilnosti (ili bolji nacin obavljanja ovog posla). Inace, ovo provereno radi, a za one kojima bi mozda posluzio ovaj kod, samo da kazem da se moze koristiti za bilo sta, samo rec "Junction" promenite u ime neke svoje strukture.

E, ovo je dosta dobro, a sada samo uzmi i rezervisi jedan veci prostor, u koji ces da prekopiras 10/20/50 Junction-a, a zatim to kompresuj i indeksijraj. Kompresija ce biti veca, a pretraga neznatno slozenija.

Pisem iz glave, mozda nije sve tacno...



U getJunction na kraju samo dodas pretragu po ovih 20 Junctiona i to je to.

<sub>[Ovu poruku je menjao obucina dana 15.03.2008. u 03:52 GMT+1]

[Ovu poruku je menjao obucina dana 15.03.2008. u 03:54 GMT+1]

[Ovu poruku je menjao obucina dana 15.03.2008. u 03:55 GMT+1]</sub>

Da, to je skroz lepo dizanje jos jednog nivoa. Mozda bi bilo pametno prilikom citanja stavljati odredjenu kolicinu Junctiona negde u memoriju, pa pre svakog sledeceg skakanja na fajl proveravati da nije mozda medju njma onaj koji se trazi. Takvo nesto je i Filip predlagao pre odredjenog vremena.
Dobio sam neocekivano produzenje roka, pa cu se poigrati sa raznim oblicima hashovanja - to je ipak stvar koju moras da testiras da bi video koliko ubrzanje dobijas. Ovako napamet se ipak cini da se mora nesto dobiti, jer je mapa izvezena iz Auto CADa, pa Junctioni koji su fizicki blizu imaju i slicne ID-jeve. Hvala na pametnom savetu.

Samo delimicno vezano za prethodne dileme, napravio sam jednu konstrukciju, pa me zanima ima li pametnijeg nacina da se to izvede:

Ako postoji struktura koja ima pointer u sebi, npr:



Kada to zelimo strpati u fajl, jedini nacin koga ja mogu da se setim je sledeci:


Pa se onda citanje obavlja na sledeci nacin:


pa onda dodelim taj niz mojoj novoj strukturi:


E sad, postoji li brzi (pametniji, zgodniji...) nacin da se ovo uradi? Ima li neko ideju? Ovako mi je malo nezgodno da cuvam indeksere, ali nista pametnije mi ne pada na pamet.