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

Question

我为我的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();
    }
}

然后我决定测试它的速度(只是为了看)在旧的Testamenet形式的国王詹姆斯圣经.这是我们用Java教授的数据结构类的标准测试文件,我们可以对其进行排序,并且霍夫曼基本上没时间对其进行编码,但这需要相当长的时间进行编码.到底是怎么回事？

Answer 1

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直接使用流,差异是巨大的.本回答中的所有代码都Apple LLVM version 5.1 (clang-503.0.38) (based on LLVM 3.4svn)使用-O3优化进行了测试.

使用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()方法我会的,但老实说,我不希望在任何奇迹.除非有一些魔法(对我而言,对其他人来说)从流中关闭 io xlat std::cin的方式FILE可能是一个合理的选择.我还没有调查是否啜std::cin的rdbuf()是一个可行的选择要么,但它可能也有承诺.

编辑:使用 std::istreambuf_iterator<char>

使用streambuf迭代器类有一个显着的改进,因为它基本上绕过了所有内联slat垃圾,但它仍然不如FILEstream 有效:

#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流结果相媲美,但其余iostream模板的开销user似乎是一个痛点(但仍然比其他iostream尝试更好).你赢了一些,你输了一些= P.

编辑:无缓冲的系统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