我写了一段代码,其中有一个数据:
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进行了内存分析,结果是正常的,我甚至尝试禁用抢占,但它仍然没有显示任何差异。如果有人可以帮助我在这里。谢谢!
冒泡排序很慢,它比较并交换您的值高达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),其大小与数组相同,大小与您选择的大小相同。最好的排序是O((n.log2 n).m)。因此,如果m很小而n很大,那么任何通用排序算法都是无与伦比的。
编辑:我添加了索引的数组。
EDIT2:引入第二个来纠正我在第一个实例中遇到的基本错误。
编辑3:评论:允许大小为0的memmove
,基本上是一个nop。
冒泡排序很慢...... O(N ^ 2)复杂性......如果你想要更快的性能,使用像堆这样的数据结构,或者在你的阵列上运行快速排序算法,这两种算法都会给你带来O (N log N)排序过程的复杂性。此外,这两种方法也可以在固定长度数组上很好地工作。