CAUTARI IN FISIERE DE DATE

CAUTARI IN FISIERE DE DATE.

01. CAUTARE SECVENTIALA.

Odata ce intr-un fisier de date s-au introdus date, in fata utilizatorului apar probleme specifice : ca regasirea unor date in fisier, consultarea bazei de date, prelucrari diverse in functie de domeniul din care s-au cules datele introduse, listari la imprimanta ale unor situatii analitice sau sintetice.

In continuare ne vom preocupa de cautarea de date (inregistrari) in vederea consultarii, si/sau a prelucrarii acestora.

In vederea insusirii CAUTARII SECVENTIALE vom introduce 2 notiuni : 'CHEIE DE INREGISTRARE' si 'CHEIE DE CAUTARE'.

Pentru aceasta vom apela la un exemplu :

Fisierul PONTAJ.DBF contine date :

FIGURA 01. (BROWSE PONTAJ)

Daca numarul de marca (numar de legitimatie) al salariatului se acorda in mod biunivoc in cadrul firmei (unui salariat ii corespunde un numar legitimatie care nu se va mai acorda altui salariat din firma si invers), atunci VALORILE din coloana MAR identifica in mod unic un angajat. Numele si prenumele salariatului, nu este sigur ca poate avea rolul de identificare a acestuia. Putem avea 2 angajati cu numele POPA ION, acestia avand numere de legitimatie diferite.

In cazul nostru, s-ar parea ca valorile din coloana MAR ar identifica o inregistrare in mod unic. Asa ar fi daca in fisierul PONTAJ.DBF ar fi date DOAR pentru o singura luna. In fisier in coloana lunii (LN) apare doar valoarea 10. Dar prezenta coloanei LN ne avertizeaza ca in fisier ar putea fi introduse date si pentru alte luni (exemplu 11). In acest caz un salariat ar putea apare de mai multe ori, adica de atatea ori cat este numarul lunilor in care respectivul salariat a lucrat si nu a parasit firma noastra.

Identificarea unei inregistrari se mai poate face doar prin numar marca ? Evident ca nu !!!

Pentru identificarea unei inregistrari va trebui sa facem referire la 'NUMARUL DE MARCA . din LUNA DE PONTAJ . '

Conform figurii de mai sus, pentru identificarea inregistrarii referitoare la MANCIU ILARION, ne vor fi necesare 2 valori : 1014 care se afla in coloana MAR, si 10 care se afla in coloana LN. Cele 2 valori 1014 si 10 impreuna formeaza CHEIA de CAUTARE.

Cele 2 coloane ale caror valori identifica o inregistrare (LN , MAR), formeaza CHEIA de INREGISTRARE in fisierul PONTAJ.DBF.

Si acum despre cautarea secventiala :

Intai ne stabilim cheia de inregistrare din fisier, in cazul nostru : LN si MAR.

Apoi, din necesitatea practica de regasire a inregistrarii, retinem in variabile de lucru valorile concrete ale CHEII de CAUTARE :

Exemplu :

Retinem in variabilele de lucru L, M valorile cheii de cautare :

L=10

M=1014

Urmeaza cautarea propriuzisa in fisierul PONTAJ care trebuie activat (deschis).

USE PONTAJ

LOCATE FOR LN=L AND MAR=M

Rezultatul cautarii poate fi cu succes sau nu.

Functia FOUND() intoarce valoarea logica de adevar T in primul caz, si F in al doilea caz - cel al cautarii fara succes.

Deci tastand :

? FOUND()

se va afisa T sau F dupa cum cautarea a fost cu succes sau fara succes.

In cazul afisarii T, putem continua cu :

DISPLAY daca dorim vizualizarea inregistrarii cautate.

Apoi putem relua cautarile cu alte atribuiri variabilelor L si M, urmate de LOCATE corespunzator etc. La sfarsit, nu uitam sa inchidem fisierul :

USE

Deocamdata sa retinem comanda pentru cautarea secventiala : LOCATE . si functia care ne ajuta prin valorile pe care le intoarce, sa stim daca operatia de cautare a avut succes sau nu : FOUND().

Din exemplul precedent se poate deduce ca in momentul gasirii unei inregistrari care satisface conditia din comanda LOCATE, aceasta inregistrare devine CEA CURENTA, si de aceea are sens comanda DISPLAY care va afisa exact inregistrarea cautata.

Legata de cautarea secventiala este si comanda

CONTINUE

