Erlang Central

Difference between revisions of "Generate Unique Values"

From ErlangCentral Wiki

Line 169:Line 169:
 
A sample of the first, naive generator for vectors of length 8 with values 1 to 10 is often failing, i.e., giving up, about 9 out of ten times. In case it succeeds, it takes from 25 up to 37 milliseconds.
 
A sample of the first, naive generator for vectors of length 8 with values 1 to 10 is often failing, i.e., giving up, about 9 out of ten times. In case it succeeds, it takes from 25 up to 37 milliseconds.
 
The second, optimized generator for vectors works much better. It always succeeds in around 4 milliseconds.
 
The second, optimized generator for vectors works much better. It always succeeds in around 4 milliseconds.
 +
 +
Thus, being a bit smart is indeed better in case your vector size is getting close to the possible numbers of values you can produce. Otherwise, it might be better to use the naive approach and make the specification very clear and keep the generator simple.

Revision as of 13:40, 11 December 2009


Contents

Authors

Thomas Arts with additional ideas from John Hughes

http://www.quviq.com/

Generating Unique Values

How to write a generator that produces unique values?

Normally, if you need unique values, there is some notion of 'state', only when there is state, it is important that a value differs from a previous value. For example, if you send a sequence of messages to a server and each message needs a unique tag, different from previous tags. The server 'remembers' the state and if you want to perform positive testing, you want to avoid sending the same tag twice.

Lists of unique values

It may be worth considering to just create a deterministic list and take consecutive values from that list.

unique() ->
   lists:seq(0,100).

This is very deterministic and no random testing is involved at all, but it may well suffice your purpose.

More advanced, if you do not use integers as values, you could create the list and filter out the values that occur more than once. Since all terms in Erlang can be compared, there is a very simple way to filter duplicates, just use lists:usort/1.

unique(Generator) ->
   ?LET(Values,list(Generator),
	lists:usort(Values)).

Note that efficiency is no issue in test value generation!

In some cases, having a strictly increasing lists of values may be insufficient for testing. One may want to shuffle the values around to see the subject under test handle that well.

shuffle([]) ->
    [];
shuffle(L) ->
    ?LET(X,elements(L),[X|shuffle(lists:delete(X,L))]).

One possibly nice thing about this is the way that it shrinks:

prop_shuffle() ->
    ?FORALL(L,shuffle(lists:seq(1,10)),
            false).


erlang> eqc:quickcheck(example:prop_shuffle()).
Failed! After 1 tests.
[1,10,3,8,6,2,5,9,4,7]
Shrinking......(6 times)
[1,2,3,4,5,6,7,8,9,10]
false

Which may be of value in your testing in case you are sure that in particular for sorted lists, your software should work.

Vectors of unique values

What if one wants to create a fixed amount of unique values, say a vector of length N. Once again, you may be happy with lists:seq(1,N), if you are happy with integers. You can even write a function from integers to your actual value that generates a unique value depending on your input.

Another surprisingly well working approach is to generate vectors until you get one with only unique numbers.

uvector(N,G) ->
    ?SUCHTHAT(V,vector(N,G),V--lists:usort(V)==[]).

This may seem rather inefficient, since many vectors may contain a duplicate and you throw the vector away and build a new one. It only seems, since this performs really well as long as the number of elements that G can generate is sufficiently larger than the length N of the vector.

erlang> eqc_gen:sample(example:uvector(20,eqc_gen:int()))).
[-17,27,8,21,2,-48,32,47,46,-31,5,33,-22,50,35,30,18,-37,26,37]
[2,1,-1,29,-22,4,31,-12,-30,24,-2,27,-28,-32,19,15,30,33,8,-23]
[10,36,-40,-34,9,-20,-5,29,24,-11,-8,20,19,-26,-37,21,38,40,-12,15]
[-44,20,15,38,-10,-11,28,-12,0,-23,5,44,10,4,-37,-27,30,1,16,-42]
[-27,3,-10,15,12,39,-35,-15,-13,-29,-1,-31,1,7,18,-11,-34,-8,2,34]
[17,23,0,-6,-5,21,-13,8,-19,-24,4,10,22,-21,-15,-11,-23,19,-16,-10]
[44,-36,-8,9,12,13,-33,41,24,36,6,-32,27,21,31,-24,-39,1,-40,25]
[23,2,-17,31,-5,-11,18,-38,38,-34,6,-10,-37,9,-26,-19,-14,-28,-39,-9]
[26,-9,31,-3,30,2,4,3,-13,13,32,-26,15,-5,-11,-6,-29,-2,-20,-27]
[-19,23,9,14,2,10,13,-8,-18,19,-7,15,16,-4,-13,-3,-1,4,-14,1]
[-40,-8,18,47,-34,-50,-37,36,5,22,-5,6,1,-26,23,26,14,2,51,-17]

