[jira] [Updated] (MATH-1152) Suboptimal implementation of EnumeratedDistribution.sample()

["Andras Sereny (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/MATH-1152?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Andras Sereny updated MATH-1152:
--------------------------------
    Description: 
org.apache.commons.math3.distribution.EnumeratedDistribution.sample() performs a *linear* search to find the appropriate element in the probability space (called singletons here) given a random double value. For large probability spaces, this is not effective. Instead, we should cache the cumulative probabilities and do a *binary* search.

Rough implementation:
{code:title=EnumeratedDistribution.java|borderStyle=solid}
void computeCumulative() {
  cumulative = new double[size]; 
  double sum = 0;
  for (int i = 1; i < weights.length - 1; i++) {
      cumulative[i] = cumulative[i-1] + weights[i-1];
   }
  cumulative[size - 1] = 1;
}
{code}

and then 
{code:title=EnumeratedDistribution.java|borderStyle=solid}
int sampleIndex() {
 double randomValue = random.nextDouble();
 int result = Arrays.binarySearch(cumulative, randomValue);
 if (result >= 0) return result;
 int insertionPoint = -result-1;
 return insertionPoint;
}

{code}


  was:
org.apache.commons.math3.distribution.EnumeratedDistribution.sample() performs a *linear* search to find the appropriate element in the probability space (called singletons here) given a random double value. For large probability spaces, this is not effective. Instead, we should cache the cumulative probabilities and do a *binary* search.

Rough implementation:
{code:title=Bar.java|borderStyle=solid}
void computeCumulative() {
  cumulative = new double[size]; 
  double sum = 0;
  for (int i = 1; i < weights.length - 1; i++) {
      cumulative[i] = cumulative[i-1] + weights[i-1];
   }
  cumulative[size - 1] = 1;
}
{code}

and then 
{code:title=Bar.java|borderStyle=solid}
int sampleIndex() {
 double randomValue = random.nextDouble();
 int result = Arrays.binarySearch(cumulative, randomValue);
 if (result >= 0) return result;
 int insertionPoint = -result-1;
 return insertionPoint;
}

{code}



> Suboptimal implementation of EnumeratedDistribution.sample()
> ------------------------------------------------------------
>
>                 Key: MATH-1152
>                 URL: https://issues.apache.org/jira/browse/MATH-1152
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.3
>            Reporter: Andras Sereny
>
> org.apache.commons.math3.distribution.EnumeratedDistribution.sample() performs a *linear* search to find the appropriate element in the probability space (called singletons here) given a random double value. For large probability spaces, this is not effective. Instead, we should cache the cumulative probabilities and do a *binary* search.
> Rough implementation:
> {code:title=EnumeratedDistribution.java|borderStyle=solid}
> void computeCumulative() {
>   cumulative = new double[size]; 
>   double sum = 0;
>   for (int i = 1; i < weights.length - 1; i++) {
>       cumulative[i] = cumulative[i-1] + weights[i-1];
>    }
>   cumulative[size - 1] = 1;
> }
> {code}
> and then 
> {code:title=EnumeratedDistribution.java|borderStyle=solid}
> int sampleIndex() {
>  double randomValue = random.nextDouble();
>  int result = Arrays.binarySearch(cumulative, randomValue);
>  if (result >= 0) return result;
>  int insertionPoint = -result-1;
>  return insertionPoint;
> }
> {code}



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)