W dniu wtorek, 16 października 2012 22:11:41 UTC+2 użytkownik M.M. napisał:
> W dniu wtorek, 16 października 2012 21:18:55 UTC+2 użytkownik bartekltg napisał:
>
> > Bardzo się z tego cieszę;)
>
> > A co do szybkości rand - nieraz do 'pierdółek'
>
> > przydałby się szybszy:)
>
> Nie tak dawno szukalem jeszcze szybszego od standardowego
>
> randa z c++. Problem na tyle prosty, ze waskim gardlem
>
> byla wlasnie stanardowa funkcja rand.
>
> Pozdrawiam

u mnie rand zajmuje 14 ns (drugie tyle doklada
modulo jesli nie potega dwojki) - czyli jest
jednak bardzo szybki (kiedys wydawalo mi sie
ze jest znacznie wolniejszy ale wynik pokazuje
ze jednak szybki) Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
jest wolniejszy niz cosinus :U (pain)

do góry

W dniu środa, 17 października 2012 09:19:43 UTC+2 użytkownik Piotr Chamera napisał:
> Ale zamiast czegoś takiego < : f(a) < f(b) używasz niejawnie
> (w zależności od algorytmu sortującego) czegoś podobnego do
> < : f(a) < f(b) dla f(a) != f(b)
> i(a) < i(b) dla f(a) = f(b)
> gdzie i(a) daje indeks elementu a w tablicy wejściowej
No tak :)

do góry

W dniu środa, 17 października 2012 09:31:22 UTC+2 użytkownik M.M. napisał:
> W dniu środa, 17 października 2012 09:19:43 UTC+2 użytkownik Piotr Chamera napisał:
>
> > Ale zamiast czegoś takiego < : f(a) < f(b) używasz niejawnie
>
> > (w zależności od algorytmu sortującego) czegoś podobnego do
>
> > < : f(a) < f(b) dla f(a) != f(b)
>
> > i(a) < i(b) dla f(a) = f(b)
>
> > gdzie i(a) daje indeks elementu a w tablicy wejściowej
>
> No tak :)

a co do tego szybkiego randa - znalazles jakis ?
jak dasz kod to sprawdze czy jest u mnie szybszy - kiedys sie tym niby interesowalem
chyba cos co sprawdzilem bylo znacznie wolniejsze, jak rand ma 14 ns to bedzie
trudno celowac w przyspieszanie tego.

do góry

On 17.10.2012 05:44, M.M. wrote:
>
> Wynikało by z tego, że jak mamy zbiór {a,b,c,d} i cechę
> f(a)=1, f(b)=1, f(c)=2, f(d)=3

Takie dwie małe uwagi na początek - zbiór jest nieuporządkowany i o ile
nie jest multizbiorem nie ma tego samego elementu więcej niż raz.

W programowaniu zazwyczaj (poza naprawdę rzadkimi przypadkami) operujemy
na ciągach wartości a nie na zbiorach.

> to nie
> da się tego zbioru posortować, bo na
> tej cesze nie da się wprowadzić porządku
> liniowego.

Utwórzmy zbiór wartości tej cechy:
{1,2,3}
Jak widzimy ten zbiór nie jest równoliczny ze zbiorem początkowym, więc
nie jest spełniony warunek konieczny aby móc wprowadzić porządek liniowy.

> Jednak posortować się da, więc
> nadal nic nie kumam

Możesz posortować w informatyce na dwa sposoby:
- stabilnie: przekształcasz zbiór w ciąg, elementom o tej samej wartości
cechy przyporządkowujesz indeksy w tym ciągu, sortujesz po parze (cecha,
indeks)
- niestabilnie: efektem sortowania jest ciąg zbiorów ({a,b},{c},{d}),
możesz go przekształcić do ciągu, ale zauważ, że pozycja elementów a i b
w tym ciągu jest nieokreślona i zależy tylko od wybranego przekształcenia.

Żeby to unaocznić:
- masz zbiór {romb, kwadrat,trójkąt, odcinek}
- sortujesz po cesze "ilość odcinków"
+ czy kwadrat i romb to to samo? (mają taką samą wartość cechy)
+ w jakiej kolejności mają być romb i kwadrat?

--
Pozdrawiam
Michoo

do góry

Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
>
> W dniu wtorek, 16 października 2012 22:11:41 UTC+2 użytkownik M.M. napisał:
>> W dniu wtorek, 16 października 2012 21:18:55 UTC+2 użytkownik bartekltg napisał:
>>
>> > Bardzo się z tego cieszę;)
>>
>> > A co do szybkości rand - nieraz do 'pierdółek'
>>
>> > przydałby się szybszy:)
>>
>> Nie tak dawno szukalem jeszcze szybszego od standardowego
>>
>> randa z c++. Problem na tyle prosty, ze waskim gardlem
>>
>> byla wlasnie stanardowa funkcja rand.
>>
>> Pozdrawiam
>
> u mnie rand zajmuje 14 ns (drugie tyle doklada
> modulo jesli nie potega dwojki) - czyli jest
> jednak bardzo szybki (kiedys wydawalo mi sie
> ze jest znacznie wolniejszy ale wynik pokazuje
> ze jednak szybki) Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
jest wolniejszy niz cosinus :U (pain)

