Critique my recursive stochastic hill-climbing algorithm
Author
I have a recursive stochastic hill-climbing algorithm for solving equations.
The things I would like to work on are performance, efficiency and my own understanding of the algorithm, as I worked it out through a combination of intuition, mathematical instinct and late-night braining.
*Snip*
Latest two code sections at the bottom.
[Edited by - Narf the Mouse on April 12, 2010 10:02:56 PM]
Just from a quick scan, there's some variables named such that their purpose is unclear, like
EquationSolveWithin takes a lot of arguments and has a shedload of data, can it be broken up into smaller methods with their own concern. Don't speculate on the performance implications of this just yet; this looks like c#, the JIT may observe the heat (high call frequency) of one of your smaller methods and optimise it further than it can with such a large method. Either way, strive for clarity over speculative performance gains.
Ditch the commented out code, it's a distraction. Don't leave in "debug hook" code, use conditional breakpoints.
Break conditions like the following out into sensibly named methods i.e instead of
prefer
These are stylistic but the will help reason about the algorithm. This is what I'd do before any actual tweaking, your mileage may vary.
(Func<Double[], Double, Double> fEquationSolveWithin takes a lot of arguments and has a shedload of data, can it be broken up into smaller methods with their own concern. Don't speculate on the performance implications of this just yet; this looks like c#, the JIT may observe the heat (high call frequency) of one of your smaller methods and optimise it further than it can with such a large method. Either way, strive for clarity over speculative performance gains.
Ditch the commented out code, it's a distraction. Don't leave in "debug hook" code, use conditional breakpoints.
Break conditions like the following out into sensibly named methods i.e instead of
} while (Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 50));prefer
} while (SomeSensibleName()); if ((closest.HasValue && high < closest && oldHigh > target) ||(closest.HasValue && high > closest && oldHigh < target))and if ((closest.HasValue && low > closest && oldHigh > target) ||(closest.HasValue && low < closest && oldHigh < target)) These are stylistic but the will help reason about the algorithm. This is what I'd do before any actual tweaking, your mileage may vary.
Author
Ok, I've put all the complicated checks into their own functions; in doing so, I found one legacy check that was unnecessary, as it was doing the same thing wether it returned true or false, so that's been optimized out.
And thanks.
And thanks.
public static List<Double> EquationSolver(Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target = 0, Filter filter = null) { List<Double> list = new List<double>(); EquationSolveWithin(equationToSolve, inputs, target, 0, Double.MaxValue, ref list, filter); EquationSolveWithin(equationToSolve, inputs, target, 0, (-Double.MaxValue), ref list, filter); return list; } public static void EquationSolveWithin( Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target, Double low, Double high, ref List<Double> list, Filter filter ) { Double current = ((high - low) / 2.0) + low; Double output = 0; Double? firstOutput = null; bool reverse = false; Double distance = high * high * high; Double lastDistance = high * high * high; Double oldLow = low; Double oldHigh = high; Double tempLow = low; Double tempHigh = high; Double? closest = null; Double closestDistance = 0; int iterationsWithoutBetter = 0; bool foundCloser = false; do { current = ((high - low) / 2.0) + low; /* if (!firstOutput.HasValue) current = ((high - low) / 2.0) + low; else current = ((high - low) * GeneralData.Random.NextDouble()) + low; */ tempLow = low; tempHigh = high; lastDistance = distance; output = equationToSolve(inputs, current); if (!firstOutput.HasValue) { firstOutput = output; distance = output - target; lastDistance = output - target; closestDistance = output - target; closest = current; foundCloser = true; iterationsWithoutBetter = 0; } distance = output - target; /* if (high <= 20000) { int j = 0; ++j; } */ if (ShouldReverse(distance, lastDistance)) reverse = !reverse; if (!reverse) { high = current; // high = ((high - current) / 2.0) + current; } else { low = current; // low = ((current - low) / 2) + low; } foundCloser = false; ++iterationsWithoutBetter; if (Math.Abs(distance) <= Math.Abs(closestDistance)) { closestDistance = output - target; closest = current; foundCloser = true; iterationsWithoutBetter = 0; } if (GoneToFarA(target, high, oldHigh, closest)) { if (!reverse) high = closest.Value * 2; else low = closest.Value / 2; } if (GoneToFarB(target, low, oldHigh, closest)) { if (!reverse) low = closest.Value / 2; else high = closest.Value * 2; } } while ( NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser) ); Boolean passedFilter = PassedFilter(filter, current); if (NewAndValid(target, list, current, output, passedFilter)) { list.Add(Math.Round(current, 11)); EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter); EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter); } // -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 = // x1 = 2.6220971863491 // x2 = 1.3224569490446 // x3 = 0.1859002930856 // x4 = -1.9980761764108 // x5 = -1.1850098310158 } private static bool ShouldReverse(Double distance, Double lastDistance) { return (distance > 0 && lastDistance < 0) || (distance < 0 && lastDistance > 0) || (Math.Abs(distance) > Math.Abs(lastDistance)); } private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest) { return (closest.HasValue && high < closest.Value && oldHigh > target) || (closest.HasValue && high > closest.Value && oldHigh < target); } private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest) { return (closest.HasValue && low > closest.Value && oldHigh > target) || (closest.HasValue && low < closest.Value && oldHigh < target); } private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser) { return Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 15); } private static Boolean PassedFilter(Filter filter, Double current) { Boolean passedFilter = false; if (filter != null) { double? first = filter.value; double? second = filter.Process(current); passedFilter = (first != second); } else passedFilter = true; return passedFilter; } private static bool NewAndValid(Double target, List<Double> list, Double current, Double output, Boolean passedFilter) { return passedFilter && !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11); }
Author
It wasn't correctly filtering; I've fixed that. Also, I've added an optional "searchRange" potential optimization.
public static List<Double> EquationSolver( Func<Double[], Double, Double> equationToSolve, Double[] inputs, double target = 0, Filter filter = null, double searchRange = Double.MaxValue) { List<Double> list = new List<double>(); EquationSolveWithin(equationToSolve, inputs, target, 0, searchRange, ref list, filter); EquationSolveWithin(equationToSolve, inputs, target, 0, (-searchRange), ref list, filter); return list; } public static void EquationSolveWithin( Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target, Double low, Double high, ref List<Double> list, Filter filter ) { Double current = ((high - low) / 2.0) + low; Double output = 0; Double? firstOutput = null; bool reverse = false; Double distance = high * high * high; Double lastDistance = high * high * high; Double oldLow = low; Double oldHigh = high; Double tempLow = low; Double tempHigh = high; Double? closest = null; Double closestDistance = 0; int iterationsWithoutBetter = 0; bool foundCloser = false; do { current = ((high - low) / 2.0) + low; /* if (!firstOutput.HasValue) current = ((high - low) / 2.0) + low; else current = ((high - low) * GeneralData.Random.NextDouble()) + low; */ tempLow = low; tempHigh = high; lastDistance = distance; output = equationToSolve(inputs, current); if (!firstOutput.HasValue) { firstOutput = output; distance = output - target; lastDistance = output - target; closestDistance = output - target; closest = current; foundCloser = true; iterationsWithoutBetter = 0; } distance = output - target; /* if (high <= 20000) { int j = 0; ++j; } */ if (ShouldReverse(distance, lastDistance)) reverse = !reverse; if (!reverse) { high = current; // high = ((high - current) / 2.0) + current; } else { low = current; // low = ((current - low) / 2) + low; } foundCloser = false; ++iterationsWithoutBetter; if (Math.Abs(distance) <= Math.Abs(closestDistance)) { closestDistance = output - target; closest = current; foundCloser = true; iterationsWithoutBetter = 0; } if (GoneToFarA(target, high, oldHigh, closest)) { if (!reverse) high = closest.Value * 2; else low = closest.Value / 2; } if (GoneToFarB(target, low, oldHigh, closest)) { if (!reverse) low = closest.Value / 2; else high = closest.Value * 2; } } while ( NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser) ); if (NewAndValid(target, list, current, output)) { if (PassedFilter(filter, current)) { list.Add(Math.Round(current, 11)); EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter); EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter); } } // -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 = // x1 = 2.6220971863491 // x2 = 1.3224569490446 // x3 = 0.1859002930856 // x4 = -1.9980761764108 // x5 = -1.1850098310158 } private static bool ShouldReverse(Double distance, Double lastDistance) { return (distance > 0 && lastDistance < 0) || (distance < 0 && lastDistance > 0) || (Math.Abs(distance) > Math.Abs(lastDistance)); } private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest) { return (closest.HasValue && high < closest.Value && oldHigh > target) || (closest.HasValue && high > closest.Value && oldHigh < target); } private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest) { return (closest.HasValue && low > closest.Value && oldHigh > target) || (closest.HasValue && low < closest.Value && oldHigh < target); } private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser) { return Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 15); } private static Boolean PassedFilter(Filter filter, Double current) { Boolean passedFilter = false; if (filter != null) { double? first = filter.value; double? second = filter.Process(current); passedFilter = (first != second); } else passedFilter = true; return passedFilter; } private static bool NewAndValid(Double target, List<Double> list, Double current, Double output) { return !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11); }This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
