brainfuck 閑話 : 配列のランダムアクセス
初めに
今回は Brainf*ck Advent Calendar 2019
の 7
日目の記事です。
adventar.org
前日の記事はこちら
明日の記事はこちら
目次
概要
今回は、配列のランダムアクセスの話をしたいと思います。
適当に思いついた 4
つの方法で計算量の観点から解説したいと思います。
配列の表現方法
brainfuck
で配列を表現する場合、配列の両端に 0
を入れることで終端を表現します。
c++
で char[]
を用いて文字列を表現するときに終端に \0
が入るようなものと思えば理解できるのではないでしょうか。
また、その性質上、数値が配列要素の値が 0
であってはいけないです。
本記事での制約
今回は、要素は 1~100
として、要素数も 100
以下として話をします。
コードとメモリ遷移
ランダムアクセスのコードと、その実行例での、メモリの遷移を書いていきます。
実行例として 11,22,33,44,55
の要素を持つ配列の 3
番目の要素にアクセスするという入力を与えています。
また、メモリ遷移は、メインループの前後と、最終的なメモリを示しました。
方法1
コード
[ ->>[>]>[-<+>]<[<]< ] >>[>]>
メモリ遷移
方法2
コード
[ ->[-<<+>>]<[->+<]> ] >
メモリ遷移
方法3
コード
[ ->[>>]+[<<]> ] >[>>]>
メモリ遷移
方法4
コード
[ -[->>+<<]>> ] >
メモリ遷移
ざっくり解説
それぞれの方法は、 1
要素のセル数とインデックスメモリが固定かどうかが異なります。
各方法の内容は以下の表のとおりです。
1 要素のセル数 |
インデックス | |
---|---|---|
方法 1 |
1 |
固定 |
方法 2 |
1 |
非固定 |
方法 3 |
2 |
固定 |
方法 4 |
2 |
非固定 |
計算量
それぞれの方法に関して、空間計算量、時間計算量の観点から利点欠点を見ていきます。
空間計算量
1
要素のセル数が多い方法 2,3
が空間計算量的に悪いです。
わざわざ書くものでもないですね。
インデックスの固定・非固定に関しては、非固定の方が若干良かったりしますが、誤差程度なので無いものとしてよさそうです。
時間計算量
brainfuck
における時間計算量をどう定義するかですが、計算ステップ数とします。
実際には、インクリメントより条件分岐の方が早い等ありそうですが、今回は無視します。
方法 1,2
では 1
要素 1
セルであるために、インデックス指定をひとつ動かすたびに値の移動を行っているために、すごく遅くなっています。
一方で、方法 3,4
では移動が発生しないために、遅いです。
方法 3,4
の i
番目へのインデックスアクセスの計算ステップ数は以下のようになります。
確認していないので間違ってたらごめんなさい。
計算ステップ数 | |
---|---|
方法 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
ライフを。