7

我为我的操作系统类写了这个：

#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 教授的数据结构类的标准测试文件，我们几乎可以立即对其进行排序和 Huffman 编码，但这需要相当长的时间来编码。到底是怎么回事？

4

4 回答 4

6

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 的随机文件上测试了上面的确切代码，该文件加载了从ato的字符z，结果在使用std::cinand时长得离谱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

总之，哎哟。值得注意的是在system中花费的时间。如果我有机会用std::istream::get()和put()方法更新它，我会的，但老实说，我不希望有任何奇迹发生。除非有一些神奇的方法（对我来说，而不是对其他人）从流中关闭io xlat可能是一个合理的选择。我还没有调查 slurping 是否是一个可行的选择，但它也可能有希望。std::cinFILEstd::cinrdbuf()

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

使用 streambuf 迭代器类有显着改进，因为它基本上绕过了所有内联 slat 垃圾，但它仍然不如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流结果相当，但其余 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
于 2014-03-24T04:41:10.683 回答
2

通过进行 2 个小改动，我的改进接近了一个数量级。

  1. 添加std::ios_base::synch_with_stdio(false)（没有明显差异，尽管影响通常是特定于实现的）
  2. 在写入之前缓冲输出（这是最大的不同）

更新后的代码如下所示：

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 秒来处理完整的国王詹姆斯圣经 - 大约 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();
}
于 2014-03-24T04:58:35.647 回答
1

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;
}
于 2014-03-24T03:37:45.037 回答
0

如果我理解正确，那么对于您读取的每个字节，您将写入 2 个字节。所以输出文件将是输入的两倍大小。如果您的输入足够大 - 总 IO（读取 + 2 * 写入）时间将很重要。

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

编辑： 正如Blorgbeard所说，这可能是缓冲的不同。C++ 也进行缓冲，但可能默认缓冲区比 Java 小得多。此外，HDD 磁头应在一个位置读取文件然后在另一个位置写入文件之间不断跳转这一事实 - 显着影响整体 IO 性能。

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

于 2014-03-24T03:05:07.157 回答