視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
せっき～のゲーム屋さん ドルアーガの塔 乱数の工夫の正体
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。 ＣＥＤＥＣの講演 「ゲーム世界を動かすサイコロの正体 ～ 往年のナムコタイトルから学ぶ乱数の進化と応用」 より、 乱数を使った ドルアーガの塔の 迷路生成のアリゴリズムについて紹介です。 講演内容は、こちらです http://sekigames.gg-blog.com/Entry/288/ 講演者の方も、 「ナムコの乱数を取り上げるなら、ドルアーガの塔をせざるえない」 という程、外せない内容との事です 「このテーマだけで講演時間を全て使っても説明しきれない」 （講演では、時間の関係で 触りのみでしたので ある程度、せっき～の解釈で補完しています） -------------------------------------------------------------------
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
グーグルのバグ予測アルゴリズムを実装したツール「bugspots」、オープンソースで公開
ソースコードのなかでバグが多いのは、より高頻度に、かつ最近になって集中的に直している部分。これが、グーグルで採用された「バグ予測アルゴリズム」であることを、先月の記事「グーグルはコードの品質向上のため「バグ予測アルゴリズム」を採用している」で紹介しました。 そのバグ予測アルゴリズムを実装したツール「bugspots」がオープンソースとして公開されています。 gitのレポジトリを分析 bugspotsはRubyで記述されており、gitのレポジトリから履歴を読み込んで分析し、どのモジュールにバグが含まれている確率が高いかを示してくれます。 以下のようにインストールして実行（説明ページから引用）。 $> gem install bugspots $> git bugspots /path/to/repo $> git bugspots . # (in current git directory)
竹内関数で音楽生成 - aike’s blog
Lisperの人ならみんな知ってる竹内関数（たらいまわし関数）という関数があります。 定義としてはこんな感じ。 そのシンプルな定義からは想像もつかないほど複雑で膨大な再帰呼び出しがおこなわれるとても興味深い関数です。たとえば引数にTarai(10,5,0)を与えると343,073回も再帰呼び出しされたりします。 この関数呼び出しの引数がどのように変化するか知りたくてプログラムを書いて調べてみたところ、Tarai(10,5,0)の場合は3つの引数がそれぞれ0〜10（xは-1〜10）の間で少しずつ変化するなかで、2つの値を固定してひとつの値が下降していくような挙動があったりして、なんだか音楽の3和音のコード進行を思わせるような動き方です。 そういうことなら、ということで実際に音にして聴いてみました。Tarai関数が呼ばれるたびに引数のx、y、zを、0=ミ、1=ファ、2=ソ、……、のように音に割
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
局所探索
巡回セールスマン問題に対する局所探索法 巡回セールスマン問題について 複数箇所の訪問先(以下都市とよびます)をすべて一度だけ訪問するとき、 その訪問の総距離が最短となる巡回路(つまり出発地に戻らなくてはならない) を求める問題です。 都市はアプレットの右上端にあるプルダウンメニューから問題例を選ぶか、 画面上をクリックすることで配置することができます。 SOLVEボタンで局所探索法による求解の動作を開始します。 動作中にSTOPボタンまたは画面をクリックすると一時停止します。 SOLVEボタンで動作を再開します。 CLEARボタンで都市を消去します。 局所探索法について 局所探索は、すでに構成済み(1)の巡回路を改良するために用いられます。 なお、ここで紹介するアプレットでは巡回路の構成はNearest Neighbour 〜もっとも近いお隣さんをたどること〜によって実現して
Source Codes -- Computer Today
Computer Today 誌では、「アルゴリズムの道具箱」という連載記事が 掲載されましたが、その中の1999年1月--12月（No.89 -- No. 94）の6回を 私が担当しました。これはその後、臨時別冊・数理科学「アルゴリズムの 道具箱」、戸川隼人・有澤誠（編）、サイエンス社、2000年1月、として出版 されています。そこに用いたCプログラムのソースコードを 以下にリストします。自由にダウンロードして、試していただければ 幸いです。バグや問題点を発見された方は、 私宛（Email: ibaraki@ksc.kwansei.ac.jp）ご連絡下さい。 1. クイックソート クイックソートのソースプログラム バブルソートのソースプログラム 2. 部分和問題 列挙法 ssum のソースプログラム 動的計画法 dpssum のソースプログラム データ例 ssumdata
Chapter.2 巡回セールスマン問題に対するGAの応用 - 田中雅博監修・日高正博製作補助 知能情報Web教材
巡回セールスマン問題(TSP)とは？ 巡回セールスマン問題 (the Traveling Salesman Problem) は，N個の都市すべてを1度ずつ訪問した後に最初の都市に戻る巡回路のうち、 最小の距離のものを求める問題である。 この巡回セールスマン問題に対してGAの応用を考えよう。 Partially Matched Crossover [PMX] 通常の交叉では、都市の重複が考えられるため、工夫する必要がある。ここでは連続した組の遺伝子対に着目し、交叉するPMXの手順を簡単に説明する。 一対の親染色体が以下のように与えられているとき、ある連続した部分列の組（この例では(3,7),(6,2),(1,5)の３組）に注目する。
機械学習に魂を売ったコンピュータ将棋 - 武蔵野日記
今月号の会誌「情報処理」(2010年8月号目次)の特集は「コンピュータ将棋の不遜な挑戦」というタイトルで、ここ数年のコンピュータ将棋の発展の技術的な解説。こうやって毎年のように情報がアップデートされると非常にありがたい。 見所は鶴岡さんによる「選手権優勝記--激指の技術的改良の解説--」とktanaka先生・kanekoさんによる「大規模クラスタシステムでの実行--GPS将棋の試み--」の2記事。特に鶴岡さんによる記事は、Bonanza のよい解説にもなっており、必読である。実は、激指は 評価関数というのは，局面の形勢判断をコンピュータで行うための関数で，任意の与えられた局面に対して，どちらがどれだけ有利なのかを数値化する関数である．[...] このようなパラメータの調整は非常に手間のかかる作業だが，かつては完全に手作業で行われており，将棋プログラム開発における作業の多くの割合を占めていた
動的計画法を学ぶリソース・練習問題まとめ - フリーフォーム フリークアウト
移転しました http://please-sleep.cou929.nu/20100708.html
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
基礎から学ぶコンピュータ
Umetani, Shunji
Edge Assembly Crossover （EAX)
TSPに対する有効な世代交代モデルの検討
サービス終了のお知らせ