いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
でっかい数を作るソルバー - xhlメモ @ hatena
ネタバレ注意。 問題解説 全ての元凶 http://twitter.com/s01/status/21375206236 ネタバレ含む解説 http://d.hatena.ne.jp/sylph01/20100817/1282028426 http://d.hatena.ne.jp/sylph01/20100818/1282120209 xhl's ソルバー ソースは末尾に載せておきます。 $ g++ -O3 solver.cpp $ ./a.out 1000000 とかすると、確か 3063060 が出てきた気がします。 http://twitter.com/xhl/status/21426888852 注意: 必要環境: 64bit環境、メモリ40GBくらい。実行時間30分くらい。ゆっくりAmazon EC2でも使っていってね!!! $ g++ -O3 solver.cpp $ ./a
はてなブログ | 無料ブログを作成しよう
鉢植えを愛す 決して何も無かったわけではないのだが、何かあった、と記録するには余りにも目まぐるしい日々である。彼との同棲を解消しようと思い立ち、引っ越し屋を予約して、翌る日には、やっぱり辞めた。手元には、届いてしまったがために買い取らざるをえなくなった新品のダン…
Taberarelooのタグ補完について - 枕を欹てて聴く
Taberarelooは基本的にid:ConstellationによるTombloo experimental branch on Chromiumだと思ってもらって結構で, 面白いと思ったことを放り込みます. そのためbugがでて急遽修正というreleaseも多いのですが... また一方で tomblooと違うというところは大抵bugであるとみなしてもらって結構です. Twitter / Constellation: @you999 何かbugありましたかー? 基本的に ... と公言していたりするのですが(Chromeでは実現不可能とかいう部分以外に関して), Tomblooと意図的に差別化している部分があります. それがタグ補完部分です. 今回logicをもうちょっと変更しいろいろ面白くなったので記事にしました. 補完, 何やってるの? Taberarelooの補完はAbbrevia
fujimap: 簡潔な連想配列 - DO++
博論終わったので仕事の合間にfujimapというライブラリを作ってみました。 fujimap project fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。 今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています．Fujimapの特徴は必要な作業領域量が非常に小さいことです．キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive（後述）にのみ依存します。 例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワー
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記
ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
![[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/7ca3ca3d9a967967d3c1900062079765c7d58c98/height=288;version=1;width=512/https%3A%2F%2Fcdn.image.st-hatena.com%2Fimage%2Fscale%2F3b21b9940827376b8faf757c1dcc041507e62d8d%2Fbackend%3Dimagemagick%3Bversion%3D1%3Bwidth%3D1300%2Fhttps%253A%252F%252Fcdn-ak.f.st-hatena.com%252Fimages%252Ffotolife%252Ft%252Ftsubosaka%252F20091103%252F20091103000001.jpg)
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
『はてなブックマークリニューアル』
日記を相当長い間書いていませんでしたすいません・・・ 今日は、ちょっと時期をのがしてしまいましたが、はてなブックマークリニューアルについて書いてみようと思います。まずは、リニューアルおめでとうございます！＞はてなの皆様 今回のはてなブックマークリニューアルでは、弊社は、はてなブックマークのエントリ全文検索に携わりました。弊社の全文検索エンジンである、「Sedue」を用いて、複数台で全文検索機能を実現しています。リアルタイム性と大規模な検索が必要なタスクであったので、Sedueは今回のタスクにぴったりなエンジンでした。 エンジン自体は、もともと分散環境でいかに簡単に動作させるか、が売りのエンジンなので、すぐに稼働させることができました。ランキングの部分は、かなり力をいれていて、id:naoyaさんと弊社のCTO太田、エンジニアの久保田が協力して作成していきました。ランキングは、もうすでに汎用
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ChordアルゴリズムによるDHT入門
MIT OpenCourseWare OCW Home
カンガルーハウス：テキストライブラリ：2007年7月 A*（A-star：エースター）探索アルゴリズム