yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
10兆までの素数のリストを作ってみませんか？
もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 記者がこんなことをいうのは、自分で10兆までの素数のリストを作ってみて、とても面白かったからだ。図1のプログラムを書いて出力が成功するまで約2週間、夢いっぱいの楽しいひとときを過ごせた。予期せぬ問題も発生したけれど、最後にはコンピュータがまだまだ発展する可能性を持つと感じられた。素数のリストを作る演習は、プログラミングと情報システムにおける有益な演習の一つである。 アルゴリズムの有効性が納得できる この演習の面白い点は、まずアルゴリズムの有効性を納得できる点だ。素数（prime）は
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
情報処理学会が日本将棋連盟に「コンピュータ将棋」で挑戦状 - 情報処理学会
社団法人情報処理学会（会長：白鳥則郎）は、コンピュータ将棋でトッププロ棋士との公開対局を望むべく、社団法人日本将棋連盟に対し挑戦状を送りました。 対戦は今秋から順次実施予定であり、具体的な日時・対戦場所は決定次第広報いたします。 ●本件に関するFAQ 挑戦状 社団法人 日本将棋連盟 会長 米長 邦雄 殿 コンピュータ将棋を作り始めてから 苦節三十五年 修行に継ぐ修行 研鑚に継ぐ研鑚を行い 漸くにして名人に伍する力ありと 情報処理学会が認める迄に強い コンピューター将棋を完成致しました 茲に社団法人 日本将棋連盟殿に 挑戦するものであります 平成ニ十ニ年四月二日 社団法人 情報処理学会 会 長 白鳥 則郎 社団法人 情報処理学会 会長 白鳥 則郎 殿 挑戦状確かに承りました いい度胸をしていると その不遜な態度に感服仕った次第 女流棋士会も誕生して三十五年 奇しくも同年であります 今回は初
「ガベージコレクションのアルゴリズムと実装」を読んだ - higepon blog
著者のから id:authorNariさんから「ガベージコレクションのアルゴリズムと実装」 献本いただきました。ありがとうございます。 竹内先生の前書きでも触れられていたが、日本語の GC の資料は今まで本当に少なかった。 2006 年に未踏で Scheme シェルを書いたときに、Mark & Sweep GC を実装したのだが資料集めに苦労したのをよく覚えている。Wikipedia にまとまっている程度のものなら見つかるのだが一歩踏み込むと英語でしか資料が見つからないという状況だった。(そのときにまとめた資料。) しかしついに本書の登場でその状況も打破された。 これだけ踏み込んだ内容であれば自前で GC を実装しようとする人にも十分だ。適切な GC 手法を選び、アルゴリズムを理解し実装するところまでいけるだろう。不足があれば補足資料として論文などをあたれば良い。 本書にはアルゴリズム編と
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
大規模ソーシャルサーチエンジンの構造 - file-glob こと k.daibaの日記
はじめに Googleのように，どのドキュメントが適切なのかを選ぶのではなく，質問を誰にするのが適切かを選ぶ検索エンジンをAardvarkという会社が作り，その構造を論文で公開しました．この会社はもともとGoogleの社員だった人達が作った物で，最近Googleが買い上げました．今日はその論文の要旨をまとめてみました． タイトルと著者 タイトルはGoogle創始者のLarry PageさんとSergey Brinさんが1988年に発表した"Anatomy of a Large-Scale Hypertextual Search Engine"と韻を踏んでいます．論文を発表したのは，Aardvark社のDamon HorowitzさんとStanford Univ.のSepandar D. Kamvarさんです．以下小見出しが章，少々見出しが節という形式で進めます． ABSTRACT Aard
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
「ガベージコレクションのアルゴリズムと実装」という本を書きました。
gcbook, gcai, GCGCLoverのみなさん、お待たせしました。「ガベージコレクションのアルゴリズムと実装」の情報公開です。 書名：ガベージコレクションのアルゴリズムと実装 著者：中村 成洋／相川 光 監修：竹内 郁雄 ページ数：472ページ 本体価格：3,200円 発売開始日：2010年3月17日（水） ※地域・書店によって遅れることがあります ISBN：978-4-7980-2562-9 C3055 読み所 本書は次の2つのテーマを扱います。 1.GCのアルゴリズム（アルゴリズム編） 2.GCの実装（実装編） アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中 から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや 高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特 性などを理解していただくのがアルゴリズム編の最大
Confidence Weighted Linear Classificationを読んだ - 射撃しつつ前転 改
ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類
天頂の囲碁 - ヨダログ
北海道岩見沢市の実家に帰った時の話だが、 級位者の母の相手のためにと、 父が、強いと評判の囲碁ソフト「天頂の囲碁」を購入していた。 母はコンピューター相手でも負けたら頭に来るらしい。 岩見沢で７段で打っている父も4子置かせて負けたらしい。 ということは、「天頂の囲碁」は岩見沢の3段はあるということになる。 僕は興味を持ったので「天頂の囲碁」に9子置かせて打ってみた。 9子でコンピューターに負けるとは想像出来なかったが、驚いたことに二連敗した。 しかしこの2局でこのソフトの間合いをつかんだ。 要するにこのソフトが、 何がわかって何がわかっていないのか、ということが何となくわかったのである。 ３局目は僕の圧勝であった。 9子置かれたら最初の数局は一流プロでも負けるかもしれないが、 間合いをつかんだら負けることはないと思った。 しかし、不思議なのは、このソフトは詰碁が出来なさすぎるのである。 お
ランキングアルゴリズムにおける「ページ読み込み速度」の位置づけ ::SEM R (#SEMR)
ランキングアルゴリズムにおける「ページ読み込み速度」の位置づけ 2009年11月にGoogleがPageRankの要素の1つとしてページ読み込み速度について言及したが、それはランキングアルゴリズム全体においてどの程度重要なのだろうか。 公開日時：2010年02月05日 04:45 先日の講演やインタビューで、Googleがランキングアルゴリズムの1つとしてスピード要素を取り入れることについて触れられた時、「そりゃ同一のページが2つあれば速いほうがいいでしょ、その程度の話」という回答をしていたのだが、ちょうどGoogleのMatt Cutts氏がビデオにてその旨の説明をしていたので紹介しておくとともに、追加解説をする。 PageRankでスピードを加味する、という話が出た時点で、Googleはどの程度それをランキングに反映させるかについて言及をしていないにもかかわらず、あたかもそれがレリバン
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
Flow Analysis & Time-based Bloom Filters - igvita.com
By Ilya Grigorik on January 06, 2010 Working with large streams of data is becoming increasingly widespread, be it for log, user behavior, or raw firehose analysis of user generated content. There is some very interesting academic literature on this type of data crunching, although much of it is focused on query or network packet analysis and is often not directly applicable to the type of data we
The Comonad.Reader » Linear Bloom Filters
This post is a bit of a departure from my recent norm. It contains no category theory whatsoever. None. I promise. Now that I've bored away the math folks, I'll point out that this also isn't a guide to better horticulture. Great, there goes the rest of you. Instead, I want to talk about Bloom filters, Bloom joins for distributed databases and some novel extensions to them that let you trade in re
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
NYから東京まで何マイル？Google検索で都市間の直線距離を表示 ｜ SEOモード
Google+にて、Google検索で「how far is it from A to B」で検索するとAとBの都市間の直線距離を表示できるようになったとの投稿がありました。 実際にやってみたところ、こんな風に表示されました。 こちらは「NYと東京の距離」。 これまでも下図のように移動距離は表示していましたが、（私が調べた限りでは）交通手段があって、アクセス可能な場合に限られていたようです。 いずれにしても、この直線距離の表示はまだ日本語環境では導入されておらず、英語環境でも「How far is it from London to New Delhi（ロンドンとニューデリーの距離）」では表示できなかったので、一先ずは限定的な提供のようですね。 ※こちらの記事は最初別のタイトルで公開されましたが、私の勘違いが含まれていたので、書き直して再投稿いたしました。 最初の記事を読まれた方にはご迷惑
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer ::SEM R (#SEMR)
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer グーグル・マリッサ・メイヤーのインタビュー記事。1日2回と小さな改良をランキングアルゴリズムに加えていき、検索をユーザにとってより便利なものにしていく。 公開日時：2009年11月12日 13:27 米Google VP・Marissa Mayer氏のインタビュー記事。ユーザがわかる範囲で週あたり2～5の変更を加えているほか、ランキングアルゴリズムも1日2回ほどの割合で変更を加えていると答えている。日々小さな改良を加えて、検索をより便利なものにしている。 また、2007年5月から始まったユニバーサル検索は現在、全検索クエリの25%で表示されているとも説明。 We have two, three, five changes every week that are visible to the e
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「俺の邪悪なメモ」跡地
liris.org
