スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
今からでも遅くない！アルゴリズム入門---目次
高速なハードウエア，至れり尽くせりのユーザー支援機能を備えた開発ツール，高機能なクラスライブラリやフレームワークなどなど，近ごろのプログラムを書くためのお膳立ては，とても充実しています。しかし，どんなに環境が整っても，ソフトウエアを作るには何らかのアルゴリズムに従って問題を解きほぐし，プログラムにするという作業が相変わらず必要です。 そこで本特集では，まずPart1で身近な例からアルゴリズムというものに迫ってみます。皆さんが普段接している便利なソフトやサービスがどのような仕組みで動いているのか，その仕組みをのぞいてみましょう。教科書で勉強するようなアルゴリズムの話とはちょっと違うものも出てきます。中には，サービスの重要な要素をプログラムで処理せず，手作業に頼って実現しているものもあります。実用ソフトの世界で本当に使いやすいものを作るには，アルゴリズムだけわかっていてもダメなことが少なくない
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
どうなっているの？あのソフトの仕組み - 今からでも遅くない！アルゴリズム入門：selfup
Webの全体像を効率よく取り込み，分類する 「YSTのシステムは大まかに三つの機能に分かれます（図2）。最初は世界中のWebページをYSTのシステムに取り込む『クローリング（crawling）』という機能です」（Yahoo! JAPAN，リスティング事業部 検索企画室の宮崎光世氏，以下同）。 取り込むと簡単に言っても，Webページの数は膨大なうえ，更新の頻度や情報の質などがまちまちです。すべてのページに同じようにアクセスしていると非効率なことこの上ありません。そこで，限られた時間で質の良い検索ができるようにするための工夫をしています。例えば，クローリングを繰り返すうちに頻繁に更新されることがわかったページは短いサイクルでチェックし，ほとんど更新のないページはチェックの頻度を落とす，といったことをしているそうです。 ただ，更新の頻度が単に高いだけではダメです。重要性が高いと考えられるWebサ
PRoxy Diary(2006-09-16) - Bayesian Sets
_ [コンピュータ] Bayesian Sets何はともあれ一番目立つところにリンクをば。 ここのところちょっと時間が取れたので、以前から気になっていたBayesian Setsを実装してみました。Bayesian Setsは、ある単語を入力すると、それと関係が深い単語を推測して返してくれるというものです。Google Setsというサービスを聞いたことがある方もおられるかもしれませんが、やりたいことはあれと同じです。理論的な話に興味がある場合はここを参照するか、元論文に当たってください。 論文で「高速」と紹介されているだけあって、Wikipediaから17万文書を使って学習させたにも関わらず結構な速度で動いてくれています。辞書に登録されている単語数も44万と豊富。これだけのものを現実的な時間で捌いているというだけでも、かなり驚きです。無理やりアドホックに処理を端折って計算量を減らしている
プログラムを2倍から4倍早くする方法 - GIGAZINE
プログラミングの話なので、ソフトウェアを使うだけのユーザーには関係ない話です。 要するに実行速度の遅いプログラムを2倍から4倍高速化させるには非常に基本的なトリックというか技術を使えば可能ですよ、というお話。 アルゴリズムの考え方なので、仕事上どうしてもプログラムの実行速度を上昇させる必要があるが、やり方がイマイチよく分からないという人は必見。 Dr. Dobb's | An Algorithm for Compressing Space and Time | 3 1, 2006 かの有名な「ライフゲーム」を例に出し、プログラミングのコードの内容を高速化するにはどういうアプローチを取ればいいのか、その際に使用する再帰的アルゴリズムの考え方、複雑な式を簡単な式に圧縮する方法、圧縮することで実行時間の節約が可能になること、などをやたら詳細に解説しています。 ぶっちゃけ、これが理解できるのであれ
algorithm
奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の
アルゴリズム for Ruby
このページは、ソフトバンク パブリッシングから出版されている『プログラミングの宝箱 アルゴリズムとデータ構造』を読んでいるときに、せっかくなのでサンプルコードを Ruby で書き直した場合、どうなるんだろうと思いつつ作っています。 アルゴリズムに関する解説は特にしていませんので、参考書籍をご覧下さい。 また、内容には充分注意していますが、あくまでも僕の勉強メモになっているため、間違いや勘違いがあるかと思います。その点、ご了承いただければ幸いです。同時に間違いや勘違いを発見された方は、メールや掲示板でご指摘いただけると、すごく嬉しいです。 【参考書籍】 紀平拓男、春日伸弥 『プログラミングの宝箱 アルゴリズムとデータ構造』（ソフトバンク パブリッシング 2003） 参考URL：http://www.cmagazine.jp/books/takarabako/
イケてないプログラム（使えない成果物）に見られる３つの共通点
クイックソートの話で書いたとおり、相変わらず Excel - VBA と格闘する日々が続いております・・・orz 「大企業にありがちな問題。委託開発の甘い罠・・・」でも書いたとおり、今まで外注して作ったソフトウェアってほぼ 100% の確率でイケていないものが完成してます。年末に納品されたソフトウェアのできも酷いの何のって・・・ さて、いままで見てきたイケてないプログラムのダメソースに共通して言えることが３点ありまして、 DRY ( Don’t Repeat Yourself ) でない。同じもしくは似たソースのコピペが至る所に散在する。 ロジックに無駄が多すぎ。行き当たりばったりで作った感、満点。 アルゴリズム知らなさすぎ。馬鹿ループ処理で時間かかりすぎ。 のいずれか、もしくは全部が当てはまります。大抵は全部ですね。こういったソースが納品されると、センス無いなぁ〜と思っちゃうわけ。こうい
Epeg で JPEG ファイルのサムネイルを高速に生成する - bkブログ
Epeg で JPEG ファイルのサムネイルを高速に生成する Epegは JPEG ファイルのサムネイル (縮小画像) を高速に生成するライブラリです。JPEG に特化した手法でサムネイルの処理を行うため、内部的に画像をビットマップに伸張せず、高速かつ少ないメモリで処理できるのが特徴です。 インストール Epeg は Debian パッケージになっていないようなので、ソース (ダウンロード) からインストールしました Epeg は内部的に libjpeg を使っているため、Debian GNU/Linux では sudo apt-get install libjpeg62-dev で事前にインストールしておく必要があります。 Epeg そのものは ./configure && make && sudo make install でビルド・インストールできます。 サンプルコード Epeg の
計算的な深さと脳
ニューロンが入力を受けてからスパイクを出すまでは早くとも数ミリ秒かかる。人間が反応するまでの時間は零点何秒かだから、入力と出力の間には最大に見積もっても数十段のニューロンが介在するだけである。（実際はもっと段数が低いだろう。） 一方コンピュータの方は現在のネズミ以下の判別能力しかないような画像認識をするにあたってさえ数千万サイクルの計算を行わなくてはならない。 だから、脳が物凄い並列計算をやっているに違い無い。ここまでは普通の話ね。 で、問題は「じゃ、物凄い並列な機械をつくったら脳の能力を再現できるのかよ」ということ。もちろん誰も答えをしらない。どんなアルゴリズムを使えば良いか分からないし。 人によっては絶望して「新しい物理法則を」とか「量子論的並列性」とか、「魂」とかに行っちゃう。 で、僕も答えは持って無いけど、この問題を考えるにあたって以下の「計算的大きさ」と「計算的深さ」の概念を
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
Life is beautiful: 恋の連立方程式、「パートナー探し」の最適化アルゴリズムに関する一考察
「自分にできるだけ相応（ふさわ）しいパートナー」を見つけることは、我々人間にとって、人生の最も重要なのテーマの一つでもある。しかし、そのプロセスである「恋愛」や「お見合い」に関して、なぜか今までシステマティックな考察がされて来なかったように思える。そこで、今回はその「パートナー探し」のプロセスをモデル化・数値化することにより、最適なアルゴリズムを見つけようと思う。 まずは、「自分にできるだけ相応しいパートナーを探す」というあいまいな問題を、もう少し明確にモデル化された問題に単純化する。もちろん、単純化するとはいえ、あまり現実とかけ離れていては役に立たないので、現実味を壊さない程度の単純化を行う。 ［モデル化された問題］ 結婚適齢期の女性が、これから１０人の男性と順番にお見合いをして、その中から結婚相手を見つけることにしたとする。相手の意思は無視して良く、「この人と結婚したい」と宣言した時点
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データマイニングを利用したプログラムの改善
kaz::hatena - 特別公演 - プロ棋士はどう考えているか
<h2>C言語によるアルゴリズム(コメント付き)</h2>