05.01.2010 10:33
[#1]
Przeszukiwanie tablicy
Czy istniej sposób szybszy niż bajt po bajcie przeszukiwania tablicy by znaleźć określony string? Jeśli tak to jaki i proszę o krótki opis, bo c++ dopiero się uczę.
05.01.2010 12:41
[#5]
Re: Przeszukiwanie tablicy
@ZED^lM, post #1
Witam,
Zależy w jaki sposób dane z tablicy są rozmieszczone i jak często chcesz dany napis przeszukiwać ( czy to jest kluczowe w programie ).
Z takich łatwych trików to jeśli szukany string jest przeważnie na końcu napisu to lepsza jest funkcja przeszukująca od końca napisu.
Jeżeli dany tekst chcesz przeszukiwać wiele razy to można rozważyć zamianę formatu danych, przenosząc ciężar wielokrotnego szukania na funkcję, która przejrzy raz dane umieszczając je w innym, lepszym formacie danych ( na ten przykład mapa będzie dosyć dobra ).
Jeżeli dane nie zmieniają się ( czyli zawsze wczytujesz plik, który nigdy się nie zmienia ) to tak naprawdę nie musisz szukać tego napisu, wystarczy to zrobić raz i zapisać sobie. Niestety to podejście ma jedyną wadę, którą bardzo szybko odkryjesz gdy ten plik się zmieni :)
Pozdrawiam
Zależy w jaki sposób dane z tablicy są rozmieszczone i jak często chcesz dany napis przeszukiwać ( czy to jest kluczowe w programie ).
Z takich łatwych trików to jeśli szukany string jest przeważnie na końcu napisu to lepsza jest funkcja przeszukująca od końca napisu.
Jeżeli dany tekst chcesz przeszukiwać wiele razy to można rozważyć zamianę formatu danych, przenosząc ciężar wielokrotnego szukania na funkcję, która przejrzy raz dane umieszczając je w innym, lepszym formacie danych ( na ten przykład mapa będzie dosyć dobra ).
Jeżeli dane nie zmieniają się ( czyli zawsze wczytujesz plik, który nigdy się nie zmienia ) to tak naprawdę nie musisz szukać tego napisu, wystarczy to zrobić raz i zapisać sobie. Niestety to podejście ma jedyną wadę, którą bardzo szybko odkryjesz gdy ten plik się zmieni :)
Pozdrawiam
05.01.2010 12:54
[#7]
Re: Przeszukiwanie tablicy
@Grzegorz Kraszewski, post #6
moze i nieco za szybko odpowiedzialem, ale i tak uwazam, ze jezeli wyszukiwanie tekstu nie jest glownym zadaniem aplikacji to nie ma sie co rozwodzic tylko uzyc gotowca. kiedys szukalem algorytmui dla amibenta i znalazlem takie cos (zmodyfikowany algorytm bayera-moorea, maly narzut na inicjalizacje i pamiec. tuned bayer-moore) na stronie: http://www-igm.univ-mlv.fr/~lecroq/string/index.html) powinno wyczerpac temat
05.01.2010 14:10
[#8]
Re: Przeszukiwanie tablicy
@kiero, post #7
Jeśli do przeszukania mamy mały plik to przeszukiwanie bajt po bajcie - żaden problem. Problem pojawia się wtedy gdy zaczniemy przeszukiwać plik o wielkosci 10, 20 lub większej liczbie mb. Otóż jestem w trakcie pisania (w ramach nauki c++) programu do odczytywania informacji o plikach wav. Przeglądając pliki wav zauważyłem, że nie które znich mają dodatkowe informacje np. o programie za pomocą którego dokonano obrubki jego i te informacje są zawarte na końcu pliku po stringu "LIST" - przyrostek do pliku.
05.01.2010 14:31
[#11]
Re: Przeszukiwanie tablicy
@ZED^lM, post #8
jezeli wiesz jaka strukture ma plik to mozesz zoptymalizowac wyszukiwanie. to chyba oczywiste. jezeli nie wiesz co jest w pliku to musisz przeleciec go od poczatku do konca (i to robia wszystkie algorytmy wyszukujace). ogolnie zbytnio bym sie tutaj algorytmem nie przejowal bo i tak wczytanie pliku do pamieci zabierze najwiecej czasu (przy tak krotki wyszukiwanym tekscie).
06.01.2010 10:29
[#15]
Re: Przeszukiwanie tablicy
@Grzegorz Kraszewski, post #13
Witam,
Ja jakoś nie mogę się do tego przekonać, że przyzwoity kompilator generuje szybki kod. Z moich doświadczeń szala przechyla się bardziej ku asemblerowi. Ale to może być kwestia moich umiejętności pisania w C + kwestia jak przyzwoity kompilator jest.
Pozdrawiam
Ja jakoś nie mogę się do tego przekonać, że przyzwoity kompilator generuje szybki kod. Z moich doświadczeń szala przechyla się bardziej ku asemblerowi. Ale to może być kwestia moich umiejętności pisania w C + kwestia jak przyzwoity kompilator jest.
Pozdrawiam
07.01.2010 01:04
[#18]
Re: Przeszukiwanie tablicy
@ZED^lM, post #1
Oto kilka podpowiedzi z mojego doświadczenia:
1. Dobra implementacja w C/C++ algorytmu Boyer-Moore w większości przypadków w zupełności wystarczy (tzn. jest zadawalająca czasowo) i nie ma po co sięgać do assemblera - choć oczywiście teoretycznie da się w ten sposób przyspieszyć każdy algorytm
2. Pisze teoretycznie bo w przypadku przeszukiwania plików na całkowity czas wykonania ma jeszcze wpływ system operacyjny i sam hardware. W systemach multitaskingowych aplikacja nie będąca jądrem systemu nie ma wpływu na wszystkie czynniki.
3. Optymalizacja kodu asemblerowego na procesory powyżej rodziny m68k wcale nie musi być łatwa i może zająć więcej czasu niż dopracowanie innych elementów pisanego programu.
4. Zazwyczaj plik ma jakąś minimalną długość od której zaczyna się szukany przez nas string. Najlepiej więc przesunąć wskaźnik pliku i od tego offesetu rozpocząć przeszukiwanie.
5. Standardowe funkcje z rodziny str poza tym że nie są dzisiaj zalecane to mają jedno poważne ograniczenie: działają na stringach w rozumieniu C - czyli ciągu znaków zakończonego . Nie nadają się więc do blików binarnych.
1. Dobra implementacja w C/C++ algorytmu Boyer-Moore w większości przypadków w zupełności wystarczy (tzn. jest zadawalająca czasowo) i nie ma po co sięgać do assemblera - choć oczywiście teoretycznie da się w ten sposób przyspieszyć każdy algorytm
2. Pisze teoretycznie bo w przypadku przeszukiwania plików na całkowity czas wykonania ma jeszcze wpływ system operacyjny i sam hardware. W systemach multitaskingowych aplikacja nie będąca jądrem systemu nie ma wpływu na wszystkie czynniki.
3. Optymalizacja kodu asemblerowego na procesory powyżej rodziny m68k wcale nie musi być łatwa i może zająć więcej czasu niż dopracowanie innych elementów pisanego programu.
4. Zazwyczaj plik ma jakąś minimalną długość od której zaczyna się szukany przez nas string. Najlepiej więc przesunąć wskaźnik pliku i od tego offesetu rozpocząć przeszukiwanie.
5. Standardowe funkcje z rodziny str poza tym że nie są dzisiaj zalecane to mają jedno poważne ograniczenie: działają na stringach w rozumieniu C - czyli ciągu znaków zakończonego . Nie nadają się więc do blików binarnych.
19.01.2010 18:25
[#19]
Re: Przeszukiwanie tablicy
@68k_tester, post #17
Ale tu zapewne chodzi ZEDowi^IM o wydajny algorytm (czyli o niskim koszcie). W tym wypadku różnica szybkości działania między kodem asemblerowym a językiem C jest znikoma. Jesli dobrze rozumiem, to autor wątku chce wyszukać zadanego stringu w tekście. Myślę, że dobrze jest tu wykorzystać tzw. funkcję haszującą, która zamienia wyrazy na liczby. Polega to na tym, że wyszukujesz w tekście wyrazów (oddzielonych białymi znakami) i zapisujesz do tablicy, przy czym jako indeks w tej tablicy obierasz wartość zwróconą przez funkcję haszującą. Teraz żeby sprawdzić czy dany wyraz znalazł się w tekście liczysz wartość hash tej liczby i porównujesz ze wszystkimi stringami o tym indeksie. Koszt sprawdzenia, czy dany wyraz znalazł się w tekście w tym systemie jest rzędu O(1) (czyli jest stały) dla bardzo dobrej funkcji haszującej.
21.01.2010 22:14
[#22]
Re: Przeszukiwanie tablicy
@Minniat, post #19
Minniat napisał(a):
> Ale tu zapewne chodzi ZEDowi^IM o wydajny algorytm (czyli o
> niskim koszcie). W tym wypadku różnica szybkości działania
> między kodem asemblerowym a językiem C jest znikoma. Jesli
> dobrze rozumiem, to autor wątku chce wyszukać zadanego stringu
> w tekście. Myślę, że dobrze jest tu wykorzystać tzw. funkcję
> haszującą, która zamienia wyrazy na liczby. Polega to na tym,
> że wyszukujesz w tekście wyrazów (oddzielonych białymi znakami)
> i zapisujesz do tablicy, przy czym jako indeks w tej tablicy
> obierasz wartość zwróconą przez funkcję haszującą. Teraz żeby
> sprawdzić czy dany wyraz znalazł się w tekście liczysz wartość
> hash tej liczby i porównujesz ze wszystkimi stringami o tym
> indeksie. Koszt sprawdzenia, czy dany wyraz znalazł się w
> tekście w tym systemie jest rzędu O(1) (czyli jest stały) dla
> bardzo dobrej funkcji haszującej.
>
Tak dokładnie chodzi mi o szybki algorytm. Im szybszy tym lepszy.
> Ale tu zapewne chodzi ZEDowi^IM o wydajny algorytm (czyli o
> niskim koszcie). W tym wypadku różnica szybkości działania
> między kodem asemblerowym a językiem C jest znikoma. Jesli
> dobrze rozumiem, to autor wątku chce wyszukać zadanego stringu
> w tekście. Myślę, że dobrze jest tu wykorzystać tzw. funkcję
> haszującą, która zamienia wyrazy na liczby. Polega to na tym,
> że wyszukujesz w tekście wyrazów (oddzielonych białymi znakami)
> i zapisujesz do tablicy, przy czym jako indeks w tej tablicy
> obierasz wartość zwróconą przez funkcję haszującą. Teraz żeby
> sprawdzić czy dany wyraz znalazł się w tekście liczysz wartość
> hash tej liczby i porównujesz ze wszystkimi stringami o tym
> indeksie. Koszt sprawdzenia, czy dany wyraz znalazł się w
> tekście w tym systemie jest rzędu O(1) (czyli jest stały) dla
> bardzo dobrej funkcji haszującej.
>
Tak dokładnie chodzi mi o szybki algorytm. Im szybszy tym lepszy.