care are drept efect continuarea cautarii in conditiile din LOCATE pentru gasirea, eventual, si altor inregistrari care ar mai putea satisface aceleasi conditii, si din nou, procesul se opreste in cazul cautarii cu succes.

Fie la executia lui LOCATE, fie la executia lui CONTINUE, daca nu se gasesc inregistrari care sa corespunda conditiilor precizate in comanda, cautarea se opreste la sfarsitul fisierului. In acest caz valoarea functiei EOF(), va confirma pozitionarea indicatorului de inregistrare pe EOF.

Cum se lucreaza in cautarea secventiala ?

Valorile cheii de cautare s-au retinut in variabilele L si M. Din PONTAJ.DBF am retinut doar coloanele care contin valorile cheii care identifica inregistrarile.

VARIABILE PONTAJ.DBF

Se parcurg succesiv inregistrarile din PONTAJ.DBF incepand cu prima, si se compara valorile din coloanele LN si MAR cu cele din variabilele L si M. Pentru inegalitate se trece automat la urmatoarea inregistrare. In cazul egalitatii valorilor din L si M cu cele gasite in coloanele LN si MAR, inregistrarea respectiva devine curenta si cautarea s-a terminat cu succes. In caz contrar, indicatorul de inregistrare se opreste pe EOF.

!!! Pentru un fisier de date relativ mare ca numar de inregistrari si in cazul unui numar destul de mare de cautari, timpul de raspuns s-ar putea sa nu fie convenabil : pentru fiecare cautare se parcurge secvential fisierul pana la gasirea inregistrarii cautate sau pana la sfarsit daca inregistrarea cautata nu este in fisier.

Sistemul FOX ne pune la dispozitie si CAUTAREA DIRECTA sau INDEXATA.

02. CAUTAREA DIRECTA (sau INDEXATA).

Aceasta cautare se bazeaza pe crearea unui fisier ajutator depinzand de fisierul in care se efectueaza cautarea. Prin intermediul acestui fisier ajutator cautarea se face mult mai rapid. Vom exemplifica metoda pe fisierul PONTAJ.DBF in care dorim o cautare indexata dupa luna pontaj si numar marca adica dupa o cheie formata din LN si MAR.

Metoda consta in urmatoarele :

1. Activam fisierul PONTAJ.DBF

2. Creem fisierul ajutator PONTAJ.IDX

USE PONTAJ

INDEX ON STR(LN,2)+STR(MAR,4) TO PONTAJ

c-da de cheie de indexare compusa fisier ajutator creat

indexare din luna si numar de marca PONTAJ.IDX

Dupa cum se vede, comanda de creare fisier ajutator (IDX), cuprinde cheia de indexare care s-a format prin concatenarea a 2 subsiruri obtinute din conversia in 'siruri de caractere' a campurilor LN si MAR care in PONTAJ.DBF erau numerice cu lungimile de 2, respectiv 4. Deasemenea, in comanda este introdus identificatorul fisierului ajutator PONTAJ care se va crea si va avea extensia IDX. Tastand DIR *. pe ecran se vor afisa si 2 fisiere PONTAJ :

PONTAJ.DBF PONTAJ.IDX

Deci in urma executiei comenzii INDEX de mai sus, s-a creat PONTAJ.IDX asociat lui PONTAJ.DBF prin cheia descrisa mai sus.

In figura 05 este aratata legatura intre cele 2 fisiere. Cheia de indexare STR(LN,2)+STR(MAR,4) se regaseste sortata crescator in PONTAJ.IDX. Alaturi de valorile cheii se regasesc (in figura, in coloana POZ) numerele de ordine ale inregistrarilor din PONTAJ.DBF, in care se gasesc cheile de identificare a acestora.

Cand voi dori sa caut o inregistrare cu cheia formata din :

L=10

M=2001

Prin intermediul lui PONTAJ.IDX se va gasi pointerul de legatura cu PONTAJ.DBF si care este 9 (coloana POZ). Pe baza acestei valori se acceseaza direct inregistrarea cautata.

Pentru o valoare a cheii de cautare formata din L=10 si M=5000, cautarea in PONTAJ.IDX va fi fara succes (vezi figura C05.05).

STR(L,2)+STR(M,4)

PONTAJ.DBF PONTAJ.IDX

FIGURA 05 (RELATIE intre PONTAJ.DBF si PONTAJ.IDX)

