Clever Geek Handbook

別のBrainfuck通訳

Brainfuckは、1つの目的のために作成されたプログラミング言語です。そのためのインタープリターを作成することです。 非常に多くのことが書かれているので、それらへのリンクすら与えません。 指に関するこの記事では、シンプルで効果的な最適化方法について説明しています。







馬









最適化を行うには、次の3つのルールに従う必要があります。







  1. 逆の命令（ +



    および-



    、 >



    および<



    ）は、次々に移動すると相互に破棄されます。 コード>++>><<-



    は>+



    ます。 これは、最適化よりも愚か者からの保護である可能性が高い そのようなコードは無意味です。







  2. 重複する命令は、特定の命令が実行される回数を引数に指定するコマンドに置き換えられます。 たとえば、コード+++



    は引数3のADDコマンドで置き換えられ、コード<<<



    はMOVE：-3で置き換えられます。







  3. bfに対応する命令がない新しいコマンドが追加されます。 値割り当てコマンド。 コード[+]



    および[-]



    は現在のセルをリセットし、このコードのADDコマンドは現在のセルをその引数の値に設定します。 コード--[-]+++



    は、ASSIGN：3コマンドに置き換えられます。


説明付きのコマンドのリスト



各コマンドには独自の引数があります（以下、単にarg）。 引数の値は、ADDコマンドにのみ制限されます。 1つのセルのサイズは256です。







チーム名 説明書 説明
追加 +



および-



現在のセルの値をargに変更します
移動 >



および<



現在のセルのインデックスをargに変更します
読む ,



入力ストリームからarg文字をスキップし、それらに続く文字を読み取ります
印刷する .



現在のセルの値に一致する文字をarg回出力します
後藤 [



および]



現在の相対的なコマンドのスコアでargを実行します
割り当て [+]



および[-]



argを現在のセルに割り当てます


通訳者コード例



解釈は3つの段階に分かれています。 ソースコードを読み取り、最適化されたコマンドに変換し、これらのコマンドを実行します。 これはすべてメイン関数と解析関数で発生します。







最初と最後のステージは、メイン関数ですぐに発生します。 コメント付きの彼女のコード： 







 int main(int argc, char* argv[]){ /*        */ if(argc == 1){ fprintf(stderr, "%s: Wrong argument count\n", argv[0]); return 1; }; /*     */ FILE* f = fopen(argv[1], "r"); if(f == NULL){ fprintf(stderr, "%s: Can't open %s\n", argv[0], argv[1]); return 2; }; /*      */ int n = fread(str, sizeof(char), SIZE - 1, f); if(n == 0){ fprintf(stderr, "%s: Can't read data from %s\n", argv[0], argv[1]); return 3; }; str[n] = '\0'; /*     */ fclose(f); if(brackets()){ fprintf(stderr, "%s: Wrong brackets sequence\n", argv[0]); return 4; }; /*    */ parse(); /*   */ ptr = mem; int (*exe[])(int) = {exe_a, exe_b, exe_c, exe_d, exe_e, exe_f}; struct code* p = src + 1; for(; p->cmd; ++p){ p += (*exe[p->cmd - 1])(p->arg); }; return 0; };


解析関数では、bf命令をインタープリター用のコマンドに変換することによる最適化が行われます。 コメント付きの彼女のコード： 







 void parse(){ /*    */ struct code *p = src; p->cmd = 0; p->arg = 0; /*     */ char* ch = str; /*         */ top = stk; /*       8     */ int (*prs[])(struct code*) = {prs_0, prs_1, prs_2, prs_3, prs_4, prs_5, prs_6, prs_7, nothing}; /*  */ for(; *ch != '\0'; ++ch){ p += (*prs[find(*ch)])(p); }; /* -     */ (p + 1)->cmd = 0; };


性能試験



比較のために、私は公式のubuntu リポジトリからインタープリターを取得し、 このリポジトリからいくつかのテストを取得しました。 表は、平均テスト実行時間を秒単位で示しています。







テスト名 公式 記事から
長い 34 20
マンデルブロ 21 26
EasyOpt 24 27
カウンター 34 37


最初のテストを除くすべてのテストで、公式の通訳者は記事の通訳者よりも約12％高速に実行されます。 最初のテストでは、他とは異なり、ほとんどのサイクルで命令の数>



が命令の数<



と一致しません。 これにより、サイクルのバランスが崩れ、最適化の影響を受けにくくなります（記事に記載されていない別のタイプの最適化）。 公式の通訳者はバランスの取れたサイクルを最適化し、これにより速度が12％向上するように見えますが、記事の通訳者は最初のテストを勝ちません。 これは、このような単純な最適化アルゴリズムにとっては良い結果ですが。







Githubのソース







More articles:


All Articles