ソートされた配列データ構造のこのコレクションの名前はありますか？

次のデータ構造の名前はありますか？論文や引用がありますか？ソートされた配列データ構造のこのコレクションの名前はありますか？

一つの方法to implement効率的セット抽象データ型各アレイは、固有パワーの2サイズを有するソート配列のコレクションを有することです。

たとえば、{1、2、...、13}の13個の要素の集合は、{[5]、[2,3,9,13]、[1 、4,6,7,8,10,11,12]}。

一般に、コレクション内の配列は、セットのサイズのバイナリ表現の1ビットに対応するサイズを持ちます。挿入は、（1）時間 O 償却で行うことができ、検索がO（線形検索よりも優れている）（（Nログ））時間で行うことができるため、データ構造が効率的です。また、平衡二分木やポインタのためO（N）余分なスペースを使用するBツリーとは異なり、唯一Oポインタのスペースオーバーヘッド（Nログ）を使用します。したがって、ペイロードデータにはほとんどすべてのスペースが使用されます。

私はWikipediaのlist of data structuresを見ましたが、一致するものは見つかりませんでした。「Introduction to Algorithms（ "CLRS"）」は、このデータ構造を「償却分析」セクションの宿題の問題として説明していますが、例ではなく質問であるため、本書ではあまり言及していません。

出典

2013-06-07 Nayuki

私はタグ "データ構造"しか考えられませんでした。関連タグの提案をお願いします！ – Nayuki

これらの既存の質問は同じデータ構造に関するものですが、実装と説明について質問します。http://stackoverflow.com/questions/2602110/、http://stackoverflow.com/questions/4701433/私はデータ構造がどのように機能するかを知っているので、私は特にそれに関する出版された文献を探しています。 – Nayuki

同様の考え方は、少なくとも1978年4月のCACM号でJean Vuilleminのoriginal publication on binomial heapsにまでさかのぼります。私はこのデータ構造を導入した論文がVuilleminによって引用されたり引用されたりすると期待していますが、「参考文献」と「引用者」リストの論文は有望です。

私があなただったら、cstheoryと尋ねて、CLRSに書き込みますが、準最適な境界と削除の欠如を考えれば、succinct data structureコミュニティがある時点で興味を持っていない限り、何も出てこないと思います。

特に知りたいことがありますか？

出典

2013-06-07 17:32:43

SE：cstheoryと簡潔なDSesを参考にしてくれてありがとう。私はこのデータ構造のために書くつもりなので質問しました。しかし、私はそれをすでに受け入れられている名前にしたいと思っているだけでなく、自分のアイデアだけに頼るのではなく、既存の文学に基づいて構築したいと思っています。 – Nayuki

検索時間が最適ではないことは事実ですが、既に訪れた何百万ものゲーム状態をメモリに保存する必要があったため、私は自分のアプリケーションの簡潔さを利用しました。削除に関しては、CLRSは「DELETEを実装する方法を議論する」と言っていますが、軽い考え方では、償却されたO（n log n）時間内に実装する明白な方法を考えることはできません... – Nayuki

@NayukiMinaseそれを考えると、削除は、削除されていない項目を示すビットマップを持ち、半分空の配列を下方にマージするという通常の手段によって、償却O（1）されるべきです。 –

ソートされた配列データ構造のこのコレクションの名前はありますか？

答えて

関連する問題