保持正在运行的信号数组排序。
我正在努力提高我当前程序的速度，这个程序记录来自多个传感器的数据，但是一个特定的部分非常慢。
在本部分中，我将信号数据存储在大小为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;回答 2
Stack Overflow用户
发布于 2016-05-20 11:54:13
对50个元素进行排序不需要很长时间，应该可以在不到三分之一秒的时间内完成。
但是，您可能实际上不需要进行排序。假设您有最后50个元素的滚动数组，那么您只需要在有限的情况下调整min和max (以及匹配它们的元素的计数、mincount和maxcount)。我将只给出一个最大值的步骤，但也很容易重复逻辑的最小值。这些都是相互排斥的情况，应该按照给定的顺序进行检查(您发现的第一次匹配排除了后面的所有其他匹配)：
- 将元素添加到空列表时，将
max设置为该元素，并将maxcount设置为1。 - 如果添加的值与要删除的值相同，则什么也不做。
- 如果要添加一个与
max相同的值，只需向maxcount添加一个。 - 如果要添加比当前
max更大的值，请将max设置为该值，并将maxcount设置为1。如果要删除的值与max和maxcount相同，则只需减少maxcount。 - 否则，如果要删除的值等于当前的
max(此时，maxcount必须是一个)，则扫描列表中的项以重新计算新的max并相应地设置计数。
唯一可能代价高昂的选择是最后一个，我希望这一选择很少发生。在任何情况下，搜索一个大小为50的数组，每次迭代都要进行几次比较，搜索速度仍然快得令人眼花缭乱。
别太在意表现了。即使是每秒钟100个读数的8个传感器也只能给你800个数据点。对于这么小的数据集，排序可能是一个愚蠢的差事，因为按顺序扫描许多项仍然非常快(特别是如果您不必每次更新滚动数据时都这样做的话)。
Stack Overflow用户
发布于 2016-05-20 12:00:00
如果排序只是为了得到最大值和最小值，而不是问题中没有包含的其他原因，那么您不需要这样做。您的代码中已经有以下循环：
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];
}免责声明:我知道，在50个元素数组中，大O表示法并不能说明什么，但在更一般的情况下，它是很重要的。
https://stackoverflow.com/questions/37345848
复制相似问题
腾讯云开发者
