7

私は自分の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 で教えられたデータ構造クラスの標準的なテスト ファイルであり、基本的にすぐに並べ替えてハフマン エンコードできましたが、エンコードにはかなりの時間がかかります。何が起こっている？

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;
}

上記の正確なaコードをz、から までの範囲の文字をロードした 10MB のランダム ファイルでテストしまし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::cinrdbuf()

編集：使用std::istreambuf_iterator<char>

streambuf イテレータ クラスを使用すると、本質的にすべてのインライン スラット ジャンクをバイパスするため、大幅に改善されますが、それでも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の結果と比較できるようになりましたが、残りの iostream テンプレートからのオーバーヘッドが問題のように見えます (ただし、他の試行よりも優れています)。いくらか勝ち、いくらか失う=PFILEuseriostream

編集：バッファリングされていないシステム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 に答える
1

C++ iostream はかなり非効率的であるという悪い意見がありますが、さまざまな数値は、iostream の欠点ではなく、むしろ実装の品質の問題であることを示唆しています。

とにかく、それが遅い hdd のようなものではないことを確認するために、実行時間を比較することができます。

cat file1 > file2

もちろんcat、データのサイズが 2 倍にならないので、少し速くなります。

次に、コードの効率を次のものと比較してみてください。

#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 バイトを書き込みます。したがって、出力ファイルは入力の 2 倍のサイズになります。入力が十分に大きい場合、合計 IO (読み取り + 2 * 書き込み) 時間はかなりの量になります。

ハフマン コーディングでは、これは当てはまりません。通常は、読み取るよりも書き込む方が少なく、合計 IO 時間ははるかに短くなるからです。

編集: Blorgbeardが言った ように、それはバッファリングの違いかもしれません。C++ もバッファリングを行いますが、デフォルトのバッファは Java よりもはるかに小さい場合があります。また、HDD ヘッドがある場所でのファイルの読み取りと別の場所への書き込みの間で常にジャンプする必要があるという事実は、全体的な IO パフォーマンスに大きな影響を与えます。

いずれにせよ、大きなブロックのシーケンシャルな読み取りと書き込みを確実にするために、エンコードはチャンクで行う必要があります

于 2014-03-24T03:05:07.157 に答える