動的計画法解説 [TopCoder SRM 468 Div2 250/Div1 500]
動的計画法解説 [SRM 468 Div2 250/Div1 500] 目次 問題１（入門編） 全探索 再帰と漸化式 メモ化再帰 動的計画法 問題２（初級～中級編） 全探索 再帰と漸化式 動的計画法 問題１ 王様は長い間出張していたので、できるだけ早く女王のもとに帰りたいと思っています。王様は都市 0 におり、女王は都市 N (1 <= N <= 50)に居ます。全ての都市 i (0 <= i <= N - 1) に対して陸路と空路があります。配列 roadTime, flightTime が与えられ、それぞれの i 番目の要素は都市 i から都市 i + 1 までの陸路、空路の所要時間 (1 以上 1000 以下) を表わします。しかし王国の科学力は低く、空路による移動は墜落の危険を伴います。そのため、王女は王様に空路は K (0 <= K <= N) 回までに留めるように言いました。王
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
Information Retrievalの発表資料 by naoya
Name Last modified Size Description Parent Directory - iir_01.ppt 05-Feb-2008 19:22 274K iir_02_1.ppt 18-Feb-2008 10:42 66K iir_02_2.ppt 08-Mar-2008 16:23 361K iir_03_1.ppt 08-Mar-2008 16:23 508K iir_04.ppt 27-Apr-2008 10:18 1.2M iir_05.ppt 17-May-2008 22:34 707K iir_06.ppt 08-Jun-2008 23:34 799K iir_07.ppt 22-Jun-2008 23:13 627K iir_08.ppt 05-Jul-2008 23:04 863K iir_09.ppt 21-Jul-2008 2
プログラムの動かし方の本 - きしだのはてな
Seasarカンファレンスで、基礎としてプログラムの動かし方であげた本。と、それに加えて挙げれなかった本。 ちなみにSeasarカンファレンスでの内容はid:tanamonがまとめてくれてる。というか、手書きスライドの書き起こしをしてもらってます。 「手書きで書く→ソーシャルに清書してもらう」という、新しいプレゼン手法が生まれました！ 差のつく勉強法200のメモ - tanamonの日記 プレゼンや以前のエントリでは、プログラムというのは計算論と意味論に分かれると書いたけど、プログラム意味論という分野と混同してへんな議論になっちゃうので、「プログラムをどう動かすか」と「プログラムをどう書くか」に分かれるとします。命令的な側面と宣言的な側面だと言ってもいいかもしれない。今回は命令的な側面について。 まずは、基礎となる数学、離散数学について。 やさしく学べる離散数学 作者: 石村園子出版社/メ
Some more advanced GC techniques
After my last two posts about garbage collection, some people people suggested some more advanced techniques be used to solve the pausing problem. Here's a quick* overview of some more advanced techniques, some of which can eliminate noticeable pauses and some of which can solve other problems in GC. The train algorithm The idea of the train algorithm is to break the heap (or, really, just the old
Bitonic Sort
Consulting in High Performance Computing. Training in Concurrency, Networking, and Parallelism, especially in Python and Java. Bitonic Sort Abstract Continuing a tutorial on sorting algorithms, this page animates bitonic sort. Author Thomas W. Christopher Bitonic sort is a sorting algorithm designed specially for parallel machines. A sorted sequence is a monotonically non-decreasing (or non-increa
ソートについて
ソートについて はじめに n個の要素がある配列をソートする方法を挙げていく。 バブルソート バブルソートは最も簡単な方法です。 単純に隣同士を比較して順番が逆なら入れ替えるという操作を 一番目の要素から順番に行っていきます。 この操作をn回行うと、要素の中でもっとも大きな要素が一番n番目に来ます。 そして、また一番目の要素からn-1回操作を行います。 これで二番目に大きな要素がn-1番目に来ます これを繰り返してソートします。 サンプルコード //バブルソート void BubbleSort(int Data[], int n) { int BeginPlace, ComparePlace; //比較を始める位置を最初からn-1まで変えていく for(BeginPlace = 0;BeginPlace Data[ComparePlace])
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
Matzにっき(2007-12-03)
<< 2007/12/ 1 2 1. [教会] 子供を理解することの力 3 1. マシン不調 2. ConsistentHashing - コンシステント・ハッシュ法 3. The Chord/DHash Project - Overview 4. [Ruby] 市報松江12月号 5. [Ruby] 山陰中央新報 - 島根県の産業活性化戦略 住みたくなる環境も必要 6. 梅田望夫×まつもとゆきひろ対談「ウェブ時代をひらく新しい仕事，新しい生き方」(前編)：ITpro 4 1. 新ディスク 2. 梅田望夫×まつもとゆきひろ対談「ウェブ時代をひらく新しい仕事，新しい生き方」(後編)：ITpro 3. [言語] YouTube - Upcoming Changes to the JavaScript Language 5 1. [Ruby] 新潟 - Rubyビジネスセミナー 6 1. 取材 2
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
algorithm
奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の
生年月日から年齢を計算する簡単な計算式：ITpro
私の個人ブログに掲載したら好評でしたので、こちらでもご紹介してみます。 最近知ったんですが、生年月日から年齢を計算する簡単な計算式というのがあるそうです。 (今日の日付-誕生日)/10000の小数点以下切捨て。 PHPで書くと echo (int)((20070823 - 19850101)/10000); Perlで書くと print int ((20070823 - 19850101)/10000); JAVAで書くと System.out.println( (int)((20070823 - 19850101)/10000) ); という感じになります。 日本の法律を確認してみました。誕生日の前日が終了する瞬間（すなわち誕生日をむかえる午前0時00分の直前）に1歳を加えることになる。ただしうるう年など、年によって期間を定めた場合において最後の月に応当する日がないときは、その月の末日を
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱数について