2

我想构造一个函数来执行一个文件分析，返回数组中从 0x0 到 0xff 的每个字节数及其频率。

所以，我写了这个原型：

// function prototype  and other stuff

unsigned int counts[256] = {0}; // byte lookup table 
FILE * pFile;                   // file handle
long fsize;             // to store file size
unsigned char* buff;            // buffer
unsigned char* pbuf;            // later, mark buffer start
unsigned char* ebuf;            // later, mark buffer end

if ( ( pFile = fopen ( FNAME , "rb" ) ) == NULL )
{
    printf("Error");
    return -1;
}
else
{
    //get file size
    fseek (pFile , 0 , SEEK_END);
    fsize = ftell (pFile);
    rewind (pFile);

    // allocate space ( file size + 1 )
    // I want file contents as string for populating it
    // with pointers
    buff = (unsigned char*)malloc( sizeof(char) * fsize + 1 );

    // read whole file into memory
    fread(buff,1,fsize,pFile);

    // close file
    fclose(pFile);

    // mark end of buffer as string
    buff[fsize] = '\0';

    // set the pointers to beginning and end
    pbuf = &buff[0];
    ebuf = &buff[fsize];


            // Here the Bottleneck
    // iterate entire file byte by byte
            // counting bytes 
    while ( pbuf != ebuf)
    {
        printf("%c\n",*pbuf);
                    // update byte count
        counts[(*pbuf)]++;
        ++pbuf;                             
    }


    // free allocated memory
    free(buff);
    buff = NULL;

}
// printing stuff

但是这种方式比较慢。我正在寻找相关的算法，因为我已经看到 HxD 例如做得更快。

我认为也许一次读取一些字节可能是一个解决方案，但我不知道如何。

我需要帮助或建议。

谢谢。

4

2 回答 2

1

假设您的文件不是那么大，它会导致系统开始分页，因为您正在将整个内容读入内存，那么您的算法与通用数据一样好 - O(n).

您需要删除printf（如上所述）；但除此之外，如果性能不高于改进它的唯一方法，那就是查看生成的汇编器 - 可能编译器没有优化所有的取消引用（尽管 gcc应该这样做）。

如果您碰巧对您的数据集有所了解，那么就有潜在的改进 - 如果它是位图类型的图像，可能具有相同字节的块，那么可能值得进行一点行程编码。也可能有一些数据集实际上值得首先对数据进行排序（尽管这会将一般情况降低到O(nlog(n))，因此不太可能。

rle 看起来像（未经测试，可能在我的头顶免责声明中不是最理想的）

unsigned int cur_count=1;
unsigned char cbuf=*(++pbuf);

while ( pbuf != ebuf)
{
    while( pbuf != ebuf && cbuf == *pbuf )
    {
        cur_count++;
        pbuf++;
    }  
    counts[cbuf]+=cur_count;
    cur_count=0;                             
}
counts[cbuf]+=cur_count;
于 2013-10-09T15:26:57.543 回答
0

您通常可以通过增加程序大小来提高速度，我认为这在您的情况下可以很好地工作。我会考虑用 unsigned short* 指针替换你的 unsigned char* 指针，并一次有效地处理两个字节。那样的话，你有一半的数组索引增量，一半的计算偏移量到你的累加器，一半的累加加法和一半的测试次数来查看你的循环是否已经完成。

就像我说的那样，这将以增加程序大小为代价，因此您的累加器数组现在需要 65536 个元素而不是 256 个，但这是一个很小的代价。我承认也有易读性的权衡。

最后，您必须对我的新的更大的累加器的所有 65536 个元素运行一个索引，并用 0xff 对其进行屏蔽以获得第一个字节并移动 8 位以获得第二个字节。然后，您将拥有与原始累加器相对应的两个索引，您可以从那里将 2 个累加到您的原始 256 累加器中。

PS 请注意，尽管您一次可以处理几乎所有文件 2 个字节，但如果您的文件大小是奇数字节，则必须自己处理最后一个字节。

PPS 请注意，如果您想让备用的 3 个 CPU 内核做一些比摆弄拇指更有用的事情，这个问题很容易跨 4 个线程并行化；-)

于 2013-10-10T07:51:01.203 回答