W dniu 21.12.2011 15:11, Roman W pisze:
> Do czego zmierzam: ze jezeli wymaganiem jest *formalna gwarancja* ze procedura
implementuje algorytm wykonujacy sie w czasie liniowym, to zaden test tego adekwatnie
nie dokumentuje. Tylko zwykla dokumentacja moze to, well, udokumentowac.
>
To ja Ci teraz napiszę o bugu, którego łatałem jakiś miesiąc temu a Ty
podpowiesz jak dokumentacja załatwi problem:
kod miał za zadanie wyszukać w każdej z dostarczonych kolekcji
(przeglądanej liniowo) dane spełniające pewien predykat a następnie
posortować wg innego predykatu. Na skutek drobnej pomyłki codera
sortowanie wylądowało w wewnętrznej pętli, dzięki czemu złożoność
przetwarzania pojedynczej kolekcji skoczyła z O(n log n) do O(n^2 log n).

--
Pozdrawiam
Michoo

do góry

On Thu, 22 Dec 2011 00:31:07 +0000, Andrzej Jarzabek
<a...@g...com> wrote:

>On 21/12/2011 23:13, Maciej Sobczak wrote:
>>
>> Jakoś jednak sądzę, że ta funkcja jest do bani. Ale test przeszła! To
>> może test jest do bani? Pewnie jest - ale jak sprawdzić ten test?
>
>Daje rozkład jednostajny. Nie daje liczb losowych, ale funkcji, która
>daje liczby losowe nie ma.
>
>> Łatwiej napisać generator liczb losowych, niż jego test.
>> To znaczy, że przy takim zadaniu w ogóle nie pisałbym unit-testu.
>
>Testy to nie tylko unit testy.
>
>Natomiast tak w ogóle w wielu przypadkach dla funkcji pseudo-losowej
>łatwo napisać unit test. Powiedzmy, że funkcja korzysta z algorytmu X,
>który wziąłeś z literatury, lub też w inny sposób stwierdziłeś, że jest
>wystarczająco "losowy". Bierzesz referencyjną implementację algorytmu,
>napisaną przez kogoś innego bądź sam piszesz, i rejestrujesz pierwszą
>zwróconą liczbę dla jakiejś puli przypadkowo wybranych seed-ów. Możesz
>też zarejestrować setną zwróconą liczbę albo tysięczną, albo
>stutysięczną (w zależności jak długo algorytm działa). Zapisujesz te
>dane w teście et voila, masz test sprawdzający, czy funkcja dalej
>korzysta z algorytmu X. Jeśli korzysta, to znaczy, że jest wystarczająco
>"losowa" według przyjętych przez ciebie kryteriów. Jeśli nie, to badamy
>o co kaman i albo naprawiamy funkcję, albo zmieniamy test.

Panowie, ograniczcie moze dyskusje do waszego obszaru kompetencji, a
jak spoza to prosze explicite dac znac ze to jest zart. Na przyklad
mordka :)

A.L.

do góry

W dniu 2011-12-21 15:39, Roman W pisze:
> On Wednesday, December 21, 2011 2:27:31 PM UTC, A. L. wrote:
>> Echem... Akurat... Metoda Simplex jak wiadomo ma zlozonosc
>> wykladnicza, a wszystkie testy pokazuja ze wielomianowa. Zeby dostac
>> naprawde zlozonosc wykladnicza tzreba skonstruowac specjalny prtzyklad
>> co nastapilo cos w 30 lat po sformulowaniu metody.
>
> Dla skonczonej liczby punktow funkcje wykladnicza zawsze da sie dofitowac
wielomianem, wiec takie testy moga byc tylko i wylacznie heurystyczne.

Czyli to, co zaproponowałem wykryje tylko "grube" błędy dla względnie
prosto testowalnych algorytmów. Jeśli to wystarczy - OK.

--
Paweł Kierski
n...@p...net

do góry

