0

私の最新のレクリエーション プロジェクトは、C++ で頭脳明晰インタープリターを作成することです。それは簡単でしたが、今日はコンパイルのステップで追加することにしました。最終的な目標は、実行可能ファイルを作成できるようにすることですが、現時点では、いくつかの基本的な最適化が行われています。たとえば、+++++ は 5 つの add 1 コマンドから単一の add 5 に変換されます。

これはうまく機能しますが、ストリップ後の実行可能ファイルのサイズが 9k から 12k になっていることに気付きました。いくつかの調査の後、以下の機能、特にマップが原因であると判断しました。私はなぜなのか理解していない。

void Brainfuck::compile(const string& input) {
    map<char, pair<Opcode, int>> instructions {
        { '<', make_pair(Opcode::MOVL,  1) },
        { '>', make_pair(Opcode::MOVR,  1) },
        { '+', make_pair(Opcode::INCR,  1) },
        { '-', make_pair(Opcode::DECR,  1) },
        { '[', make_pair(Opcode::WHILE, 0) },
        { ']', make_pair(Opcode::WEND,  0) },
        { ',', make_pair(Opcode::INP,   0) },
        { '.', make_pair(Opcode::OUTP,  0) },
    };

    string::const_iterator c = begin(input);
    while (c != end(input)) {
        if (instructions.find(*c) != end(instructions)) {
            auto instruction = instructions[*c];
            makeOp(c, instruction.first, instruction.second);
        } else {
            c++;
        }
    }
}

マップの鍵は、8 つの有効な Brainfuck オペレーションの 1 つです。関数は入力文字列を調べて、これらの有効な文字を探します。無効な文字は、Brainfuck 仕様に従ってスキップされます。見つかった場合、そのキーのマップ値を最適化を行う makeop という関数に渡し、それを op 構造体に変換して、インタープリターが実際に実行する命令のベクトルに追加します。

op 構造体には 2 つのメンバーがあります。8 つの操作の 1 つを表す uint8_t と、オペランドを含む 1 つの int に基づくスコープ付き列挙型である Opcode。(今のところ 1 つのオペランド。将来のより洗練されたバージョンでは、複数のオペランドを持つ命令が含まれる可能性があります。) したがって、上記の +++++ の例では、構造体には Opcode::INCR と 5 が含まれます。

したがって、各マップ エントリの値は、Opcode とオペランドの数で構成される std::pair です。一般的なデータ構造ではある程度のオーバーヘッドが避けられないことはわかっていますが、上記の説明の単純さを考えると、3k は少し過剰だと思いませんか?

それとも、これは私の目的を効率的に達成するための正しいアプローチではないでしょうか? しかし、std::map でない場合、どのデータ構造を使用すればよいでしょうか?

アップデート：

回答してくれたすべての人に感謝します。まず、私の動機について一言。私は日常業務で C++ をあまり使用しません。だから私は自分の知識を鋭く保つためにいくつかのレクリエーションプロジェクトを行っています. 絶対に最小のコードサイズを持つことは、たとえば明快さほど重要ではありませんが、肥大化やそのようなことがどのように起こるかを学ぶことは私にとって興味深いことです.

与えられたアドバイスに従って、私の関数は次のようになります。

static const int MAXOPS = 8;

void Brainfuck::compile(const string& input) {
    array<tuple<char, Opcode, int>, MAXOPS> instructions {
        make_tuple('<', Opcode::MOVL,  1),
        make_tuple('>', Opcode::MOVR,  1),
        make_tuple('+', Opcode::INCR,  1),
        make_tuple('-', Opcode::DECR,  1),
        make_tuple('[', Opcode::WHILE, 0),
        make_tuple(']', Opcode::WEND,  0),
        make_tuple(',', Opcode::INP,   0),
        make_tuple('.', Opcode::OUTP,  0),
    };

    string::const_iterator c = begin(input);
    while (c != end(input)) {
        auto instruction = find_if(begin(instructions), end(instructions),
        [&instructions, &c](auto i) {
            return *c == get<0>(i);
        });

        if (instruction != end(instructions)) {
            makeOp(c, get<1>(*instruction), get<2>(*instruction));
        } else {
            c++;
        }
    }
}

再コンパイルしましたが...何も起こりませんでした。マップを含む別のメソッドがあり、(現在は削除された?) 応答で、マップのインスタンス化だけでコードを追加するのに十分であることが示唆されたことを思い出しました。そのため、そのマップを配列に変更して、再度コンパイルしました。今回は、実行可能ファイルの削除されたサイズが 12280 から 9152 になりました。

4

1 に答える 1

3

map は、要素を格納するためにバランス ツリーを内部的に使用します。バランス ツリーは高速ですが、挿入または削除時にツリーのバランスを再調整するためのコード オーバーヘッドが必要です。したがって、このコードの 3k は合理的に継ぎ目があります。

于 2016-10-27T07:39:40.827 に答える