プログラミングの作業に何の価値も見出せなくなってしまったd金魚による日記 このページをアンテナに追加 RSSフィード

 iTunes Music Store(Japan) なかのひと あわせて読みたいブログパーツ
|

0001 | 00 |
2004 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2008 | 01 | 02 | 03 | 05 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 |
2010 | 03 | 04 | 06 | 07 | 09 | 10 | 11 |
2011 | 01 | 02 | 10 |
2012 | 04 |
2013 | 01 | 05 | 06 | 07 | 08 | 10 |
2014 | 02 | 03 | 05 | 09 |
2015 | 04 |
2016 | 09 | 11 | 12 |
はてな一覧
アンテナに追加
私のアンテナ
私のダイアリー
私のアーカイブ
私のアイデア
私のブックマーク
私のグループ
私のキーワード
ニュース系、今まで続いているシリーズモノの読み物
dKingyo Utility Toolkit Projectのリリース情報
やっぱり暗号化は大人の味(笑)
プログラムのパッキング方法を調べよ
ココが厳しいよMinGW
ライブラリアン通信
ゲームプログラミングどうしよう
CRCについて
ビット演算練習
d金魚の今更Ajax
Windows Tips
VC6 Tips
Win32 WTL Tips
Ruby for C++ User
Ruby Tips
今日のRubyで嵌った事
正規表現PIECE
書きかけ
続く・・・

私のダイアリーの人気記事
新しくブックマークされた記事


あまり、役に立たなそうな個人的に調べた情報や妄想に耽った事、今 勉強している事ヒソヒソと公開していたりします。 | 登録してくれている方々 | d金魚にメール | 当サイトは640x480の画面解像度に対応しています。
日記へのリンク、アンリンクはフリーですが、selfタグのついている部分のコンテンツの引用はご遠慮願います。ご協力よろしくお願いします。


 | 

2005-02-16 デースケドガーな二分木

[][]二分木の要素の削除の仕方 二分木の要素の削除の仕方を含むブックマーク 二分木の要素の削除の仕方のブックマークコメント

二分木でキーを元にそれに対応する葉を探し出して削除するのは簡単だ。

しかし、葉へのポインタを元にO(1)で削除する方法が思いつかない。ナカナカ難しい。

私は考えていた。カクカクシカジカ、3日間くらいだった。出来ると思っていた。*1

だが、私の扱っている二分木の葉のデータ構造ではO(1)で削除する事は絶対に出来ないことに気が付いた。

ハッシュ法と同じく*2 バカな物思いにふけっていた・・・。

何故なら、親の葉へのポインタが葉の構造体に宣言していなかったのだ。

何故かメモリリークやAccess Violationがでる・・・*3と、思っていたら、親の葉を更新していなかったのが問題だった。

私は「C言語によるアルゴリズム辞典」*4に書いている二分木を参考に*5組んでいた。

これは、葉の右左の幹( left ポインタと right ポインタ )へのポインタを受け取って

それを元に、ポインタ先及び自分自身を更新しているプログラムなのだ。

なので、葉へのポインタのみではO(1)でそれ自身を削除する事は出来ない。

それを実現するには前述のように「親の葉へのポインタ」を宣言してやらなければならない。

例:


typedef struct dkc_2TreeNode{
  ///左ノード
  struct dkc_2TreeNode *left;
  ///右ノード
  struct dkc_2TreeNode *right;
  ///親ノード(これが足りなかった)
  struct dkc_2TreeNode *parent;
  
  //以下は御自由に・・・
  
  ///キーへのポインタ
  void *key;
  ///データへのポインタ
  void *data;
  ///データのサイズ
  size_t data_size;
}DKC_2TREE_NODE;


それに気づかず、3日間も悩んだ時間は何だ!!!ヽ(‘Д´)ノムキィ

またしても、○| ̄|__| ̄|○ {デースケドガー} である。

[][][][]デースケドガー専用 二分木。。。*6 デースケドガー専用 二分木。。。*6を含むブックマーク デースケドガー専用 二分木。。。*6のブックマークコメント

