C代码 - 内存访问/抢占

Question

我写了一段代码,其中有一个数据:

unsigned char buf[4096]; // data in chunks of size 4k
unsigned counter[256];

我正在为每3个连续字节添加i/p数据并存储ans.例如:temp [4096]; temp [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进行了内存分析,结果是正常的,我甚至尝试禁用抢占,但它仍然没有显示任何差异.如果有人可以帮助我在这里.谢谢!

Answer 1

冒泡排序很慢，它会比较和交换您的值最多 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。