De retinut : dorind o cautare directa intr-un fisier de date dupa o anumita cheie creem cu o comanda INDEX fisierul asociat (extensie .IDX). Altei chei de cautare ii va corespunde, alt fisier asociat.

Tastand USE se inchide fisierul PONTAJ, FOX-ul gestionand relatia cu PONTAJ.IDX.

Utilizatorului ii revine sarcina sa retina doar identificatorul fisierului asociat.

3. CAUTAREA INDEXATA - DIRECTA.

Fiind creat fisierul asociat PONTAJ.IDX, ne propunem sa cautam inregistrarea care corespunde lunii a 10 - a si marcii

Aceste valori le preluam in variabile de lucru :

L=10

M=2001 Apoi formez cheia de cautare :

CH=STR(L,2)+STR(M,4) Activam PONTAJ.DBF specificand si fisierul sau

asociat creat in pasul 2

USE PONTAJ INDEX PONTAJ

SEEK CH Comanda de cautare : SEEK <cheie de cautare>

Tastand :

? FOUND() se va afisa .T. sau .F. dupa cum inregistrarea cautata a fost identificata sau nu (cautare cu succes sau fara succes).

In cazul afisarii .T. poate urma :

DISPLAY pentru afisarea inregistrarii cautate si aflate.

Pentru o alta cautare (alte valori ale cheii), reluam cu atribuiri de noi valori lui L si M etc.

La sfarsit : USE

Stimate cititor, daca sunteti incepator, OBERVATI va rog , cum am construit CHEIA DE INDEXARE in pasul 2 si cum am construit CHEIA DE CAUTARE in pasul 3.

In cheia de indexare am folosit nume de campuri din structura fisierului de date, pe cand in cheia de cautare am introdus variabilele de lucru in care am preluat valorile concrete dupa care voi efectua cautarea. Dar ordinea in care am introdus Campurile in cheia de indexare, are importanta pentru constructia cheii de cautare ? Fireste ca DA !.

De asemenea, observati si lungimile utilizate in functiile STR() !.

