0

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.

Improve this question
4
  • @gnat ...It's similar, yet different. It's not just testing randomness, but more ensuring that the weight probability holds.
    – dagnelies
    Sep 29, 2017 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, 2017 at 15:49
  • @amon: IMHO mocking the randomness source is useless in this case.
    – dagnelies
    Sep 29, 2017 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, 2017 at 16:45

1 Answer 1

Reset to default
-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).

Improve this answer
5
  • commenting a downvote is always welcome.
    – dagnelies
    Sep 29, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 12:45

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