Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: issues@commons.apache.org
Date: Fri, 12 Sep 2014 07:47:33 +0000 (UTC)
From: "Andras Sereny (JIRA)" <jira@apache.org>
To: issues@commons.apache.org
Message-ID: <JIRA.12740986.1410507998000.16768.1410508053919@Atlassian.JIRA>
In-Reply-To: <JIRA.12740986.1410507998000@Atlassian.JIRA>
References: <JIRA.12740986.1410507998000@Atlassian.JIRA>
 <JIRA.12740986.1410507998029@arcas>
Subject: [jira] [Created] (MATH-1152) Suboptimal implementation of
 EnumeratedDistribution.sample()
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit

Andras Sereny created MATH-1152:
-----------------------------------

             Summary: 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=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}


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