Salut am si eu o intrebare. Care este cea mai eficienta metoda(rapida) de a cauta niste bytes intr-un fisier?
Am facut ceva simplu dar dureaza cautarea.


trebuie sa caut 6 bytes

Spui bytes dar in cod te referi la biti, voi presupune ca vrei sa cauti 6 bytes dupa cum mentionezi la sfarsit. Daca esti putin confuz in ceea ce inseamna byte sau bit, nu-i nimic: un byte are 8 bitzi si de aceea deseori un byte este numit octet(pentru ca el contine 8 bitzi, evident). Pe langa asta folosind functiile low level de acces la fisier sau pe cele high level(cele pe care le folosesti tu in cod) nu vei putea citi un numar de biti care nu este multiplu de 8, cu alte cuvinte tot timpul vei putea citi bytes intregi(unul, doi, cati vrei tu).
In primul rand pentru ca datele tale(fisierul) nu se afla in vreo structura de accelerare a cautarii nu prea sunt multe de facut. Poti insa imbunatati foarte mult cautarea liniara daca tii cont de urmatorul aspect: accesul la disc e costisitor si de aceea ar fi bine ca de fiecare data sa citesti mai mult de 1 byte(minimizand operatiile cu discul) si sa cauti informatiile tale in acel buffer. Pseoducodul ar putea arata astfel:



Dupa cum vezi fread nu citeste tot timpul atatia bytes cati ii ceri tu ci cat poate. Uneori pot avea loc erori, alteori pur si simplu ai ajuns la sfarsitul fisierului si nu se mai poate umple buffer-ul cu 1024 de bytes.

In al doilea rand, daca ai cunoaste de la inceput datele atunci le-ai putea organiza intr-o structura ierarhica(sau tabela de dispersie), salva structura pe disc si apoi ai putea sa o citesti si sa cauti in ea de cate ori vrei, lucrurile ar putea merge mult mai repede, de obicei in O(logn) sau chiar O(1) folosind tabele hash si exploatand anumite particularitati ale datelor tale.

Multumesc de reply dap ma refer la byte nu biti
Daca citesc bucati mai mari de date si le prelucrez in ram este mult mai rapid multumesc de solutie dar ma gandesc ca se poate intampla ceva de genul urmator:
citesc primul kilobyte fac cautarea daca nu gasesc cei 6 bytes citesc in continuare
dar daca se intampla ca primii 2 bytes sa se afle in bucata care o citesc prima data(sau a n oara) iar urmatorii 4 bytes se afla in bucata urmatoare ? Am sansa sa imi returneze fals desi valoarea este prezenta in fisier (as vrea sa fie gandit pentru fisiere cu marimi diferite)

Defapt este posibil sa fac un bool setat pe true daca s-a gasit primul/al 2-lea/al 3-lea byte si se termina bufferul de 1 kilobyte astfel pot cauta in continuare.

Multumesc inca o data de reply Deliverance.

pai daca fisierul nu e foarte mare ... poti sa-l citesti pe tot.

In solutia lui deliverance, ultima citire nu va fi de 1024 ... decat daca fisierul e multiplu de 1024 ... probabil trebuie sa vezi cat a citit la ultima citire.

Incearca sa citesti blocuri de baiti si verifica intotdeauna cati baiti au fost cititi, si mentine un pointer la un set de 6 baiti care sunt baitii de detectie.

pseudo-cod:



Daca nu ai de a face cu un sistem cu resurse restranse gen mobile, atunci aloca cat mai mult ram si cauta in ram, nu fa n operatii de citire aiurea. un 64K e rezonabil, depinzand de utilizarea acestui cod se poate si mai mult. Bonus daca te prinzi pt. ce cazuri codul de mai sus nu merge cum trebuie.

grep in binary mode

Citeste tot fisierul in memorie si proceseaza acolo. Latentele cu memoria sint cam de 250 de cicli (~80ns), pe cind cu diskul, un seek ajunge pina la 41 de milioane de cicli, adica 15ms pierdute.

Citirea de pe disk fa-o cu memory mapped files, ca sa eviti bufferele interne ale sistemului si sa faci copieri aiurea din bufferele system in bufferele tale. MMF este the way to go si atunci cind fisierul este prea mare ca sa poata fi tinut in RAM. Faci un window pe el pe care-l muti pina termini de citit.

Cit priveste algoritmii de cautare de bytes, problema este asemanatoare cu cautarea unui cuvint intr-un fisier, iar pentru asta exista algoritmi consacrati. Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore. Ultimul cred ca te-ar coafa cel mai bine.

Nu cred ca algoritmii de cautare pe siruri ar ajuta prea mult, patternul de cautat va avea tot timpul lungimea 1 (adica un byte). Complexitatea algoritmului va fi oricum O(M) adica lungimea fisierului in bytes. Acesti algoritmi ar ajuta atunci cand patternul ar fi mai lung de 1 byte.

N-am inteles bine daca ce cauta el este un sir consecutiv de bytes sau nu, dar daca e consecutiv se face cu algoritmii lui peste de care ziceam, daca nu, se face cu un if().

Aaa, noi am tot discutat despre cum s-ar cauta un byte rapid. Desi daca ma gandesc bine chiar de ar cauta 6 bytes consecutivi, banuiesc ca l-ar interesa doar daca acestia exista sau nu exista si nu determinarea tuturor aparitiilor patternurilor de 6 bytes. Cred totusi ca ar fi over-kill implementarea unui algoritm avansat de pattern matching pentru 6 bytes .

multumesc de link-uri o sa ma uit peste ele.
As putea spune ca caut un string si anume OggS dar mai sunt inca 2 bytes care urmeaza (00 04 sau 00 05). In mod normal gasesc o singura data acest sir de 6 bytes.
Imediat dupa acesti biti urmeaza ceea ce ma intereseaza pe mine si anume sa aflu lungimea unui fisier ogg in milisecunde sau sub ce forma e salvat (un numar de genul 134957)

Vezi numa ca metoda mea clacheaza la un string gen "cocosu" cand ai:
"aasdfgasd_cococosu_egdfgd". Asta ca sa fie totul clar.

ma tot chinui la asta dar se pare ca nu vrea sa imi mearga prea de curand. Bytes astia trebuie sa ii gasesc in ordinea asta.
4F 67 67 53 00 04

Ia-o logic, pune baitii de cautat intr-un array si incearca sa vezi cum ai gasi tu siru, daca ai fi in locul computerului. Ia-o pas cu pas, logic.

char TargetArray[6] = {0x4F, 0x67, ... };

ah mama is varza ... mersi mult ... nush de ce nu m-am gandit la un array (parca era o zicala la c++ cand te-ai blocat foloseste un array )
Incerc sa vad ce imi iese