algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
Elsevier · Herlihy, Shavit: The Art of Multiprocessor Programming · Welcome
Discover Books & Journals by subjectLife sciencesAgricultural & Biological SciencesDrug DiscoveryImmunologyLife SciencesMicrobiology & VirologyNeurosciencePharmaceutical SciencesPharmacologyToxicologyPhysical sciences & EngineeringAstronomy, Astrophysics, Space ScienceBuilt EnvironmentChemical EngineeringChemistryComputer ScienceEarth & Planetary SciencesEnergy & PowerEngineering & TechnologyEnvir
Designing algorithms for Map Reduce
Since the emerging of Hadoop implementation, I have been trying to morph existing algorithms from various areas into the map/reduce model. The result is pretty encouraging and I've found Map/Reduce is applicable in a wide spectrum of application scenarios. So I want to write down my findings but then found the scope is too broad and also I haven't spent enough time to explore different problem dom
Sorting algorithms: quite boring until you add sound effects - Geek.com
This site may earn affiliate commissions from the links on this page. Terms of use. Anyone who has ever done a programming course or tried to learn to code out of a book will have come across sorting algorithms. Bubble, heap, merge, there’s a long list of these methods of sorting data. The subject matter is fairly dry. Thankfully someone has found a way to not only make sorting more interesting, b
PMVS2
PMVS is a multi-view stereo software that takes a set of images and camera parameters, then reconstructs 3D structure of an object or a scene visible in the images. Only rigid structure is reconstructed, in other words, the software automatically ignores non-rigid objects such as pedestrians in front of a building. The software outputs a set of oriented points instead of a polygonal (or a mesh) mo
Sparse Bundle Adjustment in C/C++
sba : A Generic Sparse Bundle Adjustment C/C++ Package Based on the Levenberg-Marquardt Algorithm If you reached this page while looking for a general-purpose Levenberg-Marquardt C/C++ implementation, please have a look at sparseLM and levmar, which are respectively aimed at problems with sparse and dense Jacobians. Introduction This site concerns sba, a C/C++ package for generic sparse bundle adj
第1回 検索エンジンとは | gihyo.jp
はじめに 検索エンジンと聞くと、みなさんは何を思い浮かべるでしょうか？ GoogleやYahoo!などの検索ページを思い浮かべる方がほとんどだと思います。近年は、それら企業の努力によって検索エンジンというものが非常に身近になり、私たちの生活に欠かせないものとなりつつあります。 しかし、検索エンジンと一言で言っても、上記のような一般の方々へのUI（ユーザインターフェース）を指す場合もあれば、そのUIの裏側（バックエンド）にあるシステムを指す場合もあります。 本連載では、Google,Yahoo!などを代表とする検索エンジンの裏側のしくみに着目し、検索エンジンというシステムのアーキテクチャやその内部で使われているデータ構造やアルゴリズムを、近年の手法や研究事例などを交えて解説していきたいと思っています。 検索エンジンとは 検索エンジンには、さまざまな種類があります。GoogleのWeb検索のよ
JavaでTrieデータ構造を実装する
WEB+DB PRESS vol.42の特集「アルゴリズム＆データ構造」でもとりあげられていたTrie(とらい; p34-37)について調べてみたので、忘れないようにメモです。 Trie(s)というのは単語を辞書のなかから見つけ出すときに人がふつうに行っている探し方のアルゴリズムです。例えば、poolならまず、pのところに行って、次にoのところに行って、、、つまり、p -> o -> o -> lと探していきます。続いてprizeを見つけるとしたら、p -> r -> i -> z -> eですが、先頭の文字が同じpなので、pの付近からはずれたところから始めたりはしません。この二つの単語の場合pをprefixと見なすのがTrieです。poolとpoleだったらprefixはpoにのびていきます。prefixがのびていけばいくほど候補は減っていきます。ちょうどIDEのメソッド補完機能のように
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
アルゴリズムとデータ構造演習
本演習の目的は、プログラミング言語C及びSchemeの基礎を習得し、 それらの言語を通じて、講義「アルゴリズムとデータ構造」の理解を深めることにあります。 重要なお知らせ 特に重要な連絡事項はここに掲載されます。 課題について 課題には、A課題とB課題があります。（課題番号の末尾が種類を表します。） B課題が基礎的な課題で、A課題が発展的な課題となっています。 B課題を全問解くことが、単位取得の目安です。 C入門第1回（10月10日） C入門第2回（10月17日） C入門第3回（10月24日） C入門第4回（10月31日） C第1回（11月7日） C第2回（11月14日） C第3回（11月21日） C第4回（11月28日） C第5回（12月5日） Scheme第1回（12月12日） Scheme第2回（12月19日） Scheme第3回（1月9日） Scheme第4回（1月16日） C補講
SubversionのDiffをC++に移植
何ですかこれは？ 二つのシーケンスのLongest Common Subsequence, Longest Common Subsequence Distance及びShortest Edit Scriptを求めるクラス。 Subversionのコードを、C++に移植したものです。 アルゴリズムは、"An O(NP) Sequence Comparison Algorithm" (Sun Wu et al.)に述べられているものと同一で、計算量は最悪でO(NP)、平均的にはO(N+PD)です。ただし、N=二つのシーケンスの長さの和、P=D/2-Δ/2、D=LCS距離、Δ=二つのシーケンスの長さの差です。 ここでいうLCS距離(longest common subsequence distance)は、あるシーケンスを別のシーケンスに変化させるために必要な、シンボルの挿入及び削除操作の最小
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Index of /~juliano/csci311/Code/Nutshell/ADK/Deployment
Musical quick sort (guitar)
パラメトロン計算機
GitHub - ben-manes/concurrentlinkedhashmap: A ConcurrentLinkedHashMap for Java
データ構造とアルゴリズム - 自習用デモプログラムおよびソースコード集 (Java)
http://hiratch.net/blog/archives/2007/02/000154.html
Algorithms Book