hillclimbing.cpp

C语言库函数的原型,有用的拿去

        return (m_count == 0) ? 0.0 : (m_sum / m_count);
    }

    /// <summary>
    ///     Computes the coefficient of variation for a given history.
    /// </summary>
    /// <returns>
    ///     The coefficient of variation.
    /// </returns>
    double HillClimbing::MeasuredHistory::CoefficientOfVariation()
    {
        double mean = Mean();
        return (mean <= 0.0) ? 0.0 : (StandardDeviation() / mean);
    }

    /// <summary>
    ///     Computes the mean of coefficients of variation for a given history.
    /// </summary>
    /// <returns>
    ///     The mean of coefficients of variation.
    /// </returns>
    double HillClimbing::MeasuredHistory::CoefficientOfVariationMean()
    {
        return (StandardDeviation() / sqrt(1.0 * m_count)) / Mean();
    }

    /// <summary>
    ///     Computes the variance for a given history.
    /// </summary>
    /// <returns>
    ///     The variance.
    /// </returns>
    double HillClimbing::MeasuredHistory::Variance()
    {
        const double smallValue = 0.0001;
        double variance = 0.0;

        if (m_count >= 2)
        {
            variance = (m_sumOfSquares - (m_sum * m_sum)/ m_count)/ (m_count - 1);		
        }

        return abs(variance) > smallValue ? variance : 0;
    }

    /// <summary>
    ///     Computes the mean of variances for a given history.
    /// </summary>
    /// <returns>
    ///     The mean of variances.
    /// </returns>
    double HillClimbing::MeasuredHistory::VarianceMean()
    {
        return Variance() / Count();
    }

    /// <summary>
    ///     Computes the standard deviation for a given history.
    /// </summary>
    /// <returns>
    ///     The standard deviation.
    /// </returns>
    double HillClimbing::MeasuredHistory::StandardDeviation()
    {
        return sqrt(Variance());
    }

    /// <summary>
    ///     Computes the mean of standard deviations for a given history.
    /// </summary>
    /// <returns>
    ///     The mean of standard deviations.
    /// </returns>
    double HillClimbing::MeasuredHistory::StandardDeviationMean()
    {
        return (m_count == 0) ? 0.0 : (StandardDeviation() / sqrt(m_count * 1.0));
    }

    /// <summary>
    ///     Tests if the difference between two measurement histories is statistically significant to
    ///     make a hill climbing decision.
    /// </summary>
    /// <remarks>
    ///     A two sided test is used.
    /// </remarks>
    /// <param name="value">
    ///     The value representing the second history.
    /// </param>
    /// <param name="significanceLevel">
    ///     The significance level in percent. Accepts 1 through 10.
    /// </param>
    /// <param name="totalSampleCount">
    ///     The value representing the total number of samples for this history, including invalid samples and samples for previous settings.
    /// </param>
    /// <returns>
    ///     -1 - second history is larger than this history
    ///      0 - statistically identical
    ///      1 - this history is larger than second history
    /// </returns>
    int HillClimbing::MeasuredHistory::SignificanceTest(double value, const int significanceLevel, unsigned int totalSampleCount)
    {
        MeasuredHistory singleValue;
        singleValue.Add(value, totalSampleCount);

        return MeasuredHistory::SignificanceTest(&singleValue, significanceLevel);
    }

    /// <summary>
    ///     Tests if the difference between two measurement histories is statistically significant to
    ///     make a hill climbing decision.
    /// </summary>
    /// <remarks>
    ///     A two sided test is used.
    /// </remarks>
    /// <param name="pMeasuredHistory">
    ///     The pointer to second measurement history.
    /// </param>
    /// <param name="significanceLevel">
    ///     The significance level in percent. Accepts 1 through 10.
    /// </param>
    /// <returns>
    ///     -1 - second history is larger than this history
    ///      0 - statistically identical
    ///      1 - this history is larger than second history
    /// </returns>
    int HillClimbing::MeasuredHistory::SignificanceTest(MeasuredHistory * pMeasuredHistory, const int significanceLevel)
    {
        const int critSize = 10;
        double critArray[critSize] = { 2.576, 2.3263, 2.17, 2.05, 1.96, 1.88, 1.81, 1.75, 1.70, 1.64 };

        double thisVariance = this->VarianceMean();
        double thisMean = Mean();
        double secondVariance = pMeasuredHistory->VarianceMean();
        double secondMean = pMeasuredHistory->Mean();

        _ASSERTE(significanceLevel > 0 && significanceLevel <= 10); // Invalid significance level

        int result = (int) sign(thisMean - secondMean);

        if (thisVariance > 0 && secondVariance > 0)
        {
            double pooledVar = thisVariance / Count() + secondVariance / pMeasuredHistory->Count();

            double testStatistic = (thisMean - secondMean) / sqrt(pooledVar);
            double critVal = critArray[significanceLevel-1];
            double absVal = abs(testStatistic);

            if (absVal < critVal)
            {
                result = 0;
            }
        }

        return result;
    }