It might feel counter-intuitive to generate random lists until finally one finds one in which no duplicates occur... The temptation is strong to be smarter than QuickCheck and do an "efficient" implementation. One way would be to generate new elements until that element has not been generated before until enough elements are generated.

uvector(0,Gen) ->
   [];
uvector(N,Gen) ->
   ?LET(Values,uvector(N-1,Gen),
        ?LET(Value,?SUCHTHAT(V,Gen, not lists:member(V,Values)),
             [Value|Values])).

A simple use of this generator could be to create unique integers or to fail on a unique vector of booleans.

9> eqc_gen:sample(example:uvector(16,eqc_gen:int())).
[-9,9,-7,-8,8,-5,2,-3,0,4,-6,6,10,-1,5,1]
[9,12,3,1,0,7,2,-9,-11,4,-2,11,-10,8,-3,10]
[13,-11,5,12,-1,10,-2,0,-10,-6,-7,3,-3,6,9,11]
[-10,9,-4,-13,1,-12,10,13,-6,-7,-14,6,-8,-11,2,-1]
[8,-2,9,-1,-11,-13,6,-8,3,15,4,-14,-7,-5,2,-3]
[-4,16,3,2,1,-13,5,0,-10,6,4,9,14,-8,-1,12]
[16,7,-5,14,-16,5,9,-10,-15,11,3,10,-2,-8,-6,-12]
[9,17,-9,-16,-3,3,-12,-13,8,7,-15,2,-5,15,13,-8]
[6,-7,18,-12,-16,-3,-17,-5,2,-6,16,4,3,11,-13,14]
[-6,18,19,20,-17,9,-14,1,15,-1,-4,-11,2,5,-18,8]
[-18,7,-7,-21,10,19,-16,-3,4,-11,3,-15,-12,-5,15,-2]
ok
10> eqc_gen:sample(example:uvector(4,eqc_gen:bool())).
** exception exit: "?SUCHTHAT failed to find a value within 100 attempts."
     in function  eqc_gen:sample/1

Is that so much better? We write a property that can be used to see the distribution for different vector lengths.

prop_uvector_dist(N,Nth) ->
    ?FORALL(L,uvector(N,choose(1,10)),
	    collect(lists:nth(Nth,L),true)).

For example, if we make a list of 4 elements, we expect an even distribution, i.e., 10% for each number in any position in that list.

71> eqc:quickcheck(unique:prop_uvector_dist(4,1)).
....................................................................................................
OK, passed 100 tests
17% 8
16% 1
12% 2
10% 5
10% 3
9% 7
8% 10
7% 6
6% 4
5% 9
true

This property generates vectors of 4 elements chosen from 1 to 10 and it collects how often each of the elements occurred at the first position. We expect 10% for each, but our sample is too little. We run 100,000 tests for lists of length 4 and we check for each position. For both versions of the generator (the first naive one and the second more optimized one), we obtain 10% for each number. We conclude that the distributions are both ok in these two generators. Now we look at the time difference.

We time generation by

erlang> timer:tc(eqc_gen,sample,[example:uvector(4,eqc_gen:choose(1,10))]).
[9,7,10,3]
[6,9,1,10]
[6,10,9,8]
[8,9,7,3]
[3,4,8,5]
[1,6,3,8]
[7,1,2,3]
[6,1,4,10]
[5,7,6,8]
[2,7,5,3]
[5,3,2,9]
{1782,ok}

That is, with the first naive generator, we need about 1,8 milliseconds to generate 11 values. When we repeat this a few times, we see very similar values. If we do the same for the optimized generator, we see similar values as well, around 1,8 milliseconds.

It becomes more interesting the more likely it becomes to find duplicates: A sample of the first, naive generator for vectors of length 8 with values 1 to 10 is often failing, i.e., giving up, about 9 out of ten times. In case it succeeds, it takes from 25 up to 37 milliseconds. The second, optimized generator for vectors works much better. It always succeeds in around 4 milliseconds.

Thus, being a bit smart is indeed better in case your vector size is getting close to the possible numbers of values you can produce. Otherwise, it might be better to use the naive approach and make the specification very clear and keep the generator simple.