O alta preocupare pentru utilizatorul unei astfel de tehnici de cautare trebuie sa fie ACTUALIZAREA fisierului asociat la fiecare modificare in fisierul DBF (stergeri de inregistrari, adaugari de inregistrari noi, modificari ale valorilor cheii de indexare (asociere). Acest lucru se va putea realiza utilizand comanda REINDEX (vezi bibliografia !).

Pana castigati experienta si cunostinte suficiente, imi permit o recomandare practica :

Aveti de efectuat mai multe cautari (directe) pentru mai multe inregistrari ; urmati cei 3 pasi de mai sus, adica :

Generati fisierul asociat in faza imediat PREMERGATOARE cautarii. Apoi procedati la cautarile dorite. In acest fel sunteti asigurat de 'concordanta' intre fisierul de date si cel asociat.

Capitolul cautarilor indexate este foarte amplu si consistent tratat in majoritatea cartilor de FOXPRO. Pe unele le-am introdus in bibliografie. Dintre acestea amintim FOXPRO 2.5 2.6 de G DIMA si M DIMA Ed TEORA 1997 cap 2.9.2. 'Indexarea tabelelor'.

Dintre avantajele acestei metode mentionam timpul de acces la o inregistrare care este foarte mic. Dezavantaje, daca pot fi astfel calificate, sunt necesitatea intretinerii corecte a fisierelor asociate, cresterea corespunzatoare a numarului acestor fisiere odata cu inmultirea tipurilor de cautare (cheilor de cautare).

In 'ARTA PROGRAMARII CALCULATOARELOR' de KNUTH, volumul 'SORTARE si CAUTARE' sunt descrisi algoritmi de cautare performanti care programati de utilizator ii pot mari acestuia eficienta procedurilor de cautare, pana la timpi comparabili cu cei ai cautarii indexate oferite de FOX. Merita incercat !!!

03. CAUTAREA PRIN INJUMATATIREA INTERVALULUI .

Sistemul FOX ne pune la dispozitie 2 tehnici de cautare : secventiala si directa (indexata) despre care am luat cunostinta mai sus. Cititorul care doreste o solutie, alta decat cele 2 prezentate, poate mai eficienta, dar sigur instructiva si cu grad inalt de satisfactie intelectuala, este indemnat sa citeasca atent capitolul prezent.

Formularea problemei.

Se da un sir oarecare de numere intregi si distincte :

in care se cere se cere sa cautam pe acela care are o valoare V.

Astfel pusa problema, rezolvarea ei este posibila dar intr-un numar mare de pasi.

O solutie mai 'desteapta' se poate da, daca sirul dat este ORDONAT CRESCATOR, de exemplu. Pentru ordonarea unui sir de numere exista algoritmi studiati, probabil, si de dumneavoastra. Deci putem presupune ca problema de mai sus este reformulata astfel :

Sa se stabileasca daca nu numar V se afla printre termenii unui sir ordonat crescator :

A1 < A2 < A3 < . < Ai < . < An-1 < An

In aceasta situatie avem 4 cazuri banale :

Daca V < A1, cautarea este terminata fara succes.

Daca V > An, cautarea este terminata fara succes.

Daca V=A1, cautarea este cu succes si A1 = V

Daca V=An, cautarea este cu succes si An = V

Asupra cazului A1 < V < An vom starui mai mult.

Intai trebuie sa facem distinctie intre valorile termenilor sirului dat si indicii acestor termeni .

Exemplu :

Sirul de numere : 11, 13, 14, 25, 29, 30, 45, 105, 200, 1003

Indicii termenilor: 1 2 3 4 5 6 7 8 9 10

Sa vedem cum putem stabili daca V=200 se afla printre termenii sirului .

Evident : 11 < 200 < 1003

PAS 1

Caut 'jumatatea intervalului' indicilor : (1 + 10) / 2 = 5.5

Partea intreaga a jumatatii intervalului este 5.

La indicele 5 corespunde termenul cu valoarea 29.

Compar V=200, cu 29

V = NU !

V < NU !

V > DA !

Pentruca , acum, 29 < 200 < 1003,

retin indicii limitelor inferioara si superioara : 5 respectiv 10

PAS 2

Partea intreaga pentru jumatatea intervalului : (5 + 10) / 2 = 7.5 , este 7.

Indicelui 7 ii corespunde termenul 45.

Din compararea V=200 cu 45 rezulta V > 45, deci

45 < 200 < 1003

Retin indicii 7 si 10.

PAS 3

Jumatatea intervalului este partea intreaga pentru (7 + 10) / 2 adica

indicele 8. Acestui indice ii corespunde 105.

Valoarea cautata 200 o compar cu 105 si rezulta ca este mai mare ca 105 adica :

105 < V < 1003

Termenii 105 si 1003 au indicii 8 respectiv 10.

PAS 4

Jumatatea intervalului indicilor 8 si 10 este (8 + 10) / 2 = 9

La indicele 9 corespunde termenul 200. Comparand V cu termenul indicelui 9 (deci cu 200) si constatand egalitatea, CAUTAREA s-a TERMINAT CU SUCCES si raspunsul pentru exemplul de mai sus este ca A9 este termenul cautat.

Si pe exemplul de mai sus putem constata urmatoarele :

Daca am fi inceput cautarea prin compararea lui V (200) cu primul termen al sirului, apoi cu al doilea, etc pana la al noulea care reprezenta valoarea cautata, am fi efectuat mai multe operatii decat prin tehnica injumatatirii succesive a intervalului de cautare (4 injumatatiri).

Sa vedem care ar fi fost pasii pentru cautarea in sirul din exemplul anterior daca valoarea V ar fi fost 205 care nu se afla printre termenii sirului

Primii 3 pasi ar fi fost identici cu cei anteriori .

PAS 4.

Jumatatea intervalului indicilor 8 si 10 este (8 + 10) / 2 = 9

La indicele 9 corespunde termenul 200. Comparand V cu termenul indicelui 9 (deci cu 200 am fi constatat ca 200 < V < 1003.

Retinand indicii pentru 200 si 1003 care sunt 9 respectiv 10, si injumatatind intervalul obtinem (9 + 10) / 2 = 9.5

Partea intreaga va fi 9. Valoarea termenului cu indice 9 este 200 si deci :

200 < V < 1003. Am ajuns in situatia de mai inainte !!!

Deci urmand metoda de mai sus nu pot da raspunsul ca V=205 nu se afla in sir .

!!! Metoda folosita, nu este PROPRIUZIS un algoritm. Deci ea trebuie ameliorata pana la a deveni un algoritm ! Asa cum a fost prezentata in exemplu, 'tehnica' utilizata nu are proprietatea de FINITUDINE sau de eficacitate !

03.1 Algoritmul CAUTARII BINARE (prin injumatatirea intervalului).

Reprezentam grafic situatia de start in care A1 < V < An

LI=1 INT( (1+n)/2)=I LS=n

A1 Ai An

FIGURA 09. Injumatatirea intervalului de cautare.

V fata de Ai se poate afla in 3 situatii, 1: in Ai, 2: la stanga lui Ai sau 3: la dreapta lui Ai

Cazul 1: Ai = V, cautare terminata cu succes.

Cazul 2: A1 < V < Ai

LI=1 LS=I-1

A1 Ai-1

Cazul 3: Ai < V < An

LI=I+1 LS=n

Ai+1 An

FIGURA 091. Continuarea cautarii in subintervale.

Prezentam mai intai algoritmul de cautare binara .

Introducem variabilele Li, Ls ca limite inferioara si superioara pentru intervalul indicilor in care urmeaza sa efectuam cautarea :

PAS 1

Li = 1

Ls = n

PAS 2

DACA Ls este mai mic decat Li, cautarea s - a terminat fara succes. STOP.

In caz contrar, injumatatim intervalul indicilor : I=INT((LI + LS)/2) (FIG. 09)

In cazul exemplului nostru, I = 5

PAS 3

Daca V = Ai, cautarea este terminata cu succes. STOP.

In caz contrar,

Daca V < Ai, urmeaza pasul 4, Daca V > Ai, urmeaza pasul 5.

PAS 4

Ls = I - FIG 091 cazul 2)

Apoi reiau cu pasul 2.

PAS 5

Li = I + FIG 091 cazul 3)

