# Critique my recursive stochastic hill-climbing algorithm

This topic is 3165 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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]

##### Share on other sites
Just from a quick scan, there's some variables named such that their purpose is unclear, like
(Func<Double[], Double, Double> f
... f? Really? Give things names that make it clear what they are doing without scanning all the code to infer it from usage.

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
   } while (Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 50));

prefer
 } while (SomeSensibleName());
, same with;
  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.

##### Share on other sites
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.
        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);        }

##### Share on other sites
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);        }

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633674
• Total Posts
3013277
×