我为课堂编写了这个汉明编码代码.为什么这么慢

我为我的OS类写了这个:

#include <iostream>
#include <fstream>
//encodes a file using the (8,4) Hamming Code.
//usage : HammingEncode.out < inputFile > outputFile 
int main() {
    unsigned char const codebook[] = {0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF};
    unsigned char in, nextByte;
    unsigned char const leftMask = 0xF0, rightMask = 0x0F;
    in = std::cin.get();
    while (!std::cin.eof()) {
        nextByte = (in & leftMask) >> 4;
        std::cout << codebook[nextByte];
        nextByte = in & rightMask;
        std::cout << codebook[nextByte];
        in = std::cin.get();
    }
}

然后我决定测试它的速度(只是为了看看)在国王詹姆斯圣经的旧约版本上。这是我们用Java教的数据结构类的标准测试文件，我们可以对它进行排序并进行霍夫曼编码，但这需要很长时间来编码。发生了什么事?

std::cin以文本模式打开，因此它不断地寻找各种需要注意的东西(如换行符等)。

给定std::cin输入流的恒定字符嗅探，我并不惊讶它需要更长的时间，但它确实看起来有点过度。下面，绕过iostream并直接使用FILE流可能会达到您所期望的效果:

#include <cstdlib>
#include <cstdio>
int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };
    for (int c = std::fgetc(stdin); c!=EOF; c=std::fgetc(stdin))
    {
        std::fputc(codebook[c >> 4], stdout);
        std::fputc(codebook[c & 0x0F], stdout);
    }
    return EXIT_SUCCESS;
}

我在一个10MB随机文件上测试了上面的精确的代码，该文件加载了从a到z的字符，当使用std::cin和std::cout时，结果非常长。直接使用FILE流，差异是巨大的。这个答案中的所有代码都是使用-O3优化的Apple LLVM version 5.1 (clang-503.0.38) (based on LLVM 3.4svn)进行测试的。

使用FILE流

time ./hamming < bigfile.txt > bigfile.ham 
real 0m1.855s
user 0m1.812s
sys  0m0.041s

使用std::cin和std::cout

time ./hamming < bigfile.txt > bigfile.ham
real 0m23.819s
user 0m7.416s
sys  0m16.377s

使用std::cin和std::cout与std::cout.sync_with_stdio(false);

time ./hamming < bigfile.txt > bigfile.ham
real 0m24.867s
user 0m7.705s
sys  0m17.118s

总之，。值得注意的是在系统中花费的时间。如果我有机会用std::istream::get()和put()方法更新这个，我会的，但老实说，我不期望有任何奇迹。除非有一些神奇的方法(对我来说，不是对其他人)将从std::cin关闭 io xlat，否则FILE流可能是一个合理的选择。我还没有研究过啜吸std::cin的rdbuf()是否是一个可行的选择，但它可能也有希望。

编辑:Using std::istreambuf_iterator<char>

使用streambuf迭代器类有一个显著的改进，因为它基本上绕过了所有的内联slab垃圾，但它仍然不如FILE流:

#include <iostream>
#include <cstdlib>
#include <cstdio>
int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };
    std::istreambuf_iterator<char> cin_it(std::cin), cin_eof;
    std::for_each(cin_it, cin_eof, [](char c)
        {
          std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) >> 4]));
          std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) & 0x0F]));
        });
    return EXIT_SUCCESS;
}

结果:

time ./hamming < bigfile.txt > bigfile.ham
real 0m6.062s
user 0m5.795s
sys  0m0.053s

请注意，system现在与FILE流结果相当，但是user中其他iostream模板的开销似乎是一个痛点(但仍然比其他iostream尝试要好)。有得也有失=P

Edit: Unbuffered System IO

为了完全公平起见，绕过所有运行时缓冲并完全依赖系统调用来完成这些疯狂的操作，以下内容也值得注意:

#include <cstdlib>
#include <cstdio>
#include <unistd.h>
int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };
    unsigned char c;
    while (read(STDIN_FILENO, &c, 1)> 0)
    {
        unsigned char duo[2] =
        {
            codebook[ c >> 4 ],
            codebook[ c & 0x0F ]
        };
        write(STDOUT_FILENO, duo, sizeof(duo));
    }
    return EXIT_SUCCESS;
}

