タグ

関連タグで絞り込む (534)

タグの絞り込みを解除

Algorithmとalgorithmに関するmanabouのブックマーク (720)

  • 東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo

    ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ.jpのものを使わせてもらいました。 使ったのは東京メトロ+都営+山手線 駅(ノード)の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路(エッジ)の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな! Hash.keys で返ってくるキーはすべて文字列に

    東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
  • 指数時間アルゴリズム - てきとーな日記

    指数時間アルゴリズムというのは,NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで,できるだけ指数の底の小さいアルゴリズムを開発することが目指されています. コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います. この分野は近年盛んに研究され始め,自分も大学でこの分野を中心に研究をしています. 今回,情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので,この分野の基礎的な手法から最先端の手法までをまとめてみました. 指数時間アルゴリズム入門@情報オリンピック春合宿講義 http://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー http://www.slideshare.net/wata_orz/ss-12208032

    指数時間アルゴリズム - てきとーな日記
  • オンライン アルゴリズム (Online Algorithms)

    後悔先に立たずという諺があります。 後になってから「あの時こうしていれば…」と思う経験は誰しもありますが、 これは、将来の情報がない状態で決断した行動と、何とを比べているのでしょうか? 後から振り返ることで、「あの時」以降の将来の情報を持っていると仮定した場合の 最良の行動と比較して、あまり良くないと思う訳です。 これをモデル化したのがオンライン問題です。 情報の授業で習うアルゴリズムは、 入力がポンとすべて与えられて、 何らかの条件を満たす最良の解を求めるものです。 しかし、将来の情報が分からない状況で、 入力が全部そろっていないから待ってください という訳にはいきません。 オンライン アルゴリズムは、時系列にそって与えられる入力を順に受け取って、 その各時点で、それまでの入力をもとにその時に取るべき行動を決定します。 下手をすると、将来の入力を知っていれば絶対しないような行動を 選択す

  • 決定木入門 | 開発ブログ | スパイシーラボ

    こんにちは。永野と申します。スパイシーソフトでは2年弱のあいだ、CGMの事業部でアプリ★ゲットおよびマンガ★ゲットのリニューアルと保守を担当していました。現在は弊社が次に出すソーシャルゲームのログ分析の開発を担当しております。最近はまっているソーシャルゲームはモバゲーの神撃のバハムートとGREEのドラゴンコレクション、聖戦ケルベロスです。(TVCMでおなじみEXILEのカードを無課金でコンプしました。) 前述の通り現在私はログ分析を担当しています。現段階ではまずKPI算出や、離脱ページ特定、プレイヤーさんの行動および状態(ステータスやゲーム内リソース)の追跡など、基的かつ効果が高い部分に注力して実装しているのですが、その先の一手のためにデータマイニングの再勉強をしています。今回はその中から決定木の紹介をいたします。 決定木とは分類器の一種で、データの集合から法則(変数)を発見するため

  • Block-Based Join Algorithms

    Created 13 years, 9 months ago Modified 2 years, 5 months ago Type article Status active License CC BY-SA / Gnu FDL History Comments In the versions of MariaDB/MySQL before 5.3 only one block-based join algorithm was implemented: the Block Nested Loops (BNL) join algorithm which could only be used for inner joins. MariaDB 5.3 enhanced the implementation of BNL joins and provides a variety of block

  • perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary

    すみません。タイトルはやや釣り気味です。 類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi   https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。(冷) 考え方と仕組み 類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。 昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。 そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。 で、今回考えたLuigiも実は近似型のインデッ

    perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary
  • Não Aqui! » SimString (類似文字列検索ライブラリ) 1.0 released

    SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました.類似文字列検索とは,文字列集合(データベース)の中から,クエリ文字列と似ているものを見つけ出す処理です.コンピュータは,正確に一致する文字列を探すのは得意ですが,表記揺れに出くわすと,途端に対応できなくなります.例えば,「スパゲティ」に対して,レストラン情報などを返すサービスにおいて,「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると,通常のデータベースでは情報を提示することが出来ません.類似文字列検索を用いると,表記揺れが検索クエリに与えられても,「スパゲティ」という既知語を代替クエリとして提案したり,「スパゲティ」の情報をダイレクトに引き出すことができるようになります. 似てる語を探す技術って,文字列処理の基中の基で,自然言語処理では当たり前のように使われていてもおかしくな

  • Dynamic Programming による類似文字列マッチの実装例

    Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索(あいまい検索)」に使うと 便利なalgorithm。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "

    Dynamic Programming による類似文字列マッチの実装例
  • Tumblr

    「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので(結局これは使わなかったんですが)圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます(低周波、高周波という言葉の意味はこの先で出てきます) 画像の上にマウスカーソルを乗せ

    Tumblr
  • acmsolver.org - acmsolver リソースおよび情報

    manabou
    manabou 2012/03/12
    competitive programming
  • MySQL SQLオプティマイザのコスト計算アルゴリズム - SH2の日記

    いちいさんにお誘いいただいて、勉強会で発表をすることになりました。 InnoDB Deep Talk #1 : ATND おそらく初見では内容が難しいと思いますので、先に資料を公開しておきます。 プレゼンテーション資料 (PDF) テストデータ生成スクリプト (JdbcRunnerで利用します。) プレゼンテーション資料からリンクしているウェブサイトの一覧です。 MySQL Bugs: #64567: Last_query_cost is not updated when executing an unique key lookup Understanding and Control of MySQL Query Optimizer: Traditional and Novel Tools and Techniques: MySQL Conference & Expo 2009 - O'R

    MySQL SQLオプティマイザのコスト計算アルゴリズム - SH2の日記
  • たぶん30分でよくわかるLOUDS入門 - EchizenBlog-Zwei

    IMEの効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。 というわけでLOUDSをどこまでわかりやすく説明できるか?ということに挑戦したくなったので記事を書いてみるよ。 LOUDSというのは木を表すデータ構造。木というのは以下のようなものを想像すればよい。 この木を表すデータ構造を作りたい。単純に考えると各ノード毎に子ノードのIDを持たせておけばよい。つまり 0 => {1, 4, 5} 1 => {2, 3} 2 => {} 3 => {} 4 => {} 5 => {6} 6 => {7}というようなものを考える。ここで各IDと子ノード数を各1バイトで管理したとして 0 => {1, 4, 5} # 1 + 3 = 4バイト 1 => {2, 3} # 1 + 2 = 3バイト 2 => {} # 1 + 0 = 1バイト 3 => {}

    たぶん30分でよくわかるLOUDS入門 - EchizenBlog-Zwei
  • 情報系修士にもわかるLOUDS - アスペ日記

    一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説(全12回、練習問題付き)というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。

    情報系修士にもわかるLOUDS - アスペ日記
  • MapReduceのパターン、アルゴリズム、そしてユースケース - きしだのHatena

    Ilya Katsov氏による「MapReduce Patterns, Algorithms, and Use Cases」の翻訳 http://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/ (下書きに入れて推敲するつもりが、なんか公開されてしまっていたので、あとでいろいろ修正すると思います) February 1, 2012 この記事では、Webや科学論文で見られる異なるテクニックの体系的な視点を与えるために、数々のMapReduceパターンとアルゴリズムをまとめた。 いくつかの実用的なケーススタディも提供している。 すべての説明とコードスニペットでは、Mapper、Reducer、Combiner、Partitionaer、ソーティングにおいてHadoopの標準的なMapReduceモデルを利用します。このフレー

    MapReduceのパターン、アルゴリズム、そしてユースケース - きしだのHatena
  • 情報系修士にもわかるダブル配列 - アスペ日記

    最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie(トライ)というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、このの説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、このを教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから

    情報系修士にもわかるダブル配列 - アスペ日記
  • Golomb-coded sets: smaller than Bloom filters

    While reading the super-interesting Imperial Violet, Adam Langley’s weblog, I stumbled upon a new data structure that I had never heard of: the Golomb-coded sets (GCS). It is a probabilistic data structure conceptually similar to the famous Bloom filters, but with a more compact in-memory representation, and a slower query time. A bloom filter with the optimal number of hash functions (= bits per

    Golomb-coded sets: smaller than Bloom filters
    manabou
    manabou 2012/01/25
    [[golomb][bloomfilter]
  • Golomb coding - Wikipedia

    This section needs additional citations for verification. Relevant discussion may be found on the talk page. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Golomb coding" – news · newspapers · books · scholar · JSTOR (October 2024) (Learn how and when to remove this message) Golomb coding is

    manabou
    manabou 2012/01/25
    [[golomb][bloomfilter]
  • バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例

    バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例 書いた人: ると 書いた日: 2012年1月21日 はじめに Twitterで「有名なオープンソースソフトで今まであったおもしろいバグを解説したとかないだろうか」とツイートしたらそれなりに需要があるようでした。そこで先ず隗より始めよという故事にのっとり、死馬の骨としてバグ解説記事を書いてみます。 今回のバグはScala 2.9の標準ライブラリに含まれるmutable.HashSet(ハッシュテーブルを使った重複無しコレクション)のコピーがJavaの標準ライブラリに含まれるHashSetの100倍遅いというバグです。並列コレクションのためにぱっと見問題の無い変更を加えたら思わぬところで影響が出たというものです。 なお、今回はScalaに関するバグですが、Scala

  • 情報知識ネットワーク特論 -講義資料- | 北海道大学オープンコースウェア (Hokkaido University OpenCourseWare, HU-OCW, 北大OCW)

    情報検索とパターン照合(7回)(喜田が担当) ガイダンス、および、準備 講義スライド Prefix型アルゴリズム(naïve、KMP、AC、Shift-And/Or) 講義スライド Suffix型アルゴリズム(BM、Galil、Horspool、Sundayほか) 講義スライド 近似文字列照合 講義スライド 正規表現の照合 講義スライド 圧縮テキスト上のパターン照合 講義スライド 文字列照合技術の今後 講義スライド

  • Damn Cool Algorithms, Part 1: BK-Trees - Nick's Blog

    Posted by Nick Johnson | Filed under tech, coding, damn-cool-algorithms This is the first post in (hopefully) a series of posts on Damn Cool Algorithms - essentially, any algorithm I think is really Damn Cool, particularly if it's simple but non-obvious. BK-Trees, or Burkhard-Keller Trees are a tree-based data structure engineered for quickly finding near-matches to a string, for example, as used