Apoi reiau cu pasul 2.

Si acum sa vedem conform algoritmului de mai sus raspunsurile la cautarea in sirul din exemplu a valorilor 200 si 205

Cazul : V = 200

Evident : 11 < 200 < 1003

Li = 1

Ls = 10 si

Li > Ls ? NU

I = INT((1 + 10)/2) = 5

V = A5 ? NU.

V < A5 ? NU.

V > A5 ? DA, deci cf pasului 5,

Li = I + 1 = 6

Ls = 10

Li > Ls ? NU

I = INT(( 6 + 10)/2)=8

V = A8 (200 = 105 NU

V < A8 ? NU

V > A8 ? DA

Li = I + 1 = 9

Ls = 10

Li > Ls ? NU

I = INT((9 + 10)/2) = 9

V = A9 ? DA, STOP. CAUTAREA s-a TERMINAT cu SUCCES.

Dar in cazul : V = 205 ?

Algoritmul se desfasoara analog pana in pasul subliniat (ingrosat) de mai inainte.

Li = 9 Ls < Li ? NU

Ls = 10

I = INT((10+10)/2) = 10

Ls < Li ? NU (acum : li = 10, ls = 10, I = 10 )

V = A10 ? NU

I = INT((9 + 10)/2) = 9 V < A10 ? DA urmeaza :

V = A9 ? NU

V > A9 ? DA Ls = I - 1 = 9

Li = 10

Li = I + 1 = 10 continuare in

Ls = 10 dreapta si deja Ls < Li, cautarea s-a terminat fara succes.

Ls < Li ? DA, STOP. Cautarea este fara succes, deci V = 205 nu se afla printre termenii sirului.

Asimiland sirului A1, A2, A3, . , An valorile cheii de cautare intr-un fisier de date, si indicilor 1,2,3, . , n valorile 'indicatorului de inregistrare' vom avea o corespondenta biunivoca intre valorile cheii si valorile indicatorului de inregistrare. Acest lucru ne va permite cautarea unei inregistrari identificata prin valoarea cheii V, in fisierul de date care, evident, in prealabil a fost sortat crescator dupa coloana (coloanele) reprezentand cheia de cautare.

Unul din dezavantajele acestei tehnici este necesitatea sortarii fisierului de date inaintea procesului de cautare.

Ca avantaj, autorul considera pe baza utilizarii acestui algoritm in fisiere de ordinul a sute de mii de inregistrari, timpul redus de cautare. Numarul maxim de injumatatiri pe care le - am contorizat a fost de

Timpul de cautare si afisarea raspunsului, a fost comparabil cu cel al cautarii indexate !.

Invit cititorul, care m-a inteles, sa identifice si alte avantaje/dezavantaje fata de tehnica de cautare indexata.

Bibliografie : Donald E. Knuth : Arta programarii calculatoarelor, Volumul 3 SORTARE si CAUTARE. (La ora redactarii acestui curs, in Ed TEORA au reaparut primele 3 volume ale acestei carti.)