To teraz ja potroluję trochę :D

Mamy pary ( klucz , wartosc ). Klucz jest liczbą
całkowitą (ujemną albo dodatnią) wartość jest liczbą
całkowitą albo zmiennoprzecinkową (jeszcze nie jestem
pewien ).

Procedura na wejście otrzymuje tablicę powyższych par i
klucz. Procedura ma zwrócić wartość stowarzyszoną z
kluczem, a jeśli klucza nie ma w tablicy i:
a) jeśli klucz jest mniejszy od najmniejszego klucza w
tablicy, to zwraca wartość stowarzyszoną z najmniejszym kluczem
b) jeśli klucz jest większy od największego klucza, to
analogicznie zwraca wartość stowarzyszoną z największym kluczem

Tablice par są małe, od dwóch elementów do tysiąca, średnio
powiedzmy trzydzieści elementów. Tablic jest od około pięćdziesiąt
do kilkuset. Tablice par są znane w czasie kompilacji, ale w
każdej kompilacji są inne, więc ręcznie wklepywanie nie wchodzi w
grę - jedynie generator kodu. Program w pętli wywołuje procedurę
dla wszystkich tablic owych par i dla jakiegoś klucza.

No i pytanie: jaka implementacja będzie najszybsza?
Raczej hash-table czy raczej wyszukiwanie binarne czy
może jeszcze coś innego?

Pozdrawiam :)


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> No i pytanie: jaka implementacja będzie najszybsza?
> Raczej hash-table czy raczej wyszukiwanie binarne czy
> może jeszcze coś innego?

A czemu dzielisz te dane na osobne tablice? One są potem
osobno jeszcze przetwarzane? Co w ogóle robisz z wynikami
tej funkcji?

w.

do góry

On 16/12/2011 20:17, M.M. wrote:
> To teraz ja potroluję trochę :D
>
> Mamy pary ( klucz , wartosc ). Klucz jest liczbą
> całkowitą (ujemną albo dodatnią) wartość jest liczbą
> całkowitą albo zmiennoprzecinkową (jeszcze nie jestem
> pewien ).
>
> Procedura na wejście otrzymuje tablicę powyższych par i
> klucz. Procedura ma zwrócić wartość stowarzyszoną z
> kluczem, a jeśli klucza nie ma w tablicy i:
> a) jeśli klucz jest mniejszy od najmniejszego klucza w
> tablicy, to zwraca wartość stowarzyszoną z najmniejszym kluczem
> b) jeśli klucz jest większy od największego klucza, to
> analogicznie zwraca wartość stowarzyszoną z największym kluczem

Jeśli ta tablica jest przeszukiwana tylko raz dla danego klucza, to
chyba najlepiej ją przeszukiwać liniowo. Jeśli jest przeszukiwana wiele
razy, lub konstruujesz ją na bieżąco dodając kolejne elementy i
przeszukując, to nie najgłupszym rozwiązaniem wydaje się chyba trzymanie
w obiekcie mapującym największej i najmniejszej wartości klucza.

do góry

Wojciech Muła <w...@g...com> napisał(a):

> > No i pytanie: jaka implementacja b=EAdzie najszybsza?
> > Raczej hash-table czy raczej wyszukiwanie binarne czy
> > mo=BFe jeszcze co=B6 innego?
>
> A czemu dzielisz te dane na osobne tablice? One s=B1 potem
> osobno jeszcze przetwarzane? Co w og=F3le robisz z wynikami
> tej funkcji?

Algorytm z liniowym wyszukiwaniem wyglądłby tak:

struct Para {
int klucz;
int_or_float wartość;
};

struct Tablica {
int size;
Para pary[MAX_SIZE];
};

Find( Tablica &tablica , int klucz ) {
for( int i=0 ; i<tablica.size ; i++ )
if( tablica.pary[i].klucz == klucz )
return tablica.pary[i].wartość;
if( klucz < tablica.pary[0],klucz )
return tablica.pary[0].wartosc;
// if( klucz > tablica.pary[tablica.size-1],klucz )
return tablica.pary[tablica.size-1].wartość;
}


FindOfFind( Tablica tablce[N] , int klucze[N] ) {
int_or_float sum = 0;
for( int i=0 ; i<N ; i++ )
sum += Find( tablice[i] , klucze[i] );
return sum;
}

Pozdrawiam :D



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Andrzej Jarzabek <a...@g...com> napisał(a):

> On 16/12/2011 20:17, M.M. wrote:
> > To teraz ja potroluję trochę :D
> >
> > Mamy pary ( klucz , wartosc ). Klucz jest liczbą
> > całkowitą (ujemną albo dodatnią) wartość jest liczbą
> > całkowitą albo zmiennoprzecinkową (jeszcze nie jestem
> > pewien ).
> >
> > Procedura na wejście otrzymuje tablicę powyższych par i
> > klucz. Procedura ma zwrócić wartość stowarzyszoną z
> > kluczem, a jeśli klucza nie ma w tablicy i:
> > a) jeśli klucz jest mniejszy od najmniejszego klucza w
> > tablicy, to zwraca wartość stowarzyszoną z najmniejszym kluczem
> > b) jeśli klucz jest większy od największego klucza, to
> > analogicznie zwraca wartość stowarzyszoną z największym kluczem
>
> Jeśli ta tablica jest przeszukiwana tylko raz dla danego klucza, to
> chyba najlepiej ją przeszukiwać liniowo. Jeśli jest przeszukiwana wiele
> razy, lub konstruujesz ją na bieżąco dodając kolejne elementy i
> przeszukując, to nie najgłupszym rozwiązaniem wydaje się chyba trzymanie
> w obiekcie mapującym największej i najmniejszej wartości klucza.

