最近のリアルタイムCGで一つのトピックとなっているのがグローバルイルミネーション（大域照明）だ。太陽のような単一の光源だけではなく，そこから反射したあらゆる光の影響を考慮したシェーディングを行うというのがグローバルイルミネーションで，PRT（Precomputed Radient Transfer）はそのモデルの一つである。 Call of Duty 2では背景描画にラジオシティ法を使い，非常にリアリティのある画面を作り出していた。ラジオシティもグローバルイルミネーションの手法の一つである。ごまかしの部分も多そうだが，通常のライティングとラジオシティの組み合わせは，CoD2でかなり成功を収めたといっていいだろう。 ようやく一般的な3Dゲームでも影が付くのが当たり前になってきた。セルフシャドウなど，単に地面に影を落とすだけではない処理も出てきているのだが，まだまだ不自然に感じてしまう部分は多
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
Windows Graphics & Presentaiton Technologies for Developers Kinect for Windows ハードウェアのアナウンス Kinect for Windows ブログで、Kinect for Windows ハードウェアのアナウンスがありました。新しいハードウェアの仕様として以下のものが挙げられています。... Author: 川西 裕幸 Date: 11/23/2011 祝：Windows Phone Icons Maker v1.0 1,000 ダウンロード Windows Phone Icons Maker v1.0 のダウンロードが 1,000 を超えました！ 使い方のヒント コピー＆貼り付けでも使えるので、Power... Author: 川西 裕幸 Date: 11/15/2011 Player Framework
何を見てもアルゴリズムを考えてしまうのがプログラマの職業病といったところです。 私は結構ゲーム好きなんですが、ついついアルゴリズムを考えてしまうんですね。 バグを発見したときなどは楽しくてたまりません。 そのほつれからプログラムのコードが透けて見えるのです。 本日のターゲットは2001年、匠から発売されたアーケードゲーム「ナイトレイド」です。 ジャンルはシューティングなのですが、変なシステムを採用した、あまり見栄えのしないゲームでした。 このゲーム、非常にマイナーです。多分、名前を聞いて分かる人の方が少数派ですね。 ちなみにプレイステーションに移植されています。 アーケード版公式ページ PS版公式ページ このゲームには非常に致命的なバグがあり一部界隈では有名です。 自機を画面左上に移動させると敵が弾を撃たなくなるのです！ なぜこんなことが起こるのでしょうか？ 矩形の衝突判定 ところで矩形(
最近、機械学習とか、そのアルゴリズムのひとつであるサポートベクターマシンとかやってるわけですが、そもそも機械学習ってなんなんでしょか？ 機械学習ってのは、なんとなく与えられた点の分類から、新たに与えられた点の分類を推測するのですが、ようするに、点が与えられたときにそこから分類の領域を推測しておいて、新たな点がきたときにはどの領域に入るかを判別するのです。 ニューラルネットワークは、名前にニューロンとかついてて、とてもステキな響きがするのですが、あれは関数のあてはめを行っているのです。そうやって関数をあてはめることで、領域の境界面を求めます。 NN法は、学習とかせず、一番近いデータが同じ分類になるはずという戦略でやってます。 サポートベクターマシンも考え方としてはNN法と同じで、新しい点がやってくると、学習したそれぞれの点までの近さを計算して、一番ちかい分類を求めます。そのため、学習データが
協調フィルタリングとはAmazonのお勧めのように「この商品を購入した人はこんな商品も購入しています」という情報を用いて推薦をする手法です。グラフィカルモデルはベイジアンネットワークとも呼ばれ、最近一部で流行している機械学習の手法です。今回は、協調フィルタリングをグラフィカルモデルで表現したらどのようになるだろう、と考えて思いついたアイデアを紹介します。 今、ユーザuとアイテムiの組{u,i}のデータが大量に与えられているとします。例えばソーシャルブックマークならユーザとブックマークしているページの組み合わせ、E-commerseならユーザと購入した商品の組み合わせ、などです。ここではSBMを例に考えるので、はてブと同様にユーザはマイナスの評価を付けることはできないものとします。 このときユーザuに対してお勧めのページを推薦することを考えると、ユーザuがまだブックマークしていないページiに
数学パズル「4つの4」入門・第3回 (2002-06-10) 「4つの4を使って0～1000までの数を作れ」というパズルを10秒以内に解くスクリプトの実演 数学パズル「4つの4」入門・第2回 (2002-06-06) 自律的思考アルゴリズムの基礎 数学パズル「4つの4」入門 (2002-06-05) 「4つの4」問題、最終解決のきざし 2002年 6月 3日 記事ID d20603a 「4つの4で遊ぼうよ」シリーズの式検索は、充分に網羅的でないし、必ずしも効率的でなかった。当初の方法からみれば相当に高速化した「ラムダ関数バージョン」ですら、まったくムダが多い。4つの4を使って作れる数全体を調べるときに、評価される値を数え上げるのが目的であるにもかかわらず、構成可能なすべての表現を数えてしまっているからだ。詳しい説明は省くが、以下のようなまったく異なる発想を用いることが望ましいように思われる
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
はじめに CやC++である程度大きなプログラムを書く場合，最大の問題点は メモリ管理である．複雑なプログラムの場合，必要なメモリの量を あらかじめ見積っておくのが難しいから，メモリが必要になった 時点でメモリを確保し，不要になったらそれを解放するという プログラミングスタイルが一般的だ．Cで言えばこんな感じだ． char *x; ... x = (char*)malloc(n*sizeof(char)); ... x を使って仕事をする ... free(x); このプログラミングスタイルの問題点は，おおまかに言って こんなところだろう． free(x) を忘れると，プロセスがどんどん大きくなってしまう． free() してはいけないものを間違ってfree()する(たとえば，同じ メモリを2回 free() してしまうとか)と，その free() の中でなく， 全然違う場所でエラーが発生す
はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループはどれか？ などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、 友達の友達は友達である と定義すると、友人関係は同値関係を作る。 その上で、 A君とB君は友達 C君とE君は友達 B君とD
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
流行っているっぽいのでやってみました． 与えられた木から、子→親への対応を作る Shiro(2008/05/24 11:55:47 PDT): たまたま昨日、仕事で扱った小ネタ。初級編クイズになりそうなので書き留めておく。 木構造が与えられる。たとえばこんなの： (define *tree* '(Root (Spine (Neck (Head)) (RClavicle (RUpperArm (RLowerArm (RHand)))) (LClavicle (LUpperArm (LLowerArm (LHand))))) (RHip (RUpperLeg (RLowerLeg (RFoot)))) (LHip (LUpperLeg (LLowerLeg (LFoot)))))) つまり、 <tree> := (<name> <tree> ...) という構造。 これから、子→親の対応を表す
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
高校数学で理解する反応拡散系 ※この項では空間パターンは扱いません。ですから反応拡散系ではありませんが、そのままこの名称を使います。 文責：尾崎 淳 いきなり言い切ってしまうが、“反応拡散機構は生物の基本原理”だと筆者は思っている。 それは、このモデルが小難しくってカッコいいから・・ではなく、言われてみれば当然な、ごく当たり前のこと言っているにすぎないのに“生物らしさ”のかなりの部分を説明できるからです。 以前より当ホームページでは簡単な反応拡散系の解説ページを掲載してきました。 実際、何人かの方よりこのページは好評価をいただいたのですが、相変わらず多くの実験生物学者や学生からは難解な概念であると感じているように見受けられました。 しかし「難解なことをやっているからすごい」と受け取られることは我々の本望ではありません。 むしろ数学や専門用語で自説を“難解”に見せている発表・出版
はじめに TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。 基本的なアイデア まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。 基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。 フォーマルな問題定義 基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデー
「食事する哲学者」の問題は、並行処理の研究課題としてダイクストラにより提案された。その内容は以下の通り。 円卓を囲んで５人の哲学者が思策にふけりつつ、時に応じて食事を取る。食事は円卓中央の皿に山盛りにされたスパゲッティである。しかし、このスパゲッティはあまりにもからまりあっているので、食べるときには両手にフォークを持って食べなければならない[*1]。 フォークは、哲学者と哲学者の間に１本ずつ、都合５本が置いてある。つまり、右隣の哲学者が食事をしている最中は、右側のフォークは使用中であり、自分では使えないことになる。左についても同じ。 ここで問題は、５人の哲学者が一人も飢えることがないように、食事をさせるプログラムを書くことである。 この問題は並行処理のモデル化であり、フォークが共有資源にあたる。また、フォークを哲学者たちが取り合う部分がCritical Sectionとなる。 一つの解答例
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く