最長共通部分列問題 (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
インフラの継続的デリバリー - naoyaのはてなダイアリー
事前に断っておくがここでいう「インフラ」はレイヤ的には OS より上の話。 少し前に GitHub 時代のデプロイ戦略 - naoyaのはてなダイアリー で、GitHub を介したデプロイを実践しているということを紹介した。普段の開発を Pull Request ベースでやっているので、デプロイもまた Pull Request を契機に実行させると色々捗る、という話。 このプラクティスの対象領域をインフラにまで拡大してみました、というのが今回の話。 DNS レコードを Pull Request を merge した契機に自動で更新 AWS を利用している場合、ドメインの管理も Amazon Route 53 を使うといろいろと都合がいい。 Route 53 での DNS レコードの更新はこれまでブラウザから操作していた。これだと誰がいつ作業したかわからないし履歴もトラックしづらい。また変更
naoyaのはてなダイアリー - tmpfs は本当に容量が動的なのか
Linux には tmpfs という便利なファイルシステムがあります。 $ mount -t tmpfs -o size=64m tmpfs /dev/shm $ mount -t tmpfs -o size=64m /dev/shm /var/tmpとすると、/var/tmp がディスク上ではなくメモリ上に作られたファイルシステムとして mount されます。なので、/var/tmp は I/O 時にディスクI/Oが一切発生しない高速なディスクとして使えると。いわゆる RAM ディスク。(もちろんサーバーの電源を落とすと保存したファイルは消えます。) この tmpfs はなかなかに便利で、キャッシュとかそういうものでディスクにおいてたものここ置くと、ディスク I/O がカットできて超高速になります。はてなでは MySQL のスレーブの MyISAM のファイルを tmpfs において、オ
Infrastructure as Code - naoyaのはてなダイアリー
今年の3月に 入門Chef Solo - Infrastructure as Code という本を書いた。 その名の通り Chef の入門書なのだけど、このサブタイトルは "Configuration Management Tool (構成管理ツール)" でもなく "Provisioning Framework (プロビジョニングフレームワーク)" でもなく、はたまた "Automated Infrastructure (自動化されたインフラ)" でもなく、"Infrastructure as Code" にした。 この一年で Chef や Puppet にはずいぶんと注目が集まった。おそらく、AWS をはじめとするクラウドサービスがより広いユーザーに浸透したことで仮想化環境が前提になって、以前よりも頻繁にサーバーを構築し直したりする機会が増えたとかその辺がひとつ理由として挙げられると思う
「書く」のは特別な道具 - naoyaのはてなダイアリー
This is why you shouldn't interrupt a programmer (なぜプログラマの作業に割り込むべきではないか) という4コマ漫画が話題になっていた。これは別にプログラマではなくても「わかるわかる」という感じの話。 コメントを見ると、だから作業を中断してもすぐ再開できるように自分の考えることをなるべく書き出すようにしているという人が結構多かった。なるほど。 今日は雨が降ったせいで予定が一つキャンセルになったことだし、ちょうどいい機会なので、文章で何かを書くということについて自分が思っていることを書いてみようとおもう。以前 Software Design のドキュメントの書き方特集みたいな号に似たような趣旨の話を寄稿したのだけど、「書く」というのは単に物事を忘れないようにするための行為に留まるものではなくて、自分の考えを整理するための道具なのだ、ということが
YAPC::Asia 2013 / Github によりバザールモデルへ - naoyaのはてなダイアリー
ブログを書くまでが YAPC、ということなので、書きます。 初日「モダンPerlリファクタリング」 自分は20分枠で 「モダンPerlリファクタリング」という題で話しました。スライドは以下で公開してます。 https://speakerdeck.com/naoya/modanperlrihuakutaringu-number-yapcasia 今回、思いの他 CI やテストに関する発表が他に多くてそれらに比べると基礎的な内容に終始しちゃいましたが と @t_wada 御大よりお褒めに与ったので個人的には満足です。 リファクタリングはテストさえ書ければその半分以上は終わったことになる、ただしテストはテストを書くことそのものが主目的になりすぎないように。そして書いたテストはとにかく計算機を利用して頻繁に実行しましょうということが言いたかったのですが、意図通りに伝えられたんじゃないかなと思う。
Crypt::CBC による Blowfish 暗号化 - naoyaのはてなダイアリー
This module is a Perl-only implementation of the cryptographic cipher block chaining mode (CBC). In combination with a block cipher such as DES or IDEA, you can encrypt and decrypt messages of arbitrarily long length. The encrypted messages are compatible with the encryption format used by SSLeay, and can be made compatible with the newer OpenSSL package by specifying the -salt argument. 先の XML.co
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
リアルグラフへの違和感 - naoyaのはてなダイアリー
なんか facebook のコメント blog とかに表示するやつに投稿されてるコメント、なんか素直に読めない感じのコメントが多い。･･･うまく言葉にできないので過激な言い方をすると気持ち悪いと感じるというか。ひどい言い方で、すみません。 実名とかで現実のアイデンティティを担保にとれば、コメントとか炎上もなくなってまともになるでしょうって話だったけれど、facebook でそれが現実になってみたが結果的にはぜんぜんまともじゃなかった。 アイデンティティが現実世界のそれだから、いろんな意味で発言の評価が本人に結びつけられた場合のフィードバックが強すぎるんじゃないだろうか。書く側は、なんだか立派なことを言ってみたり思ってもないことを言ってみたりと格好つけるし、読む側からの印象としてはそれ全部がひどいポジショントークに見えてしまって気分が萎える。 たしかに自分も、実名･･･というか現実のアイデン
Linux I/O のお話 write 編 - naoyaのはてなダイアリー
write はページに dirty フラグを立てるだけなので決してユーザープロセスを待たせない って、本当にそうなんでしょうか？（否定しているわけではなく、純粋な疑問です。） と質問をもらったので、最近追ったことをここでまとめます。かなり長文です、すいません。また、まだまだ不勉強なので間違っているところもあるかもしれません。ツッコミ大歓迎です。 まず、オライリーのカーネル本の 15章 ページキャッシュ 15.3 汚れたページのディスクへの書き込み から引用。 ご存知のように、カーネルは、ブロック型デバイスのデータを含むページをページキャッシュに蓄えています。プロセスが何らかのデータを更新した場合は、必ず対応するページに汚れている印をつけます。すなわち、PG_dirty フラグを設定します。 UNIX システムでは、汚れたページのブロック型デバイスへの書き込みを遅延することができます。この方
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
創造性の高い仕事をしたい人におすすめしたい1冊 - naoyaのはてなダイアリー
100人が選ぶソフトウェア開発の名著選 デブサミ10周年を記念して2月21日に刊行：CodeZine（コードジン） が出版されます。私も一冊推薦しました。id:secondlife:20120202:1328168076 でセコンさんが公開してるのにならって、私も原稿を公開しようかなと思います。推薦したのは以下の本です。 モチベーション3.0 持続する「やる気!」をいかに引き出すか 作者: ダニエル・ピンク,大前研一出版社/メーカー: 講談社発売日: 2010/07/07メディア: ハードカバー購入: 101人 クリック: 5,453回この商品を含むブログ (153件) を見る 邦題があまり好きじゃない。原著は『DRiVE ─ The Suprising Truth About What Motivates Us』です。本文の訳は良かったです。『フリーエージェント社会の到来』や『ハイ・コン
naoyaのはてなダイアリー - 負荷とは何か
調べごとをしたので blog に書いて理解を深めようのコーナーです。長文です。 Linux でシステム負荷を見る場合にお世話になるのが top や sar (sysstat パッケージに同梱されてるコマンド) などのツールです。 top ではシステム統計のスナップショットを見ることができます。今システムがどういう状態かなーというときは top が便利。 top - 08:16:54 up 3 days, 14:43, 6 users, load average: 0.18, 0.07, 0.03 Tasks: 43 total, 2 running, 41 sleeping, 0 stopped, 0 zombie Cpu(s): 18.2% us, 0.0% sy, 0.0% ni, 81.8% id, 0.0% wa, 0.0% hi, 0.0% si一方の sar では10分ごとのシ
naoyaのはてなダイアリー - Linuxのページキャッシュ
世間では PHP が、Perl が、と盛り上がっているようですが空気を読まずまたカーネルの話です。今回はページキャッシュについて。 /dev/shm に参照系ＤＢを持っていくと I/O 負荷が激減した件（当たり前だけど） - drk7jp で、ディスク上にあったファイルを /dev/shm (tmpfs) に移したら I/O 待ちがなくなって負荷がさがった、ということなんですがおそらくこれは tmpfs に置く必要はないかなと思います。Linux (に限らず他の OS もそうですが) にはディスクの内容を一度読んだらそれはカーネルがキャッシュして、二度目以降はメモリから読む機構 = ページキャッシュがあります。tmpfs にデータを載せることができた、ということは物理メモリの容量に収まるだけのデータサイズかと思うので、放っておけば該当のファイルの内容すべてがメモリ上にキャッシュされて io
naoyaのはてなダイアリー - コネクションプーリングの話
かなりながーいエントリになる予定なので,結論だけ最初に書くとこんな感じ. この話題については自分も あとで書く と言って書いてなかったので書いてみますよ。2006年の下期にもなってコネクションプーリングかよというツッコミもありそうですが、あとで書くといったら書くの。あとで読むといったら読む。 普通「コネクションプーリング」と言ったら、主に二つの役割があると思います。話を簡単にするためにウェブアプリケーションに限定して言及します。 ウェブアプリケーションから DB への接続を開けっ放しにして、接続に必要とされるオーバーヘッドをカットして双方の負荷を下げる。 ウェブアプリケーションと DB への接続を「使いまわす」ことで、同時接続本数を節約する。 というもの。 mod_perl で DB と接続維持するとコネクション数増えて云々という話は主に前者のみについての話になります。Apache::DB
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
