AVR-GCC i operacje na stringach



Masz problem? Zapytaj na forum elektroda.pl

Poprzedni Następny
Wiadomość
Spis treści
From: "Grzegorz" <w_o_d_e_k_at_nospam__at_nospam_poczta.onet.pl>
Subject: AVR-GCC i operacje na stringach
Date: Sat, 10 Jul 2004 01:25:50 GMT


Czy sa w AVR-GCC jakies funkcje przyspieszajace standardowe operacje na
stringach? Chodzi o wyszukanie w tablicy stringow stringa o podanym wzorcu.
Czyli funkcja ktora pobiera 2 paramety - 1. Dwuwymiarowa tablice stringow,
2. String do wyszukania, Natomiast zwraca int, ktory jest wyszukanym
indeksem z tablicy 1.
Nie ma problemu z napisaniem recznym, ale porownanie 150 stringow "troszke"
czasu zabiarze. Mi chodzi o maksymalna predkosc tej operacji. Tablica 1.
moze byc posortowana.
Pytanie 2 - czy jesli posortuje tablice 1. i bede porownywal najpierw
pierwsza litere, potem druga itp (nie uzywajac strcmp), to bedzie szybciej?

Pozdrawiam
Grzegorz


========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "BT" <kurciok_at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sat, 10 Jul 2004 12:45:56 +0200


Czy sa w AVR-GCC jakies funkcje przyspieszajace standardowe operacje na
stringach? Chodzi o wyszukanie w tablicy stringow stringa o podanym
wzorcu.
Czyli funkcja ktora pobiera 2 paramety - 1. Dwuwymiarowa tablice stringow,
2. String do wyszukania, Natomiast zwraca int, ktory jest wyszukanym
indeksem z tablicy 1.
Nie ma problemu z napisaniem recznym, ale porownanie 150 stringow
"troszke"
czasu zabiarze. Mi chodzi o maksymalna predkosc tej operacji. Tablica 1.
moze byc posortowana.
Pytanie 2 - czy jesli posortuje tablice 1. i bede porownywal najpierw
pierwsza litere, potem druga itp (nie uzywajac strcmp), to bedzie
szybciej?

Hmm ja się nie znam bo tylko raz coś pisałem w AVR-GCC ale chyba nie ma nic
poza standardową funkcją strcmp także będziesz musiał to sam napisać trudne
to to nie jest ale jeśli chodzi o przyspieszenie to ja proponuje o ile
możesz to ułożyć w tablicy wszystkie stringi tak jak powiedziałeś
posortowane. Następnie proponowany przeze mnie algorytm wyglądał by
następująco (trochę zakręcony ale powinien być bardzo szybki). Aha zakłądam
w nim że tablice 150 stringów masz wpisaną na stałe i ona nie zmienia się w
trakcie działania bo sortowanie jej co chwile zajęło by więcej czasu niż
przeszukiwanie.

1. Masz tablice tab1 w której jest 150 posortowanych stringów.
2. Tworzysz teraz coś w rodzaju indexu znanego z bazach danych (dość
uproszczonego), czyli dodatkową tablice w której zapisujesz sobie miejsca z
tab1 gdzie zmienia się pierwsza litera

Przykład:

to jest tab1:

tab1[0] = ala
tab1[1] = albert
tab1[2] = bocian
tab1[3] = bolek
tab1[4] = bratek
tab1[5] = mors
tab1[6] = wrona

a to jest tabindex (jej wielkość jest zależna od tego ile razy zmienia się
pierwsza litera w kolejnych słowach w tab1, maksymalna wielkość tab1 to
ilość liter w alfabecie):

tabindex[0]=0
tabindex[1]=2
tabindex[2]=5
tabindex[3]=6

i teraz pewnie jak się domyślasz jak czegoś szukasz to najpierw sprawdzasz
pierwszą litere czyli coś w stylu:


int i=0;
for (;i<4;i++)
{
if (tab1[tabindex[i]]==string[0])
break;
}

Teraz w zmiennej "i" będziesz miał miejsce w tab[1] od którego zaczniesz
szukać funkcją strcmp (skończysz szukać w punkcie tabindex[i+1]) dzięki temu
ograniczysz sobie krąg poszukiwań tylko do przeszukania słów zaczynających
się na tą samą litere. Gdybyś miał więcej danych to można by to ciągnąć
jeszcze dalej i robić indeksy np. dla dwóch pierwszych liter ale przy 150
stringach to nie ma sensu. Możesz też spróbować zamiast funkcji strcmp użyć
jakiegoś własnego wynalazku.

Całkiem innym rozwiązaniem może być także wykorzystanie tego że litery w
kodzie ASCI są ułożone kolejno także można wykorzystać tutaj jakieś
algorytmy wybierania co powinno być także szybkie. Ale już nie chce mi się
pisać ;)



========
Path: news-archive.icm.edu.pl!newsfeed.gazeta.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_nospam_at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sat, 10 Jul 2004 16:14:53 +0200


