久野です。グループがもはやlispじゃないと思うが計算量だとどこか…

kono@ie.u-ryukyu.ac.jpさん:
> free を O(1) にするには、memory pool みたいなのを使うと可能
> です。

  そりゃフリーリストの先頭にくっつければO(1)つまり定数時間になり
ますが、alloc するときどうするの。ヒープを端から取って使い切る前
に計算終了するんだったらそもそも動的alloc不要だよね。フリーリス
トから取ろうとしたとたんに、O(1)じゃなくなるでしょ、適合するもの
を探さなければならないから。全部同じサイズ? それはずるいな ^_^;

> 非破壊append bench mark を別プロセスでやって GC しない
> で抜けて来るみたいな感じ。それが一般的なGCの仮定に反する(自
> 由に参照をコピーできる) のはその通りです。で、そういうことす
> ると GC を持っているシステムでは、まずいってな話でしたよね。

  GCがなくてすむ例でGCが遅いとかいうのはフェアじゃないね。GCが
ないとメモリが足りない例でGCと手動と比べてよ。

> 二乗でゴミを吐くプログラムなんてダメダメなのは、その通りなん
> だけど、線形でゴミを出すのは良くありますよね。というか、これ
> までの話だと、むしろ推奨されている。で、そうやって生成したゴ
> ミを回収するコストが、ゴミの量に比例するかって言うと、それは
> アルゴリズムによります。

  比例する=それぞれのゴミについて(償却)定数時間、ね。では定数時
間のアルゴリズムを挙げてみてください。

        「よる」っていうのだからあるんでしょ?                久野