0

This question already has an answer here:

There are strings and each string has a weight in a data structure. The getRandom() method should return a string randomly with its weight/total weight probability.

There is already a question on how to define this getRandom() method on stackexchange.

But this question is about how to test this getRandom() method?

Any ideas would be really helpful. Thank you.

marked as duplicate by gnat, amon, Greg Burghardt, Christophe, Bart van Ingen Schenau Sep 29 '17 at 16:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • @gnat ...It's similar, yet different. It's not just testing randomness, but more ensuring that the weight probability holds. – dagnelies Sep 29 '17 at 15:38
  • 1
    @dagnelies The duplicate also discusses how to test algorithms that involve randomness (e.g. by mocking the randomness source). That seems to fit here. – amon Sep 29 '17 at 15:49
  • @amon: IMHO mocking the randomness source is useless in this case. – dagnelies Sep 29 '17 at 15:55
  • @dagnelies, All the considerations for testing randomness apply, except that you don't expect an equal probability for each of the outcomes. – Bart van Ingen Schenau Sep 29 '17 at 16:45
-2

I would do it like this:

Call getRandom() millions of times. The more you call it, the more the frequency histogram of the string occurences is closer to the string weights. Then, basically, if all frequencies are close enough to the weights (using an arbitrary delta), the test passes, otherwise it fails.

Note that false positive/negative are possible, but with sensible values of N and delta it should be rare.

It is probably also possible to compute a % of likelihood more accurately using statistical methods, although it might be overhead .

Although it is not perfect in every way, it makes it possible to detect most implementation failures (resulting in a wrong distribution).

  • commenting a downvote is always welcome. – dagnelies Sep 29 '17 at 15:47
  • 2
    If you're testing for randomness then simply testing the resulting distribution is insufficient, e.g. compare the stronger diehard tests. If you're testing a randomized algorithm then testing for randomness is slow+wasteful, and only ensures weak properties. It may be better to test the algorithm in isolation, by injecting a non-random number source chosen to trigger certain states. See also: Where is the line between unit testing application logic and distrusting language constructs? – amon Sep 29 '17 at 15:59
  • The first random number generator I ever used had a reasonable frequency histogram, but it had the absurd property that on two consecutive calls, the second one produced a bigger result 60% of the time. That would be one of the more trivial things that the diehard tests would find. – gnasher729 Sep 30 '17 at 12:27
  • Well, I stand to my point. In the vast majority of cases, you're just using the default random number generator of a mainstream programming language, which is a "good" one ...in the vast majority of cases. So trying to mock it is useless IMHO. – dagnelies Sep 30 '17 at 12:43
  • Sometimes I even wonder if people read the questions and comments correctly. The OP question is not about testing a random number generator. It's about testing a weighted data structure. All this "diehard tests" cannot be applied directly, and it's not clear how it should be adapted in this context. – dagnelies Sep 30 '17 at 12:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.