トップ «前の日記(2004-08-11) 最新 次の日記(2004-08-13)» 月表示 編集

日々の流転


2004-08-12 [長年日記]

λ. iconv-io 0.0.4

readpartialキター ([ruby-dev:24058]) ってことで、iconv-ioをreadpartialを使うようにする。

知らない人のために紹介すると、iconv-io はIOもどきの1つで、他のIOっぽいオブジェクトをラップし、エンコーディングを変換しながら読み書きするためのものです。例えば、以下はSTDINをラップしてshift_jisからutf-8にエンコーディングを変換しながら読む例です。


io = Iconv::Reader.new(STDIN, "shift_jis", "utf-8")
io.each_line{|l|
  ...
}
Tags: ruby

λ. "Purely Functional Data Structures", Chris Okasaki

読了。感想は後ほど追記予定。

[2005-01-27 追記] 計算量の表を時々参照したくなるので、ここに転載しておく。

Summary of Implementations
(Worst-case running times are marked with †.
All other running times are amortized.)
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のコードが加わっているとか。
Purely Functional Data Structures(Chris Okasaki)

Tags: 論文