容量上限付き可変長配列の空間計算量

boost::container::static_vectorのような動作をする、容量の上限Nコンパイル時に決められた値であり、実行時に配列の要素数sizeを(上限までの範囲で)変更できるようなデータ構造を考えます。 これを実現するには最低何bitの空間が必要でしょうか?

要素一つ当たり必要なビット数を、Kbitだとします。

 N=0 の場合

これは、自明に0bitで実現可能です。

 K=0 の場合

これは、自明に \lfloor \log_2(N+1) \rfloorbitです。配列の要素数size0である場合、1である場合、……Nである場合、の N+1通りを区別する必要があるためです。

それ以外の場合で、 2^K \ge Nの場合

この場合、 NK + 1bitで実現可能です。

まず、この値が下限値であることを示します。 要素一つ当たりに必要なビット数がKbitで、最大N要素入りうるので NKbitは確実に必要です。 N要素入っている状態は \left(2^K\right)^N = 2^{NK}状態あり、それ以外に0要素入っている状態が少なくともありますから、最低でも 2^{NK}+1通りを区別する必要があります。  NKbitでは 2^{NK}通りの状態しか区別できませんので、最低でも NK+1bit必要ということになります。

次に、実現する方法を示します。 まず、一エントリがKbitであり、N要素ある配列を普通に用意します。これには NKbitが費やされます。残りの1bitは、「sizeNと等しい」ことを表すフラグにします。 容量をケチるため、フラグの状態がtrueであるかfalseであるかによって、データ構造を変化させます。具体的には、以下のようにします。

  • フラグがtrueである、つまりsizeNと等しい場合、用意した配列にsize個のKbitデータを詰め込む
  • フラグがfalseである、つまりsizeNより小さい場合、用意した配列にsize個のKbitデータを詰め込む。配列の末尾にはsizeを書き込む

フラグがtrueである場合、問題が発生しないことはすぐにわかります。フラグがfalseである場合について少し補足します。

  • 「配列の末尾には」となっていますが、sizeNより小さいので、配列の末尾一エントリは使われていません。よって、必ず使えます。
  • sizeを書き込む」となっていますが、sizeとしてあり得るのは01、……N-1のN通りなので、(二進数として書き込むことで)Kbitで足ります。

それ以外の場合

もし、要素数取得関数size()の時間計算量が定数である必要がある*1なら、以下のケチりテクニックは使えません。 なくてもよいなら、上記と同じ NK + 1bitで実現する方法があります。ただし、size()の時間計算量が定数でなくなるということからもわかるように、かなり非効率な実装となります。

まず、先と同じ議論により、 NK+1bitが下限値であることはすぐにわかります。

実現する方法も、先の方法とおおよそ同じです。フラグがfalseの場合の議論が成り立っていないので、以下のように変更します。

  • フラグがfalseである、つまりsizeNより小さい場合、用意した配列にsize個のKbitデータを詰め込む。使っていないエントリの先頭にtrueを、他のエントリにはfalseを書き込む

少し補足します。

  • 「使っていないエントリの先頭に」となっていますが、sizeNより小さいので、使っていないエントリは常に存在します。
  • trueを」「falseを書き込む」となっていますが、 K>0であるので、そのエントリはtruefalseを区別できるビット幅を持っていることが保証されます。ただし、タグなしunionという、かなり危険なコードを書く必要があります。
  • 「ほかのエントリには」となっていますが、そのようなエントリがなければ何もする必要はありません。

このように書き込んだデータ構造を解釈するには、後ろから解釈する必要があります。前から解釈することは不可能です。

後ろから解釈する、というのはつまり、フラグ→配列の末尾→配列の末尾のその前→……という順番で確認していくということです。 このように確認を進めていき、最初にtrueが書き込まれていた部分までに並んでいたfalseの数が、N-sizeに対応しています。 つまり、sizeの情報が一進数で書き込まれているということになります。

別の解釈もできます。フラグを「trueなら配列にはN個の要素が書き込まれている、falseなら配列には『容量の上限がN-1の"この仕組み"のデータ構造』が書き込まれている」という切り替えフラグだと解釈すると、再帰的なデータ構造になっていることが確かめられます。基底ケース(N=0)ではfalseがあり得ないので常にtrueとなっていることとも整合します。

参考:要素としてあり得る状態が 2^K通り未満である場合

この場合、きっかり NKbitで実現可能です。その実例は、ヌル文字(NUL)終端文字列であり、文字列以外にも一般化可能です。

このように書き込んだデータ構造は、前から解釈することになります(一種の接頭符号になっています)。

size()の時間計算量が定数でないという特徴は似ていますが、前から解釈できる特徴により、コンパイル時に容量上限を決めなくてよいという利点があります。

*1:C++STLコンテナの要件。size関数を持たないコンテナも存在します(例えばstd::forward_list)