You can read this blog in any language using google translate as follows:

Goto http://translate.google.com/
Paste URL in the box and select "Japanese for From Language" and "To Language". Then click "Translate".

English translated pages are here:
http://bit.ly/xPuXoy

你可以閱讀這個博客,在任何使用“Google”的語言翻譯

本ブログのアクセス統計: 50万アクセスを達成しました。ご訪問ありがとうございました。

50万アクセスまでの経過

2009年12月に始めた本blog。2011年7月ごろに10万アクセスを達成し、2011年12月13日には15万アクセスを達成。
その後、私も更新しておらず、アクセスは少し減りましたが、3月1日には18万アクセス。2012/4/18に20万アクセス、2012/8/21に25万アクセス、2013/1/18に30万アクセス、2013/12/17に40万アクセスを達成しました。しばらく見ていなかったら、2015/5/1に50万2584アクセスになっていました。

2012年11月24日土曜日

アルゴリズムのお勉強

最近、C++でプログラムをしており、特に習ったことが無かったアルゴリズムだが、しっかり理解しておいたほうが良いと思い勉強し始めた。メモとしてまとめる。勉強が進んだら、おいおい追記していく。

勉強すべきもの)

  1. Data Structures: Linked list, BTree B+Tree
  2. Sort
  3. Search
  4. Graph Algorithm
  5. Weighted Graph Algorithm: Spanning Trees, Shortest Pathes
  6. Combinational Search and Heuristic Methods
  7. Dynamic Programming
  8. C++のライブラリ: STL, Boostに実装されたアルゴリズム
教材)
 The Algorithm Design Manual" by Skiena
やら、webやら。

wikiなどにあるもの) 
BTree) http://bit.ly/Tkne1I  : treeをたどれば高速検索が可能。treeの深さがバランスするよう生成する、エレガントなアルゴリズムがある。このためbalanced treeと言う意味でb treeと呼ばれる。data baseなどにも使われる。オーダ m とは、枝がm/2〜m あるものを指す。nodeの追加は分かりやすいが、nodeの削除は分かりにくく。英語サイトの図 http://en.wikipedia.org/wiki/B-tree をみると分かる。

B+Tree) http://bit.ly/TkniyA これは、アクセスが集中しがちな根を見なくても、leafのアクセスだけで、検索ができるようになっているもの。つまり、Btreeのleaf以外にあるデータをleafにも重複させて持たせている。

Sort)  http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/ が分かりやすい。quickソートが速いと思われているが、実は、入っているものが特定ケタの数値であれば、基数ソート(Radix sort)の法が速いこともある。複数ケタのRadix sortのやり方は大変エレガントである。また、そうでない場合でも、quick sortの軸要素(pivot)の選択が悪くtreeが非対称に分割されると、計算量が増えるので、マージソートの法が効率が良くなる。したがって、効率の悪いバブルソートは除外するとしても、様々なやり方を覚えておいたほうが良さそうである。
blog comments powered by Disqus