Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OKBJavaConnector/ECJClient/src/ec/util/RandomChoice.java @ 8451

Last change on this file since 8451 was 6152, checked in by bfarka, 14 years ago

added ecj and custom statistics to communicate with the okb services #1441

File size: 24.7 KB
Line 
1/*
2  Copyright 2006 by Sean Luke
3  Licensed under the Academic Free License version 3.0
4  See the file "LICENSE" for more information
5*/
6
7
8package ec.util;
9
10/*
11 * RandomChoice.java
12 *
13 * Created: January 5, 2001
14 * By: Sean Luke
15 *
16 */
17
18/**
19 * RandomChoice organizes arrays of floats into distributions which can
20 * be used to pick randomly from.  You can provide three kinds of arrays:
21 *
22 <ul>
23 <li> An array of floats
24 <li> An array of doubles
25 <li> An array of arbitrary objects, plus a RandomChoiceChooser which knows
26 how to get and set the appropriate "float" value of objects in this array.
27 </ul>
28 *
29 * <p>Before the RandomChoice can pick randomly from your array, it must first
30 * organize it.  It does this by doing the following.  First, it normalizes the
31 * values in the array.  Then it modifies them to their sums.  That is, each item i
32 * in the array is set to the sum of the original values for items 0...i.  If you
33 * cannot allow your objects to be modified, then this is not the class for you.
34 *
35 * <p>An array is valid if (1) it has no negative values and (2) not all of its
36 * values are zero.  This RandomChoice code <i>should</i> (I hope) guarantee that
37 * an element of zero probability is never returned.  RandomChoice uses a binary
38 * search to find your index, followed by linear probing (marching up or down
39 * the list) to find the first non-zero probability item in the vacinity of that
40 * index.  As long as there are not a whole lot of zero-valued items in a row,
41 * RandomChoice is efficient.
42 *
43 * You organize your array with organizeDistribution().  Then you can have the
44 * RandomChoice pick random items from the array and return their indexes to you.
45 * You do this by calling pickFromDistribution(), passing it a random floating
46 * point value between 0.0 and 1.0.  You call organizeDistribution() only once;
47 * after which you may call pickFromDistribution() as many times as you like.
48 * You should not modify the array thereafter.
49 *
50 * @author Sean Luke
51 * @version 1.0
52 */
53
54public class RandomChoice 
55    {
56
57    /** Same as organizeDistribution(probabilities,  <b>false</b>); */
58    public static void organizeDistribution(final float[] probabilities)
59        {
60        organizeDistribution(probabilities, false);
61        }
62
63    /** Normalizes probabilities, then converts them into continuing
64        sums.  This prepares them for being usable in pickFromDistribution.
65        If the probabilities are all 0, then selection is uniform, unless allowAllZeros
66        is false, in which case an ArithmeticException is thrown.  If any of them are negative,
67        or if the distribution is empty, then an ArithmeticException is thrown.
68        For example,
69        {0.6, 0.4, 0.2, 0.8} -> {0.3, 0.2, 0.1, 0.4} -> {0.3, 0.5, 0.6, 1.0} */
70
71    public static void organizeDistribution(final float[] probabilities, final boolean allowAllZeros)
72        {
73        // first normalize
74        double sum=0.0;
75        if (probabilities.length == 0)
76            throw new ArithmeticException("Distribution has no elements");
77           
78        for(int x=0;x<probabilities.length;x++)
79            {
80            if (probabilities[x]<0.0)
81                throw new ArithmeticException("Distribution has negative probabilities");
82            sum += probabilities[x];
83            }
84       
85        if (sum==0.0)
86            if (!allowAllZeros)
87                throw new ArithmeticException("Distribution has all zero probabilities");
88            else
89                {
90                for(int x=0;x<probabilities.length;x++)
91                    probabilities[x] = 1.0f;
92                sum = probabilities.length;
93                }
94       
95        for(int x=0;x<probabilities.length;x++)
96            probabilities[x] /= sum;
97
98        // now sum
99        sum=0.0;
100        for(int x=0;x<probabilities.length;x++)
101            {
102            sum += probabilities[x];
103            probabilities[x] = (float)sum;
104            }
105       
106        // now we need to work backwards setting 0 values
107        int x;
108        for(x=probabilities.length-1; x > 0; x--)
109            if (probabilities[x]==probabilities[x-1])  // we're 0.0
110                probabilities[x] = 1.0f;
111            else break;
112        probabilities[x] = 1.0f;
113        }
114
115    /** Same as organizeDistribution(probabilities,  <b>false</b>); */
116    public static void organizeDistribution(final double[] probabilities)
117        {
118        organizeDistribution(probabilities, false);
119        }
120
121    /** Normalizes probabilities, then converts them into continuing
122        sums.  This prepares them for being usable in pickFromDistribution.
123        If the probabilities are all 0, then selection is uniform, unless allowAllZeros
124        is false, in which case an ArithmeticException is thrown.  If any of them are negative,
125        or if the distribution is empty, then an ArithmeticException is thrown.
126        For example,
127        {0.6, 0.4, 0.2, 0.8} -> {0.3, 0.2, 0.1, 0.4} -> {0.3, 0.5, 0.6, 1.0} */
128
129    public static void organizeDistribution(final double[] probabilities, final boolean allowAllZeros)
130        {
131        // first normalize
132        double sum=0.0;
133
134        if (probabilities.length == 0)
135            throw new ArithmeticException("Distribution has no elements");
136
137        for(int x=0;x<probabilities.length;x++)
138            {
139            if (probabilities[x]<0.0)
140                throw new ArithmeticException("Distribution has negative probabilities");
141            sum += probabilities[x];
142            }
143
144        if (sum==0.0)
145            if (!allowAllZeros)
146                throw new ArithmeticException("Distribution has all zero probabilities");
147            else
148                {
149                for(int x=0;x<probabilities.length;x++)
150                    probabilities[x] = 1.0;
151                sum = probabilities.length;
152                }
153       
154        for(int x=0;x<probabilities.length;x++)
155            probabilities[x] /= sum;
156
157        // now sum
158        sum=0.0;
159        for(int x=0;x<probabilities.length;x++)
160            {
161            sum += probabilities[x];
162            probabilities[x] = sum;
163            }
164       
165        // now we need to work backwards setting 0 values
166        int x;
167        for(x=probabilities.length-1; x > 0; x--)
168            if (probabilities[x]==probabilities[x-1])  // we're 0.0
169                probabilities[x] = 1.0;
170            else break;
171        probabilities[x] = 1.0;
172
173        }
174
175    /** Same as organizeDistribution(objs, chooser, <b>false</b>); */
176    public static void organizeDistribution(final Object[] objs,
177        final RandomChoiceChooser chooser)
178        {
179        organizeDistribution(objs,chooser, false);
180        }
181
182    /** Normalizes the probabilities associated
183        with an array of objects, then converts them into continuing
184        sums.  This prepares them for being usable in pickFromDistribution.
185        If the probabilities are all 0, then selection is uniform, unless allowAllZeros
186        is false, in which case an ArithmeticException is thrown.  If any of them are negative,
187        or if the distribution is empty, then an ArithmeticException is thrown.
188        For example,
189        {0.6, 0.4, 0.2, 0.8} -> {0.3, 0.2, 0.1, 0.4} -> {0.3, 0.5, 0.6, 1.0}
190        The probabilities are retrieved and set using chooser.*/
191
192    public static void organizeDistribution(final Object[] objs,
193        final RandomChoiceChooser chooser, final boolean allowAllZeros)
194        {
195        // first normalize
196        double sum=0.0;
197
198        if (objs.length == 0)
199            throw new ArithmeticException("Distribution has no elements");
200
201        for(int x=0;x<objs.length;x++)
202            {
203            if (chooser.getProbability(objs[x])<0.0)
204                throw new ArithmeticException("Distribution has negative probabilities");
205            sum += chooser.getProbability(objs[x]);
206            }
207
208        if (sum==0.0)
209            if (!allowAllZeros)
210                throw new ArithmeticException("Distribution has all zero probabilities");
211            else
212                {
213                for(int x=0;x<objs.length;x++)
214                    chooser.setProbability(objs[x], 1.0f);
215                sum = objs.length;
216                }
217
218        for(int x=0;x<objs.length;x++)
219            chooser.setProbability(objs[x],
220                (float)(chooser.getProbability(objs[x]) / sum));
221
222        // now sum
223        sum=0.0;
224        for(int x=0;x<objs.length;x++)
225            {
226            sum += chooser.getProbability(objs[x]);
227            chooser.setProbability(objs[x],(float)sum);
228            }
229
230        // now we need to work backwards setting 0 values
231        int x;
232        for(x=objs.length-1; x > 0; x--)
233            if (chooser.getProbability(objs[x])==
234                chooser.getProbability(objs[x-1]))  // we're 0.0
235                chooser.setProbability(objs[x],1.0f);
236            else break;
237        chooser.setProbability(objs[x],1.0f);
238        }
239   
240    /** Same as organizeDistribution(objs, chooser, <b>false</b>); */
241    public static void organizeDistribution(final Object[] objs,
242        final RandomChoiceChooserD chooser)
243        {
244        organizeDistribution(objs,chooser, false);
245        }
246
247    /** Normalizes the probabilities associated
248        with an array of objects, then converts them into continuing
249        sums.  This prepares them for being usable in pickFromDistribution.
250        If the probabilities are all 0, then selection is uniform, unless allowAllZeros
251        is false, in which case an ArithmeticException is thrown.  If any of them are negative,
252        or if the distribution is empty, then an ArithmeticException is thrown.
253        For example,
254        {0.6, 0.4, 0.2, 0.8} -> {0.3, 0.2, 0.1, 0.4} -> {0.3, 0.5, 0.6, 1.0}
255        The probabilities are retrieved and set using chooser.*/
256
257    public static void organizeDistribution(final Object[] objs,
258        final RandomChoiceChooserD chooser, final boolean allowAllZeros)
259        {
260        // first normalize
261        double sum=0.0;
262
263        if (objs.length == 0)
264            throw new ArithmeticException("Distribution has no elements");
265
266        for(int x=0;x<objs.length;x++)
267            {
268            if (chooser.getProbability(objs[x])<0.0)
269                throw new ArithmeticException("Distribution has negative probabilities");
270            sum += chooser.getProbability(objs[x]);
271            }
272
273        if (sum==0.0)
274            if (!allowAllZeros)
275                throw new ArithmeticException("Distribution has all zero probabilities");
276            else
277                {
278                for(int x=0;x<objs.length;x++)
279                    chooser.setProbability(objs[x], 1.0);
280                sum = objs.length;
281                }
282
283        for(int x=0;x<objs.length;x++)
284            chooser.setProbability(objs[x],
285                (double)(chooser.getProbability(objs[x]) / sum));
286
287        // now sum
288        sum=0.0;
289        for(int x=0;x<objs.length;x++)
290            {
291            sum += chooser.getProbability(objs[x]);
292            chooser.setProbability(objs[x],(double)sum);
293            }
294
295        // now we need to work backwards setting 0 values
296        int x;
297        for(x=objs.length-1; x > 0; x--)
298            if (chooser.getProbability(objs[x])==
299                chooser.getProbability(objs[x-1]))  // we're 0.0
300                chooser.setProbability(objs[x],1.0);
301            else break;
302        chooser.setProbability(objs[x],1.0);
303        }
304
305
306    // allows us to have zero-probability values
307    private static final int exemptZeroes(final float[] probabilities, int index)
308        {
309        //System.out.println(index);
310        if (probabilities[index]==0.0f) // I need to scan forward because I'm in a left-trail
311            // scan forward
312            { while(index < probabilities.length-1 && probabilities[index]==0.0f) index++; }
313        else
314            // scan backwards
315            { while(index > 0 && probabilities[index]==probabilities[index-1]) index--; }
316        return index;
317        }
318
319    // allows us to have zero-probability values
320    private static final int exemptZeroes(final double[] probabilities, int index)
321        {
322        //System.out.println(index);
323        if (probabilities[index]==0.0) // I need to scan forward because I'm in a left-trail
324            // scan forward
325            { while(index < probabilities.length-1 && probabilities[index]==0.0) index++; }
326        else
327            // scan backwards
328            { while(index > 0 && probabilities[index]==probabilities[index-1]) index--; }
329        return index;
330        }
331
332
333    // allows us to have zero-probability values
334    private static final int exemptZeroes(final Object[] objs,
335        final RandomChoiceChooser chooser, int index)
336        {
337        //System.out.println(index);
338        if (chooser.getProbability(objs[index])==0.0f) // I need to scan forward because I'm in a left-trail
339            // scan forward
340            { while(index < objs.length-1 && chooser.getProbability(objs[index])==0.0f) index++; }
341        else
342            // scan backwards
343            { while(index > 0 && chooser.getProbability(objs[index])==
344                    chooser.getProbability(objs[index-1])) index--; }
345        return index;
346        }
347
348
349    // allows us to have zero-probability values
350    private static final int exemptZeroes(final Object[] objs,
351        final RandomChoiceChooserD chooser, int index)
352        {
353        //System.out.println(index);
354        if (chooser.getProbability(objs[index])==0.0) // I need to scan forward because I'm in a left-trail
355            // scan forward
356            { while(index < objs.length-1 && chooser.getProbability(objs[index])==0.0) index++; }
357        else
358            // scan backwards
359            { while(index > 0 && chooser.getProbability(objs[index])==
360                    chooser.getProbability(objs[index-1])) index--; }
361        return index;
362        }
363
364
365    public static final int CHECKBOUNDARY = 8;
366       
367    /** Picks a random item from an array of probabilities,
368        normalized and summed as follows:  For example,
369        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
370        they should get normalized and summed by the outside owners
371        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < CHECKBOUNDARY,
372        then a linear search is used, else a binary search is used. */
373
374    public static int pickFromDistribution(final float[] probabilities,
375        final float prob)
376        {
377        return pickFromDistribution(probabilities, prob, CHECKBOUNDARY);
378        }
379
380   
381    /** Picks a random item from an array of probabilities,
382        normalized and summed as follows:  For example,
383        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
384        they should get normalized and summed by the outside owners
385        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < checkboundary,
386        then a linear search is used, else a binary search is used.
387        @deprecated
388    */
389    public static int pickFromDistribution(final float[] probabilities,
390        final float prob, final int checkboundary)
391        {
392        if (prob<0.0f || prob>1.0f)
393            throw new ArithmeticException("Invalid probability for pickFromDistribution (must be 0.0<=x<=1.0)");
394        else if (probabilities.length==1) // quick
395            return 0;
396        else if (probabilities.length<checkboundary)
397            {
398            // simple linear scan
399            for(int x=0;x<probabilities.length-1;x++)
400                if (probabilities[x]>prob)
401                    return exemptZeroes(probabilities,x);
402            return exemptZeroes(probabilities,probabilities.length-1);
403            }
404        else
405            {
406            // binary search
407            int top = probabilities.length-1;
408            int bottom = 0;
409            int cur;
410
411            while(top!=bottom)
412                {
413                cur = (top + bottom) / 2; // integer division
414
415                if (probabilities[cur] > prob)
416                    if (cur==0 || probabilities[cur-1] <= prob)
417                        return exemptZeroes(probabilities,cur);
418                    else // step down
419                        top = cur;
420                else if (cur==probabilities.length-1) // oops
421                    return exemptZeroes(probabilities,cur);
422                else if (bottom==cur) // step up
423                    bottom++;  // (8 + 9)/2 = 8
424                else
425                    bottom = cur;  // (8 + 10) / 2 = 9
426                }
427            return exemptZeroes(probabilities,bottom);  // oops
428            }
429        }
430
431
432
433    /** Picks a random item from an array of probabilities,
434        normalized and summed as follows:  For example,
435        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
436        they should get normalized and summed by the outside owners
437        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < CHECKBOUNDARY,
438        then a linear search is used, else a binary search is used. */
439
440    public static int pickFromDistribution(final double[] probabilities,
441        final double prob)
442        {
443        return pickFromDistribution(probabilities, prob, CHECKBOUNDARY);
444        }
445
446   
447    /** Picks a random item from an array of probabilities,
448        normalized and summed as follows:  For example,
449        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
450        they should get normalized and summed by the outside owners
451        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < checkboundary,
452        then a linear search is used, else a binary search is used.
453        @deprecated
454    */
455   
456    public static int pickFromDistribution(final double[] probabilities,
457        final double prob, final int checkboundary)
458        {
459        if (prob<0.0 || prob>1.0)
460            throw new ArithmeticException("Invalid probability for pickFromDistribution (must be 0.0<=x<=1.0)");
461        if (probabilities.length==1) // quick
462            return 0;
463        else if (probabilities.length<checkboundary)
464            {
465            // simple linear scan
466            for(int x=0;x<probabilities.length-1;x++)
467                if (probabilities[x]>prob)
468                    return exemptZeroes(probabilities,x);
469            return exemptZeroes(probabilities,probabilities.length-1);
470            }
471        else
472            {
473            // binary search
474            int top = probabilities.length-1;
475            int bottom = 0;
476            int cur;
477
478            while(top!=bottom)
479                {
480                cur = (top + bottom) / 2; // integer division
481
482                if (probabilities[cur] > prob)
483                    if (cur==0 || probabilities[cur-1] <= prob)
484                        return exemptZeroes(probabilities,cur);
485                    else // step down
486                        top = cur;
487                else if (cur==probabilities.length-1) // oops
488                    return exemptZeroes(probabilities,cur);
489                else if (bottom==cur) // step up
490                    bottom++;  // (8 + 9)/2 = 8
491                else
492                    bottom = cur;  // (8 + 10) / 2 = 9
493                }
494            return exemptZeroes(probabilities,bottom);  // oops
495            }
496        }
497
498
499    /** Picks a random item from an array of objects, each with an
500        associated probability that is accessed by taking an object
501        and passing it to chooser.getProbability(obj).  The objects'
502        probabilities are
503        normalized and summed as follows:  For example,
504        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
505        they should get normalized and summed by the outside owners
506        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < CHECKBOUNDARY,
507        then a linear search is used, else a binary search is used. */
508   
509    public static int pickFromDistribution(final Object[] objs,
510        final RandomChoiceChooser chooser,
511        final float prob)
512        {
513        return pickFromDistribution(objs, chooser, prob, CHECKBOUNDARY);
514        }
515
516    /** Picks a random item from an array of objects, each with an
517        associated probability that is accessed by taking an object
518        and passing it to chooser.getProbability(obj).  The objects'
519        probabilities are
520        normalized and summed as follows:  For example,
521        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
522        they should get normalized and summed by the outside owners
523        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < checkboundary,
524        then a linear search is used, else a binary search is used.
525        @deprecated
526    */
527   
528    public static int pickFromDistribution(final Object[] objs,
529        final RandomChoiceChooser chooser,
530        final float prob, final int checkboundary)
531        {
532        if (prob<0.0f || prob>1.0f)
533            throw new ArithmeticException("Invalid probability for pickFromDistribution (must be 0.0<=x<=1.0)");
534        if (objs.length==1) // quick
535            return 0;
536        else if (objs.length<checkboundary)
537            {
538            // simple linear scan
539            for(int x=0;x<objs.length-1;x++)
540                if (chooser.getProbability(objs[x]) >prob)
541                    return exemptZeroes(objs,chooser,x);
542            return exemptZeroes(objs,chooser,objs.length-1);
543            }
544        else
545            {
546            // binary search
547            int top = objs.length-1;
548            int bottom = 0;
549            int cur;
550
551            while(top!=bottom)
552                {
553                cur = (top + bottom) / 2; // integer division
554
555                if (chooser.getProbability(objs[cur]) > prob)
556                    if (cur==0 || chooser.getProbability(objs[cur-1]) <= prob)
557                        return exemptZeroes(objs,chooser,cur);
558                    else // step down
559                        top = cur;
560                else if (cur==objs.length-1) // oops
561                    return exemptZeroes(objs,chooser,cur);
562                else if (bottom==cur) // step up
563                    bottom++;  // (8 + 9)/2 = 8
564                else
565                    bottom = cur;  // (8 + 10) / 2 = 9
566                }
567            return exemptZeroes(objs,chooser,bottom);  // oops
568            }
569        }
570
571
572    /** Picks a random item from an array of objects, each with an
573        associated probability that is accessed by taking an object
574        and passing it to chooser.getProbability(obj).  The objects'
575        probabilities are
576        normalized and summed as follows:  For example,
577        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
578        they should get normalized and summed by the outside owners
579        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < CHECKBOUNDARY,
580        then a linear search is used, else a binary search is used. */
581   
582    public static int pickFromDistribution(final Object[] objs,
583        final RandomChoiceChooserD chooser,
584        final double prob)
585        {
586        return pickFromDistribution(objs, chooser, prob, CHECKBOUNDARY);
587        }
588               
589    /** Picks a random item from an array of objects, each with an
590        associated probability that is accessed by taking an object
591        and passing it to chooser.getProbability(obj).  The objects'
592        probabilities are
593        normalized and summed as follows:  For example,
594        if four probabilities are {0.3, 0.2, 0.1, 0.4}, then
595        they should get normalized and summed by the outside owners
596        as: {0.3, 0.5, 0.6, 1.0}.  If probabilities.length < checkboundary,
597        then a linear search is used, else a binary search is used.
598        @deprecated
599    */
600   
601    public static int pickFromDistribution(final Object[] objs,
602        final RandomChoiceChooserD chooser,
603        final double prob, final int checkboundary)
604        {
605        if (prob<0.0 || prob>1.0)
606            throw new ArithmeticException("Invalid probability for pickFromDistribution (must be 0.0<=x<=1.0)");
607        if (objs.length==1) // quick
608            return 0;
609        else if (objs.length<checkboundary)
610            {
611            // simple linear scan
612            for(int x=0;x<objs.length-1;x++)
613                if (chooser.getProbability(objs[x]) >prob)
614                    return exemptZeroes(objs,chooser,x);
615            return exemptZeroes(objs,chooser,objs.length-1);
616            }
617        else
618            {
619            // binary search
620            int top = objs.length-1;
621            int bottom = 0;
622            int cur;
623
624            while(top!=bottom)
625                {
626                cur = (top + bottom) / 2; // integer division
627
628                if (chooser.getProbability(objs[cur]) > prob)
629                    if (cur==0 || chooser.getProbability(objs[cur-1]) <= prob)
630                        return exemptZeroes(objs,chooser,cur);
631                    else // step down
632                        top = cur;
633                else if (cur==objs.length-1) // oops
634                    return exemptZeroes(objs,chooser,cur);
635                else if (bottom==cur) // step up
636                    bottom++;  // (8 + 9)/2 = 8
637                else
638                    bottom = cur;  // (8 + 10) / 2 = 9
639                }
640            return exemptZeroes(objs,chooser,bottom);  // oops
641            }
642        }
643
644    }
645
646
647
648
Note: See TracBrowser for help on using the repository browser.