タグ

algorithmとc++に関するhiromarkのブックマーク (15)

  • 最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ?

    最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた. 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず,全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと.つまり,連結グラフから適当な辺を取り除いていき,閉路をもたない木の形にしたものが全域木となる.ここで,グラフの各辺に重みがある場合,重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という. 最小全域木を求めるアルゴリズムとしては以下の二つが有名である. クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲

    最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ?
  • Googleの並列ログ解析向け言語「Sawzall」が公開されたので使ってみた | Preferred Research Blog

    Rapidly Realizing Practical Applications of Cutting-edge Technologies

    Googleの並列ログ解析向け言語「Sawzall」が公開されたので使ってみた | Preferred Research Blog
  • Spaghetti Source - Suffix Array

    Suffix Array (Larsson-Sadakane) 説明 Suffix Arrayとは,与えられた文字列の接尾辞の集合を辞書順ソートしたものである.近年,これを用いることによって多くの文字列の問題が解かれることがわかってきた. Larsson-Sadakane は Suffix Array を O(n (log n)^2) 時間で構成するアルゴリズムである.Mamber-Myers と同様のアイデアによって文字列長を倍加させ,O(log n) 回の multikey quicksort を行うことにより,全体で O(n (log n)^2) の計算量を達成する.詳しくは適当な文献を参照. Suffix Array を用いて解けるもっとも典型的な問題は,文字列の検索である.Suffix Array 上で二分探索を行えば,O(m log n) でパターンの検索ができる.また,Suf

  • 行列分解ライブラリredsvdを公開しました - DO++

    大規模疎行列向けの行列分解ライブラリredsvdを公開しました. redsvd 大規模疎行列向けの特異値分解や主成分分析,固有値分解を行うライブラリredsvdを公開しました. 修正BSDライセンスで公開しており,コマンドラインから使える他,C++ライブラリが用意されています. 例えば,行と列数がそれぞれ10万,非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します. 特異値分解とか,使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので,興味のある方は参考にしてください. 特異値分解とは まず行列を適当に復習します.行列Xの転置をX^tと表すことにします.またIを単位行列とし,Oを全ての成分が0である零行列とします.また,行列XX^t=IであるようなXを直交行列と呼びます.Xが直交行列の時,Xvはベクトルvを長さを変えずに回転させます.ここでは

    行列分解ライブラリredsvdを公開しました - DO++
  • SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記

    SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。 アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ

    SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記
  • 構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog

    どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常 形態素解析ベース N-gramベース の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。 入力と出力入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。 <総説誌名>蛋白

    構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog
    hiromark
    hiromark 2009/12/14
    AC法って意外とシンプルに書けるんですねー。
  • Succinct なトライの実験に用いたソースコード - やた@はてな日記

    いつものように,Google Code にアップロードしました.プロジェクトの名前は sumire-tries になっています.名前を sumire にした理由は,なんとなくです…. ドキュメントは準備中ですが,基的な使い方は後述します. Google Code Archive - Long-term storage for Google Code Project Hosting. 右のメニューにある Featured downloads からアーカイブをダウンロードして,よくある手順を踏めば動作確認できます. ./configure make make check ヘッダのみで構成されているため,make install でインストールしなくても,ヘッダを格納しているディレクトリ(include/)をコピーすれば使えます. トライを構築する手順は,以下のようになっています. 基礎となる

    Succinct なトライの実験に用いたソースコード - やた@はてな日記
  • Toriumi Lab.

    2024年3月26日 「情報的健康プロジェクト:アテンションエコノミーの暗翳と『情報的健康』−総合知で創出する健全な言論空間」を慶應義塾大&オンラインで開催されました. https://www.kgri.keio.ac.jp/news-event/156808.html 査読付き論文が出版されました.Masaki Chujyo, Shu Liu, Fujio Toriumi "Improving network robustness against localized attacks by link modification", Nonlinear Theory and Its Applications, IEICE Volume 16 Issue 3 Pages 561-572 (07/2025) 査読付き論文が出版されました.Takano, M., Nishiguchi, M. & T

    Toriumi Lab.
    hiromark
    hiromark 2009/07/17
    これはうれしいかも。
  • C++: 編集距離を求めるアルゴリズム

    編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換) 2. sittin (e を i に置換) 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示

    hiromark
    hiromark 2009/07/15
    使いでが多いのでうれしい。
  • GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ

    GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー!古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠

    GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
    hiromark
    hiromark 2008/11/14
    考え方のプロセスがいろいろ応用できそうだ。
  • Google Code Archive - Long-term storage for Google Code Project Hosting.

    Code Archive Skip to content Google About Google Privacy Terms

    hiromark
    hiromark 2008/10/13
    使えるかな。
  • Spaghetti Source - 各種アルゴリズムの C++ による実装

    ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基 テンプレート グラフ

    hiromark
    hiromark 2008/10/02
    これはうれしい!
  • Spaghetti Source - 各種アルゴリズムの C++ による実装

    ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基 テンプレート グラフ

    hiromark
    hiromark 2008/09/17
    これはうれしい!
  • Darts: Double ARray Trie System

    Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが

    hiromark
    hiromark 2008/09/15
    ダブル配列を構築するための シンプルな C++ Template Library
  • Amazon.co.jp: アルゴリズムC++ : 本: ロバート セジウィック,Robert Sedgewick,野下 浩平,佐藤 創,星 守,田口 東

    Amazon.co.jp: アルゴリズムC++ : 本: ロバート セジウィック,Robert Sedgewick,野下 浩平,佐藤 創,星 守,田口 東
    hiromark
    hiromark 2008/05/01
    買う。
  • 1