C Сохранение массива работающего сигнала отсортировано

Question

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

В этой части я храню данные сигнала в целочисленном массиве размером 50 и извлекаю максимум и минимум, чтобы получить (сырую) индикацию амплитуды. Это делается для 3 датчиков каждую секунду, но сортировка массива для получения минимума и максимума занимает очень много времени.

Моя первая мысль заключалась в хранении данных в отсортированном списке, но как отслеживать, какая последняя точка сигнала должна быть удалена?

Текущий код:

static int movement[AD_SENSORS][AD_MOVEMENT_SIZE]; 
    static int totals[AD_SENSORS]; 
    int movement_sorted[AD_MOVEMENT_SIZE]; 
    int difference = 0; 
    static unsigned int i; // Movement index 
    int k = 0; 

    //Update positions 
    if (++i>(AD_MOVEMENT_SIZE-1)){i=0;} //increment index of movement array 

    //Initialise signal value 
    struct tty_data_t *Current = NULL; 
    Current = head_tty; 

    //Add signals to movement array 
    while (Current != NULL){ 
     totals[Current->ID] = totals[Current->ID] - movement[Current->ID][i]; 
     movement[Current->ID][i] = Current->AD_signal; 
     totals[Current->ID] = totals[Current->ID] + movement[Current->ID][i]; 
     Current->AD_average = totals[Current->ID]/AD_MOVEMENT_SIZE; 
     for (k = 0; k<AD_MOVEMENT_SIZE; k++){ 
      movement_sorted[k] = movement[Current->ID][k]; 
     } 
     qsort (movement_sorted, AD_MOVEMENT_SIZE, sizeof(int), Compare); 
     Current->AD_amplitude = movement_sorted[AD_MOVEMENT_SIZE-1] - movement_sorted[0]; 
     difference += movement_sorted[AD_MOVEMENT_SIZE-1] - movement_sorted[0]; 
     Current = Current->next; 
    } 
    g_movement = difference; 

Answer 1

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

Однако, вы, вероятно, на самом деле не необходимо сортировать. Предполагая, что у вас есть подвижный массив из последних пятидесяти элементов, вам нужно только отрегулировать min и max (и количество элементов, соответствующих им, mincount и maxcount) при ограниченных обстоятельствах. Я дам вам шаги только для максимального значения, но легко просто дублировать логику как минимум. Все эти взаимоисключающие ситуации и должны быть проверены в порядке, указанном (первый матч вы найдете исключает все остальные следующий его):

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

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

И не обязательно обеспокоен производительностью. Даже восемь датчиков со сто отсчетов в секунду будут давать только 800 точек данных. С небольшим набором данных сортировка может быть ошибочной ошибкой, так как при сканировании многие элементы последовательно будут по-прежнему очень быстрыми (особенно если вам не нужно это делать каждые время обновления данных проката.

Answer 2

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

for (k = 0; k < AD_MOVEMENT_SIZE; k++){ 
      movement_sorted[k] = movement[Current->ID][k]; 
     } 

Вместо того, чтобы копировать массив для сортировки (в O(nlogn) времени) просто проверить, если каждый элемент является максимальным или минимальным и получить их в O(n) время.

int max = INT_MIN; 
int min = INT_MAX; 
for (k = 0; k<AD_MOVEMENT_SIZE; k++){ 
      if (movement[Current->ID][k] < min) min = movement[Current->ID][k]; 
      if (movement[Current->ID][k] > max) max = movement[Current->ID][k]; 
     } 

Отказ от ответственности: Я знаю, что большой-O-нотация не говорит много в массивах 50 элементов, но важно, в более общем случае