#if defined(CONCRT_TRACING)

    // Logging mechanism

    struct HillClimbingLogEntry
    {
        long sampleCount;
        unsigned int currentTotalSampleCount;
        double throughput;
        double currentHistoryMean;
        double currentHistoryStd;
        double lastHistoryMean;
        double lastHistoryStd;
        unsigned int currentControlSetting;
        unsigned int lastControlSetting;
        unsigned int currentHistoryCount;
        unsigned int lastHistoryCount;
        HillClimbingStateTransition transition;
    };

    static const int HillClimbingLogCapacity = 100;
    static HillClimbingLogEntry HillClimbingLog[HillClimbingLogCapacity];
    static int HillClimbingLogFirstIndex = 0;
    static int HillClimbingLogSize = 0;

    static const wchar_t * HillClimbingTransitionNames[] = 
    {
        L"Warmup", 
        L"ContinueInitializing",
        L"CompletedInitialization",
        L"DoClimbing",
        L"ChangePoint",
        L"ContinueLookingForClimb",
        L"Undefined"
    };

    /// <summary>
    ///     Logs the hill climbing decision.
    /// </summary>
    /// <param name="recommendedSetting">
    ///     The control setting to be established.
    /// </param>
    /// <param name="transition">
    ///     The transition that is recommended by hill climbing.
    /// </param>
    /// <param name="numberOfSamples">
    ///     The number of sample points in this measurement, including invalid ones.
    /// </param>
    /// <param name="completionRate">
    ///     The number of completed units or work in that period of time.
    /// </param>
    /// <param name="arrivalRate">
    ///     The number of incoming units or work in that period of time.
    /// </param>
    /// <param name="queueLength">
    ///     The total length of the work queue.
    /// </param>
    /// <param name="throughput">
    ///     The throughput of the given instance.
    /// </param>
    void HillClimbing::LogData(unsigned int recommendedSetting, HillClimbingStateTransition transition, unsigned int numberOfSamples,
        unsigned int completionRate, unsigned int arrivalRate, unsigned int queueLength, double throughput)
    {
        //
        // First, log to memory so we can see it in the debugger
        //
        int index = (HillClimbingLogFirstIndex + HillClimbingLogSize) % HillClimbingLogCapacity;
        if (HillClimbingLogSize == HillClimbingLogCapacity)
        {
            HillClimbingLogFirstIndex = (HillClimbingLogFirstIndex + 1) % HillClimbingLogCapacity;
            HillClimbingLogSize--; //hide this slot while we update it
        }

        HillClimbingLogEntry * entry = &HillClimbingLog[index];
        unsigned int minimumSetting = m_pSchedulerProxy->MinHWThreads();
        unsigned int maximumSetting = m_pSchedulerProxy->DesiredHWThreads();

        entry->sampleCount = m_sampleCount;
        entry->currentTotalSampleCount = numberOfSamples;
        entry->throughput = throughput;
        entry->transition = transition;
        entry->currentControlSetting = m_currentControlSetting;
        entry->lastControlSetting = m_lastControlSetting;

        MeasuredHistory * currentHistory = GetHistory(m_currentControlSetting);
        entry->currentHistoryCount = currentHistory->Count();
        entry->currentHistoryMean = currentHistory->Mean();
        entry->currentHistoryStd = currentHistory->StandardDeviation();

        MeasuredHistory * lastHistory = GetHistory(m_lastControlSetting);
        entry->lastHistoryCount = lastHistory->Count();
        entry->lastHistoryMean = lastHistory->Mean();
        entry->lastHistoryStd = lastHistory->StandardDeviation();

        HillClimbingLogSize++;

        const int bufferSize = 180;
        const wchar_t * delim = L"*******************************************************";

        wchar_t dateBuffer[bufferSize];
        SYSTEMTIME time;
        GetLocalTime(&time);
        int dateLen = GetDateFormatW(LOCALE_USER_DEFAULT, DATE_SHORTDATE, &time, NULL, dateBuffer, bufferSize);
        dateBuffer[dateLen-1] = L' ';
        GetTimeFormatW(LOCALE_USER_DEFAULT, TIME_FORCE24HOURFORMAT | TIME_NOTIMEMARKER, &time, NULL, dateBuffer + dateLen, bufferSize - dateLen);

        TRACE(CONCRT_TRACE_HILLCLIMBING, L"%s\n Process: %u\n Scheduler: %d\n Date: %s\n Number of samples: %d\n Number of samples in this measurement (including invalid): %d\n Completions: %d\n Arrivals: %d\n Queue length: %d\n Throughput: %.4f\n Transition: %s\n Next random move: %s\n Minimum: %d\n Maximum: %d\n Current setting: %d\n  * count: %d mean: %g dev: %g varm: %g\n Last setting: %d\n  * count: %d mean: %g dev: %g varm: %g\n -----\n Recommended setting: %d\n%s\n", 
            delim,
            GetCurrentProcessId(),
            m_id,
            dateBuffer, 
            m_sampleCount,
            numberOfSamples,
            completionRate,
            arrivalRate,
            queueLength,
            throughput,
            HillClimbingTransitionNames[transition],
            m_nextRandomMoveIsUp ? L"Up" : L"Down",
            minimumSetting,
            maximumSetting,
            m_currentControlSetting,
            currentHistory->Count(),
            currentHistory->Mean(),
            currentHistory->StandardDeviation(),
            currentHistory->CoefficientOfVariationMean(),
            m_lastControlSetting,
            lastHistory->Count(),
            lastHistory->Mean(),
            lastHistory->StandardDeviation(),
            lastHistory->CoefficientOfVariationMean(),
            recommendedSetting,
            delim);
    }
#endif
} // namespace details
} // namespace Concurrency