Среднее значение для перемещаемых объектов

Question

Мне нужно сделать эффективный алгоритм для перемещения целых чисел.

Для примера, из 100 предметов. Так как 100 номеров приходят, в среднем за 1..100 чисел .. в 101 числа приходит в среднем 2..101 .. , как 102 номер приходит в среднем 3..102 ..

Я думал из одного решения, но я не могу придумать, чтобы минимальные числа могли быть сохранены (как после подопечных, я должен делать в микропроцессоре, но сначала эффективен на C/C++):

Шаг 1: хранить номера от 1 .. 100 и принять среднее значение Шаг 2: заменить 1 на 101 и принять среднее значение: 101,2,3 ... 100 Шаг 3: заменить 2 на 102 и принять среднее значение: 101,102,3,4 ... 100

Но он неэффективен, так как мне также нужно использовать меньший оператор разделения.

Может ли кто-нибудь помочь мне, пожалуйста.

Answer 1

Самый простой способ сделать скользящую среднюю - это перемещение суммы. Суммируйте числа n [0] через n [99], чтобы начать; средняя составляет эту сумму, деленную на 100. Для следующей суммы вычтите n [0] и добавьте n [100]; снова разделите на 100 для среднего.

Это лучше всего работает с целыми числами, так как в сумме не будет ошибок округления; с плавающей точкой любые ошибки будут накапливаться и ухудшаться по мере продвижения.

Если вы используете целые положительные числа, вы можете исключить деление, сделав размер вашего окна равным 2. Использование 128 вместо 100 означает, что вы можете разделить, используя правый сдвиг 7 на сумму.

Вы также можете исключить деление путем умножения на инверсию. Вместо деления на 100 умножить на 1/100. Если вы работаете с целыми числами, вам может понадобиться использовать фиксированную точку, и вы также можете не использовать бит, если не будете осторожны.

Answer 2

Ваш базовый подход хорош: используйте круговой буфер с 100 элементами. Ключевое понимание: скажем, вы на этапе «замените 2 на 102», а 2 - на 50, а 102 на 70 - общее количество изменится на разницу в +20: вы просто разделите новое общее количество на 100, чтобы получить новый в среднем, без сложения всех элементов.

В маловероятном случае, что разделение происходит настолько медленно, что делает значительное и проблемное разницу в вашу общую производительность, то есть только пару вещей, которые вы могли бы попробовать (но мера - они могут реально замедлить вас вниз в зависимости от ваше точное оборудование):

• если диапазон чисел, если мало, вы можете создать таблицу поиска (т.е. массив) от значения до сотых значения, затем путем добавления/удаления этих масштабируется значения в общей сложности вы непосредственно поддерживаете среднее значение

• проверить ли ваша система быстрее с помощью поплавка или двойных типов (парадоксально, некоторые системы)

• есть некоторые странные «рецепты» для деления на 100 на «сети, такие как (((((uint32_t)A * (uint32_t)0x47AF) >> 16U) + A) >> 1) >> 6 от http://embeddedgurus.com/stack-overflow/2009/06/division-of-integers-by-constants/