三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#

brainfuck 閑話 : 配列のランダムアクセス

初めに

今回は Brainf*ck Advent Calendar 20197 日目の記事です。 adventar.org
前日の記事はこちら
明日の記事はこちら

目次

概要

今回は、配列のランダムアクセスの話をしたいと思います。
適当に思いついた 4 つの方法で計算量の観点から解説したいと思います。

配列の表現方法

brainfuck で配列を表現する場合、配列の両端に 0 を入れることで終端を表現します。
c++char[] を用いて文字列を表現するときに終端に \0 が入るようなものと思えば理解できるのではないでしょうか。
また、その性質上、数値が配列要素の値が 0 であってはいけないです。

本記事での制約

今回は、要素は 1~100 として、要素数100 以下として話をします。

コードとメモリ遷移

ランダムアクセスのコードと、その実行例での、メモリの遷移を書いていきます。
実行例として 11,22,33,44,55 の要素を持つ配列の 3 番目の要素にアクセスするという入力を与えています。
また、メモリ遷移は、メインループの前後と、最終的なメモリを示しました。

方法1

コード

[ ->>[>]>[-<+>]<[<]< ]
>>[>]>

メモリ遷移
f:id:unidentifiedexe:20191207010717j:plain

方法2

コード

[ ->[-<<+>>]<[->+<]> ]
>

メモリ遷移
f:id:unidentifiedexe:20191207010812j:plain

方法3

コード

[ ->[>>]+[<<]> ]
>[>>]>

メモリ遷移
f:id:unidentifiedexe:20191207010827j:plain

方法4

コード

[ -[->>+<<]>> ]
>

メモリ遷移
f:id:unidentifiedexe:20191207010848j:plain

ざっくり解説

それぞれの方法は、 1 要素のセル数とインデックスメモリが固定かどうかが異なります。
各方法の内容は以下の表のとおりです。

1要素のセル数 インデックス
方法 1 1 固定
方法 2 1 非固定
方法 3 2 固定
方法 4 2 非固定

計算量

それぞれの方法に関して、空間計算量、時間計算量の観点から利点欠点を見ていきます。

空間計算量

1 要素のセル数が多い方法 2,3 が空間計算量的に悪いです。
わざわざ書くものでもないですね。
インデックスの固定・非固定に関しては、非固定の方が若干良かったりしますが、誤差程度なので無いものとしてよさそうです。

時間計算量

brainfuck における時間計算量をどう定義するかですが、計算ステップ数とします。
実際には、インクリメントより条件分岐の方が早い等ありそうですが、今回は無視します。
方法 1,2 では 1 要素 1 セルであるために、インデックス指定をひとつ動かすたびに値の移動を行っているために、すごく遅くなっています。
一方で、方法 3,4 では移動が発生しないために、遅いです。

方法 3,4i 番目へのインデックスアクセスの計算ステップ数は以下のようになります。
確認していないので間違ってたらごめんなさい。

計算ステップ数
方法 3 3*i^2 + 9*i + 4
方法 4 7/2*i^2 - 1/2*i + 2

諸条件によって変わってきますが、要素数が多いほど、方法 3 がいいということになります。
といっても、方法 1,2 に比べるとどっちも変わらないので、好きな方を使ったら良いと思います。

結局どうすればいいの?

正直、よほど気にしない限りはどの方法でもいいかと思います。
空間計算量は普段はあまり気にしませんが、brainfuck ではデバッグのしやすさにも影響するので、一概に方法 1,2 が悪いとも言えません。
私はよく、方法 1 を使っています。

まとめ

配列のランダムアクセスをする場合、1 要素に 2 セルを使うと、時間計算量が大幅に削減できる。

あとがき

今回の記事は brainfuck のコードが登場しまた。
お叱りを回避できそうです。
それでは皆さん、良い brainfuck ライフを。