B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
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' __ /:::::::/｀ヽ /'
インターフェイス指向設計 - naoyaのはてなダイアリー
本を読むこととは、その本を読んだことに費やした時間の間、その書籍のテーマについて考えを巡らせることではないか、と近頃思います。本を読みながら集中して、ある特定のテーマについて考え続ける。本を読み終えた頃には、その思考の量的な価値が、自らの中で質的な価値に変換されているというのが理想であり、それが読書の醍醐味ではないかと思います。 インターフェイス指向設計 ―アジャイル手法によるオブジェクト指向設計の実践 を読みました。この書籍はシステム設計における「インターフェイス」(ユーザーインターフェイスではなく、プログラムインターフェイス) についての書籍です。インターフェイスについて考えを巡らせるにあたって、思考のための指針を与えてくれる良著だと思います。 プログラムインターフェイスというものをどのように捉えるか。ファイルをブロック単位で読むための手順であるとか、ソートのアルゴリズムであるとか、そ
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
Google を支える技術 - naoyaのはてなダイアリー
Google を支える技術 を読みました。 Google のバックエンドで動いている各種分散処理システムに関しては Google 自身から論文がいくつも発表されています。それらの論文をはじめとする比較的最近の情報ソースをベースに、ある程度かみ砕いて要所要所を紹介するという内容でした。加えて著者の西田圭介さんは OpenCobol (COBOL を C 言語に変換しコンパイルする gcc のフロントエンド) を開発された、技術的なバックグラウンドがしっかりしている方であるようで、内容は信頼できると思います。 自分はこれまで Google のバックエンドの各種ソフトウェアについては方々で耳にしていましたが、漠然と何をするものか程度のことしか知りませんでした。 Web 検索の基本的な仕組みと それにまつわる Google が直面した問題、特に大規模処理 それを支えるために開発された各種ソフトウェ
はてなブックマークの作り直しについて - naoyaのはてなダイアリー
id:naoya:20080320:1206009912 でも少し触れましたが、京都に来てからはてなブックマークの作り直しをしています。どういう意図を持って作り直そうとしているかを述べておきます。 まず大前提として、今のはてなブックマークに追加したい機能、変更したい仕様、本来追加するはずが途中で頓挫したものが結構な数で山積みになっています。それを実現するための基礎作りです。 追加したい機能、変更したい箇所 おそらく新システムの最初のリリース時には、それほど大きく変わった、という印象にはならないかと思います。長く続いているサービスですし、インタフェースや使い方もリリース当初からそれほど大きくは変わっていません。既存システムからの極端な変更は歓迎されないだろうと思っており、まずはオリジナルが持っていた機能をしっかり再現することが重要です。 ただし、既存システムでも問題と思っている箇所は改善して
取締役を退任しました - naoyaのはてなダイアリー
3月7日を持って、はてなの取締役を退任し、執行役員となりました。正式な肩書きは「執行役員 最高技術責任者 (CTO)」となります。 京都に本社を移転するにあたり、数ヶ月前から今後の自分の役割について検討してきました。自分としてはやはり現場で開発の仕事を続けていきたい、また京都まで来たからにはよりそれに集中したいという思いが強くありました。会社全体の指揮を取りながら現場でサービスを作っていくというのを両立するのは、自分の能力では難しいと思い、取締役を退任することとしました。 経営の仕事というのは、自らの働きかけにより会社の中にある個々の力を結集させて、より大きな力へと増幅させることです。自分は、それが取締役に課せられる役割のうち最も重要なものだと思いました。会社全体を見渡しながら個々の力のベクトルがうまく同じ方向を向くように働きかけたり、各チームではカバーされていない隙間があったらそこを支え
ソフトウェア技術者としての残り時間 - naoyaのはてなダイアリー
年始の NHK でのイチロー特集番組を見ていて一番印象に残ったのは、他の人の道具を絶対に触らないというイチローのこだわりでした。曰く、人の道具を触るとその道具の感覚が体に残ってしまい、自分の道具を利用するときの感覚の妨げになるから、ということでした。全体を通して、イチローは他のプレイヤーとの相対的な競争の中に身を置いているのではなく、絶えず自分を改良し続けるという過程の中にいるのだというのがよくわかる内容でした。良い番組だったと思います。 気づけば自分も 30 歳になりました。まだ若いとは思っていますが、さすがに 20 代の頃に比べると、病気や怪我の治りが少し遅くなったと感じることもあり、少しずつ自分の人生、「死」ということを考えるようにもなりました。時間は有限ということが少しずつ実感できるようになってきました。あるいは実感できるようになってしまった、と言った方が良いかもしれません。 ここ
x86 Linux のメモリモデル、プロセス空間切り替え、カーネルスタック - naoyaのはてなダイアリー
ひとつ前のエントリ id:naoya:20070924:1190653790 では Linux のコンテキストスイッチにおける、主にハードウェアコンテキストの退避/復帰の処理を追ってみました。その中で カーネルスタック (switch_to() 内で pushl %ebp とかして値が積まれるスタック)とはそのときの実行コンテキストに紐づくカーネルプロセススタックという理解でよいか。 という疑問がもやもや湧いて出てきました。ここ数日 はじめて読む486―32ビットコンピュータをやさしく語る を読んでいたのですが、その中にこの疑問への答えへの入り口が載っていまして、そこを糸口に調べてみました。で、結果としては 答え: 良い でした。 x86 は特権レベルの移行と連動してスタックポインタを切り替える仕組みを持っています。Linux の場合モードはカーネルモード(特権レベル0) とユーザーモード
Linux カーネルのコンテキストスイッチ処理を読み解く - naoyaのはてなダイアリー
Linux カーネルのプロセススケジューラの核である kernel/sched.c の schedule() を読み進めていくと、タスク切り替え(実行コンテキスト切り替え)はその名も context_switch() という関数に集約されていることが分かります。2.6.20 の kernel/sched.c だと以下のコードです。 1839 static inline struct task_struct * 1840 context_switch(struct rq *rq, struct task_struct *prev, 1841 struct task_struct *next) 1842 { 1843 struct mm_struct *mm = next->mm; 1844 struct mm_struct *oldmm = prev->active_mm; 1845 184
世界を変えられるのはエンジニアしかいない ― ＠IT自分戦略研究所
企業各社にとって、人材戦略は非常に重要な課題だ。人材の育成に当たって、トップは何を思うのか。企業を担う若いITエンジニアに何を求めているのか。 日本のWeb 2.0を代表する企業として、多くのユーザーから常に注目されているはてな。同社 取締役 最高技術責任者 伊藤直也氏に、ITエンジニアとして成長するために必要なことを語ってもらった。 ■エレベータやエスカレータはない ITエンジニアとして成長するために必要なものは何か。その問いに伊藤氏は次のように答える。 フリーエンジニアになりたい、フリーとしてどう生き残ればいいか分からない。そんな人のために、＠IT自分戦略研究所では、「フリーエンジニアカンファレンス2007」を企画しました。「安定した案件を受注するテクニック」など、具体的なノウハウを伝授。詳しくはセミナーページを！ 「自分の成功体験だけで語ると、目標決めて勉強することを愚直にやるという
人力検索はてな - Emacs ユーザーの方に質問です。これは便利! と思える elisp プログラムを教えてください。 標準で組み込まれてるものでも結構です。プログラムがどういうものかの説明も
Emacs ユーザーの方に質問です。これは便利! と思える elisp プログラムを教えてください。 標準で組み込まれてるものでも結構です。プログラムがどういうものかの説明も簡単にしていただけると嬉しいです。 ちなみに自分が便利だなと思うのは ・ ELScreen (GNU screen のようなスクリーン機能を実現するもの) ・kill-summary.el (killing buffer を履歴表示して yank するものを選べるようにする) ・navi2ch (定番ですねｗ 2ちゃんねるビューワー) ・riece (IRCクライアント) などです。それから、こういう設定知ってる? 的なものも是非教えてください。 今日 (windmove-default-keybindings) で shift + カーソルキーで分割したウィンドウが移動できることを知って驚愕してます。 よろしくお願い
naoyaのはてなダイアリー - さくらインターネット移行記#1
先日のライブドアのテクノロジーセミナー(http://d.hatena.ne.jp/naoya/20061214/1166063145)でも少し触れたのですが、はてなのサーバーは今後さくらインターネットのiDCでホストすることになりました。 複数の iDC を検討しましたが、最終的にさくらインターネットに決めた理由は回線品質の高さと回線が低価格である点でした。 はてなのようなコミュニティ中心のサービスは、お金の面では、どうしても回線コストと収益の間にアンバランスが生じがちです。ショッピングサイトや各種メディアのようなコンテンツに比べてマネタイズが難しい、というのがその主な理由です。 例えばはてなのトラフィックの多くははてなダイアリーの日記へのアクセスで占められていますが、基本的に個人の日記にははてな側からは広告を掲載しないポリシーでいます。そのためトラフィックを多数必要とされる箇所で収益を
バイト募集してます。 - naoyaのはてなダイアリー
手前味噌であれですが はてなでは各種サーバーネットワークの運用アシストを募集しています。はてなの技術担当社員の指示に従って働いてもらうため、高度なスキルは必要ありませんが、経験に応じて様々な仕事をしてもらいます。 ということでつい先日からサーバー、ネットワーク関連のバイトを募集してます。 自分語りをさせていただきますと、僕がいまの仕事につくにあたって非常に重要な活動だったなあというのがありまして、それが大学のネットワーク管理のバイトでした。青山学院の理工キャンパスのネットワークを管理してたんですが、まあ仕事の内容はいま思うとお粗末というか、やばそうなのは全部教授がやっちゃってくれてたりもしましたが、それでも UNIX に触れ、ネットワークに触れ、各種サーバーに触れという感じでいろんなことを学びました。 実はそのバイトに就いた当時は UNIX の U も分からんような具合で、ネットゲームとか
naoyaグループ - naoyaの日記 - 自分にできないことをすごいと思う
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
naoyaのはてなダイアリー - Inside Hatena Bookmark's Backend の資料
以下に置いておきました。遅くなってすいません。 http://bloghackers.net/~naoya/pdf/050404inside_hatena_bookmark.pdf 会場で前置きしたように、はてなブックマークは、はてなで一番大きなシステムであるはてなダイアリーあるいは同じ YAPC で発表のあった mixi に比べると、まだそこまで大きな規模ではありません。月間の PV はだいたい 4,000 万 PV 〜 というところです。 ただ、日本でのトラフィックが上から 5 番目みたいな怪物サイトよりも、月間の PV が 1,000 万クラスのサービスの情報の方が、より現実的で役に立つのではないかと思い、はてなブックマークの裏側に絞って話しをしてみました。 ...という前提で見ていただけると嬉しいです。 はてなブックマークのデータのサイズもかなり大きくなってきたので、ぼちぼちパーテ
直交する技術から複数のものを学ぶ - naoyaのはてなダイアリー
一年前に CNET でインターネット時代のエンジニアの価値という記事を書いたのですが、それと関連する、先週 Binary 2.0 カンファレンスや PofEAA 読書会に行って来て、感じたことを書いてみたいと思います。 まず、Binary 2.0 カンファレンスに行って来て感じたことというのが、先日ちょっと述べたとおり、ソフトウェア開発の世界は多様化していて、それぞれのレイヤの間で断絶がある、ということ。断絶というとちょっとネガティブな印象があるので、それぞれ違うレイヤというかカテゴリの技術の関係を、直行する技術カテゴリ、とでも言ってみます。 Binary 2.0 カンファレンスでもうひとつ発見があったのは、ローレベルレイヤを極めているバイナリアンは、どことなく数学的にコンピュータにアプローチすることに長けている人たちというイメージだったけど、それはちょっと違うということ。もちろん、それに
Googleの組織マネジメントを前例に。 - naoyaのはてなダイアリー
「日本版Googleを目指す」と回答したのは近藤氏。今では世界企業となったGoogleだが、はてなの目指すGoogleとは何だろう。 id:jkondo が出てるこの記事。「日本版Google」 なんていうキャッチーなフレーズばかりが先行してますが、本来僕ら言いたかったのはそういうことじゃなくて。 組織のマネジメントという点でみたときに、Google というのは非常に優秀な企業で、いまや 3,000 人もの社員を抱えている大企業にもかかわらず、大企業病のジレンマには陥っていないと言われます。僕らが着目している点はその点です。 はてなはよく小さな企業だからいまのやり方ができるんだろう、とか、大企業病からは逃れられないという風に言われます。そのカウンターとして実際に同業者で 3,000 人になっても現場プログラマが満足しながら働ける企業というのが世の中に前例としてある、だったら僕らにできないは
田中良和が本を書いた - naoyaのはてなダイアリー
ただ、そんな時頭に浮かぶのは、誰もやったことがないことは、やる前に考えたところでうまくいくかどうかなんて、そもそも分かるはずがないという当たり前の事だった。実行してみなければ分からないのだ。 田中良和という人に初めて会ったのは2年ほど前だったと思います。インターネットで面白いことをやってる同世代の人たちが何人かで集まってご飯を食べるという集まりの中でした。当時彼は楽天広場の中の人。そして今はグリー株式会社の代表取締役社長。 その集まりには彼以外にも面白い人がたくさん集まっていて、特別なバックグラウンドも持っていない僕はただただ周囲に圧倒されるばかりだったのを今でも覚えていますが、そんな中でも一際目立っていたのが田中さんでした。僕とは年齢がほとんど変わらないのに、物事に関する洞察力、ビジネスの知識の幅、意思決定の速さ、積んできている経験は遥かに上をいっていて、そして現場で開発もしている。何か
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
