ballsbins.cu

// File: Balls_and_bins.cu
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/generate.h>
#include <thrust/sort.h>
#include <thrust/copy.h>
#include <thrust/unique.h>
#include <cstdlib>

struct rand_functor
{
    const int a;

    rand_functor(int _a) : a(_a) {}

    __host__ __device__
        int  operator()() const {
            return rand() % a;
        }
};


int main(void)
{
  for (int n =2; n< (2<<20); n *=2){

    thrust::host_vector<int> hv(n);
    thrust::generate(hv.begin(), hv.end(), rand_functor(n));
    thrust::device_vector<int> dv = hv;
    thrust::sort(dv.begin(), dv.end());
    thrust::device_vector<int>::iterator newend =
       thrust::unique(dv.begin(),dv.end());
    int numunique = newend - dv.begin();
    printf("#bins %d  # distinct: %d  ratio %f\n",n, numunique,  double (numunique) / n);
  }
    return 0;
}

/*
Output:

#bins 2  # distinct: 2  ratio 1.000000
#bins 4  # distinct: 2  ratio 0.500000
#bins 8  # distinct: 5  ratio 0.625000
#bins 16  # distinct: 12  ratio 0.750000
#bins 32  # distinct: 18  ratio 0.562500
#bins 64  # distinct: 36  ratio 0.562500
#bins 128  # distinct: 79  ratio 0.617188
#bins 256  # distinct: 163  ratio 0.636719
#bins 512  # distinct: 323  ratio 0.630859
#bins 1024  # distinct: 654  ratio 0.638672
#bins 2048  # distinct: 1291  ratio 0.630371
#bins 4096  # distinct: 2602  ratio 0.635254
#bins 8192  # distinct: 5154  ratio 0.629150
#bins 16384  # distinct: 10319  ratio 0.629822
#bins 32768  # distinct: 20801  ratio 0.634796
#bins 65536  # distinct: 41388  ratio 0.631531
#bins 131072  # distinct: 82811  ratio 0.631798
#bins 262144  # distinct: 165811  ratio 0.632519
#bins 524288  # distinct: 331535  ratio 0.632353
#bins 1048576  # distinct: 663439  ratio 0.632705
*/