daily pastebin goal
16%
SHARE
TWEET

Shuffle effectiveness testing

Archon Feb 5th, 2012 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // (C) 2012 Tim Gurto
  2.  
  3. #include <iostream>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <ctime>
  8. #include <list>
  9.  
  10. double correlation(int *xData, int *yData, int size){
  11.    assert(size > 0);
  12.  
  13.    //calculate means
  14.    double xMean = 0, yMean = 0;
  15.    for (int i = 0; i != size; ++i){
  16.       xMean += xData[i];
  17.       yMean += yData[i];
  18.    }
  19.    xMean /= size;
  20.    yMean /= size;
  21.  
  22.    //calculate sums
  23.    double
  24.       sumXX = 0,
  25.       sumYY = 0,
  26.       sumXY = 0;
  27.    for (int i = 0; i != size; ++i){
  28.       double
  29.          xDiff = xData[i] - xMean,
  30.          yDiff = yData[i] - yMean;
  31.       sumXX += xDiff * xDiff;
  32.       sumYY += yDiff * yDiff;
  33.       sumXY += xDiff * yDiff;
  34.    }
  35.  
  36.    return sumXY / sqrt(sumXX * sumYY);
  37. }
  38.  
  39. void bubbleShuffle(int *data, int size){
  40.    for (int i = 0; i != size-1; ++i)
  41.       for (int j = 0; j != size-1-i; ++j)
  42.          if (rand() % 2){
  43.             int temp = data[j];
  44.             data[j] = data[j+1];
  45.             data[j+1] = temp;
  46.          }
  47. }
  48.  
  49. void selectionShuffle(int *data, int size){
  50.    
  51.    //copy into list
  52.    std::list<int> list;
  53.    for (int i = 0; i != size; ++i)
  54.       list.push_back(data[i]);
  55.  
  56.    //select back to array
  57.    for (int i = 0; i != size; ++i){
  58.       //navigate to random element
  59.       int n = rand() % list.size();
  60.       std::list<int>::const_iterator it = list.begin();
  61.       while (n-- > 0)
  62.          ++it;
  63.       data[i] = *it;
  64.       list.erase(it);
  65.    }
  66.  
  67. }
  68.  
  69. double testShuffle(void (*shuffleFun)(int *data, int size)){
  70.    const static int SIZE = 1000;
  71.    const static int TESTS = 100;
  72.    int data[SIZE];
  73.    for (int i = 0; i != SIZE; ++i)
  74.       data[i] = i;
  75.  
  76.    //tests
  77.    double averageCorrelation = 0;
  78.    for (int testNum = 0; testNum != TESTS; ++testNum){
  79.  
  80.       //shuffle
  81.       int shuffledData[SIZE];
  82.       for (int i = 0; i != SIZE; ++i)
  83.          shuffledData[i] = i;
  84.       shuffleFun(data, SIZE);
  85.  
  86.       //add correlation
  87.      averageCorrelation += correlation(data, shuffledData, SIZE);
  88.    }
  89.  
  90.    //average and return
  91.    averageCorrelation /= TESTS;
  92.    return 1 - abs(averageCorrelation);
  93. }
  94.  
  95. int main(){
  96.    srand(time(0));
  97.    std::cout << "   Bubble shuffle: " << testShuffle(bubbleShuffle) << std::endl;
  98.    std::cout << "Selection shuffle: " << testShuffle(selectionShuffle) << std::endl;
  99. }
RAW Paste Data
Top