Workflow Engine をつくろう！ Part 4（Task の並列実行） - Qiita
Part 1 Task の依存関係の解決 Part 2 Workflow の冪等性 Part 3 Task 間でのデータのやり取り Part 4 Task の並列実行 Task の並列実行 今回は Workflow Engine に Task を並列実行できる機能を実装をします。Workflow Engine が利用されるのは、ある程度以上の数の Task を含む処理になるので、全体の実行時間を短縮するために並列実行の機能はとても重要なものになります。 
Workflow Engine をつくろう！ Part 2 （Workflow の冪等性） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Part 1 Task の依存関係の解決 Part 2 Workflow の冪等性 Part 3 Task 間でのデータのやり取り Part 4 Task の並列実行 まえおき この連載記事で作成する Workflow Engine は、Luigi の設計思想に大きく影響を受けています。なので、 @k24d さんの Luigi によるワークフロー管理 を先に読んでおくと、理解が深まると思います。 前回は Task の依存関係の解決方法を実装しましたが、Part 2の今回は Workflow の冪等性について実装していきます。 Workf
Workflow Engine をつくろう！ Part 1（Task の依存関係の解決） - Qiita
Part 1 Task の依存関係の解決 Part 2 Workflow の冪等性 Part 3 Task 間でのデータのやり取り Part 4 Task の並列実行 Workflow Engine って何？ Workflow Engine と言っても多機能なものから、シンプルなものまで様々なものがあります。そこで、主旨がぶれないように、この記事での Workflow Engine は、以下の要件を満たすソフトウェアとします。 Workflow Engine とは、依存関係のある複数の Task を、意図した順番通りに実行するもの この記事では、この要件を満たす Workflow Engine を Ruby でつくる方法について解説します。 依存関係を記述する 依存関係を解決するコードを書く前に、依存関係を記述する方法をまず決めましょう。 依存関係を記述するには、luigi のように Ta
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
DSIRNLP #3 LZ4 の速さの秘密に迫ってみる
[CEDEC 2021] 運用中タイトルでも怖くない！ 『メルクストーリア』におけるハイパフォーマンス・ローコストなリアルタイム通信技術の導入事例
Depixelizing Pixel Art
Naïve upsampling of pixel art images leads to unsatisfactory results. Our algorithm extracts a smooth, resolution-independent vector representation from the image which is suitable for high-resolution display devices (Image © Nintendo Co., Ltd.). Abstract We describe a novel algorithm for extracting a resolution-independent vector representation from pixel art images, which enables magnifying the
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
情報圧縮と特許
■ 初めに これまで、GIF の LZW を初めとする情報圧縮に関する特許が、様々なところで取り上げられ論議を呼んできましたが、しかし、具体的な内容に踏み込んだものは少なかったように思います。 例えば、LZW の特許にしても、LZW のどの部分に特許権が認められているのか、と言う部分は殆ど触れられていなかったと思います。 しかし、これでは無意味な特許不安が広がるばかりで、今後の圧縮技術の普及に大きな影を落としかねません。実際、特許に抵触するかもしれないと言う理由だけで公開を停止したソフトウェアは多数存在します。 そこで、私がこれまで研究してきた圧縮技術と、調査した特許に関して、一部例を挙げながら、法律的な側面、技術的な側面の両面から、情報圧縮の特許について考えてみたいと思います。 ■ 特許とは？ それでは特許とは具体的にどのような性質のものでしょうか？ 特許とは、知的財産権制度の中で、発明
Redirection
This page has moved. Click here: http://www.ericbrasseur.org/gamma.html
fujimap: 簡潔な連想配列 - DO++
博論終わったので仕事の合間にfujimapというライブラリを作ってみました。 fujimap project fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。 今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています．Fujimapの特徴は必要な作業領域量が非常に小さいことです．キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive（後述）にのみ依存します。 例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワー
kumofsはなぜ落ちないか - Blog by Sadayuki Furuhashi
前回は、kumofsはなぜスケールするかということについて紹介しました。その中で最後に、耐障害性もスケーラビリティにとって重要だーと述べました。 そこで今回は、kumofsはなぜ落ちないのか、なぜ耐障害性が高いと言えるのかーということについて紹介したいと思います。 分散システムはテストが難しいことに定評がありますが（たぶん^^;）、その中でも耐障害性の検証は最上級に困難な部類です。 耐障害性は実際のところ、アルゴリズムの設計以前に実装上のバグが大きく影響するので、設計上は耐障害性が高いと言っていても、実際に使ってみると良く止まるという話はありがちな話です。（個人で開発している場合など、開発リソースが小さい場合はなおさら） そのため耐障害性の高いシステムを実現するためには、実装しやすくバグが入り込みにくい設計も重要かなーと思います（もちろん、アルゴリズムも重要ですが）。 分散システムには複雑
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
ダイクストラとかA*とか - #3(2010-01-19)
■ ダイクストラとかA*とか 単純な迷路の最短経路を見つけるのに、ダイクストラ法とA*だとどのように異なってくるのかわかりやすく見てみたかったので、JavaScriptで実装してみました。 迷路 セルをクリックするとそのセルを通過できなくなります。もう一回クリックすると元に戻ります。スタートやゴールの位置を変更するには、[Set start]や[Set goal]ボタンをクリックしてからセルをクリックします。[Run]をクリックすると経路を探します。 探す過程で、現在のセルの状態とパスの長さを表示するようにしてあって、一ステップずつゆっくり進むようになっています。 一番上はダイクストラ法、二番目がA*で、三番目はA*なのですがヒューリスティックに指定されたゴールまでの距離が等しい場合にはゴールに近いセルから試行するようにしてあります。ちなみに、A*でのセルからゴールまでのヒューリスティック
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
Route 477 - shinhさんの迷路ゴルフ解読した
■ [ruby] shinhさんの迷路ゴルフ解読した ビフォー： q=gets(p)*1,~/S/ (a,i,*q=q a[i]<?S&&a[i]=?$ 4.times{|x|q+=[a*1,x]if$_[x=-~x%3*-~~/$/-~/$/+-x/2+i]!=$_[x]=?*})while/G/ puts a http://shinh.skr.jp/m/?date=20100113#p06 アフター： seen = gets(nil) queue = [[seen.dup, ~/S/]] wid = ~/$/ while seen =~ /G/ maze, here = *queue.shift maze[here] = ?$ unless maze[here] == ?S 4.times{|k| d = (k+1) % 3 n = here + (d-1)*wid + (d + -k
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムイントロダクション15章 動的計画法
GitHub - cubicdaiya/dtl: diff template library written by C++
