Coursera の Algorithms on Strings 受けました - たにしきんぐダム
Cousera の Algorithms on Strings を受講していて、平日にお昼ご飯食べながらビデオを見たり休日とかに課題をやったりしていたのですが先日完走しました！(講義は4週分なのですが忙しかったり難しかったりで2ヶ月くらいかかってしまった) お金を払うと課題提出システムみたいなのが使えて提出したプログラムの時間/空間計算量を教えてくれるらしいけど無料でも授業ビデオと資料にはアクセスできた めちゃくちゃ良かったのでみんなも受講しましょう www.coursera.org きっかけはアルバイト先で開催されていたのに参加させてもらったのと、 ISUCON6予選で高速な文字列マッチングアルゴリズムが全く分からず悔しい思いをしたから(正規表現の更新・キャッシュをうまく頑張れば十分な点数は獲得できたみたいですが...)でした。 学んで終わりじゃ多分忘れるから何とか応用とかできたら良い
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
KDDI研究所、世界で誰にも解読されていない60次元LWE暗号の解読に成功
sponsored 新型ケース採用の最新モデル「G TUNE FG-A7G7T」が早くもセールで大幅安 Ryzen 7 9800X3D＋RTX 5070 Tiは【ゲーミングPCの新定番】 マウスコンピューターの「G TUNE」が6万円オフ！ sponsored マウスコンピューターのセールで「mouse MH-A7U01」が対象に 自宅のWindows 10パソコン買い替えチャンス！ シンプルだけど高性能なミニタワーが注目セール中 sponsored Ryzen 5とRTX 3050を採用、設定次第ではモンスターハンターワイルズも遊べる？ 手が届きやすい14万円台のピラーレスゲーミングPC、フルHDなら結構快適に遊べてLEDライティングも堪能 sponsored 疲れにくい、集中力が途切れない、体にいい 【ASCII読者限定】長時間のパソコン作業は机、椅子、アームの三位一体でケア、Flex
Many Pivot Sort, MasSort, MatSort（クイックソート・マージソートの改良アルゴリズムの提案）
Many Pivot Sort, MasSort, MatSort （最速のソートを目指して…クイックソート・マージソートの改善） 概要 クイックソート・マージソートの改善アルゴリズムを提案してみます。 Many Pivot Sort クイックソートのピボット値選択方法改善アルゴリズム MasSort メモリの操作回数低減を狙ったマージソートの改善アルゴリズム MatSort 作業領域のメモリ使用料量削減を狙ったマージソートの改善アルゴリズム（MasSort等、他のマージソート系アルゴリズムを内部的に併用する） Many Pivot Sort, MasSortはクイックソート、マージソートの改善版でそれぞれ、元のアルゴリズムから10-20%程度高速化している。 MatSortは作業領域をソート対象の1/10程度に縮小しても元のマージソートよりも高速であり、ランダム配列においてはベースとなる
マジックカーネル – 画像のリサンプリングのメソッド | POSTD
マジックカーネルとは？ “マジックカーネル”とは、極めて高速で（一番単純なバージョンなら、必要なのは少しの整数加算とビットシフトのみです）、驚くほどの結果を出してくれる効果的な画像のリサンプリングのメソッドです（エイリアシングノイズやリンギング、細かい物体の”Width beat”の発生を防ぎます）。 私がこのマジックカーネルと出会ったのは2006年、一般的に使われているJPEGライブラリのソースコードを扱っていた時のことです。それ以来、この素晴らしい特性を深く探り、任意のリサンプリングファクタのケースにまでこのメソッドを広げました。 このWebページでは、それらの特性を要約して説明し、画像への適用も含めてマジックカーネルのC#のコード実装の全てをご紹介します。 マジックカーネルはどこから来たのか 2006年に私は、JPEGを過剰に圧縮すると発生するブロックノイズを最小限に抑えるいい方法は
AAAI'15 論文採択：Top-k 最短経路クエリとネットワーク構造予測への応用 - iwiwiの日記
国際学会 AAAI 2015 に論文が採択されました．AAAI は人工知能分野の最も有名な会議の 1 つです．発表は来年の 1 月にアメリカのオースティンです．AAAI への論文採択は 2 年連続となります． 今回の論文は "Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室後輩の林くん，京大の則さん，研究室同期の岩田，NII の吉田さんとの共著です．内容は，グラフにおける Top-k 最短経路を高速に計算するためのスケーラブルなインデクシング技法の提案，及びそのネットワーク構造予測への応用です．特に，応用面のインパクトを示す試みを論文内に入れることができたのが大変気に入っています． 背景：ネットワーク上の 2 点間の関連度推定に
TinySegmenter.jl の高速化手法を追っかけてみた - 押してダメならふて寝しろ
今日の元ネタはこちらです． chezou.hatenablog.com 他言語との比較が行われているわけですが，Julia 版はアルゴリズムの作りが他とだいぶ変わってしまっているので， そのまま比較するのはどうかなと思うわけですが，でも，Julia が書けるわけでもないので，ざっくりどんな高速化が行われたのか golangで追っかけてみました（結局 golang ネタです）． TinySegmenter はもともと javascript でコンパクトに書かれた分かち書き用のプログラムです． TinySegmenter: Javascriptだけで実装されたコンパクトな分かち書きソフトウェア なるべくオリジナルに忠実に golang で実装して，そこから Julia 版の高速化手法を盛り込んでいってパフォーマンスを見ていきます． で，こちらにご用意したのが golang 版です． shogo
タッパーの自己言及式 - Wikipedia
タッパーの自己言及式は、ジェフ・タッパー (Jeff Tupper) によって考案された不等式であり、特定の条件の下で式を満たす二つの数の組を二次元のグラフに描くと不等式そのものの形となる。 2001年にコンピュータグラフィックスを扱う国際会議SIGGRAPHで発表された[1]。 不等式は次のように定義される。 は床関数、 は剰余を表す。ここで、k を以下の値とする (543桁の数を3桁区切りで記述している)。 960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505 519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355 993 237 280 874 144 307 891 325
最長片道きっぷの経路を求める
最長片道きっぷの経路を求める Index & Overview あらまし この文書は、ＪＲの最長片道きっぷの経路を、 整数計画法と全探索の２つの方法で求めた過程をまとめたものです。 前者では厳密に、後者ではややイイカゲンに、その経路を求めることに成功し、 ２つの方法で求めた経路は一致しました。 トピックス NHK の紀行番組「列島縦断 鉄道12000kmの旅」をきっかけにこの Web ページを探し当てた方は、まず「付録２（2004年３月版）」をご覧ください。 現状の最長片道きっぷの経路や、ありそうな質問をまとめてあります。 ふと思い立って、2006年５月版の最長片道きっぷ経路図（PDF 形式、35,414 bytes）を作りました。 2004年３月版の地図との相違点はただ１点、 「富山港線を削除した」ことです（2006年２月28日廃止）。 もともと最長経路に含まれていなかった路線が廃止にな
Minimal Acyclic Subsequential Transducerで遊ぶ - Negative/Positive Thinking
はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subsequential Transducerとは Finite State Transducerの一種 Transducerにおいて、initial stateが一つで、同じ入力ラベルを共有する同じ状態からのの遷移が2つ以上なく、各最終状態での最終出力文字列が高々p個のとき、p-subsequentialで、pが整数ならfinitely subsequentialというらしい minimal(状態数が最少)、Acyclic(サイクルが無い)
SharedArrayBufferとAtomics APIについて - JS.next
概要 JSで大きな処理を効率良く捌きたい時、今までもWorker等でスレッド立てて処理を分割する事はできたが、 スレッド間のやり取りの方法は制限されたものしかなく、バッファを共有することもできなかった。 そこで新しく導入されたSharedArrayBufferを用いると、スレッド間で共同利用できるバッファを作る事ができる。 記事更新履歴 ※この記事はV8が仕様の新しいバージョンを実装するのに合わせて断続的に更新していきます。 [2016/07/19] V8の半年ぶりの新仕様追従に対応 [2015/09/30] 公開 通常のArrayBufferとの比較 前準備： // メッセージを受け取ると渡された型付配列のインデックス0を123にするWorker w = new Worker(URL.createObjectURL(new Blob([` self.onmessage = e => {
Quantization based Fast Inner Product Search
We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recent
Ragel State Machine Compiler
Ragel compiles executable finite state machines from regular languages. Ragel targets C, C++ and ASM. Ragel state machines can not only recognize byte sequences as regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language. Code embedding is done using inline operators that do not disrupt the regular language syntax. The core language con
[PDF] 最適化から見たディープラーニングの考え方 得居 誠也
c � 1. 5 2011 10 [1] ImageNet Large Scale Visual Recognition Challenge (ILSVRC) 2012 2 10 [2, 3] 1 [4] [5] 2. x ∈ X y ∈ Y z = (x, y), Z = X × Y Preferred Networks 113–0033 2–40–1 4 tokui@preferred.jp S = {zi}N i=1 ⊂ Z f : X → Y F = {fθ|θ ∈ Θ} fθ ∈ F F zi S f z = (x, y) �(f, z) f(x) y ES(f) = ( � z∈S �(f, z))/N ES(f) f z = (x, y) E(f) = Ez[�(f, z)] E(f) E(f) f f [6] f� F f� F F ˆ fF E(f) E(f� ) E(f
Skylakeファーストインプレッション - anon42’s diary
2015/8/5に開発コードSkylakeで知られていたIntelの新CPUが発売されました。私も早速動かしていますが大変よい結果を得ています。今回は主に各所で公開されている情報等から従来のマイクロアーキテクチャとの比較を見てみます。 フロントエンド とりあえず4wayのままのようです。フェッチ帯域やMacroOps Fusion等はまだ確認していません。あんまり変わっていない気がします。 実行ユニット instlatx64の結果がアップロードされています。 http://instlatx64.atw.hu/ 主にFPU周りの変更が目立ちます。私が使う上で気になったところを挙げます。 div/sqrtのスループットが劇的に向上した。ついでにrcpps/rsqrtpsも高速化している。 blendvのスループットがHaswell/Broadwellの2から1に向上した。SandyBridge
高速フーリエ変換
- The document contains code and explanations for solving optimization problems using dynamic programming, including calculating minimum costs using a 2D array to store results. - It describes applying dynamic programming to problems involving finding minimum costs for tasks that can be split into subtasks, with the overall cost determined by combining subtask costs. - The code provided shows init
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://michael.dipperstein.com/arithmetic/
Synchronization in a Distributed System | 8th Light
Welcome to nginx!
IBM Developer
