14 юни 2012, четвъртък, 10:55:59 UTC+3, smichr написа: > > On Wed, Jun 13, 2012 at 7:43 PM, Aleksandar Makelov > <[email protected]> wrote: > > How does this work (and does it work) in sympy? > > > > A classical example is a Monte Carlo algorithm. Is there an accepted way > to > > test these in sympy? For one-sided Monte Carlo algorithms, we can easily > > test one direction in a deterministic way, but this doesn't feel very > > satisfactory. > > I see two aspects to a randomized algorithm: doing the right thing > with the random input and using good random number generation. Python > has addressed the latter, so we just need to make sure that the right > thing is being done with it. Let's say I had an MC integration > routine. If I sample the region randomly I should get a good result. > But however I sample it I need to be sure that I am doing the right > thing with the results. The latter (though it may give a bad answer > for bad input) is what I should test in sympy and I don't need more > than a minimum number of points to test it (depending on how many > branches in decisions there are for the algorithm) e.g. > > ``` > def MC_integr(xrange, yrange, shape, rand_seq): > area = xrange*yrange > hit = miss = 0 > for x in rand_seq: > for y in rand_seq: > if Point(x,y) in shape: hit += 1 > else: miss += 1 > if tolerance(hit, miss) is True: break # some routine that > figures out if the precision is ok > return hit/(hit+miss)*area > ``` > > This routine could be tested with a rand_seq of 4 elements: one giving > a point inside and one outside; the return area should be > xrange*yrange/2. The tolerance function could be tested independently > to see that if hit+miss > 1000 (or whatever) that it quits. > > Yes, this way of testing randomized output (testing whether the right thing is done with random numbers) seems both reasonable and feasible. For anyone else following this discussion, see here: https://github.com/sympy/sympy/pull/1353#issuecomment-6322159 which is also relevant. One bad thing about it is that we'll have to add more arguments to the functions being tested (to store a particular precomputed randomized output) and make their code a bit more complex solely for the purposes of testing. I don't think that's such a drawback (well, it will slow down some functions that are frequently used by a really minor amount, but I guess that's OK).
Another potential downfall is that in some algorithms there are many random choices made, so coming up with a test might become ugly. I guess if we stick to small examples this won't be such a big pain. My third concern is that this kind of testing is sort of implementation-specific, so if someone changes the algorithm with another possible randomized implementation, the test are going to have to be rewritten. > > > > Another example is the algorithms outputting random group elements that > are > > supposed to be nearly uniformly distributed in the group. > > If they are selected by integers which themselves have been tested to > be uniformly distributed (i.e. python's generator) then I don't think > you have to test the sympy output. But perhaps I am misunderstanding. > Well, python's generator is certainly used, but things are more complicated than that. For starters, the algorithm outputs elements that are *nearly* uniformly distributed, and if you look at them they don't really seem uniformly distributed at all (their *properties* are said to be uniform enough for most algorithms using random elements). I think that some sort of statistical testing is not going to help here (and such tests have a small probability of failing anyway), however something like the idea described above might work. Again, loading the precomputed random elements is probably going to be ugly. -- You received this message because you are subscribed to the Google Groups "sympy" group. To view this discussion on the web visit https://groups.google.com/d/msg/sympy/-/xDoUgwovED8J. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
