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

对 50 个元素进行排序不会花费很长时间，它当然应该能够在不到三分之一秒的时间内完成。

但是，您实际上可能并不需要进行排序。假设您有一个包含最后 50 个元素的滚动数组，您只需调整 min 和 max (以及与它们匹配的元素的数量，mincount code> 和 maxcount)在有限的情况下。我只会向您提供最大值的步骤，但复制最小值的逻辑也很容易。这些都是互斥的情况，应该按照给定的顺序进行检查(您找到的第一个匹配项排除了其后的所有其他匹配项):

• 将元素添加到空列表时，请将 max 设置为该元素，并将 maxcount 设置为 1。
• 如果您要添加的值与要删除的值相同，则无需执行任何操作。
• 如果您要添加与 max 相同的值，只需在 maxcount 中添加 1 即可。
• 如果您要添加的值大于当前 max，请将 max 设置为该值，并将 maxcount 设置为 1。 如果您要删除的值与 max 相同且 maxcount 大于 1，则只需递减 maxcount 即可。
• 否则，如果您要删除的值等于当前 max(此时，maxcount 必须为 1)，请扫描列表中的项目以查找重新计算新的最大值并相应地设置计数。

唯一可能昂贵的选择是最后一个，我预计它很少发生。无论如何，搜索大小为 50 的数组并每次迭代进行几次比较应该仍然快得令人眼花缭乱。

暂时不要太担心性能。即使有 8 个传感器，每个传感器每秒读取 100 个读数，也只能为您提供 800 个数据点。对于如此小的数据集，排序可能是一件傻事，因为按顺序扫描许多项目仍然非常快(特别是如果您不必每次更新滚动数据时都执行此操作)。