スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
(HomePage '(Yasuto . Takenaka) :Page '(Lisp-Ja . Game-Theory))
HomePage Select Langage In Japanese 英語 目次 Ja Science-Ja Blog-Ja (hatena) Programming-Ja Misc-Ja BookMark-Ja (hatena) Photolog (blogspot) Contents En Science Blog (blogspot) Programming Misc BookMark (del.icio.us) Photolog (blogspot) Contact Info 連絡先 edit SideBar XHTML ゲーム理論における繰り返しゲームのパッケージ このパッケージはCommon Lispに組み込まれているオブジェクト指向言語CLOSを利用して組まれています。繰り返しゲームシミュレーションをする為のプログラムです。 繰り返しゲームとか囚人のジレンマについては説明を
ソースコード探険隊
What's new - 更新履歴 直近20件の新しい記事です。 2025-01-05: 即納・短納期ノートパソコン 2024-11-28: DELL Latitude と Inspiron の違い・比較 2024-08-25: ASUS Zenbook と Vivobook の違い・比較 2024-07-28: Lenovo IdeaPad と ThinkBook の違い・比較 2024-02-28: ASUS ROG ノートパソコン FLOW・ZEPHYRUS・STRIX の違い、比較 2024-01-14: ASUS ノートパソコン製品シリーズの違い・比較 2023-12-10: ゲーム開発に最適なノートパソコンの選び方／おすすめ機種紹介 2023-11-18: 動画編集に最適なノートパソコンの選び方／おすすめ機種紹介 2023-11-03: プログラミングに最適なノートパソコンの選
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.
ハードウェア乱数生成ルーチンhdrand.c
ハードウェア乱数生成ルーチンhdrand.c by とつげき東北 トップページに戻る 「ランダムな乱数」「良質な乱数」を得る 導入： プログラミングをしていて、「真にランダムな乱数」を得ようとしたときに困ることがある。 どんなに優れた決定論的擬似乱数ルーチンも、真にランダムな乱数を作ってはくれない。 結果としてtime値などを乱数の種にすることになるわけだ。 ゲームなどならその程度でも充分だが、セキュリティの重要なソフトではそうはいかず、ユーザのマウス入力のタイミングなどを読み取る必要が出てくる。 そこでCPUがPentium以降・Windows下でハードディスクが使用されている環境で、ユーザに不可解な入力作業をさせることなく、良い性質の乱数を得るためのルーチンを作っておく。 方法： テンポラリファイルフォルダにファイルを作成・削除し、その処理にかかった時間を高分解能
trigonometric calculation by CORDIC
CORDIC による三角関数の計算 この手の解説の最初にありがちな、CORDIC ってなんの略でしょう、 などという話は飛ばして、いきなり本題に入ります。 とりあえず、x の余弦や正接、つまり cos x や tan x が求めたいものとします。 また、三角関数の周期性を使って、 x は 0 から 45 度の間に正規化されているものとします。 また, 基本的な一次変換の知識を仮定しています。 突然ですが、問題です。コンピュータや電卓を使わずに、 人様が任意の角度の三角関数の値を求めるには、 どうするでしょうか。 答え）高校の数学の教科書にもあるように、 適当な基準線から分度器を使って求めたい角度を持つ直角三角形を書き、 その三辺の長さをはかって割り算をする。 ということで、この考えを応用したのが CORDIC です。 とりあえず、基準線の方向として、x 軸上の点 P0(1,0) から出発し
Ｃプログラミングの秘訣
特集 Ｃプログラミングの秘訣 最終更新: 2006-03-28 このテキストはC MAGAZINE 1992年4月号に掲載された原稿のオリジナルテキストを元にしてHTMLに変換したものです。掲載文章と細部が異なっていると思われます。また、気付いた個所をいくつか修正してあります。 当時はまだWindows 95もないような時代で、現在の状況から見ると違和感のある内容も結構あるかもしれませんが、時代背景を想像しながら補正しつつ読んでいただければ幸いです。 ※2006年3月28日追記: 何が原因か知りませんがこのページのアクセスが増えているそうなので、 HTML のおかしなところを修正しました。 文章の変更はありません。 なお、このサイト(表ページ)は現在休眠状態ですが、 裏ページ や 裏の裏ページ の方を、細々と更新していたりします。 目次 Part1 よいプログラムを書く条件 Part2 明
C言語 Super Technique 講座
このページは、Ｃ言語の中級テクニックを中心に解説する。長らくプログラマをしていると、Ｃ言語の面白い使い方例が蓄積している。これらを一挙公開するために、このページを作ったのである。しかし、単にＣに留まらず、他の言語の面白い特徴なども紹介していく。 内容的にはかなりヘヴィである。当然のことながら、「ポインタ虎の巻」程度の内容はちゃんと使いこなせることを前提とする。意外な技、落し穴、派手なテクニックなど、内容満載だが、ちゃんとデータ構造とアルゴリズムなども説明できれば良いと思う。（まあ、ぼちぼちやってきいます...） 以下の目次には手引きのために、評価がつけてある。凡例として示す。 レベル その解説で記載されている内容のレベル 有用度 その内容が実際に役に立つものかどうか 邪悪度 その内容が薦める方法が、一般的なコーディング規約の中で「邪悪」とされがちなものであるか否か。関数ポインタの活用（濫用
Support Vector Machine
最近よく巷で耳にするモノ． SVM， Support Vector Machine， さぽーとべくたーましん． これっていったい，どんなもんなんでしょう． なにやら便利そうなモノらしいので，ちょいと調べて要点をまとめてみようかな，なんて． でも，ただまとめただけだとそのへんの記事を読むのとなんにも変わらないので， コーディングするために必要な知識を中心にまとめてみることにします．
Mathematical Information Technology
本サイトについて アルゴリズムとデータ構造 平方根 開平方のアルゴリズム 平方根のアルゴリズム 初期値の改良による平方根計算の高速化 ソート 基本ソート 基本ソートの改良 高速なソート 高速なソートの改良 その他のソート ソートの様々な比較規則 クイックソート、マージソートのマルチスレッド化 SortApplet 数値の0埋め ヒープ 直接挿入法 連結リスト 数列の和 εアルゴリズムによる級数計算 オイラーの変換による交代級数の加速 数学 素数 素数 試行除算による素数判定 フェルマーテストによる素数判定 素数定理について Javaによる素数の判定 Javaでの平方根計算アルゴリズムの改良による素数判定の高速化 一ケタの素数の倍数を取り除くことによる素数判定の高速化 データ構造の変更による繰り返しの高速化 素数に関する情報源 ソフトウェア開発 LSI C-86 Ver. 3.30c 試食版
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://oss.timedia.co.jp/show/column/%BA%A3%C6%FC%A4%CE%B0%EC%B9%D4/%A3%B2%A3%B0%A3%B0%A3%B5%C7%AF%A3%B1%A3%B2%B7%EE
RenderNote - RenderNote
IBM JavaScript での有限状態マシン 第 2 回: ウィジェットを実装する - Japan
http://grape.c.u-tokyo.ac.jp/~makino/kougi/system_suuri4_1998/all/all.html
LOGICAL-PARADOX.ORG
システム・エンジニアの基礎知識
Ｐ２Ｐな自作ソフトとＬＩＳＰ言語 メインページ
http://www.eml.hiroshima-u.ac.jp/member/jrs/nis/javaexampl/delaunly.html
http://www.roy.hi-ho.ne.jp/pastel/home/VC/delauney.html