Более эффективный: большой массив или много скаляров

Question

Работа во встроенной (PIC) среде, программирование на языке c.

Я должен отслеживать 1000 значений для переменной (истории) и возвращать скользящее среднее этих значений. Мне просто интересно, будет ли он более эффективным с точки зрения скорости, использования ПЗУ и ОЗУ, если я использую массив или 1000 16-битных переменных. Есть ли однозначный ответ на этот вопрос? Или мне нужно попробовать оба варианта и посмотреть, что работает лучше всего?

Спасибо.

EDIT: Хм ... я уже столкнулся с другой проблемой. Компилятор ограничивает меня максимальным размером массива 256.

EDIT2:

Для пояснения ... код срабатывает примерно 1000 раз в секунду. Каждый раз значение для history [n] (или history_n) вычисляется и сохраняется. Каждый раз мне нужно рассчитать среднее значение 1000 самых последних значений истории (включая текущие). Так что (history[1000] + history[999] + ... + history[1] + history[0]) / 1000; или что-то на этот счет. Очевидно, каждый раз, когда мне нужно выкинуть самое старое и добавить самое новое.

EDIT3:

Я переработал код так, что теперь размер массива 256 не является проблемой. Подходит размер выборки около 100.

Answer 1

Предполагая, что вам нужно вести историю, и учитывая ограничение массива в 256 элементов, вот способ управления им:

int history1[256];
int history2[256];
int history3[256];
int history4[256];
int* arrays[] = {history1,history2,history3,history4}
int idx=0;
int sum = 0;
int n = 0;

int updateAverage(int newValue)
{
  int ai = (idx++)>>8;
  int* target = arrays[ai]+(idx&0xFF);

  sum -=*target;
  *target = newValue;
  sum += *target;
  n++;
  n=n<1000?n:1000;
  idx = (idx<1000)?idx:0;
  return sum/n;
}

Answer 2

Я не уверен, полностью ли понимаю ваш вопрос. Вы спрашиваете о разнице между кодом, сгенерированным для «короткой истории [1000]» и «короткой истории1, истории2, ..., истории1000;»?

Оба должны использовать одинаковые объемы ОЗУ: каждая запись будет храниться в одном регистре файлов (при условии, что вы используете 16-битный PIC). Однако код для вычисления среднего значения последнего будет уродливым и, вероятно, потребует совсем немного ПЗУ, так как для этого потребуется ссылаться на каждое значение отдельно (а не просто смещать основание).

Edit: Причиной ограничения в 256 элементов является подкачка регистра файлов на PIC. Вы не можете обратиться к большему массиву, просто сместив базовый регистр, потому что вам может потребоваться запрос на изменение страницы.

Вам абсолютно необходимо рассчитать скользящее среднее? Или вы можете сделать общее среднее? Если с общим средним значением все в порядке, используйте вариант ответа Alphaneo: просто сохраните сумму и количество значений, собранных в две переменные, и делите в любое время, когда вам нужно среднее значение.

Answer 3

Во-первых, вы можете изменить свой файл компоновщика, чтобы разрешить больший раздел. Затем вам нужно будет поместить свой массив истории в этот раздел, используя прагмы.

Во-вторых, метод массива намного лучше. Для повышения производительности вам также понадобится 32-разрядное целое число для хранения промежуточного итога массива истории.

Для каждого срабатывания функции истории вычитается самое старое значение из HistoryRunningTotal и добавляется новое значение истории. Вам также понадобится переменная OldestHistoryIndex, чтобы отслеживать, куда пойдет новейшее значение (и перезаписать старую историю).

Answer 4

Если вы хотите вычислить среднее значение, сохранив его в массиве, это будет определенно дороже, чем вычисление во время выполнения.

Причина-1: Если вы вычисляете его во время выполнения, вы просто добавите, например, следующий поток

    init-0: _tempSum_ = 0
    step-1: Read current value to _currVal_
    step-2: Add current value to _tempSum_
    step-3: Check if we have required of values _num_ (eg. 1000), if not goto-1
    step-4: Calculate _avg_ = _tempSum_ / _num_ and return
    step-5: goto init-0

Если вы храните во временном массиве 1000 значений, фактически вы будете выполнять все шаги от init-0 до step-5, за исключением того, что в конечном итоге вы будете использовать массив значений 1000.

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

Answer 5

Если вы используете массив, сгенерированный код будет намного меньше. Я не уверен в этом, но я думаю, что для доступа к массиву потребовалось бы меньше памяти, так как вам не нужно отслеживать несколько переменных, у вас просто есть указатель на один блок. Если размер вашего стека является проблемой, лучшим вариантом будет использование массива в куче, так как переменные C хранятся в стеке.

Answer 6

Если массив выделяется динамически, то использование статических переменных будет быстрее. Если массив размещен статически, компилятор должен быть в состоянии оптимизировать его, чтобы он был эквивалентно быстрым, как статические переменные. Попробуйте оба кода и профилируйте их.

Answer 7

Компилятор ограничивает массивы 256? Это довольно плохо. Это налагает на программиста бремя, о котором действительно должен заботиться компилятор. Вы уверены, что нет опции компилятора, например, "большая" модель памяти? Если нет, исследуйте другой микро и / или компилятор.

Или, чтобы все было мало, рассмотрите возможность использования небольшого БИХ-фильтра, а не большого КИХ-фильтра.

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

Answer 8

Если у вас достаточно памяти для 1000 значений, то почему бы не статически распределить память, создать вращающийся буфер и переместить указатель по значениям для вычисления суммы. (если запущенный avg не то, что вам нужно). Просто продолжайте помещать новое значение поверх самого старого значения, вычисляйте сумму значений 1000 и делите на 1000. Таким образом, фактически два указателя, один для вставки нового значения и один для итерации по всему буферу.