株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ
STLport のハッシュ・コンテナ 標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。 これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。 これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。 SGI(Silicon Graphics社)のSTL実装をベースに
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のはてなダイアリー 当日の発表はテンパってしまい，アレな感じになっ
いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
アルゴリズム講座/実践編/バックトラック
バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約90％はバックトラックを使っていると思います。 １．バックトラックの考え 人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は 広範です。もちろん不得意分野もあります。 複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」 というように仮定から仮定へと強引に突き進みます。 そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング) 仮定を立て直して、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定 を立て直して同様に進行すれば、やがては解に到達することに
Data Structures – Unraveling the Complexity of Data Organization
In the pulsating world of football, every game is a story unfolding in real-time, and every score is a heartbeat.…
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
バイオ系雑誌に載った機械学習/計算機科学の解説記事 - Loud Minority
主に計算機科学の機械学習・データマイニング系の説明で、バイオの雑誌に載った解説記事です。ツールを使いこなす人が、中身を知りたかったり、作る人に変身したい場合や、情報科学(機械学習、データマイニング系）の人が、ゲノム解析などでどうやって利用されているのかを知るのに良いとおもう。追加する記事募集です。 決定木の解説 What are decision trees? Carl Kingsford & Steven L Salzberg Nature Biotechnology 26, 1011 - 1013 (2008) http://www.nature.com/nbt/journal/v26/n9/abs/nbt0908-1011.html EMアルゴリズムの解説 What is the expectation maximization algorithm? Chuong B Do & Se
アルゴリズムコンテストの挑み方 - d.y.d.
17:29 08/09/30 クロスワード 暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。 20:15 08/09/28 だいちのよろい そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。 もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。 まあそんなもんか。 本日は強風のため登るの禁止とのことだったので、周りから見るだけ。
ハフマン符号化法
ハフマン符号化法は文字だけで説明したので、この場で読むことが出来るようにいたします。 ファイル圧縮技術 －ハフマン符号化法の紹介－ LHAってソフト、知ってますよね。ファイル圧縮ソフトです。たとえばフロッピーディスク２枚分のデータを、フロッピーディスク１枚に納まるようにしてしまいます。 なぜそんなことができるのでしょうか。 LHA付属のドキュメント・ファイルを読んでみます。 吉崎 栄泰「ＬＨＡ取り扱い説明書」Ver.2.13 1991/07/20 NIFTY-Serve SDI00506 の 「0. はじめに」には >>アルゴリズムを動的ハフマン法から静的ハフマン法に変更したので、・・・・ という一文が書いてあります。 ハフマン法って何だろう。きっと、ものすごい数学的技術を使っているんだろうな・・・と思っていたときに、たまたま読んだのがＡ・Ｋ・デュードニー「チューリング・オムニバス 第１巻
転置インデックスで学ぶ検索エンジンの中身アプリ - シリコンの谷のゾンビ
学生の頃から情報検索っぽい研究をやっていたくせに，転置インデックスてこんなものなんだ，ということを知るまで検索エンジンが正直怖かった．転置インデックスの概要を理解したら急に甘く見はじめるようになった（それはそれでいかんのだけど）． 位置情報を持たせたり，転置インデックスの圧縮をした状態で説明されると急にアッーてなるけれど，一番単純な例を見るとすぐに理解できる． というわけで転置インデックスってこんな感じなんですよー．という一例を体験するプログラムをつくってみた．またJavaScript+TinySegmenter．工藤様毎度ありがとうございます． Text search indexing demo - 転置インデックスで学ぶ検索エンジンの中身アプリ これを見ると，転置インデックスって基本的にこういう構造でデータを持つのかということが納得できると思います．Termをkey，Posting l
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
http://www.ocw.kyoto-u.ac.jp/jp/engineering/course07/index.htm
What is Creativity?-Emergent Phenomena in Complex Adaptive Systems October 20(Mon)〜22(Wed) 2008 CO-OP Inn Kyoto Conference Hall ワークショップ参加ご希望の方はrequest-ocw@media.kyoto-u.ac.jpまでお名前（漢字とローマ字表記）、所属、役職、e-mail、懇親会の参加希望の有無をお書き添えの上お申し込みください。締め切りは10月10日になります。 →ワークショップ プログラムPDF →ワークショップ詳細HP OCW関連講義 全学共通科目 創造性とは何か？（村瀬雅俊准教授） 国際交流センター 日本語入門初級 日仏交流150周年・京都大学創立111周年国際フォーラム 国際フォーラム ビデオ→ 動画で見る京都大学 ・What is Li
ベイジアンフィルター Perlで作りたい人に教えてあげたいちょっとしたこと - プログラマでありたい
昨日のはてなのホットエントリーに『入門ベイズ統計』の読みどころという記事が載っていました。ベイズ理論の人気は根強いですね。 ベースとしての数式は割とシンプルなので、自分で実装してもそれ程手間は掛からないかもしれません。しかし、CPANのモジュールとして提供されているので、そちらを使用するのも良いかと思います。私が知っている所では、Algorithm::NaiveBayesが簡単で使いやすかったです。 昔書いたコードですが、下のサンプルでは簡単なスパムフィルターを作っています。spam.txtとham.txtは、それぞれのコーパスを形態素解析して作った単語のみのリストです。test.txtは、判定したい文章から抽出した単語のリストです。スパムとハムの量を増やせば、これだけでも割と使い物になります。 応用例としては、スパムとハムの2種類のカテゴリだけではなく、複数種類のカテゴリを作ればブログの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムとデータ構造編 トップページ●Programing Place
サービス終了のお知らせ
サービス終了のお知らせ
Technical documentation
Top | ヒープの正体
はてな