C代码 - 存储器访问/抢占

我已经写了一段代码，其中一个数据：C代码 - 存储器访问/抢占

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

我添加了I/P数据为每3个连续的字节，并存储所述ANS。 ex：temp [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ...直到4096

然后从临时的使用代码的结果生成的直方图：

for(i = 0; i < 4096; i++) 
counter[temp[i]]++;

直方图排序（冒泡排序），然后顶部采取8最经常性值。代码运行在Linux内核（2.6.35）

我面临的问题是，如果我删除排序部分，执行代码所需的时间非常快（我的笔记本电脑上使用6微秒，测量使用gettimeofday func）。但是在引入分类之后，这个过程在很大程度上减缓了（44微秒）。排序功能本身需要20微秒，我不明白为什么时间增加这么多。我使用cachegrind进行了内存分析，结果是正常的，我甚至尝试禁用抢占ubut但它仍然没有显示任何区别。如果有人能帮助我在这里。谢谢！

来源

2011-07-05 randy7

为什么冒泡排序？为什么不'qsort（）'？ –

要获得8个最高值，您不需要进行完整排序。例如。 Heapsort可用于获取N个最高值（如果实现的话），它会比完整排序更快。 – osgx

甚至可以选择排序http://en.wikipedia.org/wiki/Selection_sort - 可以在获得前8个值后停止。 – osgx

气泡排序很慢... O（N^2）复杂度...如果您想要更快的性能，请使用像堆一样的数据结构，或者在您的阵列上运行快速排序算法，两者都会给你排序过程的O（N log N）复杂度。另外，这两种方法在定长阵列上也能很好地工作。

来源

2011-07-05 13:56:18 Jason

冒泡排序很慢，它比较并交换您的值到4096 * 4096 = 16777216次。如果您只需要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（n），最好的排序是O（n.log2 N）

编辑：我添加索引的数组。 EDIT2：引入第二个来纠正我第一次遇到的基本问题。 EDIT3：评论：memmove大小为0是允许的，基本上是一个nop。

来源

2011-07-05 14:02:47

你的代码似乎有点不对。你实施了什么排序方法？ – osgx

没有排序方法，我从计数器数组中选择最高值。当然，如果你想知道'counter'的哪个索引是最高的，那么你必须将它存储在一个数组中，这个数组与你一起'同步'。 –

如果你把'n'作为4096，这将是一个选择排序。正常选择排序的复杂度是O（n^2），但是当我们将'memmove'限制为一个小的常量值时，我们得到O（8n）= O（n）。 –

C代码 - 存储器访问/抢占

回答

相关问题