top page > computer > haskell > web_lecture > for_programmer > list_efficiency.html
更新日:
文責: 重城良国

リストによる「くりかえし」の空間効率

空間効率の問題は?

空間効率とはどのくらいメモリを食うかだ。リストによる「くりかえし」の実装は空間効率が悪いのではないか。いちいち全要素のリストを作っていたらメモリの使用量はひどいことになる。

問題ない

「リストを作成した」ときリストはまだ作成されていない。何を言っているかわからねーと思うが(ry

Haskellの遅延性が利く。リストの各要素は本当に必要になるまで作成されない。作られた要素はあとで使わないならばGCされる。「くりかえし」として使うとき要素は前から順に1度だけ使われる。それぞれの要素のために確保されたメモリ領域はすぐに解放される。この動作は手続き的な「くりかえし」と似ている。「リストをわたしていく」ように書くが手続き的な「くりかえし」と同様の空間効率となる。

「転写」へもどる 「データ構造としてのリスト」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics