B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
ALENEX'15 論文採択：指数時間 Branch-and-Reduce アルゴリズムの実性能 - iwiwiの日記
国際学会 ALENEX 2015 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカの San Diego です． 今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで，研究室同期の岩田との共著です． 背景１：アルゴリズム研究における理論と実性能の乖離 アルゴリズムが好きな人はよ
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
