No Such Blog or Diary
ランダマイズドな近似アルゴリズムに関する論文は読みにくい
- 2010-07-15 (Thu)
- 一般
ランダマイズドアルゴリズムや近似アルゴリズムには,平均の計算量とか近似比とかをコントロールする為のパラメータが含まれる.そして,多くの場合,ランダム選択のための確率や条件分岐の条件には,そのパラメータの一見して意味不明な多項式とかが大量に出てくる.基本的にこれらの式の形の複雑さは,計算量とかの保証のために証明上都合の良いしきい値を取っていることに起因する.そのため,アルゴリズム中のパラメータによる判定式が何の目的でその形をしているのかは証明を詳しく追わないと理解出来ない.とどのつまり,直感が働かないのでアルゴリズムの本質がなんなのか一見しただけではわからない(論文の本文中に説明があれば別なのだけど,紙面の都合上,そこまで親切にするのは難しいのでしょう).
ということで,Max-cover を解くためのランダマイズド近似並列アルゴリズムの論文読むのに二日かかった.MapReduce使えるとか言っているのを確かめたかっただけなので,そこまで細かく読む必要はなかったかもしれない.
そしてこいつは GroupByKey によって,「集合→含まれる要素達」という関係と「要素→それを含む集合達」という関係とをスイッチングするのがキモらしい.ということで,こういった視点の切り替えが必要な集合上のアルゴリズムならGBK演算が必要といえそう.他にっどんな問題があるのか良く解らんけど.
とりあえず Set-cover と Weighted Max-cover と BudgetありMax-cover も同じで動くでしょう.Set-cover はもっと単純かもしれんけど.
- Comments: 0
- TrackBack (Close): -
何かを思い立つ
- 2010-07-14 (Wed)
- 一般
免許の更新期限まであと2週間.自動二輪の免許を最速で取るのも2週間.やることはひとつ.
ということで,自動二輪の免許を取りに教習所に行くことにした.虹色のとこ.受付のお姉さんに技能予約を無理矢理突っ込んでもらったりして,規定通りに行けば免許の更新が一回で済む予定.さてどうなることやら.
そして,前に使ってたヘルメットは実家に置きっぱなしなので,新しくSHOEIのMultitecを買った(前のはAraiの何か).かぶると丁度良いフィット感なのだけど,まだ新しいせいなのか脱ぐ時に耳たぶが変に引っかかって痛い.そのうち慣れるといいなぁ.
- Comments: 0
- TrackBack (Close): -
プリンタをエラー状態に追い込む論文
- 2010-07-14 (Wed)
- 一般
とある論文のPDFをLinuxから印刷しようとしたら,送りつけた色々なPSプリンタがエラー状態に追い込まれて印刷できなかった.Windows側からやったら問題なかったので,Linux側のGhostscriptとかの辺りで何かがおかしかったのかもしれないけど… よくわからん.
- Comments: 0
- TrackBack (Close): -
梅雨の時期になると溜まるもの
- 2010-07-13 (Tue)
- 一般
雑誌とダンボール.
濡れた紙とか微妙すぎるので雨降ってるとゴミに出す気になれない.
来週にはゴミに出せるといいなぁ.
- Comments: 0
- TrackBack (Close): -
工事した
- 2010-07-13 (Tue)
- 一般
棚を壁にくっつけてもらいましたとさ.これで文句なかろう.
それにしても現場に来た方と受付の事務の方とで情報がうまく伝わっていなかったり現場に見積りに来たのに施工箇所を間違っていたり微妙にハズレ感が漂っていたのだけど… とりあえず物はちゃんと固定されているので問題なかろう.
- Comments: 0
- TrackBack (Close): -
価格で千円ずれると買う気になるの法則
- 2010-07-12 (Mon)
- 一般
価格=「kakaku」,千円=「k」,ずらすと「kakkau」で「かっ買う!」.
「価格」と打とうとしてミスって「かっ買う」になっちゃって微妙に面白かったのでその下らなさをメモっておく.
- Comments: 0
- TrackBack (Close): -