[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
第2回 memcachedのメモリストレージを理解する | gihyo.jp
株式会社ミクシィ 研究開発グループの前坂です。前回の記事でmemcachedは分散に長けた高速なキャッシュサーバであることが紹介されました。今回はmemcachedの内部構造がどう実装されているのか、そしてメモリがどう管理されているのかをご紹介します。また、memcachedの内部構造の事情による弱点も紹介します。 メモリを整理して再利用するSlab Allocationメカニズム 昨今のmemcachedはデフォルトでSlab Allocatorというメカニズムを使ってメモリの確保・管理を行っています。このメカニズムが登場する以前のメモリ確保の戦略は、単純にすべてのレコードに対してmallocとfreeを行うといったものでした。しがしながら、このアプローチではメモリにフラグメンテーション（断片化）を発生させてしまい、OSのメモリマネージャに負荷をかけ、最悪の場合だとmemcachedのプ
404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明する
2007年12月03日11:15 カテゴリアルゴリズム百選 アルゴリズム百選 - ハッシュを再発明する (実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。 現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。 しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。 誰でも
Y コンビネータって何？ - IT戦記
このエントリの 親友へ。ブログを書こう。 - IT戦記 y がブログを始めたみたいなので、読んでみた。 で、最新のエントリを読んでみたら、 Y コンビネータというものについて書いてあったので、 Y Combinatorが凄すぎる！ - yuji1982の日記 Y コンビネータって何ってところから、自分でもいろいろ考えてみた。 結局なんなのかさっぱり分からなかったんですが、自分が考えたことをまとめておく まず、フィボナッチ数を求める fib を定義する var fib = function(n){ return (n <= 2) ? 1 : (arguments.callee(n-1) + arguments.callee(n-2)); }; fib(10); おお！ JS すげー！名前は n しか使ってねーよ！ めでたし、めでたし。。。。じゃなくて！ JS が素晴らし過ぎて話が終わってしま
書評 - アルゴリズム・サイエンス (入口|出口)からの超入門 : 404 Blog Not Found
2007年05月30日04:00 カテゴリ書評/画評/品評 書評 - アルゴリズム・サイエンス (入口|出口)からの超入門 正三郎さんのお薦めという事で、手に入れてみた。 出口からの超入門 入口からの超入門 共立出版「アルゴリズム・サイエンスシリーズ」: ホットコーナーの舞台裏そのとき、見つけたのが、休刊したbit誌など我々コンピュータ業界ではおなじみの共立出版が新たに刊行を開始した「アルゴリズム・サイエンスシリーズ」。 本シリーズ「アルゴリズム・サイエンス」の嚆矢である「入口からの超入門」ならびに「出口からの超入門」は、読んで字のごとくアルゴリズムの入門である。入口と出口に分けているのがニクい。入口はまだアルゴリズムというものを意識していない人々のための、そして出口はすでにアルゴリズムの威力は知っていても、日々の業務に負われて仕様書をそのままプログラムに書き直すのに疲れ気味の人々にアピー
algorithm
奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の
- サルでもわかる待ち行列
(株)永和システムマネジメント 平鍋健児 作成日：初版 1999, 3/16 第2版 2002, 11/6 第3版 2004, 9/14 第4版 2008, 5/1 情報処理技術社試験の中で良く出て来る「待ち行列」理論を，直感的に覚えやすく解説してみました． 何度もトライしたけど待ち行列が理解できない人向けです． 正確な定義や論理展開は重視せず，いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました．
最速インターフェース研究会 :: 実践JavaScriptで配列をシャッフルする方法リファクタリング
JavaScriptで配列をシャッフルする話を見て、そういえばArray#shuffleは以前書いた記憶があるなーと思って調べてみたらコピペだった。 http://www.fumiononaka.com/TechNotes/Flash/FN0212002.html Fisher-Yatesというアルゴリズムだそうです。 Array.prototype.shuffle = function() { var i = this.length; while(i){ var j = Math.floor(Math.random()*i); var t = this[--i]; this[i] = this[j]; this[j] = t; } return this; } a = [1,2,3,4,5]; a.shuffle() // 3,1,5,2,4 a // 3,1,5,2,4 ごく普通に実装
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
Google、Flashをインデックスできる新アルゴリズム公開
Googleは6月30日、Flashに含まれるテキストコンテンツをインデックスできる新しい検索エンジンのアルゴリズムを開発したことを発表した。これによりFlashメニューやボタン、バナー、Flashで構築されたサイトなどがGoogleにインデックスされるようになった。 これまでサイト開発にFlashを選択することは、検索エンジンにインデックスされにくいという点で懸念されていたが、Googleの新しいアルゴリズムにより、ビジュアルに優れたウェブコンテンツと、より良い検索結果を同時に手に入れることができるようになる。 Flashコンテンツのインデックスについて詳細なQ&Aは、Googleの「Webmaster Central blog」に掲載されている。
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
[JavaScript] Animation.Cube - サイコロ回転エフェクト (rotating cube animation)
Kawa.netxp [JavaScript] Animation.Cube - サイコロ回転エフェクト (rotating cube animation) Animation.Cube クラスは、JavaScript のみでサイコロ回転風の アニメーションエフェクト(rotating cube animation)を実現するライブラリです。 事前に画像ファイルを加工(拡大縮小や分割処理)せず、JavaScript のみで リアルタイムにアニメーション処理を行います。 2画像の切替えエフェクト処理用、または、 サイコロの4面に貼り付けた画像をループで回転させるような処理に利用できます。 画像の拡大縮小処理が入っているため、 ラスタスクロール よりもマシン負荷が高いようです。 Opera だと少しスムーズなようです。 画像サイズを抑えれば、Celeron 2.4GHz 機でも十分に回転してく
エブログ JavaScript で形態素解析もどき
JavaScript で形態素解析もどき JavaScript で形態素解析のようなものを。 totonの日記 - すべての漢字を取り出す正規表現 「すべての漢字を取り出す正規表現」をPHPで試す:phpspot開発日誌 これらの記事を参考にして JavaScript で漢字、ひらがな、カタカナ、英数字に区切ることをしています。 ただ、文字コード的にちゃんとできるのか、よくわかりません。Seesaa はShift_jis なのでおかしくなる場合もあるかも知れないです。 下のテキストエリアに文章を入力して解析ボタンを押すと解析結果が表示されます。解析というか、単純に改行で区切っているだけですが。 サンプルは青空文庫の太宰治 走れメロスの冒頭部分。 メロスは激怒した。必ず、かの邪智暴虐（じゃちぼうぎゃく）の王を除かなければならぬと決意した。メロスには政治がわからぬ。メロスは、村の牧人である。笛
計算物理のためのC/C++言語入門
Last revised on May 25, 2000 UNIX & XWindow 環境における C/C++プログラミング言語の基礎とその計算物理への応用を解説します。 このホームページの古い版の偽ミラーサイトが存在するのでご注意ください。 本物のサイトは http://www-cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/ です。 前書き 推奨図書一覧 C言語とC++言語の基礎文法の初心者向け解説 (プログラム初心者を対象としたC/C++言語の入門です) 第1章 C言語とC++言語の役割 第2章 簡単な計算 第3章 ループで繰り返し計算 第4章 配列で大量データ処理 第5章 関数で計算の分担 第6章 文字列の操作 第7章 ファイルの操作 第8章 グラフィック(XWindow System利用者向け) 高校物理の計算例 (高校生を対象として初歩的な物
最速インターフェース研究会 :: Mozilla24でしゃべってきました
9/15日にMozilla 24 出張Shibuya.js 24でしゃべってきました。 http://shibuyajs.org/articles/2007/08/24/Shibuya-js-24 資料はこちら。 http://ma.la/files/shibuya.js/mozilla24.html JavaScriptでBloom filterのデモ。今のところ実用性が無い。仕組みを理解するのには良いかも。 http://la.ma.la/misc/js/bloomfilter/ Bloom Filterについてはここら辺が詳しい。 http://chasen.org/~taku/blog/archives/2006/01/bloom_filter_1.html http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ゲームプログラミングWiki
ニューラルネットワーク入門
Amazon.co.jp： Binary Hacks ―ハッカー秘伝のテクニック100選: 高林 哲, 鵜飼 文敏, 佐藤 祐介, 浜地 慎一郎, 首藤 一幸: 本
Rogue Engineer's Diary / やさぐれ日記(2005-11-13) / 「アルゴリズム＋データ構造＝プログラム」？ 本当に？
502 Bad Gateway