我写了一段代码,其中有一个数据:
unsigned char buf[4096]; // data in chunks of size 4k
unsigned counter[256];
我将每 3 个连续字节的 i/p 数据相加并存储 ans。 例如:温度[4096];温度[0] = buf[0] + buf[1] + buf[2]; ...直到 4096
然后使用代码从 temp 的结果生成直方图:
for(i = 0; i < 4096; i++)
counter[temp[i]]++;
对直方图进行排序(冒泡排序),然后取前 8 个最常出现的值。代码运行在linux内核(2.6.35)
我面临的问题是,如果删除排序部分,执行代码所需的时间会非常快(在我的笔记本电脑上为 6 微秒,使用 gettimeofday 函数测量)。但是在引入排序之后,这个过程在很大程度上变慢了(44 微秒)。排序函数本身需要 20 微秒,我不明白为什么时间会增加这么多。我使用 cachegrind 进行了内存分析,结果是正常的,我什至尝试禁用抢占但它仍然没有显示任何差异。如果有人可以在这里帮助我。谢谢!
最佳答案
冒泡排序很慢,它最多比较和交换您的值 4096*4096 = 16,777,216 次。如果您只需要 8 个最佳值,则 1 次扫描选择肯定更快。诸如此类。
const uint_t n = 8;
uint_t best[n] = {0};
uint_t index[n] = {0};
uint_t j;
for(uint_t i=0; i<4096; i++) {
if(counter[i] > best[n-1]) {
for(j=n-2; j && counter[i] > best[j]; j--); /* Find the insertion position, as our value might be bigger than the value at position n-1. */
memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]); /* Shift the values beyond j up 1 */
memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]);
best[j] = counter[i]; /* Put the current best value at the top */
index[j] = i; /* Store the index in the second array to know where the best value was. */
}
}
有了它,您只需比较您的值一次,并且 memmove
的成本可以忽略不计,因为您的选择数组很小。
无需对数组进行排序,此算法为 O(nm),其中 n 是数组的大小,m 是您选择的大小。最好的排序是 O((n.log2 n).m)。因此,如果 m 很小且 n 很大,则它是任何通用排序算法所无法比拟的。
编辑:我为索引添加了数组。
EDIT2:第二次引入以纠正我在第一个实例中遇到的基本错误。
EDIT3:评论:memmove
大小为 0 是允许的,基本上是 nop。
关于C代码——内存访问/抢占,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6583590/