SATソルバを作る会 (1) - ひとり勉強会 (2009-02-08)
適当にまったりと。今回は下準備みたいなものだけです。 入力 せっかくなのでデータ形式は SAT Competitions の形式と揃えておこうかと思いました。出せるようなものはとても作れないですけど、比較する時にその方が便利そう。 まず、入力はConjunctive Normal Formの論理式で与えるとのこと。 (x1 or !x5 or x4) and (!x1 or x5 or x3 or x4) and (!x3 or !x4)こういう、『「変数か変数の否定 (= リテラル)」をorで繋いだもの (= 選言節)』をandで繋いだもの、という形の式です。ファイル形式としては、DIMACS形式というので与えられるらしい。こんなテキストファイルです。 c c コメント〜 c p cnf 5 3 1 -5 4 0 -1 5 3 4 0 -3 -4 0 最初に何行かコメント (c XXXX
Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
)
GC/extend/TreadmillGC(Barker 1992) - GCアルゴリズム詳細解説
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 GC/extend/TreadmillGC(Barker 1992) 最終更新：ID:e3W7ppwkaA 2009年08月24日(月) 17:00:10履歴 Tweet TreadmillGC(Barker 1992) Copyingに似たnon-movingなインクリメンタルGC アルゴリズム このアルゴリズムは双方向リンクを利用し，Copyingと似た動きをする． つまりMark&Sweepは行わない． Copyingのようにルートからたどったオブジェクトを移動させるアルゴリズムである． 移動の際，単純なChenyCopyingGCだとオブジェクトを物理的に移動するが，このアルゴリズムの場合，双方向リンクを付け替える事で移動とする． このアルゴリズムではGCの
マリオのジャンプ実装法とVerlet積分(実践編) - Gemmaの日記
前回の続き 実際にやってみました。(Canvas要素を使っているのでFirefoxでどうぞ) http://eva-lu-ator.net/~gemma/geocities/jsmario/jsmario.html マリオのようにジャンプで放物線運動をするゲームを作るとき、 たいていは、座標と速度を使って物理計算すると思います。これはEuler法といいます。 Verlet法では、座標と、前回の座標を使って計算します。つまり、速度を記憶しません。 Verlet法では、座標だけ扱えばすむので、壁にめりこんじゃいけないといった条件を簡単に書くことができます。 単に座標を、壁の直前にするだけでいいです。 ネタ元はCowboy Programming >> Blob Physicsです。 今回のコードの肝は以下の部分です。衝突判定がすっきり書けました。 //Verlet法 var y_temp =
2008-07-26 - 兼雑記 - SGC
色々あって GC に興味がちょっと出たので色々見てました。とりあえずまとまった日本語資料としては以下の PDF が一番良いように思いました。 kinaba さんがちょっと前に言及しておられたえんどう豆的でない方の遠藤さんが書いた文章らしい。 http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf これをざーと読んでいくと、すごくためになって、色々わかるのですが、最後の方の 7.2 に、 筆者は、 parallel かつ concurrent な GC を、 Boehm GC を基にして実装している。 とか書いてあって、そのちょっと前に concurrent GC ってのは要は別スレッドでちょいちょい GC 動かす実装で、 incremental GC の一種と考えられて、要 write barrier 。とか書いてあるわけです。でこれってちょっと考
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
xe-kdoo(2008-04-11)
>> BMS Starter Pack オフライン期に何故だか「音ゲーやりたい！」熱が高まっていたので、BMS をやることにした。BMS をやるのは、BM98 で DRUNK MONKY [A] の（音無しの）譜面を練習してたころ以来、のような気がする。前世紀末か。 んで、 どっかから辿って BMS Starter Pack 2006 というのを見つけ、やってみる。 その後 BMS Starter Pack 2007 があることを知って、こっちもダウンロード。 と思ったら、BMS Starter Pack 2008 があったのね。←いまここ nazobmplay（Starter Pack に同梱されている BMSプレイヤー）にはインターネットランキング機能がついているので、とりあえず登録してみた。 が。……レベル高ぇ。何曲かやってみたけど、ほとんどが下位5%くらいの順位ですよ。 >> [
西川善司の3Dゲームファンのための「CRYSIS」、「CRY ENGINE2」講座〜知性シェーダーが作り出す新世代グラフィックスの秘密
【10月2日】 「任天堂カンファレンス 2008.秋」レポートその1 ハード編 「自分専用DS」を目指した「ニンテンドーDSi」 「任天堂カンファレンス 2008.秋」レポートその2 ソフト編 年末年始も磐石? 「Wii Music」ではとたけけ登場!? 「任天堂カンファレンス2008秋」 主要タイトル・ファーストインプレッション 「ニンテンドーDSi」を一足先に体験!! 他 任天堂、スクリーンショット集〜DS編 「マリオ&ルイージRPG3!!! (仮)」、「メイドイン俺」、「立体ピクロス (仮称)」など 任天堂、スクリーンショット集〜Wii編 「罪と罰2 (仮称)」、「Punch-Out!!」、「街へいこうよ どうぶつの森」など 任天堂、「ニンテンドーDSi」を発表 30万画素カメラ付、SDカードスロット付で11月1日発売 【速報版】 佐藤カフジの「PCゲーミ
lucille development blog » Blog Archive » 解析的レンダリング
OoO 第一回にご参加いただいた皆様、参加ありがとうございました。 私が担当した、 A First Order Analysis of Lighting, Shading, and Shadows の論文紹介のスライドを貼付けておきます。 (OoO グループのページにもあります) OoO に参加いただいたレンダラ野郎含め、海外のレンダラ野郎ともやりとりすることが多くなったのですが (英語で blog を公開し始めたからですね)、いまなぜかちょうど皆、解析的レンダリングに注目しており、 (特にビジビリティの解析的処理) 解析的なアプローチが時期 G.I. レンダリングの主流になるのではないかと注目しているので、 今回この論文を紹介することにしたました。
多項式時間素数判定アルゴリズム
ＡＫＳアルゴリズムと PRIMES is in Pに関する解説のページです 以下の説明は、元論文を参照しながらお読みください。 元論分のサイト：Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P, the original version of the paper. アルゴリズムの基本となるアイデア アルゴリズムの概要 AKS アルゴリズム 使用する用語と記号 アルゴリズムの動作概要 アルゴリズムの正当性の証明概要 アルゴリズムの正当性の証明の蛇足説明 アルゴリズムの正当性の証明詳細のための準備 PRIMES is in P セクション３の解説 Lemma 3.1. Lemma 3.1.(fact 1) Lemma 3.1.(fact 2) Lemma 3.1.(fact 3) Lemma 3.1.(fact 4
Bigtable: A Distributed Storage System for Structured Data - steps to phantasien t(2006-09-11)
2006-09-11 近況 今月は貧乏なので慎しく暮らしている. 週末もひきこもりとしてオンラインの記事を読んで過ごすことに. ウェブを眺めているといいタイミングで Google の新作論文が出ていた. ありがとう, Google の中の人. これ. GFS, MapReduce, Sawzall とつづく Google インフラ N 部作の 4 章が幕をあげた. 実はデータベースも作ってるんだぜ, という話. BigTable という名前だけは以前から O'Reilly Radar などに登場していた. ようやく公式な文書があらわれた. BigTable は GFS をはじめとする Google インフラの上に作られた分散データベース. 少し変わったデータモデルと, 運用までワンセットのヘビーな実装を持つ. 実装の話もまあ面白いんだけれど, それよりデータモデルが印象的だった. 先にその
lucille development blog » Blog Archive » Fast Barrier for x86 Platforms
Fast Barrier for x86 Platforms 自動最適化で Spiral の資料をあさることが多くなっていますが、 ひとつ面白そうなネタを見つけました。 x86 での最速なバリア同期処理は何か？というもの。 Fast Barrier for x86 Platforms http://www.spiral.net/software/barrier.html まず、驚きだったのが、pthread のバリア同期関数の遅さ。 2×2 cores では 27000 cycles もかかっている。 これは CPU の周波数が 2.7 GHz なら、0.1 msec かかるということになる。ひょえ〜〜 lock + アトミック加算でのバリア同期だと、数千サイクル程度に減る。 どれもそうだけど、2×2 cores(2 dies) では、FSB をまたぐ必要があるわけで 2 cor
「計算的な深さ」について - 186 @ hatenablog
▼ 「計算的な深さと脳」 で書いた計算的深さの概念はシンプルかつ重要だと思う。 もしそうならこの程度の概念がすでに専門の学者によって発明されていないはずはない。そう思ったのだけど、相変わらず私のアンテナにはかかってこない。もしかしたらまだ存在しないのだろうか。 (中略) ここで、試論として、「2入力NANDゲートだけで最速な回路構成をした時の計算時間」と定義する。こうすれば大きさNのメモリによる解決はlog N時間かかる事になる。同じ問題を、テーブルで解いてもハードワイアードロジックで解いても同じ程度の時間になるだろう。 ご想像の通り, 既にあります. (並列計算量とか回路計算量の文脈で調べると良いんじゃないかと.) Complexity Zoo - Qwikiから引っ張ってくると, こんな感じ. ACi 多項式サイズ/unbounded fan-in/AND, OR, NOT/深さO(l
音声合成 - Wikipedia
「読み上げソフト」はこの項目へ転送されています。耳が聞こえる視覚障害者向けにウェブサイトなどのコンピューター上の表示を読み上げるソフトウェアについては「スクリーンリーダー」をご覧ください。 この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "音声合成" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年11月) ヒトは発声器官を通じて音声を生成し、コミュニケーションを行なう（会話や演説、講演、各種芸能およびその中継や録音・録画など）。この音声を人工的に生成するタスクが音声合成である。合成された音声を合成音声（ごうせいおんせい）と呼ぶ。 音声合成は様々な手法で実現できる。ある種の楽
西川善司の3Dゲームファンのための「2007年3Dゲームグラフィックス」講座
【10月11日】 カプコンブースポート 「モンスターハンター3」など全タイトルが試遊可能 「THE IDOLM@STER SP presents 765プロ新曲発表会」開催 765プロ&961プロが新曲を披露! CD先行発売決定!! コーエー、「ネットエンターテインメントフェスタ 2008」レポート 今年も4人のプロデューサーが集結!! サプライズはPS3版「大航海時代 Online」 SCEJブースレポート PS3編その2 日本初プレイアブルのPS3「KILLZONE2」、「RESISTANCE2」などをプレイ! ＫＯＮＡＭＩイベントレポート PS3/Xbox 360版「悪魔城ドラキュラ」製作決定、 MGO拡張パック第二弾追加情報を発表 「METAL GEAR ONLINE WORLD CHAMPIONSHIP 2008」決勝大会レポート 個人戦・クラン戦ともに日
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
lucille development blog » Blog Archive » Course notes on Beyond Programmable Shading
情報処理学会電子図書館
lucille development blog » Blog Archive » Quasi-Monte Carlo light transport simulation by efficient ray tracing
lucille development blog » Blog Archive » floating point. part 1 : 非正規化数の恐怖