ちと、しっかりバグが取れたようなのでパフォーマンス計測。

ちなみに、C言語で汎用的な構造として組まれました。

Debug mode

ranking_tiemr / clock type : MilliSecondClock / compile mode : DEBUG

1 / all erase / 203.000000

2 / insert / loopnum = 0xFFFFFF / 52160.000000

Release mode

ranking_tiemr / clock type : MilliSecondClock / compile mode : RELEASE

1 / all erase / 137.000000

2 / insert / loopnum = 0xFFFFFF / 31041.000000

むぅ、速いのか遅いのか・・・

汎用的でないキーがint型の二分木のプログラム*7と比べて見た

ranking_tiemr / clock type : MilliSecondClock / compile mode : RELEASE

1 / all erase / 43.000000

2 / insert / loopnum = 0xFFFFFF / 9863.000000

insert部分のみ時間比較

orthodox9863
generic31041

より、

orthodoxの方が3.14721687113454倍速い!!!(って円周率か!!?

やっぱり、templateでC++というのが現状で一版パフォーマンスが良く、

かつ汎用的と言うことはこれにより結論を出してしまうことにしよう!!!

Mona OSがCやasmではなくC++にした理由がかなり分かった。

早速、二分木のプログラムアーカイブをを・・・

http://www33.tok2.com/home/dca/dkutil.html

・・・dkutil_c_tree_compareの所に置いておきました。

2treeフォルダ内です。


2tree.cppのコンパイルには多分、dkutilの最新版のリリースか、それ以降が必要です。ヽ(^^;)*8

ついでに、ESPELION for Win32のアーカイブをexe自己解凍形式のも追加しました。

[][]20051216現在私が知り得る最速の二分木 20051216現在私が知り得る最速の二分木を含むブックマーク 20051216現在私が知り得る最速の二分木のブックマークコメント

http://d.hatena.ne.jp/studiokingyo/20041213#p1

にて、

私の知る限り、パフォーマンスが良いと言われているのが?

Red Black TreeとAVL Treeの二つだ。

(実際速度的にどうなのかは良く分からない。ただ、聞いただけ。B-Treeとかはどうなんでしょう?)

と、無責任な事を書いていたが、とある書籍だか、記事だかにはB木が平均的にパフォーマンスが良いのではないかとの事が・・・。

しかし、他にもB木を元にした別のアルゴリズムもありそうですし、N分木とかもパフォーマンスを計測したこと無いので良く分からないですし・・・。

実際、自分でプログラムして計測していないのでなんとも言えないのですが・・・*9

http://memorandumhcr.g.hatena.ne.jp/hcr/20041221

未確認な情報引用されちゃいましたね^^;(/ω\)ハズカシーィ スミマセンデス m(_ _)m

*1:何故なら、STLでのstd::mapのeraseにはerase(iterator)メンバ関数が存在したからだ。しかし、今になって考えてみると、Red Black treeで実装されているのだから、親の葉を参照していなければ実装できないのでこれはこれで当たり前のような気もする。

*2http://d.hatena.ne.jp/studiokingyo/20050208

*3:ちなみに、こう言う時に 即 原因がわからないときは机上デバッグ(または騎乗位でバック)を行うと速くバグが見つかる。事実、私も机上デバッグバグに気づいた。

*4http://studiokingyo.fc2web.com/dxlib/shiryou/book.html

*5:ちなみに、http://oku.edu.mie-u.ac.jp/~okumura/algo/archive/からダウンロードできるアーカイブ内にあるtree.cがそれ

*6:オーソドックスな二分木・・・

*7:キーの型がint型という所だけが違う

*8:でも、コンパイルできないかもしれません、むしろ、出来ません かもしれません。

*9:いずれ行いたいのですが・・・

トラックバック - http://d.hatena.ne.jp/studiokingyo/20050216
 | 
Program | Debug | dKingyo Utility Toolkit | library | D言語 | 御本とか | 備忘録 | テクニック | WayBack | 格言 | 英語 | 他力本願 | news | software |

デースケドガー