アルゴリズム - 合コンの効用を最大化する : 404 Blog Not Found
2008年03月16日19:00 カテゴリアルゴリズム百選 アルゴリズム - 合コンの効用を最大化する 実は、1対1という制約を課せば、全体として最も満足が行く縁結びを決定するアルゴリズムがすでに存在する。 金融日記:東京 - ニューヨーク - ロンドン - パリ 世界の先進国の恋愛シーンで今起こっていること これから紹介する計量経済学モデルは、あらゆる社会科学の理論の中でも最もエレガントでそしてシンプルなもののひとつだと思います。 C言語による最新アルゴリズム事典 奥村晴彦 C言語による最新アルゴリズム事典 P. 4 安定な結婚の問題 stable mariage problem N人の男性とN人の女性が集団見合いをし、おのおのの異性を好みの順に順位付けした。この順位表をもとにして安定な縁結びの仕方を決めるのがこの問題である。仮に男性M1と女性F1が結婚したが、じつはM1はF1よりF2を
アルゴリズム百選 - ユークリッドの互除法 : 404 Blog Not Found
2007年12月11日16:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - ユークリッドの互除法 今回は、ユークリッドの互除法を取り上げます。 ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。 それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、 mをnで割り、余りがrだとする 余りrが0なら、nがGCD。 そうでなければ、nとrのGCDを求める 互い違いに割っていくので、互除法というわけです。 function gcd(m, n){ if (m < n) return gcd(
アルゴリズム百選 - 迷ったらbenchmark : 404 Blog Not Found
2007年12月09日03:30 カテゴリアルゴリズム百選 アルゴリズム百選 - 迷ったらbenchmark この話題、以下の答えとしても適度なのでそのまま。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org 「O()が小さいからといって速いとは限らない」が抜けている。ベキ乗アルゴリズム再考 ベキ乗のやり方として、すぐに思いつくのは以下の方法です。 function power(b, n){ var result = 1; while(n--) result *= b; // b を n 回掛け算 return result; } これがO(n)であることは、直感的にわかります。 ところが、これをO(log n)でやる方法も比較的すぐに思いつきます。 例えばbを21乗したいとします。21=16+4+1なので、b21はb(16 + 4 + 1)とも書
アルゴリズム百選 - 値と参照 : 404 Blog Not Found
2007年12月06日15:30 カテゴリアルゴリズム百選 アルゴリズム百選 - 値と参照 今回は値と参照について取り上げます。 突然ですが問題です。以下のJavaScriptプログラムを実行すると、何と表示されるでしょうか? プログラム: var a = [0, 1, 2, 3]; var b = a; b[0] = 'zero'; p(a); 出力: エラー: 答えは、"zero, 1, 2, 3"です。しかし、なぜaを直接変更していないのにaの中身が変わっているのでしょうか? ここで、二行目に注目してみます。ここでは変数bに変数aを代入しています。変数aは配列です。ここだけ見ると、内部で起こっているのは以下のようなことに見えなくもありません。 array b -+ array b -+ | 0 | | 0 | | 1 | = | 1 | | 2 | | 2 | | 3 | | 3 |
アルゴリズム百選 - 用語の定義、またはその欠如 : 404 Blog Not Found
2007年12月05日03:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - 用語の定義、またはその欠如 いい機会なのでお断りしておくと、 O(1)というのはご機嫌に速いということ？ by Inquisitor たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう それが「ふつう」だという人向けの本にするつもりはありません。 本書はなるべく正確な知識を提供することを目指しますが、その正確さのためにページ数が倍になるのであればそれを恐れずに割愛するつもりでもあります。脚注や参考文献など、「より正確な知識のため」のポインターはその場合なるべく明示するつもりではありますが。 厳密に言えば、こういう言い方は許されないはずです。精度に限りが
アルゴリズム百選 - ベキ乗はO(1)でOK? : 404 Blog Not Found
2007年12月04日23:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - ベキ乗はO(1)でOK? これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？まずは、論より証拠、というわけで実測値をご覧下さい。Cでフィボナッチ数をO(n)アルゴリズムと公式を使ってそれぞれ100万回計算した時にかかった時間をプロットしたものです。最適化をかけていないものと-O3で最適化をかけたものと双方を計測しています。fib(73)まで計算したのは、doubleで整数で保っておける限界がそこまでだったので。ソースは本
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明する
2007年12月03日11:15 カテゴリアルゴリズム百選 アルゴリズム百選 - ハッシュを再発明する (実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。 現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。 しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。 誰でも
404 Blog Not Found:アルゴリズム百選 - 配列を再発明する
2007年12月03日04:00 カテゴリアルゴリズム百選 アルゴリズム百選 - 配列を再発明する アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。 ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。 残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。 function MyArray(){ this.size = argum
404 Blog Not Found:私ごときがアルゴリズム本を書くことにした訳
2007年12月02日04:00 カテゴリアルゴリズム百選 私ごときがアルゴリズム本を書くことにした訳 アルゴリズムを評価するのは、プロにとっても難しい。 アルゴリズム - 186::Diary * あとメモ化のときの最初の呼び出し回数の評価も間違ってるよね. 1回目は関数をナイーブな実装で評価するから. ところが、この下りに関して間違いなのは私の元発言ではなく、この突っ込みの方なのである。 そのことは、以下を見れば一目瞭然である。 ナイーブ プログラム: var c = 0; function fib(n){ c++; if (n <= 2) return 1; return fib(n-1) + fib(n-2); } (function(n){ p('fib('+n+') = ' + fib(n) + ', count = ' + c) })(25) 出力: エラー: メモ化 プログ
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
