Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Random access u kompresovanom fajlu

[es] :: C/C++ programiranje :: Random access u kompresovanom fajlu

Strane: 1 2

[ Pregleda: 4861 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

DjoleReject
Djordje Knezevic
Zvezdara

Član broj: 85258
Poruke: 309
*.dynamic.sbb.co.yu.



+1 Profil

icon Re: Random access u kompresovanom fajlu10.03.2008. u 21:15 - pre 195 meseci
Citat:
Filip Strugar: 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.
De si Deda...
 
Odgovor na temu

DjoleReject
Djordje Knezevic
Zvezdara

Član broj: 85258
Poruke: 309
*.dynamic.sbb.co.yu.



+1 Profil

icon Re: Random access u kompresovanom fajlu11.03.2008. u 21:09 - pre 195 meseci
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:

Code:

void packAndSaveData(vector<Junction>& vec){
    
    string dpath = "putanja do fajla za pretragu";
    string fpath = "putanja do fajla sa zapakovanim podacima";

    ofstream ofsd(dpath.c_str(), ios::binary);
    ofstream ofsf(fpath.c_str(), ios::binary);
    
    int placeInFile = 0;
    //Pravljenje isfoliranog pointera koji sluzi da na pocetku fajla imamo ukupan broj elemenata, cime ubrzavamo binarnu pretragu
    fPositioner fp1;
    fp1.file = vec.size();
    fp1.ID = 0;
    fp1.placeInFile = 0;
    fp1.packedSize = 0;
    fp1.unpackedSize = 0;
    ofsd.write((char*) &fp1, sizeof fPositioner);
    
    for(int i=0; i<vec.size(); i++){

        Junction jnc = vec.at(i);
        
        int orgSize        = sizeof Junction;
        BYTE* orgData    = (BYTE*) malloc (orgSize);
        
        memcpy(orgData, &jnc, orgSize);

        ULONG comSize = (ULONG) (orgSize * 1.1 + 20);
        BYTE* compData = (BYTE*) malloc(comSize);
        //
        compress(compData, &comSize, orgData, orgSize);
        //        
        
        fPositioner fp;
        fp.file = 1;
        fp.ID = jnc.ID;
        fp.placeInFile = placeInFile;
        fp.packedSize = comSize;
        fp.unpackedSize = orgSize;
        placeInFile += fp.packedSize;

        ofsd.write((char*) &fp, sizeof fPositioner);
        ofsf.write((char*) compData, fp.packedSize);        
    }
    ofsd.close();
    ofsf.close();    
}

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:

Code:

struct fPositioner{
    int file;
    int placeInFile;
    int packedSize;
    int unpackedSize;
    
    int ID;
};

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:

Code:

Junction getJunction(int ID){
    ifstream ifsd(dpath.c_str(), ios::binary);
    
    filePositioner pos;
    ifsd.read((char*) &pos, sizeof fPositioner);
        
    int first=1, last = pos.file; //Ovo je onaj element koji ne sluzi nicemu drugom, nego vadjenju broja elemenata sa pocetka fajla
    while (first <= last){
        int mid = (first + last) / 2;  // compute mid point.
        ifsd.seekg(mid * sizeof fPositioner);
        ifsd.read((char*) &pos, sizeof fPositioner);
        if (ID > pos.ID){
            first = mid + 1;  // repeat search in top half.
        }
        else if (ID < pos.ID){
            last = mid - 1; // repeat search in bottom half.
        }
        else { break; }
    }    
    ifsd.close();
    
    ULONG finalSize = pos.unpackedSize;
    
    BYTE* freadData = (BYTE*) malloc(pos.packedSize);
    BYTE* finalData = (BYTE*) malloc(pos.unpackedSize);

    ifstream ifsf(fpath.c_str(), ios::binary);
    ifsf.seekg(pos.placeInFile);
    ifsf.read((char*) freadData, pos.packedSize);
    ifsf.close();
    
    //
    uncompress(finalData, &finalSize, freadData, pos.packedSize);
    //
    Junction temp;
    memcpy(&temp, finalData, finalSize);
    return temp;
}

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.
De si Deda...
 
Odgovor na temu

obucina

Član broj: 38191
Poruke: 723

Jabber: obucina


+7 Profil

icon Re: Random access u kompresovanom fajlu15.03.2008. u 02:29 - pre 195 meseci
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...

Code:

    int orgSize        = sizeof Junction; // Junction je fiksne velicine, zar ne?
    int jcount = 20;
    int startID;

    for(int i=0; i<vec.size(); i++){

        Junction jnc = vec.at(i);

        if ((i % jcount) == 0) { // Po jcount Junction-a
            BYTE* orgData    = (BYTE*) malloc (orgSize*jcount );
            startID = jnc.ID;
        }
        
        memcpy(orgData + ((i % jcount )*orgSize), &jnc, orgSize);

        if ((i % jcount) == (jcount - 1)) {
            ULONG comSize = (ULONG) (jcount * orgSize * 1.1 + 20);
            BYTE* compData = (BYTE*) malloc(jcount * comSize);
            //
            compress(compData, &comSize, orgData, orgSize);
            // Ovde treba da imas spakovanih 20 Junction-a
            // Positioner moras prepraviti tako da ti belezi od kog do kog indeksa imas Junction-e u ovom bloku

        
            fPositioner fp;
            fp.file = 1;
            fp.IDfrom = startID;
            fp.IDto = jnc.ID;
            fp.placeInFile = placeInFile;
            fp.packedSize = comSize;
            fp.unpackedSize = orgSize;
            placeInFile += fp.packedSize;

            ofsd.write((char*) &fp, sizeof fPositioner);
            ofsf.write((char*) compData, fp.packedSize); 
        }       
    }


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

[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]
 
Odgovor na temu

DjoleReject
Djordje Knezevic
Zvezdara

Član broj: 85258
Poruke: 309
*.dynamic.sbb.co.yu.



+1 Profil

icon Re: Random access u kompresovanom fajlu16.03.2008. u 00:05 - pre 195 meseci
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:

Code:

struct NekaStruktura{
    int ID;
    int* niz;
    int sizeOfNiz;
}:


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

mojOfstream((char*) &struktura, sizeof NekaStruktura);
mojOfstream((char*) struktura.niz, sizeOfNiz * sizeof (int));


Pa se onda citanje obavlja na sledeci nacin:
Code:

mojIfstream((char*) &upravoProcitanaStruktura, sizeof NekaStruktura);

int* procitaniNiz = new int[upravoProcitanaStruktura.sizeOfNiz];

mojIfstream((char*) procitaniNiz, upravoProcitanaStruktura.sizeOfNiz * sizeof (int));



pa onda dodelim taj niz mojoj novoj strukturi:
Code:
upravoProcitanaStruktura.niz = procitaniNiz;


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.
De si Deda...
 
Odgovor na temu

[es] :: C/C++ programiranje :: Random access u kompresovanom fajlu

Strane: 1 2

[ Pregleda: 4861 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.