マージ・ソート : 巨大データのソート法
はじめに まずはともあれ腕試し、この問題を解いてみてくださいな: 【問1】 デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。 ※各文字列は改行で区切られています。 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ: using System; using System.IO; using System.C
特定領域 > 研究成果報告 > 列挙学校
資料 ``列挙の基本と基礎的なアルゴリズム'' 岡本 吉央 (東京工業大学) [ Slides PDF (5.3 MB) ] / [ Handout PDF (1.8 MB) ] / [ Exercises PDF (46 KB) ] C プログラム等 (岡本さんの列挙のページ) ``グラフ列挙の手法'' 中野 眞一 (群馬大学) [ Powerpoint (568 KB) ] ``パターンマイニングにおける列挙アルゴリズム'' 有村 博紀 (北海道大学) [ PDF (1.2 MB) ] ``複雑な構造の簡潔な列挙法と実装法'' 宇野 毅明 (情報学研究所) [ Powerpoint (2.0 MB) ] © The Copyrights for the PowerPoint / PDF files are owned by their authors.
アルゴリズムの名前を教えてください - OKWAVE
面白いアルゴリズムですね：） すぐには理解できず，「本当に初期化しなくても動くの？」と懐疑的だったので， flag[] と link[] にイジワルな (つもりの) 初期値を入れて動かしてみたところ， ちゃんと動いたので，落ち着いて考え直して理解しました． そのアルゴリズムは初めて見るので，当然作者にも心当たりがないのですが， ついさっき「ひょっとしたら…」ということを思い出したのでコメントしました． 昔，LIFEBOAT の機関誌 (？) に載っていた超高速ソートライブラリ LSORT の話です． (今，「LSORT LIFEBOAT」で検索してみたところ， 「The Lifeboat PERSPECTIVE 1984.4」と出ました．) http://www.geocities.jp/oldbig_ancient/KodaiHP3.htm 「LSORT」とは線形時間 (linear t
404 Blog Not Found:私ごときがアルゴリズム本を書くことにした訳
2007年12月02日04:00 カテゴリアルゴリズム百選 私ごときがアルゴリズム本を書くことにした訳 アルゴリズムを評価するのは、プロにとっても難しい。 アルゴリズム - 186::Diary * あとメモ化のときの最初の呼び出し回数の評価も間違ってるよね. 1回目は関数をナイーブな実装で評価するから. ところが、この下りに関して間違いなのは私の元発言ではなく、この突っ込みの方なのである。 そのことは、以下を見れば一目瞭然である。 ナイーブ プログラム: var c = 0; function fib(n){ c++; if (n <= 2) return 1; return fib(n-1) + fib(n-2); } (function(n){ p('fib('+n+') = ' + fib(n) + ', count = ' + c) })(25) 出力: エラー: メモ化 プログ
最大エントロピーモデル - DO++
自分の復習も含め、最大エントロピーモデルについて勉強会で発表しました。発表資料 [ppt] [pdf] 今年のACLやICMLなどでの発表などを解説してます。論文中になかった式導出とかもしてみてます。 発表中では結構口頭で補足した部分があって、この資料だけでは不十分だと思います。適宜引用先などを参照してください。 最大エントロピーモデルは高次元の確率分布推定に適していて自然言語処理や、最近だと動植物がどのように分布しているかなどの推定等、広い分野で使われている確率モデルです。 ＃修正＋質問・回答スライドを追加しました
DO : Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです． キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています） 特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります． 最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当
Iterative deepening
トップ / ゲーム木の探索問題 / Iterative deepening Iterative deepening （反復深化法） DFS の様に必要な記憶容量が少なく、BFS の様に必ず解が求まる方法、それが Iterative deepening です。ここでは、その方法とコストについて考察します。 Iterative deepening とは Iterative deepening とは、その名の通り、探索する深さをだんだんと深くしていく方法です。具体的には、まず深さ１の DFS を行い、解が見つからなかったら深さ２の DFS を行い、……、と繰り返していきます。手順をまとめると次のようになります。 cutoff c を１に設定する 深さ c の DFS を行う 2 で解が見つかれば終了、見つからなければ c := c + 1 として 2 を行う 行っているのは DFS なので、記憶
キミならどう書く 油売り算 - デー
d.y.d.さんで見かけた。 こういうパズル系のプログラムは苦手なんですが、がんばって挑戦してみました。 問題が微妙に分からなかったのですが、他の方と同じ答えが出ているので、たぶんできたと言えば出きたっぽいですが、あらかじめ発見できる深さが分かってないとかなり無駄に動くと言う……ダメな感じです。 夜中に他の方のを見てます。 use strict; my $MAX = 1000; # 最大深さ my $SUCCESS = 1; my $FAILURE = 2; abura(10, 7, 3); # 成功? sub is_goal { my $data = shift; my $count = 0; foreach my $c (@$data) { $count += $c->{cur}; } return $$data[0]->{cur} == $count / 2 ? 1:0; } # あ
Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)
Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J
きまぐれ日記: L1-regularized CRFを実装してみた
hillbigさんのブログで 紹介されていた "Scalable Training of L1-regularized Log-linear Models", G. Andrew and J. Gao., ICML 2007. をCRF++上に実装してみました。 現在の CRF++ の実装、そしてオリジナルも含めた多くの実装は L2-regularized log-linear model です。hillbig さんのプレゼンにもありますが、L2は若干高性能だけど、全パラメータが非0になって、最終的なモデルがデカく なってしまうのですが、L1だと不必要･冗長なパラメータを完全に0にする効果があり、モデルをコンパクトにします。 3年前のmecabに関する論文では、L2 と L1 の CRF を比較して、L2のほうが若干高性能ということを確認していました。 L1-regularized の場合
研究室コンピュータ関連: 数独の解き方とプログラム
数独(ナンプレ)を解くプログラムを作成した．いくつかのプログラムがあるようであるが，それらよりも良さそうである．学生のための人間の思考をプログラムにするという練習問題として作った．下敷になった参考ソースなしに書きはじめた．３つのアルゴリズムを用いた． ●第一次アルゴリズム 数独は第一次アルゴリズムとして次のように解く。このアルゴリズムは初級者のアルゴリズムである。 (1) 空欄を探す。 (2) その空欄に入る候補の数字は全部である。 (3) 横１列をみて, すでに数字が入っていた時はその空欄の候補から除く (4) 縦１列をみて, すでに数字が入っていた時はその空欄の候補から除く (5) 空欄が所属する 3x3 の小枠を計算して,その枠を見て，すでに数字が入っていた時はその空欄の候補から除く。 (6) 候補が１つになった場合には,その数値を記入する。 (7) 以上をすべての空欄に対して繰り返
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
gboost - Graph Boosting Toolbox for Matlab
The gboost toolbox is a framework for classification of connected, undirected, labeled graphs. A typical graph is shown on the right: each node and edge is labeled by a discrete value. The gboost classifiers check for the presence of certain subgraphs in the larger graph. The subgraphs being checked are optimally determined by discriminative subgraph mining. The classification hypotheses is interp
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
Azul Systems - Cliff Click Jr.’s Blog: A Non-Blocking HashTable
A Non-Blocking HashTable March 27, 2007 I've been wrestling with concurrent algorithms again. This time, it's a Non-Blocking (concurrent, lock-free) HashTable. I've had it basically figured out for a few months now and I'm slowing widening the circle of people I expose it too. This HashTable seems too good to be true, which is why I'm trying hard to vet it's correctness before claiming victory
mito2003_wx
WX法は、データを最小構成要素（以下これをUnitと呼ぶ）に分解するアルゴリズムです。 Unitは例えば、自然言語で言えば、単語などに相当し、DNAの配列情報で言えばコドンに相当します。 様々なデータに対してそれぞれのUnitを一つ一つ定義するのはコストがかかる上、柔軟性がありません。そこで、Unitは、その内部に、さらに小さい構成要素を持たないという定義とします。 WX法は、データから、統計情報を用いて、そのような独立した部分列を抽出し、全データを上の評価基準で尤も的確な形に分解するアルゴリズムです。 WX法は次の五つのステップからなります (i) 全ての部分列を列挙する (ii) それぞれの部分列に対し、Unitらしさを表す評価値を与える (iii) (ii)の評価値を用いて、Unit分解を行う (iv) (iii)の結果を用いて評価値を再計算する (v) 収束するまで(
The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
2007-11-29
Google Code Archive - Long-term storage for Google Code Project Hosting.