論文読み1

Fast and compact updating algorithms of a double-array structureという論文を読んだ。要するに、double arrayの空き部分を探すのに、オリジナルのやり方（適当な空き部分が見付かるまでdouble arrayの全領域をスキャン）で探すと使用率が高い場合に効率が非常に落ちるので、空き領域だけをリンクしてやろう、という話。どうやってやるかというと、CHECKに次の空き部分へのオフセット（の符号をマイナスにした物）を入れておく。
個人的なアイデアとしては、BASEとかCHECKに基本的にはポインタを入れておき、ポインタの下位3bitを用いて空き部分を表現する、という方式を考えていたのだけれど、この論文のやり方の方が探索時にちょっとだけ早く探索できるような気がする。負けた。