「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
ツイートID生成とツイッターリアルタイム検索システムの話
PostgreSQLの行レベルセキュリティと SpringAOPでマルチテナントの ユーザー間情報漏洩を防止する (JJUG CCC 2021 Spring) Webアプリケーションにおいて、マルチテナント型、つまり複数のユーザー組織がアプリケーションとデータベースを共有する構成にすることがあります。この構成の持つリスクとして、万が一バグにより他テナントの情報が見えてしまうとそれは情報漏洩となり、重大なインシデントとなってしまうことがあります。この重要性を考えると、「気を付けて実装する」だけではなく、仕組みで漏洩を防ぐような対策には価値があります。 そこで、今回はPostgresSQLの行レベルセキュリティと、SpringAOPによる処理を組み合わせて、ログインしているテナントのデータにしかアクセスできなくする仕組みを実現しました。 導入にあたり考慮した複数の選択肢、乗り越えたいくつかの壁
Project EulerにGaucheで挑戦する話 - Qiita
Lisp Advent Calendar 19日目担当の @naoya_t です。 「昨晩@g000001さんと回転寿司屋でLispについて話した」（※実話）とかでもいいんですが、予告通りProject Eulerの話を書こうと思います。 ちょっと投稿が遅くなりましたが、インド標準時（UTC+05:30；日本時間より3時間半遅れています）でぎりぎり19日ということでお許しください。 はじめに 本記事では、特定の問題の解答や、それを導くプログラムはProject Eulerの参加規約に抵触するため掲載しません。 Project Eulerとは 偉大な数学者レオンハルト・オイラーの名を冠するProject Eulerとはいったい何なのでしょうか？ 英語版WikipediaでProject Eulerを開いてみると Project Eulerは、コンピュータプログラムで解くことを意図した計算問題
有限オートマトン - Wikipedia
オートマトン理論 有限オートマトン（ゆうげんオートマトン、英: finite automaton）または有限状態機械（ゆうげんじょうたいきかい、（）英: finite state machine, FSM）とは、有限個の状態と遷移規則からなる状態機械。 チューリングマシンとは異なり計算状態を記憶するテープを持たず、チューリング完全ではないが、様々な応用がある。 状態[注 1]は、システムの振る舞いのノードであり、システム内で遷移[注 2]を実行するトリガーを待っている。一般に状態は、同じトリガーに対してシステムの反応が常に同じではない場合に導入される。例えば、カーラジオのシステムでは、特定のラジオ局の放送を聴いている状態で「次へ」というトリガーは次のラジオ局（の放送受信）への移行を意味する。しかし、CDプレーヤーのシステムでは、「次へ」は次のトラックへの移行を意味する。これらは、同じトリガ
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。 K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。 クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、Restart を押すと好きなパラメータで試すことができます。 こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。 (追記) HTML5 版の K-means 法を D3.js でビジュアライズしてみた も作成しました。Flash を表示できない環境ではそちらをご覧ください。 K-means 法とは K平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージに
非決定性
第 8 回 非決定性 本日の内容 8-1. 非決定性の計算 8-2. オートマトン理論 8-3. 宿題 8-4. 次週の予告 8-1. 非決定性の計算 非決定性の計算を取り上げます。 非決定性の計算を行うコンピュータは存在しません。 しかし、非決定性の計算モデルを考えると、実存する多くの問題の複雑さを明 らかにすることができ、有用です。 次の状態が一意に定まらない計算を 非決定性 と言います。 ここでは、最終的な答として、 yes か no を出力する計算を考えます。 非決定性の計算を通常のプログラミング言語にさせるためには、通常 guess 命令と accept 命令と reject 命令を使用します。 guess 命令は変数を伴い、これは最終的に accept 命 令にたどり着けるような、都合の良い値を変数に代入します(時間計算量は代 入する長さに比例するものとします)。 一つでも a
ruby 1.9 におけるハッシュ飽和攻撃による DoS 脆弱性 (CVE-2012-5371)
Posted by usa on 9 Nov 2012 ruby 1.9 系列で使用しているハッシュ関数について、ハッシュ飽和攻撃によってサービスを停止させることができる脆弱性が報告されました。 この脆弱性は 1.8.7 に対して公表された CVE-2011-4815 とは異なるものです。 全ての ruby 1.9 ユーザーは、この問題に対するセキュリティフィックスが含まれた ruby-1.9.3 patchlevel 327 に更新することが推奨されます。 影響 綿密に構築された文字列の並びをサーバーに対して送信することにより、そのサーバーがこの文字列の並びを文字列をキーとした Hash オブジェクトの生成に利用する場合、サービス停止攻撃が成立します。 例えば、信頼できない送信元から送られた JSON データを解釈する Web アプリケーションなどがこの脆弱性の影響を受けます。 詳細 こ
Understanding Padding Oracle attacks « Limited Entropy Dot Com
It's been a long time I haven't written anything here... I've had to travel for work and have been doing other things and didn't find the right moment to write about anything useful. But a few days ago I decided to take a look at Padding Oracle attacks after hearing several times about them, and I thought it would be nice to share with you guys. Padding Oracle attacks were introduced in 2002 in pa
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
Knight's tour - Wikipedia
An open knight's tour of a chessboard An animation of an open knight's tour on a 5 × 5 board A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is "closed", or
The log-structured merge-tree (LSM-tree) - Acta Informatica
Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The design and analysis of computer algorithms. Reading, MA, Addison-Wesley Anon et al.: A measure of transaction processing power. In: Stonebraker, M. (ed.) Readings in database systems, 2nd. edn., pp. 442–454. San Mateo, CA, Morgan Kaufmann, 1988 Google Scholar Bayer, R., Schkolnick, M.: Concurrency of operations on B-trees. In: Stonebraker, M. (ed.) R
Mersenne Twister: A random number generator (since 1997/10)
English Version News: MTToolBox をGitHubで公開しました。(2013/10/04) TinyMTをリリースしました。 (2011/06/20) MTGPをリリースしました。(2009/11/17) SIMD-oriented Fast Mersenne Twister (SFMT) をリリースしました。 SFMTはオリジナルのMersenne Twisterより約二倍速く、 よりよい均等分布特性を持ち、零超過初期状態からの回復も高速です。 SFMTのページを見てください。 (2007/1/31) お願い：使う時にemailを一通下されば、 今後の改良のはげみになります。 どんなささいな問題点でも、見つけ次第御連絡下さい。 m-mat ＠ math.sci.hiroshima-u.ac.jp (このメールアドレスは スペースを抜いて手で打ち直してください)
Implementing Regular Expressions
Implementing Regular Expressions Russ Cox rsc@swtch.com This page collects resources about implementing regular expression search efficiently. Articles and Notes “Regular Expression Matching Can Be Simple And Fast” An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bound
おねえさんのコンピュータ
同じ所を２度通らない道順の数 Total number of routes that do not pass by the same place twice
Kazuho@Cybozu Labs: REST におけるトランザクションについて (Re: Web を支える技術)
といいつつ、ひとつだけ理解できないというか、納得できないところが。トランザクションのところがなんだかRESTっぽくないのがすごく気になる Webを支える技術 -HTTP、URI、HTML、そしてREST (WEB+DB PRESSプラスシリーズ)(山本 陽平) - ただのにっき(2010-04-23) 「Web を支える技術」は自分もとてもいい本だと思う (教科書としてすばらしいし復習用としても読みやすいのでイイ) のですが、トランザクションの所だけは分かりづらいなと感じました。その原因は、atomic transaction で解決できる課題を例として使っているという点と、トランザクションと更新クエリのレイヤ分割がされていない、という２つの点によるものではないでしょうか。 HTTP 上でトランザクションを表現する必要があるケースのほとんどは、atomic transaction ではなく
Two-phase commit protocol - Wikipedia
"2PC" redirects here. For the play in American and Canadian football, see Two-point conversion. For the cryptographic protocol, see Commitment scheme. For the concurrency control, see Two-phase locking. A typical sequence of a Two-phase commit. In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Garbage Collection for Dummies
ExpireSEO