skiplist について
細かい説明とかを書こうとしたのだが面倒くさくなった。いつか書くかもしれないけど。ソースコードを http://www.city5.org/hg/hgwebdir.cgi/skiplist/file/295b7bb0d927/ に置いたので、興味があったら見てください。 hg clone http://www.city5.org/hg/hgwebdir.cgi/skiplist/ で手元に持ってきてもよい。
ところで、なぜ乱数が必要でないかというと。 skiplist では数系列が固定であってもよく、数の分布が p^n に従ってさえいえばいい。ところで、ある整数をビット表現にしたときに下位からいくつ0が連続するか、という計算をする関数を考えると、数に対してちょうど (1/2)^n となるような分布になる。ので、最初は「疑似乱数で整数を生成」→「下位のビットを調べて新しいノードのランクを決める」という処理にしていたが、これべつに乱数でなくても初期値を1としてインクリメントしてもぜんぜん問題がないことにあとで気付いた、という次第。
あと、 Gauche の拡張パッケージが書きやすい話とか、 gauche-package という補助ツールがあるので細かいことを考えなくてよく便利ということですが、でもまあ乱数がなければ c ライブラリにして c-wrapper の方がよかったかもとか、そういう話もあるかも。あとコールバックの書き方は treemap を真似ました。
ああ、あとプロファイラの件ですが、当たり前っちゃ当たり前だけど C 関数のなかにはプローブは落ちないんですよね。でないとおかしい。