W dniu 2011-12-22 00:13, Maciej Sobczak pisze:
> On Dec 21, 5:18 pm, Roman W<b...@g...pl> wrote:
>
>>> Oprócz złożoności liniowej i pogłosu w filharmonii w Koluszkach,
>>> takich przykładów jest znacznie więcej. Np. mamy napisać generator
>>> liczb losowych o zadanym rozkładzie - jak to sprawdzić przez TDD?
>>
>> To akurat robilem. Losowalem np. 10000 probem i sprawdzalem czy histogram sprawdza
sie w ramach zadanej tolerancji z zadana dystrybucja,
>
> Jasne. Powiedzmy, że chodzi o liczby od 0 do 9 i rozkład jednostajny.
>
> Oto mój generator:
>
> int getNextValue()
> {
> static int x = 0;
> if (x == 10) x = 0;
> return x++;
> }
>
> Powyższa funkcja przy odpowiednio wielu wywołaniach daje całkiem dobry
> "histogram".
> Można tak zrobić dowolny zadany "rozkład" i go "przetestować" tak jak
> opisałeś.
>
> Jakoś jednak sądzę, że ta funkcja jest do bani. Ale test przeszła! To
> może test jest do bani? Pewnie jest - ale jak sprawdzić ten test?

Pytanie było o to, czy dany generator daje odpowiedni rozkład,
nie o własności liczb 'losowe'.

> Łatwiej napisać generator liczb losowych, niż jego test.
> To znaczy, że przy takim zadaniu w ogóle nie pisałbym unit-testu.

Dobre generatory liczb losowych _ciężko_ napisać. Łatwo*) to napisać
zamianę zmiennych transformującą np rozkład jednostajny na jakiś
inny zadany.

*) w pewnych przypadkach etc. Czasem nie jest to takie trywialne,
np. rozkład normalny generuje się dość sprytnie.

pzdr
bartekltg

do góry

On 12/22/2011 01:09 AM, Andrzej Jarzabek wrote:
> On 21/12/2011 19:37, Edek wrote:
>>
>> Z samego programowania dowody (pół)formalne stosuje
>> się przy algorytmach wątkowych. Żaden unit test nie pokaże
>> błędu wielowątkowego, co najwyżej wysypie się np. raz na 1e4.
>
> No więc jeśli wiesz, że błędna implementacja wysypie się raz na 1e4, to
> jeśli zrobiłeś test, który odpala się 1e6 razy, to masz znacznie lepszą
> gwarancję poprawności, niż gdybyś tylko zrobił dowód (pół)formalny.

Bzdura...

>
>> Jak wielu programistów robi, TDD: test, implementacja, przeszło
>> - czyli już zrobione.
>
> Nie wiem, ale inteligentni programiści z jakimkolwiek doświadczeniem,
> lub choćby tacy, którzy czytali o tym książkę, wiedzą o
> obszarach-pułapkach, jakimi są np. wątki,

To było o sobie? I nadal twierdzą to co powyżej?

i w związku z tym wiedzą, że
> trzeba zrobić coś więcej. A jak sami nie wiedzą co, to mogą spytać
> bardziej doświadczonych kolegów, albo chociażby przeczytać o tym
> książkę. Freeman i Pryce mają np. bardzo sensowny rozdział o testowaniu
> programów wielowątkowych w TDD.

Edek

do góry

On Wednesday, December 21, 2011 11:13:42 PM UTC, Maciej Sobczak wrote:
> On Dec 21, 5:18 pm, Roman W <b...@g...pl> wrote:
>
> > > Oprócz złożoności liniowej i pogłosu w filharmonii w Koluszkach,
> > > takich przykładów jest znacznie więcej. Np. mamy napisać generator
> > > liczb losowych o zadanym rozkładzie - jak to sprawdzić przez TDD?
> >
> > To akurat robilem. Losowalem np. 10000 probem i sprawdzalem czy histogram
sprawdza sie w ramach zadanej tolerancji z zadana dystrybucja,
>
> Jasne. Powiedzmy, że chodzi o liczby od 0 do 9 i rozkład jednostajny.
>
> Oto mój generator:
>
> int getNextValue()
> {
> static int x = 0;
> if (x == 10) x = 0;
> return x++;
> }
>
> Powyższa funkcja przy odpowiednio wielu wywołaniach daje całkiem dobry
> "histogram".
> Można tak zrobić dowolny zadany "rozkład" i go "przetestować" tak jak
> opisałeś.

I jezeli moj generator ma sluzyc *wylacznie* do obliczania wartosci oczekiwanych
E[f(X)], gdzie X ma miec rozklad jednostajny w zbiorze {0,1,2,...,9}, to taki test w
zupelnosci wystarcza, bo korelacje pomiedzy poszczegolnymi losowaniami mnie nie
obchodza. Ba, do calkowania Monte Carlo takie generatory moga byc lepsze od
standardowych (roznica pomiedzy liczbami pseudo- i quasilosowymi).

