Witam. Mam taki tyci problem. Napisałem program, bazę danych we własnym formacie (struktura i zapis do plików niezdefiniowanych). Wszystko było pięknie do czasu, kiedy rozmiar bazy trochę się powiększył (do ok. 10M). I teraz moje pytanie: czy istnieją jakieś metody szybszego dostępu do danych w pliku? Np. jakaś metoda indeksowania czy coś takiego jak to ma miejsce np. w bazach danych typu dBase lub Paradox. Ogólnie chodzi mi o szybki dostęp do danych zawartych w dużym rozmiarowo pliku.
Z góry thx.
0
0
Witaj,
Czy chodzi Ci o szybsze wyszukiwanie odpowiedniego rekordu? Bo jesli tak to proponuje ksiazki pana Goczyły pt. "Struktury Danych" lub "Metody indeksowania w obiektowych bazach danych".
Pozdrawiam,
Wodzu
Ps. "Struktury Danych" kosztuja 14 zl a mozesz je zamowic tutaj: http://www.pg.gda.pl/WydawnictwoPG/ :)
0
Dzieki, o to mi właśnie chodzi, pędze do księgarni... A może jakieś infa na www?
0
Podalem Ci linka do strony gdzie mozesz to zamowic nie wychodzac z domu:)
Co do informacji na WWW to pewnie gdzies cos takiego znajdziesz ale gdzie to ja juz nie wiem...
Wpisz w przegladarce hasla "hashing", "tablice hashowane".
W "Strukturach Danych" masz kilka algorytmow wraz z omowieniem ich wad i zalet. Chetnie bym Ci podyktowal co i jak ale niestety nie mam ksiazki przy sobie a program z uzyciem owych algorytmow pisalem rok temu i nie bardzo pamietam;) Mniej wiecej chodzi jednak o cos takiego:
Zalozmy ze masz 1000 rekrodow.
Przykladowy rekord:
Rekord[1].Imie:="Zosia"
Rekord[1].Nazwisko:="Samosia"
Rekord[1].Wiek:=23
Rekord[1].Adres:="Warszawa ul. Kogostam 23/5"
Aby odnalezc ten rekord w bazie normalnie musilabys przeszukac od 1 do 1000 rekordow i porownac kazde z pol tych rekordow. Z tego co pamietam to srednia ilosc przeszukiwanych rekordow jest rowna n/2 gdzie n to liczba rekordow w Twej bazie. Wiec musisz przeszukac 500 rekrodow i porownac je z szukanym co zaczyna zajmowac sporo czasu przy wiekszej bazie.
Proces wyszukiania mozesz bardzo przyspieszyc stosujac tak zwany klucz. Uzywajac klucza dla tej przykladowej bazy musialbys przeszukac okolo 4 rekordow...(jest to zalezne od rodzaju algorytmu).Co wiecej gdy baza rosnie liczba rekordow , ktore musisz przeszukac aby znalezc wlasciwy rosnie nieznacznie(dla pewnych algorytmow).
Czym jest ów klucz?
Klucz jest ciagiem znakow/cyfr tworzonym przez tak zwana funkcje hashujaca(mieszajaca). Funkcja ta generuje klucz na podstawie rekrodow w Twej bazie. Dla kazdego rekordu oddzielnyu klucz, ktory powinien byc niepowtarzalny. W praktyce jednak klucze czesto sie powtarzaja i dlatego zwieksza sie liczba przeszukanych rekrodow zanim znajdziesz ten wlasciwy. Oczywiscie moglbys stworzyc bardzo dlugi niepowtarzalnhy klucz ale mija sie to raczej z celem...(wymagania pamieciowe).
Ciagle zakladamy ze mamy baze skladajaca sie z 1000 rekrodow. Twoim zadaniem bedzie stworzenie funkcji haszujacej ktora dla kazdego z tych rekrodow wygeneruje liczbe z przedzialu od 1-1000.
Liczba ta bedzie jednoczesnie oznaczac polozenie danego rekordu w Twojej tablicy. Dzieki temu gdy zechcesz wyszukac jakis rekord, Twoja funkcja stworzy po prostu do niego klucz i od razu skoczy do miejsca w tablicy. Proste nie? Warunkiem jest aby Twoja funckja hashujaca zawsze generowala ten sam klucz dla danego rekordu. Wybor wlasciwej funkcji ma duzy wplyw na czas wyszukiwania rekordu.
Jak sie taka funkcje tworzy? Moze ona dzialac na przyklad w ten sposob:
- Dodaje wszystkie pola Twojego rekordu i tworzy z nich jeden ciag.
- Z tego ciagu wybiera co trzeci znak i zamienia go na kod ASCI.
3.Dodaje wszystkie kody do siebie. - Otrzymana liczbe dzieli tak aby wynik dzielenia zawieral sie miedzy 1-1000.
W Delphi mamy sprawe jeszcze prostsza. Z tego co pamietam to istnieje funkcja Seed gdzie jako ziarno generatora mozesz podac np liczbe utworzona z dodania wszystkich znakow z Twojego rekordu przetworzonych na kod ASCI. Nastepnie robisz tylko NrIndeksu:=Random(1000)+1 i otrzymnujesz indeks w tablicy dla danego rekordu. Musisz pamietac by za kazdym razem zmieniac ziarno generatora.
A co gdy masz dwa bardzo podobne do siebie rekordy w teblicy?
Np.
Rekord.Imie:="Zosia"
Rekord.Nazwisko:="Samosia"
Rekord.Wiek:=23
Rekord.Adres:="Warszawa ul. Kogostam 23/5"
i
Rekord.Imie:="Zofia" <--niewielka zmiana
Rekord.Nazwisko:="Szamosia" <-- niewielka zmiana
Rekord.Wiek:=23
Rekord.Adres:="Warszawa ul. Kogostam 23/5"
Istnieje duze prawdopodobienstwo ze klucze wygenerowane dla tych rekordow beda identyczne. Tym bardziej jesli bedzie to mala tablica, np 10 elemetowa, wtedy mozesz byc prawie pewien ze dostaniesz dwa takie same klucze. Co wtedy robic? Przeciez nie mozesz wstawic dwóch rekrodow do tego samego miejsca w tablicy...
Jedna z metod radzenia sobie z tym problemem jest taka, ze Twoj rekord musi jeszcze zwierac jedno pole. A mianowicie pole w ktorym jest przechowywany klucz nastepenego rekordu w tablicy, Postaram sie to wyjasnic jasniej.
- Funkcja generuje klucz dla pierwszego rekordu, otrzymnujesz np liczbe 235.
- Rekord zostaje wstawiony do tablicy i znajduje sie pod indeksem o numerze 235.
- Funkcja generuje klucz dla drugiego rekordu, otrzymnujesz ZNOWU liczbe 235.
- Nastepuje proba wstawienia tego rekordu do tablicy ale miejsce jest juz ZAJETE.
- Rekord zostaje wstawiony do pierwszego wolnego miejsca w tablicy np 239 i jednoczesnie w rekordzie o indeksie 235 znajduje sie informacja, ze pod indeksem 239 zostal zapisany kolejny rekord o takim samym kluczu.
Wada tej metody jest to ze musisz miec w kazdym z rekordow jeszcze jedno dodatkowe pole co zajmuje troche pamieci.
Kazda z metoda ma jakies wady i zalety, wybor nalezy do Ciebie. O innych metodach mozesz poczytac w ksiazce ktorej tytul Ci podalem.
Mam nadzieje, ze chociaz troszke rozjasnilem Ci w glowie. Przepraszam ze post wyszedl taki dlugi.
Pozdrawiam,
Wodzu
0
wielkie dzieki, juz sobie (prawie) poradze... Przyjamniej wiem czego sie czepic ;)
0
wielkie dzieki, juz sobie (prawie) poradze... Przyjamniej wiem czego sie czepic ;)
Domyslam sie, ze moje wyjasnienia byly nieco metne;) ale na pewno cos Ci sie uda zdzialac, jakby co to pytaj smialo;P
Powodzenia,
Wodzu