contrib/psg/src/peersim/util/WeightedRandPerm.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.util;
  20
  21 import java.util.NoSuchElementException;
  22 import java.util.Random;
  23
  24 /**
  25 * This class provides a weighted random permutation of indexes.
  26 * Useful for weighted random sampling without replacement.
  27 * The next sample is taken according to the weights given as a parameter
  28 * to {@link #reset(int)}.
  29 * The weights work as follows.
  30 * The first sample is drawn according to the probability distribution
  31 * defined by the (normalized) weights.
  32 * After this the remaining k-1 elements and the associated k-1
  33 * (re-normalized) weights
  34 * define a new probability distribution, according to which the 2nd element
  35 * is drawn, and so on.
  36 */
  37 public class WeightedRandPerm implements IndexIterator {
  38
  39
  40 // ======================= private fields ============================
  41 // ===================================================================
  42
  43 /** Holds the weights that are used to initialize the permutation */
  44 private final double[] w;
  45
  46 /** Holds the sum of the weights until the given index, inclusive. */
  47 private final double[] wsum;
  48
  49 private int[] buffer = null;
  50
  51 /** Working array for calculating the permutation */
  52 private double[] weights = null;
  53
  54 private int len = 0;
  55
  56 private int pointer = 0;
  57
  58 private double sum = 0.0;
  59
  60 private final Random r;
  61
  62
  63 // ======================= initialization ============================
  64 // ===================================================================
  65
  66
  67 /** Set the source of randomness to use and the weights. You need to call
  68 * {@link #reset} to fully initialize the object.
  69 * @param r source of randomness
  70 * @param weights The array that holds the weights for the calculation of the
  71 * permutation. The length of the array will be an upper bound on the
  72 * parameter {@link #reset} accepts. If {@link #reset} is called with a
  73 * parameter less than the length of weights, the prefix of the same length
  74 * is used.
  75 * The vector elements must be positive, that is, zero is not accepted either.
  76 */
  77 public WeightedRandPerm( Random r, double[] weights ) {
  78
  79         this.r=r;
  80         w = weights.clone();
  81         wsum = weights.clone();;
  82         this.weights = new double[w.length];
  83         buffer = new int[w.length];
  84
  85         for(int i=0; i<w.length; ++i)
  86         {
  87                 if( w[i] <= 0.0 ) throw new IllegalArgumentException(
  88                         "weights should be positive: w["+i+"]="+w[i]);
  89         }
  90
  91         for(int i=1; i<w.length; ++i) wsum[i]+=wsum[i-1];
  92 }
  93
  94
  95 // ======================= public methods ============================
  96 // ===================================================================
  97
  98
  99 /**
 100 * It initiates a random weighted permutation of the integeres from 0 to k-1.
 101 * It does not actually calculate the permutation.
 102 * The permutation can be read using method {@link #next}.
 103 * If the previous permutation was of the same length, it is more efficient.
 104 * The weights set at construction time work as follows.
 105 * The first sample is drawn according to the probability distribution
 106 * defined by the (normalized) weights.
 107 * After this the remaining k-1 elements and the associated k-1
 108 * (re-normalized) weights
 109 * define a new probability distribution, according to which the 2nd element
 110 * is drawn, and so on.
 111 * @param k the set is defined as 0,...,k-1
 112 */
 113 public void reset(int k) {
 114
 115         if( k<0 || k>w.length )
 116                 throw new IllegalArgumentException(
 117                         "k should be non-negative and <= "+w.length);
 118
 119         pointer = k;
 120         sum = wsum[k-1];
 121
 122         if( k != len )
 123         {
 124                 // we need to initialize weights and buffer
 125                 for(int i=0; i<k; ++i)
 126                 {
 127                         weights[i]=w[i];
 128                         buffer[i]=i;
 129                 }
 130                 len=k;
 131         }
 132 }
 133
 134 // -------------------------------------------------------------------
 135
 136 /**
 137 * The first sample is drawn according to the probability distribution
 138 * defined by the (normalized) weights.
 139 * After this the remaining k-1 elements and the associated k-1
 140 * (re-normalized) weights
 141 * define a new probability distribution, according to which the 2nd element
 142 * is drawn, and so on.
 143 * @see #reset
 144 */
 145 public int next() {
 146
 147         if( pointer < 1 ) throw new NoSuchElementException();
 148
 149         double d = sum*r.nextDouble();
 150         int i = pointer;
 151         double tmp = weights[i-1];
 152         while( tmp < d && i>1 ) tmp += weights[--i-1];
 153
 154         // now i-1 is the selected element, we shift it to next position
 155         int a = buffer[i-1];
 156         double b = weights[i-1];
 157         buffer[i-1] = buffer[pointer-1];
 158         weights[i-1] = weights[pointer-1];
 159         buffer[pointer-1] = a;
 160         weights[pointer-1] = b;
 161         sum -= b;
 162
 163         return buffer[--pointer];
 164 }
 165
 166 // -------------------------------------------------------------------
 167
 168 public boolean hasNext() { return pointer > 0; }
 169
 170 // -------------------------------------------------------------------
 171
 172 /*
 173 public static void main( String pars[] ) throws Exception {
 174
 175
 176         int k = pars.length;
 177         double w[] = new double[k];
 178         for(int i=0; i<k; ++i) w[i] = Double.parseDouble(pars[i]);
 179
 180         WeightedRandPerm rp = new WeightedRandPerm(new Random(),w);
 181         rp.reset(k);
 182         for(int i=0; i<1000; ++i)
 183         {
 184                 if(i%2==0) rp.reset(k);
 185                 if(i%2==1) rp.reset(k-1);
 186                 while(rp.hasNext()) System.out.print(rp.next()+" ");
 187                 System.out.println();
 188         }
 189
 190         System.out.println();
 191 }
 192 */
 193 }
 194