AVR-GCC i operacje na stringach

On Sat, 10 Jul 2004 01:25:50 GMT, "Grzegorz"

A te stringi to sa podobnej dlugosci ? Bo moze miec sens nie dwuwymiarowa tablica, tylko stringi po kolei i tablica adresow. Albo po tablicy tablicy na kazda dlugosc - od razu ci sie skraca przeszukiwanie.

Jesli ma byc szybko - to poczyczaj o przeszukiwaniu binarnym [binary search, bsearch]. I raczej nie uzywaj strcmp, bo wywolanie funkcji to narzut wiekszy niz ustalenie ze sie stringi roznia - a zazwyczaj beda sie na pierwszym znaku roznic. Poza tym w AVR pewnie jeden string bedzie w ROM. Wpisz wszystko w jednej funkcji i zdaj sie na optymalizator.

Dodatkowo .. mozna spakowac te stringi. Liter jest tylko ~26, w int wejda trzy litery naraz, mozna tez na jakims ciekawszym hashem pomyslec, zeby wszystkie te 150 slow zapakowac w 16 bit..

J.

W artykule <yAHHc.28202$ snipped-for-privacy@news.chello.at> autorem którego mieni się Grzegorz, napisano:

Poczytaj o bsearch (deklaracja w stdlib.h). Tablica napisów musi zawierać elementy posortowane. Dla <= 255 napisów wystarczy co najwyżej 8 porównań (wywołań strcmp) do znalezienia napisu lub stwierdzenia, że nie ma go w tablicy.

Na jakich stringach? Zwyklych prymitywnych char*, czy tez na std::string (nie wiem czy piszesz w C czy w C++)? Poza tym co rozumiesz przez standardowe operacje -- porownywanie i konkatenacja?

Co to jest wzorzec? Wyrazenie regularne?

Czyli zwykle wyszukiwanie stringa w tablicy? Mozliwosci jest wiele, w zaleznosci od Twoich checi i umiejetnosci:

1. Utrzymywanie posortowanej tablicy, wyszukiwanie binarne. Metoda ta ma pesymistyczna zlozonosc logarytmiczna.

1,5: wyszukiwanie binarne interpolacyjne.

1. Hashowanie z adresowaniem otwartym (skoro koniecznie ma byc prosta tablica).

2. Hashowanie z dowiazywaniem.

1. Drzewa DST i prefiksowe; Trie, w szczegolnosci Patricia.

2. Mozesz tez te tablice zamienic na automat skonczony

-- wyszukiwanie bedziesz mial najszybsze mozliwe, ale chyba skorka jest niewarta wyprawki...

Zwykle wyszukiwanie binarne bedzie w tym przypadku wymagalo

8 porownan. Czy to jest dostatecznie szybko? Jesli nie, to sprobuj hashowania: 2--3 powownania + koszt obliczenia funkcji hashujacej. Jesli razem z kazdym stringiem mozesz pamietac rowniez jego wartosc funkcji hashujacej, to "pelnoskalowe" porownywanie musisz wykonywac tylko gdy hash(str_1) == hash(str_2). Poniewaz taka sytuacja jest bardzo nieprawdopodobna, da Ci to gigantyczne przyspieszenie czasu porownan. Sam uzywam czegos takiego (+ cache w postaci przenoszenia czesto wyszukiwanych stringow na poczatek list hashujacych).

W pesymistycznym przypadku nie.

Pozdrawiam Piotr Wyderski

Chyba tym wyszukiwaniem binarnym sie zajme. Stringi maja stala dlugosc - 16 znakow, nie zmieniaja sie w czasie pracy, i sa posortowane. 8 porownan to nie 150, wiec jest to bardzo dobry wynik. A co do predkosci - zalezy mi, aby cala operacja zajela mniej niz ok 2ms od wywolania funkcji do zwrocenia True lub False. To bedzie prawdopodobnie na ATMega32 16Mhz /ogolnie AVR, z ramem

