「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
動的計画法再入門(1) - nokunoの日記
プログラミングコンテストチャレンジブックを読みながら、動的計画法の復習をしています。プログラミングコンテストチャレンジブックこの本はコンテストの紹介とか環境構築の説明はほとんどなく、普通にアルゴリズムの教科書として優れているのでタイトルに騙されないようにしましょう（笑）。それはさておき、この記事ではp.52のナップサック問題を例に、動的計画法の考え方と実装方法について検討してみます。 ナップサック問題重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の、価値の総和の最大値を求めなさい。制約：1 1 1 ＜例＞入力：n = 4(w, v) = {(2,3), (1,2), (3,4), (2,2)}出力：7 （0,1,3番の品物を選ぶ） 方法1最初に書いたコードがこれです。再帰による全探索で、荷物を左から順番に選んで
密／疎ベクトルのトレードオフを調べてみた - ny23の日記
k-means を実装していて，疎ベクトルと密ベクトルのトレードオフ（距離計算の速度差）が気になったので軽く実験してみた．具体的に知りたかったのは，どれぐらい疎なら疎ベクトルを使った方が距離計算が速くなるか，という問に対する答え．空間使用率の改善については sparse vector における index と value の型のサイズ比でほぼ自明に分かるが，速度に関してはコンパイラの最適化の加減もあるので良く分からない．以下がテストコード（ややずぼらな実装）． [追記] 折角なので，Eigen 3.0-beta2 とも比べてみた． #include <sys/time.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <tr1/random> #include <eig
Não Aqui! » 10行強で書けるロジスティック回帰モデル学習
ロジスティック回帰（logistic regression）の学習が，確率的勾配降下法（SGD: stochastic gradient descent）を使って，非常に簡単に書けることを示すPythonコード．コメントや空行を除けば十数行です． リストの内包表記，条件演算子（Cで言う三項演算子），自動的に初期化してくれる辞書型（collections.defaultdict）は，Python以外ではあまり見ないかも知れません． リストの内包表記は，Haskell, OCaml, C#にもあるようなので，結構メジャーかも知れません． [W[x] for x in X] と書くと，「Xに含まれるすべてのxに対し，それぞれW[x]を計算した結果をリストにしたもの」という意味になります．sum関数はリストの値の和を返すので，変数aにはXとWの内積が計算されます． Pythonでは，三項演算子を条
基本となるDoubleArrayの実装 - sileのブログ
各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区切り('\n')で保持するソート済みのファイルを入力に取り、DoubleArrayを構築する BASE配列とCHECK配列から成る BASE配列: 遷移情報およびキーのIDを保持する配列 BASE[ノード] = 遷移のベースとなるノード => 遷移先ノードは、BASE[ノード] + 遷移文字、で求める BASE[ノード]の値がマイナスの場合は、キーの終端を意味し、そのIDが格納されている => キーのIDは、BASE[ノード] x -1、で求める CHECK配列: 遷移の正当性をチェックするための配列 CHECK[ノー
パターン認識に関する公開プログラム
宇野毅明と有村博紀による公開プログラム（コード） このページでは、公開しているプログラムのコードがダウンロードできます。主に、列挙アルゴリズムやデータマイニングに関するものです。全て、宇野毅明、あるいは、良く一緒に研究をしてお世話になっている北海道大学の有村博紀先生によって作られたものです。各プログラムに使用言語とコード作成者が書いてありますので、質問、あるいはバグの報告などは、作成者にご連絡ください。宇野毅明は uno@nii.ac.jp、有村博紀先生は arim@ist.hokudai.ac.jp です。 !!! コードの最近のバージョンに、マッキントッシュのフォーマットではエラーが出るというバグがありました。現行バージョンではこのバグは治っています。 LCM (Linear time Closed itemset Miner) ver.2 (C言語、宇野毅明) [文献 1]
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
データ構造とアルゴリズムの記事一覧 - いろいろ解析日記
データ構造 Javaを使うなら必ず覚えておきたいデータ構造 - 配列・リスト・マップ PHPなら覚えるべきデータ構造はひとつだけ？ - 配列 Perlで覚えたいデータ構造 - 配列・ハッシュ VBAで覚えておくデータ構造 - 静的配列・動的配列・ディクショナリ JavaScriptで覚えておくとよいデータ構造 - 配列・オブジェクト Bashで覚えておくとよいデータ構造 - 配列 - 何かしらの言語による記述を解析する日記 アルゴリズム Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆マップ編) Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆ビーン編) PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 VBAを使うなら理解しておきたいアルゴリズム - 抽出・結合・集計 Javascr
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog
どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常 形態素解析ベース N-gramベース の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。 入力と出力入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。 <総説誌名>蛋白
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
画像研究入門
【目次】 ０．Ｃ言語基礎 ０－１．本当の基礎 ０－２．配列とポインタ ０－３．文字列操作・ファイル操作 １．画像基礎 １－１．画像フォーマット １－２．テキストとバイナリ １－３．配列とポインタ ２．画像処理基礎 ２－１．エッジ処理 ２－２．背景差分処理 ３．グラフ描画基礎 ３－１．ｇｕｎｐｌｏｔ ３－２．折れ線グラフ ３－３．ヒストグラム表示 ４．アルゴリズム基礎 ４－１．ｋ－平均アルゴリズム ４－２．ＥＭアルゴリズム ５．画像表示基礎 ５－１．ＯｐｅｎＧＬ ５－２．ＯｐｅｎＧＬによる二次元表示 ５－３．ＯｐｅｎＧＬによる三次元表示 はじめに これから画像処理・認識の研究を始めようという人を対象とした入門書を作っています．対象は研究室に配属されたばかりの情報系大学の４年生を想定していますが，誰が読んでも分かるように心がけているつもりです．読み進めながら課題を解いていくうちに画像の基礎知識
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
Canonical Huffman Codes での符号長の効率的な計算 - naoyaのはてなダイアリー
週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。 輪講では時間切れのためこのアルゴリズムの解説が駆け足になってしまいましたので、改めて解説資料を作ってみました。2009 年の今に Managing Gigabytes を読んでいるという方はあまり多くないかもしれませんが、参考になれば幸いです。 https://www.dropbox.com/s/539fhyc7rf6b9ik/090518computing_huffman_code_length.ppt?dl=0 (PPT, 258K) 先日 Canonical Huffman Codes の習作を Python で実装しましたが、このコード
ランダムソート(笑)とは - 西尾泰和のはてなダイアリー
誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。 たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。 >>> def quicksort(xs): from random import random if len(xs) < 2: return xs pivot = xs[0] left = [] right = [] for x in xs[1:]: if random() < 0.5: left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right
論文ファイブ - d.y.d.
16:40 09/01/28 インドコンテスト おとといのを読み返してて、 全体として並列並行系多いなーといっておきながら、 個別紹介に１個もそれ系のがなくて面白いなあと思いました。 と、それはともかく、今年もインド発プログラミングコンテストのお知らせが来てました。 ICPCやTopCoder系の問題の出る CodeCraft、 Project Euler系の問題の出る MathematiKa、 あと今年はなんだか縛り付きプログラミング（ゴルフとか）系の Time Limit Exceeded というのがあるらしい。毎年恒例行事にするつもりなのかな。 去年のはわりと面白かったので、今年も参加してみるつもり。 23:10 09/01/26 POPL 2009 行ってきました。MS Research 多いなーというのと、 まあ当たり前ですが並列並行系多いなーというのが全体的な感想。 以下印象に
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムとデータ構造編 トップページ●Programing Place
Amazon.co.jp: 集合知プログラミング: Toby Segaran (著), 當山仁健 (翻訳), 鴨澤眞夫 (翻訳): 本
座学と実学、無知と無理解、数学と真理