たつをの ChangeLog
: 2010-05-11
前後の日:
2010-05-10
< >
2010-05-12
この月:
2010-05
別の年の同じ日:
2000
2001
2002
2003
2004
2005
2006
2008
2009
2010
2011
2012
2014
2015
2016
2017
2018
2019
2020
2022
【書評・感想】オンラインアルゴリズムとストリームアルゴリズム
2010-05-11-1 [
BookReview
][
Algorithm
]
とりあえず読了。
(ref.
[2007-09-13-2]
)
■
徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)
私の場合こういう教科書は「読了した」といっても「ざっと目を通した」レベルで、証明とかは「あとで理解する」とタグ付けし飛ばし飛ばしなのです。「本の内容の理解」とはほど遠いのです。
第4章の冒頭にこんな記述が。
読み方としては、まずは数式や証明の詳細はスキップして全体のストーリーとアルゴリズムの設計の手法を眺めて、その後で解析の部分の数式をチェックするというのがお奨めである。
ということで、難しいところは「あとで読む」!
今月、来月いっぱいはちょこちょこ見直すことになるかと。
そんなわけですが、アルゴリズムの詳細以外に関しての自分用インデックスだけ載せておきます。一番興味を持って読んだ6章の分のみだけど。
第6章 ストリームアルゴリズム
- オンラインアルゴリズム:過去の履歴はすべて記録しておける。
- ストリームアルゴリズム:過去の履歴は記録できない。
- そろばんでの計算術はストリームアルゴリズムそのもの。
- 誤り許容カウント法(lossy count method)。省メモリで高頻度のものをカウント。これは使える。
- チェビシェフ(Chebyshev)の定理によるランダムサンプリング。省メモリで種類数をカウント。
- スライド窓モデル(sliding window model)・時間窓モデル(time window model)。有効期限切れ最大値問題に使う。マキシマ(maxima)というデータ構造を使う(この問題では時間最新順と値最大順の両方を満たす)。
- マルチパス・ストリームアルゴリズムは本書では対象外だけど少しだけ紹介ということで Apriori アルゴリズムが解説されていた。現場でバリバリ使えそうだ。
この記事に言及しているこのブログ内の記事
2010 年 5 月に読んだ本 (2010-05-31)
誤り許容カウント法(lossy count method)のサンプルプログラム (2010-05-12)
地下鉄六本木駅にはがせる広告!
2010-05-11-2 [
Marketing
]
地下鉄日比谷線六本木駅の壁にはがせる広告がありました。
COTTON USA の広告です。
広告パネルに四角い磁石シートが貼られており、自由に持ち帰れるようになっていました。
道で配られてるといらないんだけど、さりげなく置いてある(貼ってある)とついつい持って帰っちゃうんだよな。
釣られてるなあ。
前後の日:
2010-05-10
< >
2010-05-12
この月:
2010-05
別の年の同じ日:
2000
2001
2002
2003
2004
2005
2006
2008
2009
2010
2011
2012
2014
2015
2016
2017
2018
2019
2020
2022
たつをの ChangeLog
Powered by
chalow