Za każdym razem przeszukiwany jest cały zestaw tablic (czyli wszystkie
tablice z zestawu). Za każdym razem tablice są takie same, a inne
są klucze. Cały zestaw jest przeszukiwany bardzo często, stanowi około
30% gorącego punktu programu.
Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2011-12-17 06:28, M.M. pisze:

> Za każdym razem przeszukiwany jest cały zestaw tablic (czyli wszystkie
> tablice z zestawu). Za każdym razem tablice są takie same, a inne
> są klucze. Cały zestaw jest przeszukiwany bardzo często, stanowi około
> 30% gorącego punktu programu.
> Pozdrawiam

Może nie do końca rozumiem istotę problemu, ale czy nie lepiej byłoby tak:

Skoro znasz zawartość tablicy na etapie kompilacji, to czy nie lepiej /
szybciej byłoby zamiast generować sobie kod, który definiuje tablicę,
zdefiniować sobie switch / case?

--
npe

do góry

On Saturday, December 17, 2011 6:24:42 AM UTC+1, M.M. wrote:
> FindOfFind( Tablica tablce[N] , int klucze[N] ) {
> int_or_float sum = 0;
> for( int i=0 ; i<N ; i++ )
> sum += Find( tablice[i] , klucze[i] );
> return sum;
> }

A czy zbiór wartości kluczy jest jakoś ograniczony?

w.

do góry

Wojciech Muła <w...@g...com> napisał(a):

> On Saturday, December 17, 2011 6:24:42 AM UTC+1, M.M. wrote:
> > FindOfFind( Tablica tablce[N] , int klucze[N] ) {
> > int_or_float sum =3D 0;
> > for( int i=3D0 ; i<N ; i++ )
> > sum +=3D Find( tablice[i] , klucze[i] );
> > return sum;
> > }
>
> A czy zbi=C3=B3r warto=C5=9Bci kluczy jest jako=C5=9B ograniczony?
>

Tak, zbior kluczy jest ograniczony.

W niektorych tablicach jest ograniczony np. do trzech wartosci {0,1,2} i
wtedy implementacja jest banalna - klucz jest od razu indeksem.

Najczesciej jest to np. 30 wartosci z przedzialu <-1000,+1000>.

Rzadko jest to 1000 wartosci z przedzialu <-15000,+15000>

Chyba hash-table bedzie najszybsza, cos w ten desen:
struct Tablica {
int minimum;
typ val_mini;
typ val_max;
int size;
Para pary[size+padding]; // sory za skladnie
};
Find( const Tablica &t , int klucz ) {
klucz = ( (klucz) + (klucz>>1) + (klucz>2) ) % t.size; // jakas lepsza funkcja
if( t.pary[klucz].klucz == klucz ) return t.pary[klucz].wartosc;
if( t.minimum > klucz ) return t.val_mini;
return t.val_max;
}

Pozdrawiam





--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

nullpointer <i...@n...dojdzie.pl> napisał(a):

> Skoro znasz zawartość tablicy na etapie kompilacji, to czy nie lepiej /
> szybciej byłoby zamiast generować sobie kod, który definiuje tablicę,
> zdefiniować sobie switch / case?

Nie wiem. Jak wydajny jest kod ktory ma okolo 5-10tys linii z samych
switchow? :D

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Sat, 17 Dec 2011 12:52:53 +0000 (UTC) " M.M."
<m...@g...pl> wrote:

> Tak, zbior kluczy jest ograniczony.
>
> W niektorych tablicach jest ograniczony np. do trzech wartosci
> {0,1,2} i wtedy implementacja jest banalna - klucz jest od razu
> indeksem.
>
> Najczesciej jest to np. 30 wartosci z przedzialu <-1000,+1000>.
>
> Rzadko jest to 1000 wartosci z przedzialu <-15000,+15000>
>
> Chyba hash-table bedzie najszybsza, cos w ten desen:
> struct Tablica {
> int minimum;
> typ val_mini;
> typ val_max;
> int size;
> Para pary[size+padding]; // sory za skladnie
> };
> Find( const Tablica &t , int klucz ) {
> klucz = ( (klucz) + (klucz>>1) + (klucz>2) ) % t.size; // jakas
> lepsza funkcja if( t.pary[klucz].klucz == klucz ) return
> t.pary[klucz].wartosc; if( t.minimum > klucz ) return t.val_mini;
> return t.val_max;
> }

To masz mało danych. Prościej zapisać ciągłą tablice o rozmiarze
klucz_max - klucz_min + 1, zapisać wartości dla klucz_min...max
i uzupełnić wartości niewystępujące w oryginalnej tablicy.

struct Tablica {
int klucz_min;
int klucz_max;
int val_min;
int val_max;
int tablica[klucz_max - klucz_min + 1];
}

find(...) {
if (klucz < tablica.klucz_min)
return val_min;
else if (klucz > tablica_klucz_max)
return val_max;
else
return tablica[klucz - klucz_min];
}

w.

do góry