Dziekuje wszystkim za pomoc. Pozdrawiam Grzegorz

On Sun, 11 Jul 2004 10:37:09 GMT, "Grzegorz"

A skad te stringi pochodza ? [wesze odciski palcow ?] Bo na oko to bardzo warto jakiegos hasha rozwazyc.

Przy dobrej optymalizacji to na oko nawet zwykle liniowe by sie zmiescilo w 2 ms :-) Ale binarne to niewielka komplikacja, wiec czemu nie.

mozesz tez sprobowac po pierwszej [albo po innej] literze indeks zrobic - od razu trafiasz do wlasciwej czesci tablicy, a potem zostaje kilka wpisow do sprawdzenia..

J.

Te stringi to tekst, ktory ma byc wyswietlany na LCD. Stad 16 znakow (oczywiscie pozostaje problem czy na koncu krotszych napisow maja byc spacje dopelniajace do rownych 16 znakow, ale to nie ta bajka). Najwazniejsze, to znalezc odpowiedni string w tablicy.

Owszem, ale jesli wszystko bede musial zmiescic w AVRze, z 2048 kB ramu, to moze braknac na dodatkowe tablice i zmienne.

A co do hashowania - nie wiem, czy sie uda, poniewaz cala tablica w ktorej dokonuje wyszukiwania zostaje wczytana na poczatku programu z zewnetrznego eproma, zatem w czasie kompilacji klucze nie sa znane. Chyba, ze jakos dynamicznie to wszystko sie da... ale w tym dobry nie jestem.. Pozdrawiam Grzegorz

Hehe, przeciez 2ms to jest trudna do wyobrazenia sobie kupa czasu. ;-) Aby sie w tym czasie nie zmiescic, to nie wiem, chyba bys to musial w Bascomie napisac. ;-)

Ale skoro dopuszczasz taka mozliwosc, ze ta tablica jest posortowana, to kiedys musial nastapic proces tego sortowania. Co za problem dorzucic do tej procedury obliczanie funkcji hashujacej? Tylko jesli sie juz zdecydowales na wyszukiwanie binarne (co jest bardzo dobrym wyborem, lecz pomysl jeszcze nad wyszukiwaniem _interpolacyjnym_ -- dziala tak samo, ale nie dzieli sie tablicy dokladnie w srodku, lecz na podstawie wartosci danych wejsciowych probuje sie zgadnac w ktorym mniej wiecej miejscu ma szanse znajdowac sie szukany obiekt. Podobnie jak przy wertowaniu ksiazki telefonicznej osob z nazwiskiem na P nie bedziesz szukal blisko jej poczatku. Przy zalozeniu sensownego rozkladu wystepowania stringow pozwala to osiagnal zlozonosc O(log log n) zamiast O(log n). Z drugiej strony wymaga ona dzielenia calkowitego, wiec dla danych o podanym przez Ciebie rozmiarze moze buc nawet wolniejsza...), to nie kombinuj z hashowaniem; aby dobrze polaczyc obie rzeczy trzeba sie troche znac na algorytmice. Tak wiec albo wyszukiwanie binarne, albo hashowanie.

Oczywiscie, inaczej by to nie mialo wielkiego sensu. :-)

Dlatego zostan przy wyszukiwaniu binarnym.

Pozdrawiam Piotr Wyderski

On Sun, 11 Jul 2004 12:07:16 GMT, "Grzegorz"

Nie bardzo rozumiem .. nadchodzi ci z jakiegos zrodla tekst, chcesz wyszukac ktora to pozycja w tablicy tekstow zeby go wyswietlic na wyswietlaczu ? To wyswietl to co przyszlo.

Ty masz chyba zupelnie odwrotny problem - jak pobrac z tablicy tekst nr 46 ?

Tym bardziej - zamiast przepisywac calosc do ram obliczasz hasha, i w RAM zapisujesz juz tylko wartosci hashy. tablica nie zajmuje ci

110*16 tylko 110*2, albo 110*4.

J.