B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
B-Tree - アルゴリズム・イントロダクション 18章 - ninjinkun's diary
アルゴリズム・イントロダクション勉強会，B-Treeの章を担当しましたので，資料を公開いたします． Algorithm Introduction #18 B-Tree View more presentations from ninjinkun. B-Treeはデータ容量が主記憶に収まらないような場合に有効なデータ構造で，MySQLなどのDBや，最新のファイルシステムのインデックスとして用いられています．（MySQLはインデックス管理の方式を選択可能） 主に以下の利点があります． ノードの大きさをページサイズに最適化できる ページの読み込みがディスクアクセスに最適化される ページの読み込み数を木の高さhに抑えられる ディスクへのアクセス回数を抑えることができる id:naoyaのブログも参考になります． B木 - naoyaのはてなダイアリー 当日の発表はテンパってしまい，アレな感じになっ
オーダーについて知っておくべき5つのこと - わさっきhb
研究室のゼミ発表で，「オーダーのことはよく分かっていませんが…」という前置きで計算量の見積もりをしているものを，昨年，今年と見かけました． この日記が役に立つか，余計な御世話になるか分かっていませんが，ここに整理を試みてみました． 1. ビッグ・オー記法 「アルゴリズムの計算量をオーダーで表してみなさい」と指示されたときのオーダーは， 注文，発注という意味でもなく， 順番*1，順序，秩序という意味でもなく， 「百万のオーダー」*2というような使い方でもなく， 数学の位数という意味でもなく， ビッグ・オー記法，あるいはwikipedia:ランダウの記号を用いて表すものを言います． 2. 一番次数の高いもの以外，それと係数は無視 ビッグ・オー記法では，基本的に，一つの文字に関するできるだけ簡単な数式に，「O( )」をかぶせます．このとき， 複数の項の足し算なら，次数の最も高いものだけを残し，他
Sorting Algorithms Demo
This page is based upon http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html. Modified by Guido Bunsen. Sorting Algorithms We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorthms while sorting an array of dat
Sorting Algorithms Demo
We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms. This means that the algorithms do not allocate additional storage to hold temporary results: they so
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
シェルソート
シェルソートのアルゴリズム シェルソートは挿入ソートの原理を応用した比較的簡単なソートアルゴリズムである． 挿入ソートの内側ループでは添え字を1ずつ動かしながら順番に比較していったが，動かす幅を可変したものがシェルソートである． シェルソートでは，添え字の動かす幅を1より大きくしたものを前処理として何回か行い，最後に挿入ソートを行う． シェルソートのアルゴリズム 以下のアルゴリズムでは，添え字を動かす幅 h の計算式 h = m * h + n で，m = 2，n = 1 としたものである． この場合， h = 1，3，7，15，31，63，127，255，... となる． h の系列をそれぞれの数が素になるように選ぶと効果が大きい． void sort() { // シェルソート(昇順) int j, h, work; h = 1; while (h // 配列の長さ以上で最
クイックソート
ソートアルゴリズムの最後を飾るのは、やはりクリックソートです。 クイックソートは、データの比較と交換回数が非常に少ないのが特徴で、一般的なばらばらデータ（ランダムに散らばっているデータ）に対して、最も効率良く並べ替えを実行します。 クイックソートは、実用上もっとも高速であるとされている並べ替えアルゴリズムで、多くのプログラムで利用されています。 ばらばらなデータが格納された配列 a[ ] が与えられた場合に、それらをクイックソートで並べ替える手順を、下の図に示します。 まず始めに、「軸要素」と呼ばれるデータ値を決定します。この値は、データ全体を2つに分割するときのしきい値として使われます。軸要素は、分割が均等に行われるように選ぶのが望ましいのですが、その選択に時間をかけると、かえって並べ替えの時間を大きくしてしまいます。一般には、次のような方法がよく用いられているようです。 データの先頭の
ソート ‐ 通信用語の基礎知識
非常に多数のアルゴリズムが考案されている。 現在使われているソートプログラムはそのほとんどがクイックソートをベースに作られており、その計算量はO(n log n)である。
ブロックアルゴリズムとB-Treeアルゴリズム
ext2とext3は、「ブロックアルゴリズム」を採用している。ブロックアルゴリズムとは、例えばディスクを4Kbytesなどの単位（ブロック）に分けて管理する方法である。ext2にジャーナリング機能を追加したものがext3である。ext2、ext3以外のファイルシステムで用いられているB-Treeとそのバリエーションは、バランス木（Balanced Tree）をベースとしたアルゴリズムである。 拡張機能としては、今回紹介する「動的iノード」と「エクステント」方式が挙げられる。「エクステント」は、ブロックアドレスの代わりに「論理セット」と呼ばれる「開始アドレス」「サイズ」「オフセット」を渡すことでアドレッシングを効率化する方式である。「動的iノード」はiノードを動的に付与する方法で、これまで存在していたiノード数の制約を解決するものとして期待されている。ReiserFSやJFS、XFSはこれら
いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
ソート処理時間、選ぶアルゴリズムでこんな差が！ ― ＠IT自分戦略研究所
ソート処理時間、選ぶアルゴリズムでこんな差が！：いまから始めるアルゴリズム（2）（1/2 ページ） 連載第1回「『＋1』だけで四則演算をするには？」に引き続き、プログラミングにおけるアルゴリズムの重要性と面白さを紹介したいと思います。例としてプログラミングで頻繁に使われる並べ替えと検索のアルゴリズムを取り上げ、それぞれがどういった処理を行っているのか考えてみましょう。 同じ問題でも解き方（アルゴリズム）によってかなりの速度の違いが出てくる可能性があることは、前回紹介したとおりです。今回は代表的な並べ替えのアルゴリズムを基にプログラムを作成し、実行にかかった時間を測定して、具体的な処理速度の違いをお見せしようと試みています。 プログラミング言語では、すでに並べ替えの仕組みが用意されていることが多いので、このアルゴリズムをあまり意識していない人もいるのではないでしょうか。しかし、すべてのプログ
B木 (B-tree)
□ 多レベル索引の一種 挿入や削除のタイミングで動的な再編成が効率良く可能． レベル数は層レコード数 に対して ですむ． □ B-tree よりも後述の B-tree の方が良く使われるが，原理の 理解は B-tree の方が理解しやすいので，先に説明する． 以下ではキー値に重複がないものと仮定する． 定義 8 (B木 (B-tree)) が正整数であるとする．次の B木 (a B-tree of degree ) の 各ノードは次のような情報を持つページで，以下に述べる条件を満たすものである (図 6.5, p112 参照．): はroot ノード以外では である． root ノードでは である． レコード のキー値を で表すとすると， である． レコードは最大で 個まで持てる． はページへのポインタである． (つまり部分木へのポインタである．) 中に現れる全てのレコード
ブロックアルゴリズムとB-Treeアルゴリズム
ファイルサーチを高速化するB-Treeアルゴリズム ext2、ext3がベースとするブロックアルゴリズムは、ブロック数が対応するディスクのジオメトリ数に制限されること、ファイルサーチにO（n）かかる（注）こと、ファイルサイズに関係するパフォーマンス低下など、いくつかの問題があった。 注：「O（n）」とは、実行時間が入力の大きさ「n」に比例するアルゴリズムである。O（n）は「nのオーダー」または「オーダーn」と読む。後述する「O（log n）」は、アルゴリズムの計算量に関する議論の場合logの底は常に2で、O（log n）の方がO（n）よりも効率が良い。例えばn＝8の場合、O（log n）は入力8に対して3回の実行で済むが、O（n）は8回の実行となる。 ReiserFS、JFS、XFSといったファイルシステムでは、こうしたブロックアルゴリズムの限界に対して、早い段階からデータベースの技術をフ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
cmagazine.jp | Just another WordPress site
時間計算量 とは 【time complexity】 - 意味・解説 ： IT用語辞典
漸近計算量理論
Security Akademeia【セキュリティアカデメイア】