最新のレクリエーションプロジェクトでは、brainfuckインタプリタをC++で作成しています。十分に簡単でしたが、今日はコンパイルのステップで追加することにしました。最終的な目標は、実行可能ファイルを作成できるようにすることですが、現在は基本的な最適化を行うだけです。たとえば、+++++が5つのaddコマンドを1つのadd 5に追加するなどのようになります。std :: mapがなぜ私のコードを膨大にするのですか?
これはうまくいきますが、私は実行ファイルのサイズが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++;
}
}
}
有効なBrainfuck操作の1つです。この関数は入力文字列を調べ、これらの有効な文字を探します。無効な文字は、Brainfuck仕様に従ってスキップされます。見つかった場合は、そのキーのマップ値を最適化を行うmakeopという関数に渡し、op構造体に変換し、それをインタープリタが実際に実行する命令のベクトルに追加します。
op構造体には2つのメンバーがあります。オペコード:8つのオペレーションのうちの1つを表すuint8_tとオペランドを含む1つのintに基づくスコープ付き列挙型です。上の+++++の例では、Opcode :: INCRと5が含まれています。
したがって、各マップの値(つまり、1つのオペランドは現在は1つのオペランドです。エントリは、オペコードとオペランドの数で構成される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から91552になりました。
マップは、各エントリごとに個別に動的割り当てを使用します。コードサイズが目標であれば、通常のルックアップテーブルが良いでしょう。 –
3kは、赤黒のツリーを構築、検索、破棄するのに必要なすべてのコードを持っています。私にあまりにも異様に聞こえません。 –
Fwiw、3kbは、ストレージ/メモリの過酷な制約のある組み込みプラットフォームでこれをやっていない限り、ほとんど何もありません。 –