Zależy od implementacji rand(), jeśli implementacja korzysta na
przykład z /dev/random to kernel "gromadzi" pewien zapas losowych
bitów i dostępne są one natychmiast (skuteczne do generowania kluczy
szyfrujących, gdzie zwykle potrzeba maksymalnie 2048 bitów a gdzie
zwykły rand() z libc jest jednak zbyt "deterministyczny"), ale już
wywołanie takiego rand() powiedzmy milion razy takie szybkie nie jest.

do góry

Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
> Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
> jest wolniejszy niz cosinus :U (pain)

Może dlatego, że sinus jest zaimplementowany jako cos(x-pi/4) i
dochodzi dodatkowa operacja :D

do góry

W dniu środa, 17 października 2012 12:40:24 UTC+2 użytkownik Baranosiu napisał:
> Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
>
> > Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
>
> > jest wolniejszy niz cosinus :U (pain)
>
>
>
> Może dlatego, że sinus jest zaimplementowany jako cos(x-pi/4) i
>
> dochodzi dodatkowa operacja :D

wogole czas sinusa zalezy od kata np

d = sin(5); //101 ns
d = sin(6); //81 ns

(poprzednio podane wieksze wartosci byly z
przypisywaniem do inta bo to trwa przy
zlym rzutowaniu w kompilatorze u mnie 65 ns
samo z siebie)

do góry

W dniu środa, 17 października 2012 14:38:29 UTC+2 użytkownik kenobi napisał:
> W dniu środa, 17 października 2012 12:40:24 UTC+2 użytkownik Baranosiu napisał:
>
> > Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
>
> >
>
> > > Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
>
> >
>
> > > jest wolniejszy niz cosinus :U (pain)
>
> >
>
> >
>
> >
>
> > Może dlatego, że sinus jest zaimplementowany jako cos(x-pi/4) i
>
> >
>
> > dochodzi dodatkowa operacja :D
>
>
>
> wogole czas sinusa zalezy od kata np
>
>
>
> d = sin(5); //101 ns
>
> d = sin(6); //81 ns
>
>
>
> (poprzednio podane wieksze wartosci byly z
>
> przypisywaniem do inta bo to trwa przy
>
> zlym rzutowaniu w kompilatorze u mnie 65 ns
>
> samo z siebie)

dziwnie dlugo tez trwa takie cos

f+=0.001; // okolo 30 ns
f=i; // okolo 30 ns

to jest jakos duzo i sprzeczne to jest
z tym co czytalem nt fpu gdzie wydawaloby sie
ze to powinno byc z 10 razy szybsze

totalnym killerem wydajnosci jest tez funkcja pow - 500 ns - co widywalem w praktyce
przy
robieniu w ten sposob gammy - jest to tak wolne
ze zabija prog - wogole to mam starego kompa
ale jak kupie nowszego to spobie porownam
i warto znac stare wartosci

do góry

Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
> W dniu środa, 17 października 2012 12:40:24 UTC+2 użytkownik Baranosiu napisał:
>> Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
>>
>> > Dla porownania sinus 190 ns cosinus 160 - nie wiem dlaczego sinus
>>
>> > jest wolniejszy niz cosinus :U (pain)
>>
>>
>>
>> Może dlatego, że sinus jest zaimplementowany jako cos(x-pi/4) i
>>
>> dochodzi dodatkowa operacja :D
>
> wogole czas sinusa zalezy od kata np
>
> d = sin(5); //101 ns
> d = sin(6); //81 ns

Tak, zależy, bo dla różnych kątów jest różna szybkość zbieżności
szeregów używanych przez FPU do wyliczeń. Przy okazji przejrzyj jaki
kod w assemblerze Ci produkuje kompilator, bo czasem jak kompilator
jest "sprytny" to wyliczy wartość w trakcie kompilacji, a nie w czasie
wykonania :D Najlepiej takie rzeczy testować z wyłączonym
optymalizowaniem (albo wprost napisać program w assemblerze).

do góry

Dnia 17.10.2012 kenobi <p...@g...com> napisał/a:
[...]
>
> dziwnie dlugo tez trwa takie cos
>
> f+=0.001; // okolo 30 ns
> f=i; // okolo 30 ns
>
> to jest jakos duzo i sprzeczne to jest
> z tym co czytalem nt fpu gdzie wydawaloby sie
> ze to powinno byc z 10 razy szybsze

Sprawdź jaki kod w assemblerze generuje Ci kompilator :D Jak zrobisz
po kolei f+=0.001; a potem f=i; to pierwszą instrukcję kompilator wyrzuci;


>
> totalnym killerem wydajnosci jest tez funkcja pow - 500 ns - co widywalem w
praktyce przy
> robieniu w ten sposob gammy - jest to tak wolne
> ze zabija prog - wogole to mam starego kompa
> ale jak kupie nowszego to spobie porownam
> i warto znac stare wartosci

Testuj FPU w assemblerze, kompilatory robią różne sztuczki (mało tego,
kompilator czasem wyłączy korzystanie z FPU jeśli do "otaczających"
instrukcji użyje MMX, bo w procesorach Intela x86 akurat FPU i MMX to
ten sam zestaw rejestrów i nie można z nich korzystać równocześnie,
czyli albo wektory albo FPU ale nie równocześnie :D)

do góry