Embedded Files
でもインデックスは維持しつつ
配列とかリストには
- 普通の配列（リストも含める）
- スタック/キュー
- リンクリスト
- ハッシュテーブル
とかがありますね。
えーと、それで、次のような条件を満たす配列が欲しくなりました。
- インデックスでどこからでもアクセスできる
- シーケンシャルアクセス・ランダムアクセス両方できる
- 追加・削除したときに（その処理対象の1要素の他は）既存要素のインデックスが変わらないことが保証されている
- 追加・削除が高速、できればO(1)
- というか何をしてもできるだけ高速が良いあと無駄にメモリ消費が重くなるのも嫌だ（当たり前）
『ぼくの考えたさいきょうの配列』みたいなものになってしまいましたが、その時作っていたのが『ある要素が他の要素をインデックスで参照している』という、一種のリンク構造を持っているものだったので、インデックスが変わると困るのです。
（それってランダムアクセスになるから遅いじゃんという問題もあるのですが話がズレるので割愛）しかも要素は10万～1000万とか大量に作ることになりそうで、要素の生成と削除も割と頻繁に起こるので、出入りも激しい。というわけでこういうオールマイティな配列みたいなものが欲しくなりました。
そういうちょっと特殊な状況に最適化した配列の使い方をしたいという話で、やってることは単に普通の配列の使い方をちょっと工夫しただけです。
既存の配列では無理
既存の配列では無理
「追加・削除が高速」という条件でまず大体選択肢に上がるのはリンクリストですが、前から順々に辿ることしかできません（前後双方向のリンクだったら後ろからも辿れるけどそれだけ）。インデックスによるピンポイントなアクセスができないので、選択肢から消えます。
また『削除したときにもインデックスが変わらないことが保証されている』ことを条件にしていますが、これが結構無茶で、この条件を愚直に適用すると、ハッシュテーブルしか残りません（ハッシュテーブルはハッシュで検索するようなものなので正確にはインデックスとは違いますが）。
ハッシュテーブルは空間分割とかでもよく使うみたいですが、（ハッシュが重複しなければ）O(1)で要素に辿りつけるとはいえ、そのハッシュを求める計算が必要（O(1)のコストが重い）とか、あとメモリの確保幅が見えづらいなど、中身の複雑ブラックボックス感が強くて個人的にあまり使いたくなかったのでこちらも選択肢から消えました。
スタック/キューは全く用途が違うのでこれも除外。
つまり…
- 普通の配列（リストも含める）
- スタック/キュー
- リンクリスト
- Dictionary（ハッシュ計算でインデックスを決める配列）
普通の配列orリストしか選択肢がありません。
削除しない削除
削除しない削除
普通の配列だと、そもそも削除は想定されていません。削除したいなら要素を排除して1個分縮んだ配列を新たに用意するような処理になります。
一方でリストには要素を削除して切りつめを自動で行ってくれるRemove()がありますが、削除した要素以降のすべての要素が1コずつ前にズレてくるのでインデックスが全部変わってしまうし、このインデックスずらす分はコピー処理になります。
例えば100個の中身があるリストの1個目の要素をRemoveしたら、残りの99個分を一つ前に移動するコピー操作が走ります。
インデックスが変わっても良ければ、末尾の要素と削除要素を入れ替えることでO(1)負荷で削除する手法というのもあるようですが、今回はインデックスが変わるのは困るのでこれも使えません。
参照側の参照インデックスを書き換えるという選択肢もありますが、構造上 参照を逆に辿れないため、ある要素が削除された時にその要素を参照している要素を探すためには配列内を全検索する必要があり、削除に伴って位置がシフトされた全要素に対してこれを行うのは無茶です。
なので、インデックスを動かさずに要素を削除するには、削除しないという選択肢しかありません。（矛盾）
今回は削除して配列を切り詰める代わりに無効値を詰めることにしました。
当然、この『削除』ではメモリ使用量も全く減りません。しかし今回の場合は追加も頻繁に行われることが分かっているため、次に要素が追加されるときには、配列を伸長するのではなく、この『削除』された要素（空き家と呼ぶことにします）のところに新しい要素を入れます。
削除だけが大量に行われたとかいう場合を除いて、長い目で見れば一応少ない無駄で要素が詰まっている状態が維持できるはず。
考えてみた
考えてみた
こういうタイプの配列には何か正しい呼び方があるのかもしれないですが知らないので、FixedListという名前にしました（インデックスが固定だから）。
1. 追加のたびに空き家を探す方式
1. 追加のたびに空き家を探す方式
愚直な実装。
Addのたびに配列を前から順に走査して、無効値（空き家）を探すだけ。
Removeは対象要素を無効値で置き換えるだけです。
（無効値は<T>の制約条件に取るインターフェースで定義する（例：参照型ならnullが空き家状態だと見做す、数値なら符号が負なら無効値とか））
クラス定義：
public class FixedList<T>
{
List<T> data; //データ配列
}
処理の例：
O：有効な要素x：無効値（空き家）データ配列：OOOOOOOOOO 10個の要素を持つリスト
データ配列：OOxOOOOOOO ←要素[2]が削除された
データ配列：OOxOOOOOxO ←要素[8]も削除された
データ配列：OOOOOOOOxO ←要素が追加された（前から順に空き家を探し、[2]に入る）
データ配列：OOOOOOOOOO ←要素が追加された（前から順に空き家を探し、[8]に入る）
データ配列：OOOOOOOOOOOxxxxxxxxx ← 要素が追加された（もう空き家はないのでリストが2倍の長さに拡張）
追加のメモリ消費もなくシンプルですが、もちろんAddのたびに走査するので、Addが最悪の場合で（読み込み走査のみとはいえ）O(n)操作になります。
要素数が多いと不安。
2. 空き家一覧を持っておく方式
2. 空き家一覧を持っておく方式
データ配列とは別に、削除された空き家のインデックスをすべて記憶しておく方式です。
こちらはAddもRemoveもO(1)で済みますが、追加のメモリ消費が生じます。
具体的には、要素がRemoveされる度に空き家一覧用の別の配列（QueueまたはStackあたりが使いやすい）に削除された要素のインデックスを記憶させるようにします。その後要素をAddする場合はまずこの空き家一覧を見て、空き家があればその空き家のところから先に詰めていきます。空き家一覧がゼロになった段階で、初めてリストの長さの伸長が選択肢に入ります。
クラス定義：
public class FixedList<T>
{
List<T> data; //データ配列
Queue<int> empties; //空き家記憶用キュー
}
処理の例：
データ配列：OOOOOOOOOO
空き家キュー：
データ配列：OOxOOOOOOO ←要素[2]が削除された
空き家キュー：2 ←2を記憶する
データ配列：OOxOOOOOxO ←要素[8]も削除された
空き家キュー：2,8 ←8も記憶する
データ配列：OOxOOOOOOO ←要素が追加された（一番新しい空き家[8]に入る）
空き家キュー：2 ←8は埋まったので空き家ではなくなる
データ配列：OOOOOOOOOO ←要素が追加された（空き家[2]に入る）
空き家キュー： ←2も埋まったので空き家ではなくなる
データ配列：OOOOOOOOOOOxxxxxxxxx ← 要素が追加された（もう空き家はないのでリストが2倍の長さに拡張）
空き家キュー：11,12,13,14,15,16,17,18,19 ← 一気に空き家が増えたので空き家配列も増える
走査は必要なくなりました。概念がわかりやすく、メモリ消費も「空き家個数×4byte」くらいです。上のように空き家が2個の例であれば、メモリ消費も4byte×2個で済むので、空き家が少ないのなら有用そうです。
ただ、例えばリストが伸長された時などは（リストは現在のキャパシティの二倍の長さに伸長していくので）、リストの後ろ半分がすべて空き家になったりします。これを全部記憶していくと結構空き家記憶に必要なメモリが増えてきます。
（伸長したときにできる空き家は例外扱いとし、ヘッダーのみ記憶しておくことで代用するとかいう工夫もできなくはない）
でも最悪の場合でもデータ配列の要素数×4byteくらいで済むので、データ配列の1要素のサイズがでかい場合などは相対的な追加メモリ消費は少なく済みます。分かりやすいし結構アリかもと思いました。
3. 寄生的リンクリスト（造語）を構築する方式
3. 寄生的リンクリスト（造語）を構築する方式
例えば配列の要素がint型で、正の値しか有効値として使わないという条件があるとしたら、負の値の要素は無効値、つまり空き家と見なすことができます。
無効値は意味のあるデータとしては使われないはずなので、それならば空き家の時はその変数を利用しちゃえ！的な発想のやつです。
上の負の値を空き家と見なす場合では、負の値も膨大な幅があるので、負の整数を使って他の空き家インデックスへの参照を表現すれば、データ配列そのものを利用して追加のメモリ消費は空き家ヘッダーを記憶するためのint一個だけで『空き家リンクリスト』を構築できます。
クラス定義：
public class FixedList<T>
{
List<T> data; //データ配列
int emptyHeader; //空き家ヘッダー
}
具体例：
データ配列：OOOOOOOOOO
空き家ヘッダー：
データ配列：OOxOOOOOOO ←要素[2]が削除された
空き家ヘッダー：2 ←2を記憶する
データ配列：OOxOOOOO2O ←要素[8]も削除された（[8]には-2(2への空き家参照)が入る）
空き家ヘッダー：8 ←ヘッダーは8を記憶する
データ配列：8OxOOOOO2O ←要素[0]も削除された（[0]には-8(8への空き家参照)が入る。空き家リンクがつながっていく）
空き家ヘッダー：0 ←ヘッダーは0を記憶する
データ配列：OOxOOOOO2O ←要素が追加された（空き家ヘッダーが示していた[0]に入る）
空き家ヘッダー：8 ←[0]に入っていた8への参照が新しい空き家ヘッダーとなる
データ配列：OOxOOOOOOO ←要素が追加された（空き家ヘッダーが示していた[8]に入る）
空き家ヘッダー：2 ←[8]に入っていた2への参照が新しい空き家ヘッダーとなる
(以下省略)
int一個のメモリ追加消費だけで、空き家がすべて網羅されているのでよさそうですが、実際は取り扱いがやや煩雑です。
というのも
要素側は、空き家リンク参照を表すための十分な幅の整数値を表現できなくてはならない（なのでbool単体の型とかだと不可）
空き家かどうかを表すフラグも決めておかなくてはいけない
空き家要素である間、外部でその空き家リンクの値を変えてはいけない（リンクリストが辿れなくなってそれ以降の空き家要素が忘れ去られる）
などの条件が守られていなくてはならないからです。
今回の例では、負の値が空き家を表し、負の整数が空き家リンクの参照を表すという感じですが、つまりは値が負の時にはその値を勝手に書き換えてはいけないということになります（空き家リンクの情報として意味を持ってるから）。
無効値として扱っているのなら書き換えたりはしないはずだ！というちょっと危なっかしい前提に基づいた実装にするか、またはFixedListの<T>の制約条件として取るためのインターフェースを定義して、負の値だったらその構造体は空き家であるとかいった条件を定義させる感じにすると思うのですが、慎重な実装が必要になり、扱いを間違えると話がややこしくなりそうです。
（FixedListのインデクサーで空き家要素が置換されるのを監視するとかいうのもできなくはない）
この理由から、これも個人的にボツになりました。
(この先は書いてません)
(この先は書いてません)
Page updated
Google Sites
Report abuse