Вопрос по performance, c++, algorithm – Расчет минимума, максимума и среднего числа введенных чисел

1

Есть ли способ рассчитать среднее / мин / макс всех чисел без использования массива? Необходимо рассчитать до 10000 номеров в секунду.

@ ColinD: Вы очень быстро потеряете точность. Целочисленное деление уменьшит дробную часть (как вы думаете, что произойдет, если вы умножите его обратно?), А деление с плавающей запятой пострадает от ошибок округления. Кроме того, это не спасет вас от переполнения. Умножьте 65536 на 65536, и он больше не будет соответствовать int32. SigTerm
Я вижу несколько решений, в которых упоминается сохранение всей суммы всех чисел. Это может вызвать переполнение? Colin D
При необходимости добавьте тег домашней работы. thb
@ ColinD: это зависит от спецификации. Добавление 32-битных целых чисел с 64-битным счетчиком вполне безопасно;) Karoly Horvath
Это не домашняя работа Jennifer Canas

Ваш Ответ

5   ответов
2

Сохраните минимальную переменную, которая инициализируется высоким значением, и обновите ее, если увидите более низкое значение.

Сделай наоборот с максимальной переменной.

Сложите все числа и разделите эту сумму на общее количество, чтобы получить среднее значение.

Следующий код не выполняет проверки границ (например, count> 0, total не переполняется), но должен дать вам представление:

int minimum = // Initialize to large #, in C# would be int.MaxValue
int maximum = // Initialize to most negative #, in C# would be int.MinValue
int count = 0;
int total = 0;

void StatsForNewNumber(int number)
{
    if (number < minimum) minimum = number;
    if (number > maximum) maximum = number;
    count++;
    total += number;
}

int Average()
{
    return total / count;
}
@ EricJ., Проблем с двойниками в основном избегают, если вы инициализируете их целыми числами. Это как 53-битный целочисленный тип, который изящно обрабатывает переполнение. Mark Ransom
У вас будет та же проблема, что и в математике с массивом. Проверьте наличие переполнений, если это возможно удаленно для данных случаев использования. Используйте long или даже библиотеку, которая может управлять произвольно большими целыми числами, если это необходимо. Сумма также может быть сделана в двойном, если приемлемые проблемы с двойными числами являются приемлемыми. Eric J.
а как насчет переполнени Colin D
long long теперь стандарт, и почти у каждого компилятора есть. Используйте это. Mooing Duck
1

Сохраните текущий минимум и текущий максимум, вычислите промежуточный итог и количество. Когда вам нужно среднее значение, разделите промежуточную сумму на количество, и вы получите ответ.

class calc {
    double minVal, maxVal, total;
    int count;
public:
    calc()
    :   minVal(numeric_limits<double>::max)
    ,   maxVal(numeric_limits<double>::min)
    ,   total(0)
    ,   count(0) {
    }
    void process(double num) {
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
        total += num;
        count++;
    }
    double getAvg() {
        // TODO: Check count to be > 0 here
        return total / count;
    }
    double getMin() {
        return minVal;
    }
    double getMax() {
        return maxVal;
    }
}
а как насчет переполнени Colin D
@ ColinD Учитывая, что OP запрашивает решение, которое заменяет решение на основе массива, не похоже, что переполнение итогов является проблемой. dasblinkenlight
1

чтобы найти среднее / мин / макс, поскольку вы перебираете числа, которые вы делаете

if(currentSmallest > currentNumber)
     currentSmallest = currentNumber

if(currentLargest < currentNumber)
     currentLargest = currentNumber

и, кроме того, вы сохраните счетчик и общую сумму, и, разделив эти числа, вы получите среднее значение. Нет необходимости хранить их в массиве.

Как насчет переполнения общего количества? Colin D
2

которые вы получили, а также сумму и количество чисел. Когда вам нужно наименьшее или наибольшее, верните его. Когда вам нужно среднее значение, разделите сумму на число.

Аккумуляторы Boost включает реализации всего вышеперечисленного, а также немало других.

а как насчет переполнени Colin D
@ ColinD: Примерно так же, как если бы вы использовали массив, что означает, что это зависит. Вы можете игнорировать это или использовать больший тип. Есть и другие способы, но нет особых оснований полагать, что они особенно подходят здесь. Я полагаю, что в связанной библиотеке Аккумуляторов есть код, чтобы справиться с / предотвратить переполнения (но не помню точно). Jerry Coffin
1

одну для хранения minVal, одну для maxVal, одну для общей суммы и одну для увеличения после каждого нового ввода. Сравните каждый новый вход с minVal и maxVal и обновите при необходимости. Добавьте входное значение к общей сумме, увеличьте счетчик. Среднее значение всегда является общей суммой / счетчиком, поэтому вы можете запросить это значение на лету, если вам нужно, или просто рассчитать его в конце, когда вы закончите.

Он работает с большим количеством значений. Что происходит, когда общее переполнение? Colin D
@ ColinD: просто используйте int64_t (или long long) для хранения итогов и чтения ввода в целых числах, да. SigTerm

Похожие вопросы