You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by lq...@apache.org on 2016/02/26 18:07:19 UTC
svn commit: r1732523 - in /qpid/java/trunk/perftests/src:
main/java/org/apache/qpid/disttest/controller/HillClimber.java
test/java/org/apache/qpid/disttest/controller/HillClimberTest.java
Author: lquack
Date: Fri Feb 26 17:07:18 2016
New Revision: 1732523
URL: http://svn.apache.org/viewvc?rev=1732523&view=rev
Log:
QPID-7038: [Java Perftests] Add Bias to HillClimber
Modified:
qpid/java/trunk/perftests/src/main/java/org/apache/qpid/disttest/controller/HillClimber.java
qpid/java/trunk/perftests/src/test/java/org/apache/qpid/disttest/controller/HillClimberTest.java
Modified: qpid/java/trunk/perftests/src/main/java/org/apache/qpid/disttest/controller/HillClimber.java
URL: http://svn.apache.org/viewvc/qpid/java/trunk/perftests/src/main/java/org/apache/qpid/disttest/controller/HillClimber.java?rev=1732523&r1=1732522&r2=1732523&view=diff
==============================================================================
--- qpid/java/trunk/perftests/src/main/java/org/apache/qpid/disttest/controller/HillClimber.java (original)
+++ qpid/java/trunk/perftests/src/main/java/org/apache/qpid/disttest/controller/HillClimber.java Fri Feb 26 17:07:18 2016
@@ -21,64 +21,174 @@ package org.apache.qpid.disttest.control
public class HillClimber
{
- private double _value;
- private double _delta;
- private boolean _expSearch = true;
- private int _direction = 0;
+ private final double _bias;
+ private StepPolicy _stepPolicy;
public HillClimber(double initialValue, double initialDelta)
{
- _value = initialValue;
- _delta = initialDelta / 2.0;
+ this(initialValue, initialDelta, 0.5);
+ }
+
+ public HillClimber(double initialValue, double initialDelta, double bias)
+ {
+ _stepPolicy = new UnknownDirectionStepPolicy(initialValue, initialDelta);
+ _bias = bias;
}
public double nextHigher()
{
- if (_direction == 0)
+ return _stepPolicy.nextHigher();
+ }
+
+ public double nextLower()
+ {
+ return _stepPolicy.nextLower();
+ }
+
+ public double getCurrentDelta()
+ {
+ return _stepPolicy.getCurrentDelta();
+ }
+
+ public double getBias()
+ {
+ return _bias;
+ }
+
+ private interface StepPolicy
+ {
+ double getCurrentDelta();
+ double nextHigher();
+ double nextLower();
+ }
+
+ private abstract class AbstractStepPolicy implements StepPolicy
+ {
+ protected double _value;
+ protected double _stepSize;
+
+ @Override
+ public double getCurrentDelta()
{
- _direction = 1;
+ return _stepSize;
}
- else if (_direction == -1)
+ }
+
+ private class UnknownDirectionStepPolicy extends AbstractStepPolicy
+ {
+ UnknownDirectionStepPolicy(final double initialValue, final double initialStepSize)
{
- _expSearch = false;
- _direction = 1;
+ _value = initialValue;
+ _stepSize = initialStepSize;
}
- return step();
+ @Override
+ public double nextHigher()
+ {
+ _stepPolicy = new ExponentialUpStepPolicy(_value, _stepSize);
+ return _stepPolicy.nextHigher();
+ }
+
+ @Override
+ public double nextLower()
+ {
+ _stepPolicy = new ExponentialDownStepPolicy(_value, _stepSize);
+ return _stepPolicy.nextLower();
+ }
}
- public double nextLower()
+ private class ExponentialUpStepPolicy extends AbstractStepPolicy
{
- if (_direction == 0)
+ private double _lastValue;
+
+ public ExponentialUpStepPolicy(final double initialValue, final double initialStepSize)
{
- _direction = -1;
+ _value = _lastValue = initialValue;
+ _stepSize = initialStepSize;
}
- else if (_direction == 1)
+
+ @Override
+ public double nextHigher()
{
- _expSearch = false;
- _direction = -1;
+ _lastValue = _value;
+ _value += _stepSize;
+ _stepSize *= 2;
+ return _value;
}
- return step();
+ @Override
+ public double nextLower()
+ {
+ _stepPolicy = new BisectionStepPolicy(_lastValue, _value, _value);
+ return _stepPolicy.nextLower();
+ }
}
- private double step()
+ private class ExponentialDownStepPolicy extends AbstractStepPolicy
{
- if (_expSearch)
+ private double _lastValue;
+
+ public ExponentialDownStepPolicy(final double initialValue, final double initialStepSize)
{
- _delta *= 2;
- _value += _direction * _delta;
+ this._value = _lastValue = initialValue;
+ this._stepSize = initialStepSize;
}
- else
+
+ @Override
+ public double nextHigher()
+ {
+ _stepPolicy = new BisectionStepPolicy(_value, _lastValue, _value);
+ return _stepPolicy.nextHigher();
+ }
+
+ @Override
+ public double nextLower()
{
- _delta /= 2.0;
- _value += _direction * _delta;
+ _lastValue = _value;
+ _value -= _stepSize;
+ _stepSize *= 2;
+ return _value;
}
- return _value;
}
- public double getCurrentDelta()
+ private class BisectionStepPolicy extends AbstractStepPolicy
{
- return _delta;
+ private double _lowerBound;
+ private double _upperBound;
+
+ public BisectionStepPolicy(double lowerBound, double upperBound, double currentValue)
+ {
+ _lowerBound = lowerBound;
+ _upperBound = upperBound;
+ _value = currentValue;
+ }
+
+ @Override
+ public double getCurrentDelta()
+ {
+ return _upperBound - _lowerBound;
+ }
+
+ @Override
+ public double nextHigher()
+ {
+ _lowerBound = _value;
+ return step();
+ }
+
+ @Override
+ public double nextLower()
+ {
+ _upperBound = _value;
+ return step();
+ }
+
+ private double step()
+ {
+ double delta = getCurrentDelta();
+ _value = _lowerBound + getBias() * delta;
+ return _value;
+ }
+
}
}
Modified: qpid/java/trunk/perftests/src/test/java/org/apache/qpid/disttest/controller/HillClimberTest.java
URL: http://svn.apache.org/viewvc/qpid/java/trunk/perftests/src/test/java/org/apache/qpid/disttest/controller/HillClimberTest.java?rev=1732523&r1=1732522&r2=1732523&view=diff
==============================================================================
--- qpid/java/trunk/perftests/src/test/java/org/apache/qpid/disttest/controller/HillClimberTest.java (original)
+++ qpid/java/trunk/perftests/src/test/java/org/apache/qpid/disttest/controller/HillClimberTest.java Fri Feb 26 17:07:18 2016
@@ -67,4 +67,59 @@ public class HillClimberTest extends Qpi
assertEquals(-96 + 10, hillClimber.nextLower(), EPSILON);
assertEquals(-104 + 10, hillClimber.nextLower(), EPSILON);
}
+
+ public void testExhaustiveCoverage()
+ {
+ assertExhaustiveCoverageForBias(0.5);
+ assertExhaustiveCoverageForBias(0.25);
+ assertExhaustiveCoverageForBias(0.66);
+ }
+
+ private void assertExhaustiveCoverageForBias(final double bias)
+ {
+ int numberOfBits = 5;
+ int maxValue = 1<<numberOfBits;
+ boolean valuesSeen[] = new boolean[maxValue];
+ double maxBias = Math.max(bias, 1-bias);
+ int maxHillClimberSteps = (int) Math.floor(-numberOfBits / log(maxBias, 2));
+ for (int bitPattern = 0; bitPattern < 1<<maxHillClimberSteps; ++bitPattern)
+ {
+ HillClimber hillClimber = new HillClimber(0, maxValue, bias);
+ double finalValue = -1;
+ // step twice to avoid initial exponential phase and position ourselves in the middle of the range
+ hillClimber.nextHigher();
+ hillClimber.nextLower();
+ for (int step = 0; step < maxHillClimberSteps; ++step)
+ {
+ boolean stepUp = getBit(bitPattern, maxHillClimberSteps - step - 1);
+ if (stepUp)
+ {
+ finalValue = hillClimber.nextHigher();
+ }
+ else
+ {
+ finalValue = hillClimber.nextLower();
+ }
+ if (hillClimber.getCurrentDelta() < 1)
+ {
+ break;
+ }
+ }
+ valuesSeen[(int)finalValue] = true;
+ }
+ for (int i = 0; i < maxValue; ++i)
+ {
+ assertTrue("HillClimber with bias=" + bias + " missed value " + i, valuesSeen[i]);
+ }
+ }
+
+ private static boolean getBit(long x, int bit)
+ {
+ return (x & (1<<bit)) != 0;
+ }
+
+ private static double log(double x, double base)
+ {
+ return Math.log(x) / Math.log(base);
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org