profileをかける

　どうにも遅くて仕方ないので、sysprofでprofileをとってみた。profileの結果を信じるなら、配列のひとつ前の空き要素を線形探索する部分が遅いようだ。
というわけで、探索している関数をちょっといじって、どれぐらいの要素を線形探索しているのかを調べてみたら、軽々と数万要素は探索している。（もちろん、すぐに空き要素が見付かる場合もあるのだが、平均すると数万要素は探索している。）こりゃ遅いわけだ。
　これをどうすれば早くできるかという問題だが、アイデアとしてはふたつ。

1. 線形探索をやめる
2. 探索を呼び出す回数を減らす

　線形探索を止めるためには、なんらかの形で前の空き要素へのリンクを持っておかねばならない。これは容量が増えるので却下。
　というわけで、線形探索を呼び出す回数を減らしたいのだが、profile結果を見る限り、そう簡単には減らせそうにない。