On Sat, 10 Jul 2004 01:25:50 GMT, "Grzegorz"
Czy sa w AVR-GCC jakies funkcje przyspieszajace standardowe operacje na
stringach? Chodzi o wyszukanie w tablicy stringow stringa o podanym wzorcu.
Czyli funkcja ktora pobiera 2 paramety - 1. Dwuwymiarowa tablice stringow,
2. String do wyszukania, Natomiast zwraca int, ktory jest wyszukanym
indeksem z tablicy 1.

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.

Pytanie 2 - czy jesli posortuje tablice 1. i bede porownywal najpierw
pierwsza litere, potem druga itp (nie uzywajac strcmp), to bedzie szybciej?

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.


========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news.nask.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: JS <jar0sz_at_nospam_polbox.com.pl_without_pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sat, 10 Jul 2004 14:42:06 +0000 (UTC)


W artykule <yAHHc.28202$Q74.3475_at_nospam_news.chello.at>
autorem którego mieni się Grzegorz, napisano:

Czy sa w AVR-GCC jakies funkcje przyspieszajace standardowe operacje na
stringach? Chodzi o wyszukanie w tablicy stringow stringa o podanym wzorcu.

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.

--
Pozdrawiam
Jarosław Szynal

========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news.dialog.net.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <wyderskiREMOVE_at_nospam_ii.uni.wroc.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sat, 10 Jul 2004 17:26:39 +0200



Grzegorz wrote:

Czy sa w AVR-GCC jakies funkcje przyspieszajace standardowe operacje na
stringach?

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?

Chodzi o wyszukanie w tablicy stringow stringa o podanym wzorcu.

Co to jest wzorzec? Wyrazenie regularne?

Czyli funkcja ktora pobiera 2 paramety - 1. Dwuwymiarowa tablice stringow,
2. String do wyszukania, Natomiast zwraca int, ktory jest wyszukanym
indeksem z tablicy 1.

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.

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

3. Hashowanie z dowiazywaniem.

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

5. Mozesz tez te tablice zamienic na automat skonczony
-- wyszukiwanie bedziesz mial najszybsze mozliwe, ale chyba
skorka jest niewarta wyprawki...

Nie ma problemu z napisaniem recznym, ale porownanie 150 stringow
"troszke"
czasu zabiarze.

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).

Pytanie 2 - czy jesli posortuje tablice 1. i bede porownywal najpierw
pierwsza litere, potem druga itp (nie uzywajac strcmp), to bedzie
szybciej?

W pesymistycznym przypadku nie.

Pozdrawiam
Piotr Wyderski


========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news-fra1.dfn.de!newsfeed.ision.net!ision!news.belwue.de!feed.news.tiscali.de!newsfeed02.chello.at!news.chello.at.POSTED!53ab2750!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Grzegorz" <w_o_d_e_k_at_nospam__at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sun, 11 Jul 2004 10:37:09 GMT



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).

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
= 2048 kb (stringow w sumie wyjdzie jakies 100 - 120)/.
Dziekuje wszystkim za pomoc.
Pozdrawiam
Grzegorz


========
Path: news-archive.icm.edu.pl!newsfeed.gazeta.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_nospam_at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sun, 11 Jul 2004 13:11:28 +0200


On Sun, 11 Jul 2004 10:37:09 GMT, "Grzegorz"
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 skad te stringi pochodza ? [wesze odciski palcow ?]
Bo na oko to bardzo warto jakiegos hasha rozwazyc.

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
= 2048 kb (stringow w sumie wyjdzie jakies 100 - 120)/.

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.




========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news-fra1.dfn.de!newsfeed.ision.net!ision!newsfeed.freenet.de!195.34.132.48.MISMATCH!newsfeed02.chello.at!news.chello.at.POSTED!53ab2750!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Grzegorz" <w_o_d_e_k_at_nospam__at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sun, 11 Jul 2004 12:07:16 GMT



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

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.

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..

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


========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news.dialog.net.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <wyderskiREMOVE_at_nospam_ii.uni.wroc.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sun, 11 Jul 2004 16:31:34 +0200



Grzegorz wrote:

A co do predkosci - zalezy mi, aby cala operacja zajela mniej
niz ok 2ms od wywolania funkcji do zwrocenia True lub False.

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. ;-)

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.

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.

Chyba, ze jakos dynamicznie to wszystko sie da...

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

ale w tym dobry nie jestem..

Dlatego zostan przy wyszukiwaniu binarnym.

Pozdrawiam
Piotr Wyderski


========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_nospam_at_nospam_poczta.onet.pl>
Subject: Re: AVR-GCC i operacje na stringach
Date: Sun, 11 Jul 2004 22:37:38 +0200


On Sun, 11 Jul 2004 12:07:16 GMT, "Grzegorz"
A skad te stringi pochodza ? [wesze odciski palcow ?]
Bo na oko to bardzo warto jakiegos hasha rozwazyc.

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.

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 ?

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..

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.


========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!newsfeed.pionier.net.pl!news.icp.pl!not-for-mai