TouchRetouchのアルゴリズム
画像修復（inpainting)とは画像中の欠損領域を、何らかの方法で修復することを指します。iPhoneアプリとしてはTouchRetouchが有名ですね。 基本的に、画像修復はマルチコアのCPUを使っても2・３分は余裕でかかる処理なのに、TouchRetouchでは、iPhoneという非力なプラットフォームにもかかわらず10秒程度で処理が終了しています。このTouchRetouchがどのようなアルゴリズムで修復を行っているのかが気になったので、少し調べてみました。 画像修復とひとくちにいっても、 1. 輝度値の連続性を考慮した画像修復 2 .特徴空間での補間による画像修復 3. テクスチャの逐次合成による画像修復 4. テクスチャの全体最適化による画像修復 といったものがあるようです。 ここらへんはこちらの論文を参考にさせていただきました。 輝度値の変化と画像の局所性を考慮したパターン
【レポート】効果的な文字列検索アルゴリズム「Boyer-Moore-Horspool」 | エンタープライズ | マイコミジャーナル
Hello World, We Are Phusion. We provide amazing Ruby & Rails products and services to companies that shape our modern day culture. エンタープライズ向けの高速Ruby on Rails実行環境を提供しているPhusionがEfficient substring searching - Phusion Corporate Blogにおいて、特定の文字列からある文字列を検索をするためのアルゴリズムの比較と、その実装系(C++)の公開を実施している。文字列検索はプログラミングで頻出する処理のひとつであり、プログラミング上の参考になる。 文字列から特定の文字列を検出する場合、全体の文字列長(M)と一致させたい文字列の長さ(N)の積O(M*N)が計算量となる。O(M*N)
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
そのアルゴリズム、貪欲につき――貪欲法のススメ
そのアルゴリズム、貪欲につき――貪欲法のススメ：最強最速アルゴリズマー養成講座（1/3 ページ） アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。 動的計画法は本当に万能なのか？ 本連載ではこれまで、かなりの文量を割いて動的計画法について説明してきました。動的計画法はさまざまな問題で有効な解決手段ですが、動的計画法が使えるからといって、常に動的計画法を利用することが正しい選択である、というわけではありません。この理由は簡単で、動的計画法は計算量を大幅に削減できますが、その本質は、不要である要素を切り捨てることで問題全体を見渡すというアルゴリズムであるためです。 ここで問
Mostly-Concurrent Mark & Sweep GC のアルゴリズム
目次 1. 前置き 2. HotSpot VM 1.4.x の GC の種類 3. Mostly-concurrent Mark & Sweep 4. 応用 4.1 世代別 GC との組み合わせ 4.2 カードマーキング (Card Marking) 4.3 並列化 (Parallel GC) 4.4 ビットワイズ・スイープ (Bitwise Sweep) 4.5 インクリメンタル・コンパクション (Incremental Compaction) 5. 参考文献 脚注 コメント 1. 背景 ガーベージコレクション(GC) には色々なアルゴリズムが存在するが、大雑把に言って Stop-the-World (STW) 型 GC と On-the-fly 型 GC に大別される。 STW 型の GC はプログラムの実行中にはガーベージの回収を行わず、メモリが枯渇した時になって始めてガーベージの回
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
QuickDrawが素早く楕円を描く手順を追う - ザリガニが見ていた...。
2010年7月20日、QuickDrawのソースコードがダウンロード可能になったらしい。 MacPaint と QuickDraw のソースコード、公開される - スラッシュドット・ジャパン yebo blog: AppleがMacPaintとQuickDrawのソースコードを寄贈 QuickDrawは、Lisaや初代MacintoshからOS9の時代まで、Macの画面に見えるもの（ほとんど）すべてを描いていたGUIなOSの核となる描画プログラムだ。25年以上も昔から、角の丸い四角形を当然のように高速に描画していた。そのQuickDrawがどのように円を描いていたのか？以前の日記で思いを馳せたことがある。 QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。 奇数の数列の和が、二乗の数列になる（1 + 3 = 2^2、1 + 3 + 5 = 3^2、1
遺伝的アルゴリズムを楽しく理解できるサイトをまとめてみた - download_takeshi’s diary
女優の菊川怜さんが学生時代に研究テーマにしていたという事で有名な「遺伝的アルゴリズム」ですが、名前の仰々しさとは裏腹に、意外と直感的に理解できる取っ付きやすいアルゴリズムだったりします。 それにしても菊川怜さん、美人ですねー。こんな先生にイロイロと教えてもらいたかったなぁ。。。 という願望はおいといて、「遺伝的アルゴリズム」を目で見て＆手で触って、直感的に「理解したつもり」になれそうなサイトをまとめてみました！ 学術的なことはガン無視でいきます。 動画で見て雰囲気を知る まずは動画で見て楽しみましょう。ニコ動から何本か動画を紹介します。 【人工知能】物理エンジンで人工生命つくって学習させた http://www.nicovideo.jp/watch/sm6392515 いきなりですが、強烈なインパクトをはなつ動画です。 人工生命がうにょうにょ動きながら、勝手に「歩き方」を学んでいきます。超
グーグルの検索アルゴリズム--結果の信頼性を理由に高まる開示要求
Googleは秘密を守れるのだろうか。 ここから先を読みたくない陰謀論者は、米国家安全保障局（NSA）やWi-Fiデータの誤収集について好きなだけ語ればいい。本記事の実際のテーマは、もっとGoogleの中核的なアイデンティティの根幹にかかわるような問題だ。つまり、Googleが検索結果を不正に操作していないことを規制当局やインターネットパブリッシャーが確認できるように、インターネットを整理する秘密のアルゴリズムを開示することが必要なのか、という問題である。 GoogleのMarissa Mayer氏は、同社は検索に関する秘密をスパマーの手から守らなければならないと主張する。 提供：Stephen Shankland/CNET この件に関して、（少なくとも先週における）最初の攻撃を行ったのは、The New York Times（NYT）だった。NYTは米国時間7月14日付の社説の中で、「イ
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
【レビュー】高性能ソフトウェアの開発方法、仮想メモリを活用 | エンタープライズ | マイコミジャーナル
Queue is the ACM's magazine for practicing software engineers. 高いパフォーマンスを発揮するプログラミングに関する興味深い実験結果と考察をまとめたPoul-Henning Kamp氏の記事がACM QueueにおいてYou're Doing It Wrongというタイトルのもの掲載されている。同氏は超高速リバースキャッシュプロクシVarnishの開発者であるとともに、FreeBSD主要開発者のひとり。これまでの開発経験から現在のOSやH/Wの特性を活用したプログラミングについて言及している。 VarnishはFacebookをはじめWikia、Slashdot、Opera、VGなどさまざまなサイトで超高速リバースキャッシュプロクシとして採用されている。従来のリバースキャッシュプロクシと比較して徹底した高速化とOSの性能をフルに発
10兆までの素数のリストを作ってみませんか？
もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 記者がこんなことをいうのは、自分で10兆までの素数のリストを作ってみて、とても面白かったからだ。図1のプログラムを書いて出力が成功するまで約2週間、夢いっぱいの楽しいひとときを過ごせた。予期せぬ問題も発生したけれど、最後にはコンピュータがまだまだ発展する可能性を持つと感じられた。素数のリストを作る演習は、プログラミングと情報システムにおける有益な演習の一つである。 アルゴリズムの有効性が納得できる この演習の面白い点は、まずアルゴリズムの有効性を納得できる点だ。素数（prime）は
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
誤り許容カウント法(lossy count method)のサンプルプログラム
誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします （ラベルの頻度分布はジップの法則にだいたい準拠するとします）。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。） しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低
JavaScript, Canvas スキャンライン・シードフィル アルゴリズムによる塗り潰し : Serendip – Webデザイン・プログラミング
HTML5 Canvas でバケツツールによる塗り潰しを実現するために、スキャンライン・シードフィル (Scan Line Seed Fill) というアルゴリズムを使ってみた。 アルゴリズムの詳細については、以下のサイトを参考にした。 参考：ActionScript入門Wiki@rsakane – 塗りつぶしアルゴリズム(スキャンライン – シードフィル編) ペイント・ルーチン (1)シード・フィル アルゴリズム 単純に言えば、水平方向に塗り潰し可能な範囲を探して塗り潰してゆき、それを塗り潰し可能な範囲が無くなるまで上下方向に繰り返していくといったもの。 JavaScript, Canvas スキャンライン・シードフィル アルゴリズムによる塗り潰しデモ 塗り潰し処理のコード var fillColor = function(startX, startY, imgData, penColo
LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
第12回 索引の分散 | gihyo.jp
はじめに GoogleなどのWeb検索エンジンでは、2004年ごろには数10Tバイトの索引を数万台のサーバに分散させていたと言われています。これは、大量のデータを索引化したり大量のクエリを捌く必要がある際に、1台のマシンでは十分な速度が出ないことがあるためです。近年のハードウェアの進化はめまぐるしいですが、それでもハードウェアによるスケールアップには限界があるため、大規模な検索エンジンにおいて検索処理をスケールさせるには複数台のマシンの利用が不可欠となります。今回は、転置索引の複数のサーバへの分散方法について見ていきます。 複数台サーバにおける転置索引 複数のサーバを利用して検索処理を高速化させる方法には、索引のレプリケーション（replication）と索引の分散（distribution）の2つがあります。索引のレプリケーションとは、複数台のマシンに同じ転置索引（のコピー）を配置する方
Quicksilverは如何にして鋭い検索を行っているのか？ - ザリガニが見ていた...。
Quicksilverの検索性能が、感性をくすぐってきた。 「apple」→「AppleScript Editor」 「ase」→「AppleScript Editor」 「prol」→「Property List Editor」 「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。 そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。 直近のユーザーの好みを学習してくれるのだ。 もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。 「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
M.Hiroi's Home Page / Lightweight Language
インテルTBBによる選択ソートの高速化（1/3）：CodeZine
