アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
memcachedを超える成果も、Interopで若手技術者がクラウドを支える技術を競う
「日本でゼロからクラウドを生み出すムーブメントを作り出したい」（実行委員長 門林雄基氏）---“クラウドを支える技術”の開発力を競う「クラウドコンピューティングコンペティション」が2009年6月11日、Interop 2009の会場で開催された（写真1）。企業や大学・大学院の研究者、そして高校生を含む若手エンジニアが、新しいアイディアと技術力で作り上げたクラウドコンピューティングの基盤ソフトウエアを披露した。 クラウドコンピューティングコンペティションは、奈良先端科学技術大学院大学の門林雄基准教授らの呼びかけで実現したイベント。若手のエンジニアがP2P（ピア・ツー・ピア）技術や分散データ処理技術といったクラウドコンピューティングの基盤技術を開発し、その成果を競う。検証環境として、情報通信研究機構（NICT）が運用するクラスタ環境「StarBED」のコンピュータを最大1000台まで使用可能で
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
OpenGLの基礎
OpenGLは，3次元グラフィクスプログラミングにつかわれる標準的なライブラリです． ライブラリとは，プログラムの部品セットであるといえます． ライブラリを利用することで，自分で0から書かなくても， ライブラリが提供する部品を組み合わせることでプログラムを作成することができます． ここでは，OpenGLの基礎を説明します． OpenGLの概要 Ruby/OpenGL OpenGLプログラムの基本的な構造 イベント，コールバック，イベントループ 2次元図形の描画 図形プリミティブ 属性 2次元ビューの設定 ビューポート OpenGLの概要 OpenGLは，3次元グラフィクスプログラミングにつかわれる標準的なライブラリで，SGI(Silicon Graphics, Inc.)がGLという同社のコンピュータ専用のグラフィクスライブラリをもとに開発したものです． OpenGL以外でよく用いられる3
大都会の夜景をコンピューターによって完全自動で描画するムービー
ハリウッド映画のCGシーンは何人ものCGアーティストが、高価な機材を何台も使って手作業で作成されるために、予算が高騰している要因の1つにもなっているほどですが、これらのCGにも勝るとも劣らない大都会の夜景をどこにでもあるコンピューター1台だけで生成してみた人がいます。 手作業でテクスチャーを描いたり、グラフィックボードに搭載されているピクセルシェーダーのように、外部のプログラムを用いて特殊な効果を与えるなどの手間をかけることなく、内部のプログラムが自動で生成するポリゴンとテクスチャのみを用いて壮大な夜景が生成されています。いかに単純な仕掛けで人間の目をだましてものすごい映像を作り出すか、よいヒントになるかもしれません。 詳細は以下。 Twenty Sided >> Blog Archive >> Procedural City, Part 1: Introduction このプログラムはS
Logarithmic merging - naoyaのはてなダイアリー
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更
フォント同士を交配させて新しいフォントを作る「genoTyp」が面白い - てっく煮ブログ
「この発想はなかった！」と驚いた。genoTyp はフォント同士を交配させて新しいフォントを生み出す実験サイトだ。早速、試しにやってみた。1. 第一世代の親を決めるgenoTyp を開いて左上の [Breed] タブをクリックすると「交配ページ」が表示される。[add original font] ボタンをクリックして、祖先となるフォントを２つ追加してみた。交配させるために２つのフォントをドラッグしてくっつけた。くっついた状態になれば交配の準備は完了だ。2. 交配させてみる中央の [cross] ボタンを押すと第一世代が誕生する。４人の子供が誕生した。父親似だったり、母親似だったり、子供によって雰囲気が異なっている。3. 第一世代でも交配別の [original font] を追加させて、第一世代の中から気に入ったものと交配させてみた。３人の子供が第二世代に誕生した。4. さらに交配！今度
統計的に正しいランキングを行う方法 - Hello, world! - s21g
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ポジティブ／ネガティブ投票による正しいランキング方法が以下の記事で紹介されています。 How Not To Sort By Average Rating この計算方法では、投票数が少ない場合には分散が大きく不正確な評価で、 投票数が多くなるにつれて分散が小さく正確な評価が得られているという事を考慮しています。以下数式 これはScoreの信頼区間を表しています。 この信頼区間の下界をランキングのスコアにすれば良い事になります。 ここで、は、 です。全体に占めるポジティブ投票数の割合ですね。 は標準正規分布上の 信頼区間の有意確率です。 さて、五段階評価によるRatingに同様のテクニックを適用する場合はどうしたらいいでしょうか
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
きまぐれ日記: 「読めてしまう」コピペがなぜ読めてしまうのか
http://www.asks.jp/users/hiro/59059.html http://www.itmedia.co.jp/news/articles/0905/08/news021.html 最初読んだとき、違和感なく読めてしまったのですが、よくよく見てみると、そんなトリックがあったのですね。 さて、この「読めてしまう」がなぜよめてしまうのでしょうか？ 人間の言語モデルの単語パープレキシティは、約100ぐらいであると言われています。どういうことかというと、 人間が文章を読んでいるときに、次の単語を過去の文章から推測するのは 1/100 程度の 確率で正解するということです。 件のコピペですが、最初の文字は変わらないので、その正解率は平仮名の数(52)倍になります。 すなわち、52/100 =~ 0.5 実際には、最後の文字も変わらないし、 単語の長さが変わらないというもの、大きな
「しりとり」の戦いかた、すこし反省した - Active Galactic : 11次元と自然科学と拷問的日常
「しりとり」は経験者人口が極めて多いゲームだけど、鬼神のごとき強さで他を圧倒するしりとりプレイヤーを私は知らない。ちょっと真剣に戦ってみたところで、 そんな程度のレベルで満足していやしないか。 さいしょは「る」の同字返しでガッチリ組み合う。先に「る→る」のストックが切れて、「る」で返せなくなったほうがひたすら「る攻め」で投げられ続ける。 小学生の時から進歩していないような、こんな大雑把でマンネリな「る攻め」戦略から脱却できないものか。 攻撃防御比最大の最強文字「る」 復習。周知の事実だが「る」は強い。 下の表は、[A](文字Ｘで終わる単語)と、[B](文字Ｘではじまる単語)をその比[A/B]の高いものから順にリストしたものである。標本の単語数は２０万語であり豚辞書から、伸ばし棒をトリムした上で抽出した。*1 文字X[A]Xで終わる単語[B]Xで始まる単語[A/B] １位る43235208.
北海道を落とすとどう跳ねるのか？の裏側 - てっく煮ブログ
asおかげさまで大好評の 北海道を落とすとどう跳ねるのか？ ですが、どのように作ったか、製作過程を紹介することにします。1. 地図の素材を取ってくるまずは地図の素材が必要です。以下のサイトから拝借しました。白地図、世界地図、日本地図が無料pdf や eps 形式の地図データを無料で配布してくれているありがたいサイトです。2. 都道府県ごとに分割する上記の素材は県境もベクター形式で提供されていて大変ありがたかったのですが、島がどの都道府県に属しているかの情報がありませんでした。そこで、Google Maps と見比べながら、島を都道府県ごとに分類していきました。無事、全ての島を分類し終わって、こんな感じになりました。とても地味な作業でした…。3. 都道府県ごとに SVG で出力する次に、Illustrator 内で分類したデータをプログラムで扱える形式にしなければなりません。ここでは XML
PerlとRubyで省メモリなハッシュを使おう - mixi engineer blog
サボっていた早朝ジョギング＠駒沢公園を再開して2週間たち、やっと抜かれる数より抜く数の方が増えてきたmikioです。今回は、PerlやRubyのハッシュの代用としてTokyo Cabinetを使うことでメモリ使用量を激減させられることを説明します。 抽象データベースAPI Tokyo Cabinetには抽象データベースという機構があり、先日、そのPerlとRubyのバインディングをリリースしました。それを使うと、各種言語のハッシュとほぼ同じような共通したインターフェイスで、以下のデータ構造を利用することができます。 オンメモリハッシュ：各種言語に標準のハッシュと同じく、メモリ上でkey/valueの関係を表現する。 オンメモリツリー：メモリ上の二分探索木としてkey/valueの関係を表現する。 ファイルハッシュ：いわゆるDBMとして、ファイル上でkey/valueの関係を表現する。 ファ
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
「物理法則を自力で発見」した人工知能 | WIRED VISION
前の記事 「衛星成功に総書記は涙」：北朝鮮の核再開宣言とミサイル輸出 「物理法則を自力で発見」した人工知能 2009年4月15日 Brandon Keim Image credit: Science、サイトトップの画像はフーコーの振り子。Wikimedia Commonsより 物理学者が何百年もかけて出した答えに、コンピューター・プログラムがたった1日でたどり着いた。揺れる振り子の動きから、運動の法則を導き出したのだ。 コーネル大学の研究チームが開発したこのプログラムは、物理学や幾何学の知識を一切使わずに、自然法則を導き出すことに成功した。 この研究は、膨大な量のデータを扱う科学界にブレークスルーをもたらすものとして期待が寄せられている。 科学は今や、ペタバイト級[1ペタバイトは100万ギガバイト]のデータを扱う時代を迎えている。あまりに膨大で複雑なため、人間の頭脳では解析できないデータセ
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
都市シミュレーションと教育・学習をテーマ とした報告書。