结果，正如你所料，是可怕的:

time ./hamming < bigfile.txt > bigfile.ham
real 0m26.509s
user 0m2.370s
sys  0m24.087s

我做了两个小的改变，接近一个数量级的改进。

添加std::ios_base::synch_with_stdio(false)(没有明显的差异，尽管影响通常是特定于实现的)
在写入前缓冲输出(这是最重要的)

更新后的代码如下所示:

int main()
{
    //encodes a file using the (8,4) Hamming Code.
    //usage : HammingEncode.out < inputFile > outputFile 
        unsigned char const codebook[] = { 0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF };
        unsigned char in, nextByte;
        unsigned char const leftMask = 0xF0, rightMask = 0x0F;
        std::stringstream os;
        std::ios_base::sync_with_stdio(false);
        in = std::cin.get();
        while (std::cin) {
            nextByte = (in & leftMask) >> 4;
            os.put(codebook[nextByte]);
            nextByte = in & rightMask;
            os.put(codebook[nextByte]);
            in = std::cin.get();
        }
        std::cout << os.rdbuf();
}

我尝试了另一个实现-使用底层std::streambuf。

在我的系统上，原始代码大约需要14秒来处理完整的King James Bible -大约4.3 MB

我最初尝试的代码大约花了2.1秒来处理。

这个新的实现花费0.71秒来处理相同的文档。

int main()
{
    //encodes a file using the (8,4) Hamming Code.
    //usage : HammingEncode.out < inputFile > outputFile 
    unsigned char const codebook[] = { 0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF };
    unsigned char in, nextByte;
    unsigned char const leftMask = 0xF0, rightMask = 0x0F;
    std::stringstream os;
    std::ios_base::sync_with_stdio(false);
std::streambuf * pbuf = std::cin.rdbuf();
    do {
        in = pbuf->sgetc();
        nextByte = (in & leftMask) >> 4;
        os << codebook[nextByte];
        nextByte = in & rightMask;
        os << codebook[nextByte];
    } while (pbuf->snextc() != EOF);
    std::cout << os.rdbuf();
}

c++ iostreams被认为效率低下，尽管不同的数字表明这是实现质量问题，而不是iostream的缺点。

无论如何，只是为了确保它不是像慢硬盘一样，你可以比较执行时间，例如

cat file1 > file2

当然cat会快一点，因为它不会使你的数据大小翻倍。

然后试着将你的代码的效率与以下代码进行比较:

#include <stdio.h>
#include <unistd.h>
int main()
{
    unsigned char buffer[1024*1024]; // 1MB buffer should be enough
    while (!eof(STDIN_FILENO)){
        size_t len = read(STDIN_FILENO, &buffer[0], 1024*1024);
        write(STDOUT_FILENO, &buffer[0], len);
        write(STDOUT_FILENO, &buffer[0], len);
    }
    return 0;
}

编辑:

对不起，我错了。试着

#include <stdio.h>
#include <unistd.h>
int main()
{
    unsigned char buffer[1024*1024]; // 1MB buffer should be enough
    size_t len = read(STDIN_FILENO, &buffer[0], 1024*1024);
    while(len > 0){
        write(STDOUT_FILENO, &buffer[0], len);
        write(STDOUT_FILENO, &buffer[0], len);
        len = read(STDIN_FILENO, &buffer[0], 1024*1024);
    }
    return 0;
}

如果我理解正确的话，对于您读取的每个字节，您然后写入2个字节。因此，输出文件将是输入文件的两倍大小。如果你的输入足够大-总的IO(读+ 2 *写)时间将是显著的。

在霍夫曼编码中，情况并非如此——因为你通常写的比读的少，总的IO时间会少得多。

编辑:

正如Blorgbeard所说，它可以是缓冲的区别。c++也有缓冲，但默认的缓冲区可能比Java小得多。此外，HDD磁头应该不断地在一个位置读取文件和在另一个位置写入文件之间跳转，这对整体IO性能有很大的影响。

在任何情况下，编码都应该以块为单位进行，以确保大块的顺序读写

相关内容

最新更新

热门标签：