I have a list $l$ containing integers in the range $[1,max]$
On list $l$ I do an operation $isPresent(x)$ which return
x is present in $l$.
I generate $x$ using the function $nextX()$ which generates the next $x$ on the fly using some random distribution
List $l$ and function $isPresent(x)$ put together is a system where list $l$ is a customized data structure similar to a binary search tree and $isPresent(x)$ is a new a algorithm similar to a binary search algorithm which efficiently operates on the data structure.
I want to test the performance of this system against known search trees and search algorithms.
The current method I'm using to benchmark these systems is, I generate a
random workload. I populate the list $l$ with uniform random numbers in the range $[1,max]$. Then I generate a uniform random number $x$ using $nextX()$ and pass it to the function $isPresent(x)$. I do $k$ such operations. Here the function $nextX()$ just calls $rand()$ to get the next random number.
What I wanted to try is a
skewed workload. I tried to use Poisson distribution in $nextX()$ to generate $x$ (Using Poisson distribution to generate random integers) with $mu$ as
max/1.1 but the standard deviation is small and the numbers generated are clustered close to $max$. I want to choose a discrete distribution other than uniform distribution but the values generated should
roughly cover the whole range $[1,max]$
Another workload which I want to generate should have the below property.
The function $nextX()$ should return an integer in the range $[1,max]$. If I call $nextX$ function $k$ times, some of the $k$ integers should be random but there can be a period where some of them could be a sorted sequence (ascending or desending)
For example, if $max=32$, then calling $nextX()$
18 times can return 17,11,23,5,7,17,23,30,2,31,17,1,19,14,8,6,5,2
Here the first
3 integers are random followed by a sorted sequence of random length
5, followed by a random sequence of integers of length
4 followed by a reverse sorted sequence of random length
I can achieve this by generating
18 sorted numbers and them randomly choosing number of partitions and on each partition I can randomly choose to shuffle them. But the problem with this is it needs lot of storage and the value of $k$ which represents the number of times the function $nextX()$ is invoked is very large so I want to generate this skewed distribution on the fly.
The reason I look to generate such a sequence is that an unbalanced binary search tree works well for random distribution as the height of the tree is close to $O(log(n))$. For sorted sequence the height can go as high as $O(n)$. In practice both are never the case. Workloads tend to be random with occasional sorted sequences interleaved.