Jezeli mnie obchodza, to taki test jest dalece niewystarczajacy.

W praktyce to ja nie pisalem nigdy swoich wlasnych generatorow, tylko bralem Mersenne
Twister (np. z boost) i przeksztalcalem dystrybucje z jednostajnej w np. Gaussowska
albo Levy'ego. I wtedy histogramem + momentami sprawdzalem to co moglem sprawdzic, a
co do reszty to polegalem na poprawnosci implementacji bibliotecznej.

>
> Jakoś jednak sądzę, że ta funkcja jest do bani. Ale test przeszła! To
> może test jest do bani? Pewnie jest - ale jak sprawdzić ten test?

Dobrze wiem, jak trudno jest testowac generatory liczb losowych.

>
> Łatwiej napisać generator liczb losowych, niż jego test.
> To znaczy, że przy takim zadaniu w ogóle nie pisałbym unit-testu.

Nie, to jest bez sensu. Jezeli nie moge sprawdzic 100% wymagan, to nie znaczy, ze
powinienem sprawdzac 0%.

RW

do góry

On Thursday, December 22, 2011 12:00:11 AM UTC, Andrzej Jarzabek wrote:

> Banalnie - zakładasz poziom pewności, np. 5 sigma i robisz skwantyzowany
> soak test - generujesz liczby, wrzucasz w odpowiednie przedziały, jak
> wygenerujesz odpowiednio dużo, to sprawdzasz, czy w każdym z przedziałów
> jest odpowiednia ilość plus minus błąd. Jak ci się nie chce porządnie
> liczyć błędów, to robisz "na oko" i ewentualnie korygujesz. Na tym
> schemacie możesz zrobić unit test, który ci to sprawdza w pół sekundy, i
> soak test, który leci godzinę.

To sprawdza tylko rozklad, nie sprawdza czy kolejne losowania sa more or less
niezalezne. Wystarczy do calkowania funkcji metoda Monte Carlo, nie wystarczy do np.
symulowania procesow stochastycznych.

RW

do góry

On Thursday, December 22, 2011 8:28:34 AM UTC, bartekltg wrote:

> *) w pewnych przypadkach etc. Czasem nie jest to takie trywialne,
> np. rozkład normalny generuje się dość sprytnie.

Jezeli umiemy obliczyc odwrotnosc dystrybuanty, to jest latwe.

RW

do góry

On Thursday, December 22, 2011 12:09:57 AM UTC, Andrzej Jarzabek wrote:
> On 21/12/2011 19:37, Edek wrote:
> >
> > Z samego programowania dowody (pół)formalne stosuje
> > się przy algorytmach wątkowych. Żaden unit test nie pokaże
> > błędu wielowątkowego, co najwyżej wysypie się np. raz na 1e4.
>
> No więc jeśli wiesz, że błędna implementacja wysypie się raz na 1e4, to
> jeśli zrobiłeś test, który odpala się 1e6 razy, to masz znacznie lepszą
> gwarancję poprawności, niż gdybyś tylko zrobił dowód (pół)formalny.

A jak w produkcji algorytm wykonuje sie 24h na dobe co 10 milisekund, to takie dowody
poprawnosci mozna sobie, hmm, wsadzic w rurke.

RW

do góry

On Thursday, December 22, 2011 12:58:17 AM UTC, Michoo wrote:
> To ja Ci teraz napiszę o bugu, którego łatałem jakiś miesiąc temu a Ty
> podpowiesz jak dokumentacja załatwi problem:
> kod miał za zadanie wyszukać w każdej z dostarczonych kolekcji
> (przeglądanej liniowo) dane spełniające pewien predykat a następnie
> posortować wg innego predykatu. Na skutek drobnej pomyłki codera
> sortowanie wylądowało w wewnętrznej pętli, dzięki czemu złożoność
> przetwarzania pojedynczej kolekcji skoczyła z O(n log n) do O(n^2 log n).

Dokumentacja nie powstrzyma ludzkiej bezmyslnosci i nieuwagi, ale daje szanse ludziom
sumiennym i uwaznym.

RW

do góry