2004-08-12 [長年日記]
λ. iconv-io 0.0.4
readpartialキター ([ruby-dev:24058]) ってことで、iconv-ioをreadpartialを使うようにする。
知らない人のために紹介すると、iconv-io はIOもどきの１つで、他のIOっぽいオブジェクトをラップし、エンコーディングを変換しながら読み書きするためのものです。例えば、以下はSTDINをラップしてshift_jisからutf-8にエンコーディングを変換しながら読む例です。
io = Iconv::Reader.new(STDIN, "shift_jis", "utf-8") io.each_line{|l| ... }
λ. "Purely Functional Data Structures", Chris Okasaki
読了。感想は後ほど追記予定。
[2005-01-27 追記] 計算量の表を時々参照したくなるので、ここに転載しておく。
| Name | Running Times of Supported Functions | Page |
|---|---|---|
| banker's queues | snoc/head/tail: O(1) | 26 |
| physicist's queues | snoc/head/tail: O(1) | 31 |
| real-time queues | snoc/head/tail: O(1)† | 43 |
| bootstrapped queues | head: O(1)†, snoc/tail: O(log× n) | 89 |
| implicit queues | snoc/head/tail: O(1) | 113 |
| banker's deques | cons/head/tail/snoc/last/init: O(1) | 56 |
| real-time deques | cons/head/tail/snoc/last/init: O(1)† | 59 |
| implicit deques | cons/head/tail/snoc/last/init: O(1)† | 116 |
| catenable lists | cons/snoc/head/tail/++: O(1) | 97 |
| simple catenable deques | cons/head/tail/snoc/last/init: O(1), ++: O(log n) | 119 |
| catenable deques | cons/head/tail/snoc/last/init/++: O(1) | 122 |
| skew-binary random-access lists | cons/head/tail: O(1)†, lookup/update: O(log n)† | 79 |
| skew-binomial heaps | insert: O(1)†, merge/findMin/deleteMin: O(log n)† | 83 |
| bootstrapped heaps | insert/merge/findMin: O(1)†, deleteMin: O(log n)† | 102 |
| sortable collections | add: O(log n), sort: O(n) | 35 |
| scheduled sortable collections | add: O(log n)†, sort: O(n)† | 47 |
[追記]
ちなみに、この論文を元にした本が出版されています。
より一般向けの話とHaskellのコードが加わっているとか。
[ツッコミを入れる]
