Linux KernelのLinked Listの実装が面白い件 - 愛と勇気と缶ビール
最近、Robert Love先生の本を暇な時にダラーと読んでいたりするわけですが、それの中にLinux Kernel内部で使われているLinked Listの実装が書いてあって面白かったので共有。 まず、Linked Listの一個一個のエントリを表すstructを定義します。 struct list_head { struct list_head *next, *prev; }; いやいやいやいや。いかにC力の低い僕でも流石にこれはあきません。騙されませんよ。前後のエントリへのポインタは確かにあるけれども、これにはデータを指すためのポインタがないじゃないの。おじいちゃんまたデータ忘れてきちゃったの？いやあねえ。 おじいちゃんは言った。「それはお前の短見というものじゃ。このLinked Listは以下のコードのようにデータ構造に埋め込んで使うものなんじゃよ。」そしてそれは正しかった。 st
基本情報技術者Web学習室(データ構造とアルゴリズム)
これは、「整数型」「実数型」「文字型」があります。その他として以下のものがあります。 ●論理型 論理演算に使用される変数の型で「True」と「False」の2値をとります。 ●列挙型 要素に順序をつけたものです。例えば、「CPU」「メモリ」「HDD」の場合 1番目：CPU 2番目：メモリ 3番目：HDD のように順序付けたものです。 一般的には、(CPU、メモリ、HDD)と表現します。 ●ポインタ型 「ポインタ」というのは、「データが格納されているメモリのアドレス」を格納します。通常、変数には、値が格納されていますが、それがメモリ上のどの番地(アドレス)かをポインタが格納することが出来ます。例えば変数「a」が100という値が格納されていて、アドレスが10番地の時、ポインタ型の変数には、「10」が格納されています。 ●構造型 「レコード型」とも言います。これは、「複
インメモリー・データベースの注意点
インメモリー・データベースの仕組み メモリーにデータを展開するインメモリー・データベースでは、基本的にディスク・アクセスは存在しません。十分なメモリーを確保することで、劇的なパフォーマンスを得ることができます。 また、従来のデータベースとは異なり、単にクエリーのキャッシュ用途や、インデックスの展開用にメモリーを利用しているわけではありません。 従来のディスクI/Oを使うデータベースは、B+ツリー索引でインデックスを付けています。ディスクI/Oを減らして、より多くのデータを取得できるように設計されています。これに対して、インメモリー・データベースは、インデックス構造をTツリー索引と呼ばれる方法に切り替えているものがあります。 Tツリー索引は、B+ツリー索引に比べて、消費するメモリーがより少なくなっています。具体的な例を挙げると、MySQLのオンメモリー・モードがB+ツリー索引を使っており、O
第5回 転置索引の実装 | gihyo.jp
はじめに 前回、前々回と転置索引の論理的構造について見てきました。今回は、転置索引の具体的なデータ構造や実装について説明していきます。 辞書の実装 辞書は通常、単語に対応した情報を高速に取得するために、ハッシュや木構造などのデータ構造を取ります。現在は, 安定した性能や単語の順序関係を利用したいなどの理由で、木構造のデータ構造が使われることが多いと思います。最も単純な場合、2分探索木（Binary Search Tree）や2分探索（Binary Search）の実装が考えられます。 2分探索（木）による辞書の実装 では、辞書の具体的なデータ構造について、図を交えて解説していきましょう。 前回も触れましたが、辞書には単語とその単語に対応するポスティングリストの位置情報のペア（のリスト）が格納されています。単語で検索をするので、ペア自体は単語をキーとして並び換えられます。 たとえば, 前回の
algorithm - 基数木 + 平衡二分探索木 = 三分探索木 : 404 Blog Not Found
2012年01月22日16:36 カテゴリアルゴリズム百選翻訳/紹介 algorithm - 基数木 + 平衡二分探索木 = 三分探索木 珠玉のプログラミング Jon Bentley /小林健一郎訳 最有力候補は、これかも。 Ternary search tree - Wikipedia, the free encyclopedia 三分探索木 - Wikipedia 404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
2分探索木
概要 一般に木構造というと、循環のない有向グラフのことなんですが、 そういう一般論はまた別の機会に話をしましょう。 ここでは、要素の挿入・削除・検索を高速に行うことの出来るコレクションのデータ構造として、 2分探索木（binary search tree）というものを紹介します。 2分探索木は、以下のような特徴を持つ木構造です（図1）。 2分木（各ノードは最大で2本の子を持つ）。 全ての要素が「左の子＜親≦右の子」（あるいは「左の子≦親＜右の子」）という大小関係を満たす。 2分探索木 要素の挿入・削除・検索は、 木の根から葉までの経路を1つ探索することになるので、 木の高さ分に比例する計算量が必要です。 理想的には、木のバランスが均等に整っていれば、 要素数を n として計算量は O(log n) になります。 しかしながら、逆に、 図2に示すように、木が左右どちらかに偏っている場合、 計
ハッシュテーブル
概要 ハッシュテーブル（hash table）は、 「ハッシュ値」という物を使うことによって、 要素の挿入・削除・検索を非常に高速に行うことの出来るコレクションです。 挿入する要素の数よりも、余裕を見て大きめのメモリを確保して置くならば、 要素の挿入・削除・検索をほぼ O(1) （要素数によらず一定時間）で行うことができます。 ハッシュ値 ハッシュ（hash）というのは、 文字列などの任意のデータから、そのデータを要約して得られる固定長の値のことです。 得られた値のことをハッシュ値（hash value）、 値を得る操作をハッシュ関数（hash function）といいます。 ネットワークなどを通してメッセージを送る際、 通信路でエラーが混入していないかどうかを確かめるために、 送信元と受信先の双方でハッシュ値を計算し、値を比較するのに使われたりします。 hash という言葉は、料理のハッ
List は Array にあらず : 404 Blog Not Found
2007年05月19日18:00 カテゴリLightweight Languages List は Array にあらず 無謀というより、もともと違うものを一緒にすることはないと思う。 Matzにっき(2007-05-07) こういうの(Lazy List)を将来のArrayクラスに突っ込みたいんだけど、無謀かなあ。 そう。もともとListとArrayは別物なのだから。 確かに、List(リスト)とArray(配列)には、Ordered Collection of Data -- 順番に並んだデーター --という共通点がある。この共通点があるが故に、特にLLにおいてはどちらも同じように扱われる場合が多いけれども、重要な違いが一つある。 Listが Sequentially Accessible なのに対し、 Array が Randomly Accessible だというのが、その違いだ。
デバッグより重要なもの : 404 Blog Not Found
2009年04月02日16:00 カテゴリCodeArt デバッグより重要なもの この話題、すっかり乗り遅れてしまった。 2009-03-22 - 未来のいつか/hyoshiokの日記 プログラミング入門書では、デバッグについて、ほとんど議論されていないし、仮にふれられていても、おざなりな方法というか、かなり邪険にあつかわれていたりする。プログラマの多くの時間がデバッグについやされていたとしてもだ。 あえていわせていただく。コードはデバッグできるだけはるかにましなのだ、と。printfを使うかどうかなんぞ、その問題と比べれば屁ですらないのだと。 デバッグよりもはるかに重要なもの、それはデータ構造の選定。 ここで一歩間違えると、バグが仕様化し、デバッグどころかバグにあわせてプログラムを書かねばならぬ羽目になる。 その最も顕著な例が、Unicodeだろう。最初の設計を間違えたおかげで、最新のソ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
二分木
サービス終了のお知らせ